Quantifiers

Date: 03/25/2003 at 20:45:35
From: Dan Gibson
Subject: Quantifiers

I am having a hard time understanding quantifiers. A lot of the time I 
can understand the simpler problems, but the complicated ones really 
throw me for a loop. Often if I think a proposition is true, it's 
actually false, and vice versa. I am currently working on four 
problems and I can't get anywhere with them. The problems are: 

(A=For every, E=There exists)
  1. A x in {0,1}, E y in {0,1), A z in {0,1), x less than or equal to 
     y + z.
  2. A x in Reals, A y in Reals, A z in Reals, E d in Reals, s.t. 
     x + y + z = d.
  3. A x in Naturals E y in {0,1,2} (x + y)/3 is in the Naturals.
  4. A x in Reals, A y in Reals, A z in Reals, x^2 + y^2 + z^2 > 0.

I never know how to read a proposition if it has more than two 
quantifiers. Three of the above problems all have three quantifiers. 
Also I get confused how to read them. I know order makes a difference, 
but how?

I would say the second and third propositions are true. This is just 
by looking at them.

Date: 03/26/2003 at 21:49:26
From: Doctor Nbrooke
Subject: Re: Quantifiers

Hi Dan, and thanks for writing to Dr. Math.

First we'll remember when statements involving quantifiers are true 
or false:

For all, for each: \A x, P(x)
-------------------------
\A x, P(x) is true if P(x) is true for every possible x.
\A x, P(x) is false if there is an x for which P(x) is false.

There exists, for some: \E x : P(x)
----------------------------------------
\E x : P(x) is true if there is an x for which P(x) is true.
\E x : P(x) is false if P(x) is false for every x.

Now in understanding statements with quantifiers, it is useful to 
translate them into English to get our heads around them. You said 
that you thought that statements (2) and (3) are true. Let's start 
with (2):

\A x in R, \A y in R, \A z in R, \E d in R : x + y + z = d.

For simplicity's sake, we can go ahead and group the three quantifiers 
on the left together, like this:

\A x, y, z in R, \E d in R : x+y+z=d.

Now to English, this reads "For all real numbers x, y, and z, there 
exists a real number d such that x + y + z = d." To prove that this 
is true, you have to select a real number d such that x + y + z = d.  
Well, let d = x + y + z; since the real numbers are closed under 
addition, we know that the sum of any three real numbers is itself a 
real number. Now our statement reads like this:

\A x, y, z in R, \E d in R : x + y + z = x + y + z.

This is a tautology. It is universally true for all reals x, y, and z.  

Now consider statement (3).

\A x in N, \E y in {0,1,2} : (x+y)/3 in N.

You claim that this is true. Translated, we say that "For every 
natural number x, there exists a y equal to 0, 1, or 2 such that 
(x+y)/3 is a natural number." This is indeed a true statement, but 
we have to prove it. Perhaps you're already familiar with the division 
algorithm for natural numbers:

\A a, d in N \E unique q, r in N : a = qd + r and 0 <= r < d.

In words, "For every natural number a (the dividend) and natural 
number d (the divisor), there exists a natural number q (the 
quotient) and natural number r (the remainder) such that a = qd + r 
and 0 <= r < d."  This is a proven theorem, and very useful for 
proofs like these.

Back to our original statement. We need to find a way to choose y for 
every possible x if we are to prove our statement true. By the 
division algorithm, we have that x = 3q + r for some integer q and r, 
where 0 <= r < 3. If r is an integer such that 0 <= r < 3, it has 
three possible values: 0, 1, and 2. We'll proceed by cases.

Case r = 0: If r = 0, then x = 3q for some natural number q. We need 
to choose a y such that (x + y)/3 is in N, that is (3q + y)/3 is in 
N. Choose y = 0. Then (3q + y)/3 = (3q)/3 = q, which is a natural 
number.  

Case r = 1: If r = 1, then x = 3q + 1 for some natural number q.  
Choose y = 2. Then (x + y)/3 = ((3q + 1) +2)/3 = (3q + 3)/3 = q + 1, 
which is a natural number.

Case r = 2: Choose y = 1. Then (x + y)/3 = ((3q + 2) + 1)/3 = (3q + 
3)/3 = q+1, which is a natural number.  

Our cases are exhausted: We have now found a y equal to 0, 1, or 2 
for all possible values of x.  We finish our proof off with a Q.E.D.

I hope this helps.  Feel free to write back if you have any more 
questions.  

- Doctor Nbrooke, The Math Forum
  http://mathforum.org/dr.math/