Last edited 9/3/2007 3:31:00 PM
MORE ABOUT QUANTIFIERS
[ label:
rulqua] Many important mathematical principles are statements with
several quantified variables. The ordering of the quantifiers matters. The
subtleties involved can be confusing.
Example
The following
statement is the Archimedean property of the
real numbers.
|
 xRnN(x<n)
|
(0.7)
|
In other words,
"For any real number x there is an integer
n bigger than x."
Proof: If you are given a real number x, then trunc (x)+1 is an integer bigger than x. END PROOF
Example
On the other hand,
the statement
|
nNxR(x<n)
|
(0.8)
|
is false. It says
there is an integer which is
bigger than any real number. That is certainly not true: if you think 456,789
is bigger than any real number, then I reply, "It is not bigger than 456,790".
In general, for any integer n, n+1 is
bigger - and of course it is a real number, like any integer.
As these examples
illustrate, in general, xyP(x,y) does not
mean the same as yxP(x,y), although
of course for particular
statements both might be true.
On the other hand,
two occurrences of the same quantifier in a row can be interchanged:
Theorem: interqFor any statement P(x,y),
and
and similarly
and
Exercise
Are these statements
true or false? Explain your answers. All variables are real.
xy(x>y).
xy(x>y)
xy((x>y)(x=y)).
Answer: (a) means that for every real number the statement y(x>y) is true.
A witness for that statement is
x-1, so the statement is true. (b) means that there is a real number greater
than any real number, which is false. (c) is true. Witness: Let x=y=3. Then the
statement becomes ((3>3)(3=3)), which is (vacuously)
true.
Exercise
Are these statements
true or false? Explain your answers. All variables are of type integer.
mn(m|n).
mn(m|n).
mn((m|n)(m| mn)).
mn((m|n)(m| mn)).
Exercise
Are these statements
true or false? Give counterexamples if
they are false. In these statements, p is a prime
and m and n are positive integers.
pmn ((p|mp|n)m|n )
, mn (m|np(p|mp|n) )
Exercise
hard Are these equivalences true for all assertions P and Q? Assume that the only variable in P
is x and the only variables in Q are x and y. Give reasons for your answer.
xy (P(x)Q(x,y) )⇔x (P(x)yQ(x,y) )
xy (P(x)Q(x,y) )⇔x (P(x)yQ(x,y) )
Negating quantifiers
Negating quantifiers
must be handled with care, too:
Theorem: negqMoving "not" past a quantifierFor any
assertion P,
Q
¬(xP(x))⇔x(¬P(x))