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.

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.

share|improve this question
2  
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

10 Answers 10

up vote 15 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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?

share|improve this answer

$\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.

source : http://mathforum.org/library/drmath/view/61813.html

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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.)

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
"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?

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.