Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

is $\forall x\,\exists y\, Q(x, y)$ the same as $\exists y\,\forall x\,Q(x, y)$?

I read in the book that the order of quantifiers make a big difference so I was wondering if these two expressions are equivalent or not.

Thanks.

share|improve this question
7  
no. but the second implies the first. –  user59671 Feb 14 '13 at 19:18
3  
"For any person x there exists a person y such that y is the mother of x." versus "For any person y, there exists a person x such that y is the mother of x." –  minimalrho Feb 14 '13 at 19:21
2  
Try $Q(x,y)=[x=y]$. –  Did Feb 14 '13 at 20:30
    
I addressed this problem in a problem here: math.stackexchange.com/questions/304172/… –  Joe Z. Feb 14 '13 at 20:30

7 Answers 7

up vote 10 down vote accepted

Certainly not. In that useful "loglish" dialect (a halfway house between the formal language and natural English), the first says

For any $x$, there is a $y$ such that $Qxy$.

The second says

For some $y$, all $x$ are such that $Qxy$.

These are quite different. Compare

For any natural number $x$, there is some number $y$, such that $x < y$. True (for any number, there's a bigger one).

For some natural number $y$, any number $x$ we take is such that $x < y$. False (there is no number larger than all numbers!).

A more general comment. The whole point of the quantifier-variable notation is to enforce clarity as to the relative scope of logical operators.

To take a simple case, consider the English "Everyone's not yet arrived". This is structurally ambiguous. You can easily imagine contexts where the natural reading is "It isn't the case that everyone has arrived", and other contexts where the natural reading is "Not everyone has arrived". Compare, however,

$\neg\forall xAx$

$\forall x\neg Ax$

Here, in the language of first-order logic, the order of the logical operators ensures that each sentence has a unique parsing, and there is no possibility of structural ambiguity.

share|improve this answer
1  
The second rather says: "for some y, Qxy holds for all x" or "there is a y, such that for all x Qxy.", but "for some y, there is an x such that Qxy." would be the same as $\exists y\exists x Qxy$ –  Elmar Zander Feb 14 '13 at 19:30
    
@Elmer sorry yes, very careless cutting'n'pasting on an iPad ;-) Corrected on a proper keyboard! –  Peter Smith Feb 14 '13 at 19:37

Switching the order of quantifiers is often not valid. In particular, we change the meaning of a statement when we switch the order of different quantifiers whose scope is the entire statement - as in this case - and it is usually not valid to switch a leading quantifier with a nested one.

In this case, we have:

$$\forall x \exists yQ(x, y) \not\equiv \exists y \forall x Q(x, y)$$

For example:

Let $Q(x, y)$ means "x loves y". Domain of $x, y$ : people

  • The left hand side would read, effectively:

    $\forall x \exists y Q(x, y)$: "Everyone loves somebody" (every person loves somebody);

  • The right-hand side would read, effectively:

    $\exists y \forall x Q(x, y)$: "There is someone whom everyone loves." Or alternatively, "there is someone who is loved by everyone."

Those are not at all equivalent statements.

share|improve this answer
1  
Could you provide a counterexample as to when the quantifiers are the same, but switching the order is not legitimate? I can't think of one. –  Elmar Zander Feb 14 '13 at 19:33
    
@JoeZeng adding to ruakh's comment: $\forall x\exists x Q(x)$ isn't even a valid logical formula, you cannot have two quantifiers on one variable. What I meant was: when would something like $\forall x\forall y Q(x,y)\not=\forall y\forall x Q(x,y)$ or $\exists x\exists y Q(x,y)\not=\exists y\exists x Q(x,y)$? –  Elmar Zander Feb 14 '13 at 21:48
1  
@Elmar: Never. You can always interchange adjacent quantifiers of the same kind. –  Brian M. Scott Feb 14 '13 at 22:47
    
Oh, whoops, I mistook "quantifiers" for "variables". –  Joe Z. Feb 15 '13 at 0:02
    
I really have to admit that after grading that exam last year (and the one before that, actually) I become loathsome of all the "real world analogies" when explaining quantifiers. This is why when I do give those analogies they are always preposterous to the point that no student would write them in the exam. –  Asaf Karagila Feb 15 '13 at 2:39

Because I really hate the real world analogies (after an exam I was forced to read nearly 300 answers mumbling "every pot has a lid" analogies), let me give you a mathematical way of understanding this without evaluating the actual formulas.

Let $M$ be an arbitrary structure for our language, let $A(x)=\{y\in M\mid M\models Q(x,y)\}$. So given a point $m\in M$ we match it the set $A(m)$ of all those which are satisfying $Q$ with $m$.

  1. The first sentence $\forall x\exists yQ(x,y)$ tells us that for every $m\in M$, $A(m)$ is non-empty.

  2. The second sentence $\exists y\forall xQ(x,y)$ tells us that there is some $y$ such that $y\in A(m)$ for all $m$. That is to say that the intersection of all $A(m)$ is not empty.

We can immediately draw the conclusion that the second sentence implies the first. If the intersection of all the $A(m)$'s non-empty then certainly no $A(m)$ can be empty.

On the other hand it is also quite clear that the second sentence implies that the intersection of all the $A(m)$'s is not empty, they all contain at least one shared point. The first sentence makes no such requirement, so it's not difficult to construct a structure where the first sentence is true but the second is false.

share|improve this answer

The answer is no.

Here's the way I like to think about it myself: $\forall x \exists y Qxy$ allows for a different $y$ for each $x$, but $\exists y \forall x Qxy$ requires the same $y$ work for all $x$.

Sometimes people get confused due to this construction: "There exists a $y$ for all $x$ such that $Q(x, y)$ holds." The placing of the "such that" is critically important.

share|improve this answer

Besides to @Asaf's and @amWhy's detailed answer, I am noting an example, maybe, it paves just a small piece of the way. Consider $M=\mathbb Z$ and $$Q(x,y): x+y=0$$ Obviously, for all $x\in\mathbb Z$, there is a $y\in\mathbb Z$ such that $Q(x,y)$ be a true statement. Now, think about this sentence: There is an $y\in\mathbb Z$ such that for all integers $x$, $x=-y$. Clearly, it is wrong. Because if for example $y=a$ then we can't write $-a=x$ when $x$ is freely moving alongside the set $\mathbb Z$. So, your claim is not true in general.

share|improve this answer
    
This example was touched on in this question: math.stackexchange.com/questions/304172/… –  Joe Z. Feb 15 '13 at 14:26
    
@JoeZeng: I didn't know that. However, it can be changed to another smilar example. –  Babak S. Feb 15 '13 at 17:47
    
Examples are good to have, and a variety...they help now and in the future, for future "askers" +1 –  amWhy Feb 16 '13 at 0:10

Let $x$ be a man (from the set of all men), $y$ be a woman (from the set of all women), and let $Q(x,y)$ mean "the man $x$ and the woman $y$ are happy together".

Then:

$ \forall x\,\exists y\, Q(x, y) $ means "Whatever man you pick, there is such a woman, that they'd be happy together".

$\exists y\,\forall x\,Q(x, y) $ means "There is such a woman, that whatever man you pick, they'd be happy together".

Now it's quite easy to see and feel the difference.

(I would not mind to see the woman.)

share|improve this answer

Sometimes it's good to think about this in geometric terms. Suppose $Q(x,y)$ is the statement $(x,y) \in A$, where $A$ is a subset of the plane.

$\forall x\exists y Q(x,y)$ means "each vertical line intersects $A$".

$\exists y \forall x Q(x,y)$ means "$A$ contains a horizontal line".

They are clearly not the same... let $A$ be the line $y=x$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.