# Quantifier Notation

What's the difference between $\forall \space x \space \exists \space y$ and $\exists \space y \space \forall \space x$ ? I don't believe they mean the same thing even though the quantifiers are attached to the same variable, but I'm having a hard time understanding the difference. Any examples to make the distinction clear would be appreciated.

-
This is definitely not a question about notation. –  Asaf Karagila Mar 25 '13 at 0:04
Ok my bad, I didn't check if there was a quantifiers tag, so I guess that's what should have been selected. –  Benzne_O Mar 25 '13 at 0:05
@AsafKaragila: I don't see why not? A convention is implied here: one has to read from left to right. If the convention had been different the notation would have had a different meaning. –  Raskolnikov Mar 25 '13 at 13:39
@Raskolnikov: Sure, everything fits the [notation] tag because everything depends on the way you read it... –  Asaf Karagila Mar 25 '13 at 13:49

Consider this example.

For all $x\neq 0$ there is a $y\neq 0$ such that $xy = 1$.

There is a $y\neq 0$ such that for all $x\neq 0$ you have $xy = 1$.

You can probably see that the one statement is true and the other false.

-

Every natural number has a successor. There is no natural number which is the successor of every number.

-

One reads "For every $x$, there exists a $y$...", and the other says "There exists a $y$, such that for every $x$..."

An example of the difference can be found by making the (totally non-mathy) statement: $$\forall x \;\exists y \text{ s.t. x loves y}$$ That is, everybody loves at least one other person.

On the other hand: $$\exists y \;\forall x \text{ s.t. x loves y}$$ That is, there is a person that everyone loves.

Does this make the difference a bit more clear?

-

$\forall m \exists k | k>m$ which in plain English means: For any integer, there is another integer greater than it.

$\exists k \forall m | 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.

-

Everybody has a nose, but there is no nose that belongs to everybody.

-

A quick summary of the essential parts of what others have written: $\forall x\,\exists y$ allows $y$ to depend on $x$; $\exists y\,\forall x$ requires the same $y$ for all $x$'s.

-

You really should read some of Daniel Velleman's How to Prove It, 2nd ed. He discusses this kind of stuff in the beginning of his chapter 2. (Chapter 1 is short, covering sentential logic.)

-

There has been a lot of clear examples given as answers.

So, not giving any example but trying to make a stronger sense:

You can regard the quantifiers part of your formula as a bound. Therefore, comparing $\forall x \exists y$ vs $\exists x \forall y$, you should consider the first one as "first bound your formula by $x$ and then relative to $x$, bound it by $y$". For the second one, the matter must be obvious(interchange $x$ and $y$ in the quotation marks). Consequently, these two different ways of bounding are not necessarily the same.

-

One is, "for each x there is a y, the other, "there is a (single) y for all x." It is a "uniformity difference".

-
"there exists x" doesn't necessarily require that x be a single, unique entity. –  amWhy Mar 25 '13 at 0:14

As others have pointed out one says "for all x, there exists a y such that..." while the other says "there exists a y, such that for all x..."

An operation O on a finite number of elements can get described by its operation table:

  O  a  b  c ...
k
j
l
.
.
.


with the points where horizontal and vertical lines intersect describing the value of O(x, y) at point (x, y).

Thus, if we have a "for all x, there exists a y such that O(x, y)=z" statement, that means for any input from k, j, l... there exists a single input from a, b, c ... such that O(x, y)=z. A "there exists a y such that for all x, O(x, y)=z" statement means that for a single input from a, b, c, ... all elements from the k, j, l ... satisfy O(x, y)=z.

To understand this a little more concretely consider this operation table

 A  0  1  2
0  2  0  1
1  1  0  2
2  1  0  2


We have that for all x, there exists a y such that A(x, y)=2. Here, if x=0, there exists the y=0, such that A(x, y)=2, if x=1, there exists y=2 such that A(x, y)=2, and if x=2, then y=2 such that A(x, y)=2. Similarly, if you have a "for all x, there exists a y such that O(x, y)=z" statement concerning a binary operation, then for each row of its operation table there will exist an element y such that x and y will intersect at element z. Thus, z will appear at least once in each row. Symmetrically, if we have a "for all y, there exists an x such that O(x, y)=z" statement, then z will appear at least once in each column.

On the other hand, for operation A we have that there exists a y, such that for all x, A(x, y)=0. In this case, y=1. Similarly, if you have a "there exists a y, such that for all x, O(x, y)=z" statement concerning a binary operation, then its operation table will have a single element z which appears throughout at least one column. In a symmetrical manner, if we have a "there exists an x, such that for all y", then its operation table will have single element z which throughout each row. See the difference?

-