2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Git Gud Sep 29 '14 at 22:57
  • 1
    $\begingroup$ 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. $\endgroup$ – hmakholm left over Monica Sep 29 '14 at 22:58
  • 1
    $\begingroup$ Check what happens if we let $x=-1000$. $\endgroup$ – André Nicolas Sep 29 '14 at 22:59
  • 1
    $\begingroup$ Not any $x<0$,but certainly any $x<-200$. $\endgroup$ – Thomas Andrews Sep 29 '14 at 22:59
  • $\begingroup$ 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? $\endgroup$ – StrugglingCalcStudent Sep 29 '14 at 23:01
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – StrugglingCalcStudent Sep 29 '14 at 23:38
  • $\begingroup$ Exactly right. ${}{}{}$ $\endgroup$ – MJD Sep 29 '14 at 23:40
  • $\begingroup$ 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)? $\endgroup$ – StrugglingCalcStudent Sep 29 '14 at 23:44
  • 1
    $\begingroup$ 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. $\endgroup$ – MJD Sep 29 '14 at 23:45
  • 1
    $\begingroup$ 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! $\endgroup$ – MJD Sep 29 '14 at 23:56

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.