I just took an exam and the following problems were asked:
Determine the truth value of each of these statements if the domain
consists of all real numbers.
$\forall x \forall y \; (4-x^2 < y)$
$\exists x\exists y \; (4-x^2 < y)$
$\forall x\exists y \; (x^2 < y)$
$\exists x\forall y \; (x^2 < y)$
I answered True, False, True, and True respectively. Was I correct?
Best Answer
I’m afraid not: $x=y=0$ is a counterexample to the first statement, $x=y=2$ shows that the second statement is true, and $y=-1$ is a counterexample to the fourth statement. The third statement is, as you say, true.
Added: I expect that statements with a single quantifier don’t cause much trouble, but statements with two quantifiers can be a little confusing when you’re just starting. The ones in which the two quantifiers are of the same type are easiest:
$\forall x\forall y\,\varphi(x,y)$ says that no matter what values you give $x$ and $y$ (in the relevant universe of discourse), the statement $\varphi(x,y)$ is true of that pair of $x$ and $y$. One counterexample $-$ one bad pair of $x$ and $y$ for which $\varphi(x,y)$ isn’t true $-$ is enough to show that this statement is false.
$\exists x\exists y\,\varphi(x,y)$ makes a much weaker statement: it just says that there is at least one pair of $x$ and $y$ such that $\varphi(x,y)$ is a true statement about that pair. This time one example can show that the statement is true.
When there’s one quantifier of each type, the order is very important. Think of it as a game: your opponent picks the first variable, and you pick the second one. Whichever of you is picking the existentially quantified variable wins if $\varphi(x,y)$ is true of the pair that you jointly pick.
$\forall x\exists y\,\varphi(x,y)$: Your opponent can pick any value at all for $x$, and you win if you can find a value of $y$ that makes $\varphi(x,y)$ true. Note that you get to know what his choice of $x$ is before you choose your $y$, so your choice of $y$ can depend on his choice of $x$. For instance, $\forall x\exists y(x+y=0)$ is true, because no matter what real number $x$ your opponent picks, you can choose $y=-x$ and make $x+y=0$ true.
$\exists x\forall y\,\varphi(x,y)$: This time your opponent picks a value for $x$ and wins if you can’t find a $y$ to make $\varphi(x,y)$ false, i.e., if every possible choice of $y$ makes $\varphi(x,y)$ true. For example, $\exists x\forall y(xy=0)$ is true, because your opponent can pick $x$ to be $0$, and no matter what you choose for $y$, $xy$ will indeed by $0$.