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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.