Order of Quantifiers

Date: 12/19/2002 at 05:58:55
From: Line
Subject: Order of Quantifiers

Hi, 

Can anyone help me to understand the order of quantifiers, i.e., the 
backward E and inverted A ?
 
For example:

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

In books, it is said that quantifiers are read from the right. But I
get more confused.

For instance, for the first part, (Ex)(Vt)F(x,t) is the answer. F(x,t) 
means you can fool person x at time t. (E is the backward E and V is 
the inverted A.) But what if I put (Vx)(Ex)F(x,t)? What difference 
does it make?

Please help me.

Date: 12/19/2002 at 02:40:11 
From: Doctor Mike Subject: 
Re: Order of Quantifiers

Hi,

I'm not sure I understand exactly what you are asking, but here are a 
few comments that may help. Feel free to write back with extra 
information for us if this is not enough.

First of all, since we cannot do the backward E (there exists) or 
inverted A (for all) symbols, I'll just use E and A.

The first main important thing to say is that the order can go EITHER 
way. The order you use depends on what you want to say. Consider these 
two sample statements, which should be considered to be about 
integers:

(1) Am Ek k>m   which in plain English means: For any integer, there 
is another integer greater than it.

(2) Ek Am k>m   which in plain English means: There is some integer 
that is greater than every integer.

The only difference is the order of the quantifiers, but the meaning 
is MUCH changed. In fact, the first is true and the second is false. I 
am NOT saying that one is the correct order and one is the incorrect 
order.  They are just statements that say different things.

Your question about "right to left" probably is due to the books not 
explaining their terminology carefully. They are probably not clear on 
what they mean by "read."  Maybe I can help by examining statement (1) 
in these terms.

It is obvious that when you actually "read" the statement you say "For 
every m there exists a k such that k is greater than m." You must read 
it that way. But what those books probably mean is that it is useful 
for you to think about them in the other order.  Look at the structure 
of the statement: It is:

   For every m, SOMETHING

To really understand the whole statement, you need to first understand 
what the SOMETHING is saying. That SOMETHING is the shorter statement 
Ek k>m.  So you will have better success understanding the full 
statement (1) if you FIRST understand the shorter statement Ek k>m; 
THEN realize that the whole statement says that the shorter statement 
is true for all m.

I hope reading the comments above will help.  In any case, I will stop 
here, and wait to learn if more is needed.

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

Date: 12/19/2002 at 23:21:00
From: Doctor Peterson
Subject: Re: Order of Quantifiers

Hi, Line.

I'm not sure what they would mean by saying quantifiers should be read 
from the right; but they associate with the expression to the right, 
so that you determine the truth of a statement from the inside out by 
starting at the right. That is, this

    (Ex)(Vt)F(x,t)

could be parenthesized as

    (Ex)[(Vt)F(x,t)]

We'll come back to look at this at the end.

I would express your three statements more precisely in this way:

    (1) there exist people whom you can fool at all times

    (2) for every person, there exists a time when you can fool him

    (3) it is not true that all people can be fooled at all times

Now, English (or any human language) can be ambiguous. We could also 
interpret the first statement a slightly different way:

    (1a) at all times, there exist people whom you can fool

Your translation of the first of these is correct, as I interpreted 
it. Now, if you wrote

    (Vt)(Ex)F(x,t)

(which I think is what you meant, using Vt) this would mean my (1a). 
Does that mean the same thing, so that the English is not really 
ambiguous?

Let's make this concrete. Suppose there are three people named A, B, 
and C, and three times, 1:00, 2:00, and 3:00. If "you can fool some 
of the people all the time," using my interpretation that "there 
exist people whom you can fool at all times," then there is one of 
the people, say A, who can be fooled at all three times. If "at all 
times, there exist people whom you can fool," then no matter what 
time you choose, you can find someone you can fool.

Let's make a table showing when each person can be fooled:

        1:00   2:00   3:00
    A     F      F      F
    B      
    C            F      F

Here A is that person who can be fooled all the time; so statement (1) 
is true. And because that person exists, there is always someone 
(namely A) whom you can fool. So (1) implies (1a).

But now take this situation:

        1:00   2:00   3:00
    A     F             F
    B      
    C            F      F

This time there is no one person whom you can always fool, so (1) is 
false. But at every time there is SOMEONE (not always the same one) 
whom you can fool. So (1a) is true. We see that the two statements 
are NOT equivalent, and the English is in fact ambiguous!

In fact, look back at statement (2). That too, in its original form, 
was ambiguous. I can interpret it this way:

    (2a) there exists a time when you can fool all of the people

Even statement (3) can be read differently:

    (3a) at every time, you can't fool all the people

These, too, are not equivalent to the earlier versions.

Finally, let's read your symbolic statement using my tables:

    (Ex)(Vt)F(x,t)

Reading from the right, we first look at

    (Vt)F(x,t)

This says (for any chosen person x) that at all times, he can be 
fooled. This will be true if there is an F at every time in his row. 
Now the claim that "Ex" for which this is true says that we can find 
at least one row in our table that has an F everywhere. This is true 
in the first table, but not in the second.

In your alternative formulation,

    (Vt)(Ex)F(x,t)

we see that

    (Ex)F(x,t)

means that (for whatever t we have chosen) we can find some row with 
an F IN THAT COLUMN. The quantifier Vt before that asserts that we can 
do this no matter what time we choose; so that every column has at 
least one F in it.

Does this make sense?

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