Associated Topics || Dr. Math Home || Search Dr. Math

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/
```
Associated Topics:
High School Logic

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search