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?

  • 2
    $\begingroup$ Putting "and" between two quantifiers does not make much sense. $\endgroup$ – Chris Eagle Feb 28 '13 at 0:05
  • $\begingroup$ Sorry about that. Didn't mean to do that. $\endgroup$ – ctzdev Feb 28 '13 at 0:08
  • $\begingroup$ I thought it seemed odd, but didn't want to assume anything, so I didn't change those when I added the $$ in to make the quantifiers come out properly. $\endgroup$ – Tara B Feb 28 '13 at 0:09
  • $\begingroup$ @Tara: I’d have done the same, but in view of the OP’s comment I’ve gone ahead and fixed it. $\endgroup$ – Brian M. Scott Feb 28 '13 at 0:10
  • $\begingroup$ @BrianM.Scott: Fair enough. $\endgroup$ – Tara B Feb 28 '13 at 0:13

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

  • $\begingroup$ So I went 1/4? Damn it, I know better than that. $\endgroup$ – ctzdev Feb 28 '13 at 0:11
  • 1
    $\begingroup$ @NotoriousArab: 1/4, unless I miscounted: the third is the only one that you got right. $\endgroup$ – Brian M. Scott Feb 28 '13 at 0:12
  • $\begingroup$ Oh and that makes it even worse. Damn, I felt good coming out of that test. Thanks for clearing it up. $\endgroup$ – ctzdev Feb 28 '13 at 0:13
  • 1
    $\begingroup$ @NotoriousArab: No, the third is true: whatever $x$ you pick, I’ll pick $x^2+1$ for $y$, and it will be true that $x^2<y$. Thus, $\forall x\exists y(x^2<y)$. The difference is that in the third there just has to be (for each $x$) one $y$ that works; in the fourth all $y$’s have to work for some particular $x$. $\endgroup$ – Brian M. Scott Feb 28 '13 at 0:28
  • 2
    $\begingroup$ @NotoriousArab: You’re welcome. Practice can’t hurt, but there are a couple of useful guidelines. I’ll add them to my answer. $\endgroup$ – Brian M. Scott Feb 28 '13 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.