Is the Statement True or False?

[skate_nerd]

Studying for my proofs final right now...there's a problem on the study guide:
True or False. Assume standard properties of real numbers. Support your answers.

(a) For all \(x\) in the real numbers, there exists a \(y\) in the real numbers such that \(x+y>0\).
The answer: True. Given an \(x\), take \(y=|x|+1\).

(b) There exists some \(x\) in the real numbers such that for all \(y\) in the real numbers, \(x+y>0\).
The answer: False. There is no single \(x\) that can "accommodate" all \(y\)'s.

I understand how the first answer makes sense, because taking \(y=|x|+1\) would give you \(x+|x|+1>0\). For any \(x<0\), we would have \(1>0\). Any \(x>0\) would clearly give something more than 1.
However when looking at part (b), I feel like it is exactly the same thing as part (a), except the variable \(x\) is now the constant and the constant \(y\) is now the variable. So why would it not be valid to say:
"True: Given a \(y\), take \(x=|y|+1\)"?

 

[Evgeny.Makarov]

You have to take the order of quantifiers into account. That this order matters should be clear from the difference between "Every person has a friend" and "There is a person who is everyone's friend". Indeed, let $F(x,y)$ mean that $x$ and $y$ are friends. We can even assume that $F$ is symmetric, just like $x+y>0$ is, though this is not important. Then the first statement says
\[
\forall x\exists y\,F(x,y)\tag{1}
\]
while the second one says
\[
\exists x\forall y\,F(x,y)\tag{2}
\]
It is clear that (1) is usually true; at least it is easy to find a group of people ("the universe of discourse") where it is true. In contrast, (2) is less likely to be true for large groups of people, and it is easy to find a counterexample, such as a circle of people where only neighbors are friends. You can probably figure out that (2) implies (1) for any symmetric $F$, but the converse is not true, as we have just shown.

The gist lies in the order of choices that are made during the interpretation of a statement with quantifiers. This interpretation can be viewed as a construction game between two players $A$ and $E$: the forces of nature (or chaos) and a constructive agent (or a human). Player $A$ throws at $E$ all kinds of circumstances, and $E$ has to take them into account while building the desires structure. Then in general who has the winning strategy depends crucially on who makes the first move. For example, consider building and maintaining a highway. For every local damage that is done by weather or wildlife, humans are able to reverse it by fixing that damage. So, if the goal of the game is to have a highway in good order, humans have a winning strategy in the game where they move second. However, it is probably unrealistic to construct a highway that nature cannot damage in some way..

Why is making the second move easier for player $E$? Because $E$ knows the result of the first move by $A$ and can respond correspondingly. What does this have to do with first-order logic? By definition, a formula $\forall x\,A(x)$ is true if $A(a)$ is true for every possible element $a$ of the universe of discourse. Similarly, $\exists y\,E(y)$ is true if there exists an element $e$ in the universe such that $E(e)$ is true. So, $\forall x\exists y\,C(x,y)$ is true if for every $a$, $\exists y\,C(a,y)$ is true. Player $A$ chooses some particular $a$ as the first move. At this point, player $E$ has to choose an $e$ that works for that particular formula $\exists y\,C(a,y)$. For each particular $a$ there may be its own $e$ that makes $C(a,e)$ true. Contrast this with $\exists y\forall x\,C(x,y)$. It is true if $E$ can find an $e$ such that $\forall x\,C(x,e)$ is true. But after the choice of $e$ is made, $A$ can substitute any $a$ for $x$ to get $C(a,e)$. Clearly, coming up with such universal $e$ is harder.

Back to real numbers. You are right that $\forall x\exists y\,x+y>0$ is true because $E$ can choose $y=|x|+1$. But to make $\exists x\forall y\,x+y>0$ true, $E$ has to find an $e$ such that $\forall y\,e+y>0$ is true. Now $A$ can take the result of $E$'s move into account and substitute $-|e|-1$ for $y$. The result $e+(-|e|-1)$, which is negative. This shows how to formally prove that $\exists x\forall y\,x+y>0$ is false: we do it by contradiction, assuming that it is true.

Sorry if this is too long.

 

[skate_nerd]

Thank you evgeny. That helped a lot. It's always really useful to get new techniques/points of view for things like this.