Produced by Charles Wells.  Home    Website TOC    Website Index 

Last edited 9/3/2007 3:31:00 PM

MORE ABOUT QUANTIFIERS

Order of 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.

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

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))

¬(xP(x))⇔x(¬P(x)).

Proof: We give the argument for Q.1; the argument for Q.2 is similar.

For xAP(x) to be false requires that P(x) be false for every x of type A; in other words, that ¬P(x) be true for every x of type A. For example, if P(x) is the assertion , (x>5)(x< 3), then xRP(x) is false. In other words, the rule Q.1 is valid. END PROOF

Remark

Finding the negation of a proposition with several quantifiers can be done mechanically by applying the rules (Q.1) and (Q.2) over and over.

Example

The negation of the Archimedean property can take any of the following equivalent forms:

¬ (xRnN(x<n) )

xR¬ (nN(x<n) )

xRnN(x≥n)

The last version is easiest to read, and clearly false - there is no real number bigger than any integer. It is usually true that the easiest form to understand is the one with the ` ¬ ' as "far in as possible".

Worked Exercise

Express the negation of x(x<7) without using a word or symbol meaning "not". Answer: x(x≥7).

Exercise

Express the negation of x(x≤7) without using a word or symbol meaning "not".

Exercise

Write a statement in symbolic form equivalent to the negation of

without using the ` ' symbol.

Exercise

Write a statement in symbolic form equivalent to the negation of the expression " x(P(x)¬Q(x))" without using ` ', ` ' or ` ¬'.

Reading and writing quantified statements

An annoying fact about the assertion calculus is that even when you get pretty good at disentangling complicated logical statements, you may still have trouble reading mathematical proofs. One reason for this may be unfamiliarity with certain techniques of proof, some of which are discussed in the next chapter. Another is the variety of ways a statement in logic can be written in English prose. You have already seen the many ways an implication can be written (Section  [howword] ).

Much more about reading mathematical writing may be found in the author's works [], [], [], and [].

Example

The true statement, for real numbers,

could be written in a math text in any of the following ways:

If x≥0, then there is a y for which y2 =x.

For any x≥0, there is some y such that y2 =x.

If x is nonnegative, then it is the square of some real number.

Any nonnegative real number is the square of another one.

A nonnegative real number has a square root.

Or it could be set off this way

with the (x) on the far right side denoting " x". Sometimes (x) is used instead of x next to the assertion, too:

The words "any", "all" and "every" have rather delicate rules of usage, as well. Sometimes they are interchangeable and sometimes not. The Archimedean axiom could be stated, "For every real x there is an integer n>x," or "For any real x there is an integer n>x." But it would be misleading, although perhaps not strictly wrong, to say, "For all real numbers x there is an integer n>x," which could be misread as claiming that there is one integer n that works for all x.

Observe that the statements in (a), (c) and (e) have no obvious English word corresponding to the quantifier. This usage there is somewhat similar to the use of the word "dog" in a sentence such as, "A wolf mates for life", meaning every wolf mates for life.

Students sometimes respond to a question such as, "Prove that an integer divisible by 4 is even" with an answer such as, "The integer 12 is divisible by 4 and it is even". However, the question means, "Prove that every integer divisible by 4 is even." This blunder is the result of not understanding the way a universal quantifier can be signaled by the indefinite article.

Example

Consider the well-known remark, "All that glitters is not gold." This statement means

rather than

In other words, it means, "Not all that glitters is gold." (We do not say the statement is incorrect English or correct English with a different meaning; we only give it as an illustration of the subtleties involved in translating from English to logic.)

Worked Exercise

Write these statements in logical notation. Make up suitable names for the assertions.

All people are mortal.

Some people are not mortal.

All people are not mortal.

Answer: (a) x ( Person (x) Mortal (x) )
(b) , x ( Person (x)¬ Mortal (x) )
(c) x ( Person (x)¬ Mortal (x) )

Exercise

Write these statements in logical notation.

Everybody likes somebody.

Everybody doesn't like something.

Nobody likes everything.

You can fool all of the people some of the time and some of the people all of the time, but you can't fool all of the people all of the time.

Answer: (a) ,, xy ( Like (x,y) Person (x) Person (y) )
(b) ,, xy (¬ Like (x,y) Person (x) Thing (y) )
(Observe that the negation of an implication is not an implication: ¬(PQ) is the same as , P¬Q.)

Exercise

Write the statement in GS. [svvv] , page , using quantifiers. Answer: aA\uextbB((<a,b>Γ(F) ).