# Predicate logic proof problem

Where the domain of the variables are Real Numbers, determine the truth value for the following:

$$\forall x \exists y(y^2-x<200)$$

I don't understand how to formally prove this problem. Since $y^2\geq 0$ it would stand to reason that any $x< 0$ could disprove this statement. I tried to prove it true by using one case where $x=3$ and $y=3 \therefore 9-3<900$ which makes it True.

How should I tackle a problem like this?

Thanks

• I'd rewrite it as $\forall x\exists y(y^2<200+x)$. This basically says that every real number is strictly greater than some square. – Git Gud Sep 29 '14 at 22:57
• You can't prove $\forall x\cdots$ true by considering only one $x$. If it's true you need to prove it for every $x$. You can prove it false with a single counterexample, however. – hmakholm left over Monica Sep 29 '14 at 22:58
• Check what happens if we let $x=-1000$. – André Nicolas Sep 29 '14 at 22:59
• Not any $x<0$,but certainly any $x<-200$. – Thomas Andrews Sep 29 '14 at 22:59
• So basically by rewriting it as $\forall x \exists y(y^2<200+x)$ I need to choose an $x$ such that the statement is false and therefore has a false truth value? – StrugglingCalcStudent Sep 29 '14 at 23:01

One way to understand the statement $$\forall x \exists y(y^2-x<200)$$ is to think of it as a game. One player takes the $\forall$ quantifiers and one takes the $\exists$ quantifiers. The $\forall$ player is trying to make the statement at the end (the $y^2-x<200$) false, and the $\exists$ player is trying to make it true. Each quantifier, $\exists$ or $\forall$, is one move in the game.

In this game, the $\forall$ player moves first, and picks a value for $x$. Then the $\exists$ player moves second, and picks a value for $y$. The entire statement, including the quantifiers, is true if the $\exists$ player can always make $y^2-x < 200$.

Suppose the $\forall$ player picks $x=17$. Then the $\exists$ player can win by picking $y=10$, since $10^2 - 17 < 200$.

Suppose the $\forall$ player picks $x=2$. Can the $\exists$ player pick a $y$ that still makes $y^2-x < 200$?

Can the $\forall$ player make a move that leaves the $\exists$ player without a winning reply? That's the question you are supposed to answer.

Here's my favorite example: The statement $$\forall x\exists y (\text{y is the mother of x})$$ is true, because whoever $\forall$ picks in move 1, $\exists$ can win by picking that person's mother. Suppose $\forall$ picks $x$ equal to Angela Merkel; then $\exists$ wins by picking $y$ equal to Angela Merkel's mother.

But the statement $$\exists y\forall x (\text{y is the mother of x})$$ is false, because now $\exists$ must go first, and she has no winning move. Suppose she picks $y$ equal to Angela Merkel's mother. Then $\forall$ can win by picking $x$ equal to someone who is not Angela Merkel or one of Merkel's siblings; say George W. Bush. Of course if $\exists$ picks Barbara Bush in her move, $\forall$ must not pick George W. Bush; he should pick someone else, like say Sisqo.

You asked in comments for an example with an implication. Let's consider $$\forall x\exists y (\text{x is even} \to \text {xy = 2}).$$

The $\forall$ player moves first. If he picks an odd number for $x$ he loses immediately, because then regardless of what $\exists$ does, the implication $\text{$x$is even} \to xy=2$ is vacuously true (the antecedent is false, so the entire implication is true), and the $\forall$ player loses when the final statement is true. So if $\forall$ wants to win he had better pick an even number! Suppose he picks $x=2$. Then $\exists$ can answer with $y=1$. And suppose he picks $x=4$; then $\exists$ can answer with $\frac12$ (if that is allowed; it may be clear from context, or it may be stated explicitly what moves are allowed.) But if $\forall$ picks $x=0$, he wins no matter what $\exists$ does, and so the quantified statement is false.

• This makes a lot of sense! I didn't consider order when I tried to interpret this question. Thanks. So if I choose say $x = -201$ then there is no $y$ that could prove the statement true. Therefore the statement is false right? – StrugglingCalcStudent Sep 29 '14 at 23:38
• Exactly right. ${}{}{}$ – MJD Sep 29 '14 at 23:40
• Okay I got it! If you don't mind, how should I think of a statement that involves implication? For example: $\forall x \exists y ( x \rightarrow xy )$ (I made it up but I have a complicated problem sort of like this)? – StrugglingCalcStudent Sep 29 '14 at 23:44
• You can do the same thing: $\forall$ picks an $x$, and then $\exists$ picks a $y$, and then you evaluate $x\to xy$ to see if it is true or false; if true, $\exists$ has won, and if false, $\forall$ has won. And the entire statement $\forall x\exists y(x\to xy)$ is true if $\exists$ can always win. I will add an example to the post. – MJD Sep 29 '14 at 23:45
• I'm glad this worked for you. After I wrote it I decided it probably was not helpful and planned to delete it. I must have posted it by accident. I'm glad I was wrong! – MJD Sep 29 '14 at 23:56