Quantifiers
Mathematics is the tool specially suited for dealing with
abstract concepts of any kind and there is no limit to its power in this field.
—
Paul Adrien Maurice Dirac (1902–1984)
Definition.
An open
sentence is a statement involving one or more variables.
Examples.
(a)
(b) She owns a stereo.
(c) It is a triangle.
An open sentence is neither true nor false. An open sentence becomes a proposition only after the variables are replaced by some particular values. We will let P(x) denote a single variable open sentence and P(x1, x2,…, xn) will denote an open sentence in the n variables x1, x2,…, xn.
Example. P(x1, x2, x3, x4) : x3 = 5x1 – 2x2 + 3x4
Definition. The truth set of an open sentence is a collection
of objects from a specified universe which makes the open sentence a true
proposition.
Examples.
P(x) : x < 3
(i) If the universe is the set of
natural numbers, then the truth set is {1, 2}.
(ii) If the universe is the set of
integers, then the truth set is {…, –3, –2, –1, 0, 1, 2}.
P(x) : All lines parallel to a given
line through a point not on the given line.
(i) In Euclidean geometry, the truth
set contains one line.
(ii) In hyperbolic geometry, the truth
set contains infinitely many lines.
(iii) In elliptic geometry, the truth set is the empty set/null set.
Definition. For an open sentence P(x), is read "for all x, P(x)". The sentence is
true precisely when P(x) is true for all x in the specified universe, i.e. the truth set is the universe.
is called the universal quantifier.
Definition. For an open sentence P(x), is read "There exists x such that P(x)." or
"There exists
."
The sentence is true when the truth set for P(x) is nonempty.
is called the existential quantifier.
Examples. Let the universe be the set of real numbers.
(a) is true; whereas,
is false.
[Consider x = 0.]
(b) is false; whereas,
is true.
(c) Assume P(x)
represents "x is positive."
and S(x) represents "x is
a square."
(i)
is false.
[Not all real numbers are positive.]
(ii)
is true.
(iii)
is true.
(iv)
is false.
[Consider x = 0.]
Quantifiers are often not obvious when we use the English
language. We need to be aware that a sentence may be a quantified sentence even
if for all and there exists are not stated. That is, we need to be alert for
hidden quantifiers.
Examples.
(1) "Some quadrilaterals
are rectangles." means (x is
a quadrilateral and x is a rectangle).
(2) "Some transformations are reflections and some are translations." means
.
Or, .
Be careful of translating the sentence incorrectly either as
or as .
(3) "All P(x)
are Q(x)." means .
"All triangles have three sides." means " For all x, if x is a triangle, then x
has three sides."
(4) Let N represent the set of natural numbers
and represent the set of real numbers.
(a)
is a true sentence.
(b)
is a false sentence.
(c)
is a false sentence.
Definition. Two quantified sentences, having the same universe, are equivalent iff they have the same truth set.
Example. is equivalent to x < 4 when the universe is the set of natural numbers, but are not
equivalent when the universe is the set of real numbers.
The following theorem gives the relationships between quantified sentences.
Theorem
2. For open sentences A(x),
(1) is equivalent to
;
and
(2)
is equivalent to
.
Proof.
(1) is true iff
is false
iff the truth set for A(x)
is not the universe
iff the truth set for ~A(x)
is not the empty set
iff is true.
(2) The proof is similar. Write this proof out as an exercise.//
Example. Find a denial of
"All projectivities are perspectivities."
Statement:
Negation:
"There exists a one-to-one mapping that is a
projectivity and is not a perspectivity" or more simply written as "There
exists a projectivity that is not a perspectivity."
Definition. For an open sentence P(x), is read "There exists a unique x such that P(x)." The sentence
is true when the truth set for P(x)
contains exactly one element for the universe.
is called the unique
existence quantifier.
Example. is true when the universe is the natural
numbers, but is false if the universe is the integers.
An alternate equivalent form for the open sentence is
This alternate form is useful when writing a
denial for an open sentence involving the unique existence quantifier.
