1
$\begingroup$

$\exists\ x \in \mathbb{N}\ \textrm{such that}\ \forall\ y \in \mathbb{N}, 2x \leq y + 1$

$\forall\ y \in \mathbb{N}, \exists\ x \in \mathbb{N}\ \textrm{such that}\ 2x \leq y + 1$

I'm having trouble understanding the differences between these two statements. To me, they seem to mean the same thing. Can anyone explain in basic terms? Thanks.

  • 0
    Answers to [Confused between Nested Quantifiers](http://math.stackexchange.com/q/64500/15198) question may help you to better understand nested quantifiers.2012-09-21

2 Answers 2

2

Let $L(x,y)$ stand for "$x$ loves $y$". Then $\exists x\forall y: L(x,y)$ means "There is someone who loves everyone." and $\forall y\exists x: L(x,y)$ means "Everybody is loved by someone". Clearly, these two are very different.

Now compare the simple mathematical statements.

$\exists x\in\mathbb{N}$ such that $\forall y\in\mathbb{N}$, $x\leq y$.

$\forall y\in\mathbb{N},$ $\exists x$ such that $x\leq y$.

The first one says that there is some natural number $x$ that is smaller or equal than every natural number $y$.

The second statement says that for every natural number $y$, there is a natural number $x$ that is less or equal than $y$.

It turns out that both of these statements are true. But now replace $\mathbb{N}$ by $\mathbb{Z}$. There is no smallest integer, so the first statement becomes wrong then. But the second one would still be true because for every integer $y$, the integer $y-1$ is smaller or equal than y$.

3
  1. There is some $x$, such that no matter what $y$ you choose, $x$ will be less than $y+1$. $x=0$ fits the bill.
  2. No matter which $y$ you choose, you can always choose some $x$ s.t. $2x\leq y+1$. E.g. if $y=5$, then $x=1$ satisfies.

Note that if we were dealing with say the integers, the second statement would be true but the first one would be false. It might be instructive to figure out why.