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?
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)$
-
0Consider [Confused between Nested Quantifiers](http://math.stackexchange.com/questions/64500/confused-between-nested-quantifiers) – 2012-04-03
2 Answers
Consider statements
$\forall x\in \mathbb N$ there is $y\in \mathbb N$ such that $x
and there is $y\in \mathbb N$ such that $\forall x\in \mathbb N$ it holds that $x
.
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$:
- $\Leftrightarrow$ $\forall x\in \mathbb N$ there is $y(x)\in \mathbb N$ such that $x
where $y(x) = x+1$ for example.
-
0@Templar: is there anything which is still unclear to you? – 2012-04-03
$\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.
-
0In 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. – 2012-04-02