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.

I don't understand why there's difference between $\forall x \in T\ \exists y \in S\ F(x,y)$ and $\exists y \in S\ \forall x \in T\ F(x,y)$. It sems that it's exactly same thing just order is changed like 2+3 and 3+2. So it means $\forall$ and $\exists$ are not commutative, but why?

share|improve this question
6  
"For every person, there is someone who is that person's mother" $\neq$ "there is someone who is every person's mother." –  Arturo Magidin Apr 2 '12 at 15:27
    
Consider Confused between Nested Quantifiers –  Oleksandr Kozlov Apr 3 '12 at 7:14

2 Answers 2

up vote 12 down vote accepted

Consider statements

  1. $\forall x\in \mathbb N$ there is $y\in \mathbb N$ such that $x<y$ and

  2. there is $y\in \mathbb N$ such that $\forall x\in \mathbb N$ it holds that $x<y$.

The first is true, the second is not. Namely, in the second case you fix $y$ and does not allow it depend on $x$ while in the first case, given any $x$ you can choose $y$ so in general it depends on $x$:

  1. $\Leftrightarrow$ $\forall x\in \mathbb N$ there is $y(x)\in \mathbb N$ such that $x<y(x)$

where $y(x) = x+1$ for example.

share|improve this answer
    
why it's true? x and y are both from 0 to infinity so for all numbers from 0 to infinity there should be such number y from 0 to infinity that x is smaller than y, so this can't be true, for example let x and y be only from 0 to 5, so for all 0, 1, 2, 3, 4, 5 there should be such y that x is lower than y but it's impossible because y maximum value is 5 and 5 < 5 will never be true –  Templar Apr 2 '12 at 14:47
    
@Templar: why what's true? –  Ilya Apr 2 '12 at 14:48
    
I think that both your statements are always false –  Templar Apr 2 '12 at 14:49
    
@Templar: the first is true - did you read the last part of the answer? For any $x$ there is $y$ (e.g. $y =x+1$) such that $x<y$ –  Ilya Apr 2 '12 at 14:53
    
@Templar: yes, for any (fixed) $x\in \mathbb N$ there is (you can find) $y\in \mathbb N$ such that $x<y$ –  Ilya Apr 2 '12 at 14:54

$\forall x\exists y F(x,y)$: For every person $x$, there is a person $y$ who is $x$'s mother.

$\exists y \forall x F(x,y)$: There is a person $y$ who is everyone's mother.

In the first instance, $y$ is allowed to depend (silenty) on $x$: change $x$, you are allowed to change the $y$ that makes $F(x,y)$ true.

In the second instance, there is a single, fixed $y$ that makes $F(x,y)$ true for every $x$; $y$ is not allowed to change.

(Or, it's not the same thing to say that everyone has someone who loves them, than to say that there is someone who loves everyone)

For a mathematical example, let $S=T=\mathbb{Z}$, $F(x,y)$ means "$x+y=0$. Then $$\forall x\in T\exists y\in S\;F(x,y)$$ is true: for every integer number $x$, there is an integer $y$ such that $x+y=0$.

However, $$\exists y\in S\forall x\in T\; F(x,y)$$ is false: there does not exist an integer $y$ such that for every integer $x$ we have $x+y=0$.

That is: if we are allowed to select a $y$ after we know what $x$ is, we can find a $y$ that added to $x$ will yield $0$. But we cannot pick a single $y$ that will work for every $x$.

Note that $\exists y\forall x F(x,y)$ implies that $\forall x\exists y F(x,y)$; it is the implication going the other way which does not hold.

share|improve this answer
    
In OP's opinion, $\forall x \;\exists y: F(x,y)$ means that $\exists y: F(x,y)$ should hold for all $x$ simultaneously, hence $y$ has to be independent of $x$. I am not sure if OP now convinced about the correct meaning. –  Ilya Apr 2 '12 at 15:56

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.