# 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)$

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?

-
"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
– olek Apr 3 '12 at 7:14

## 2 Answers

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.

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

-
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