2
$\begingroup$

Trying to learn quantification but my head just stops when I try to figure it out.

$ \forall x,\exists y, x = 2y $

This is one of the examples. And what I am thinking here is: Every x is so that there exists an y where x = 2y

This is all fine and dandy I guess, but I just can't get this into my head, any tips or help here?

  • 0
    Well, if for $x=3$ there is no suitable $y$, then the statement $\forall x, \exists y, x=2y$ is false. If you allow rational numbers, however, odd numbers are no problem: For $x=3$ you can take $y=\frac32$ and have $x=2y$.2012-09-26

2 Answers 2

4

Think of it as a game: the first player gets to pick any $x$ at all, and the second player then has to find a $y$ that makes the statement $x=2y$ true. If the second player can always do this, the quantified statement $\forall x\exists y(x=2y)$ is true; if she can’t always do it, the quantified statement is false.

If we’re talking about integers, it’s false: if the first player picks $x=1$, the second player won’t be able to find an integer $y$ such that $2y=1$. If we’re talking about the real numbers, on the other hand, it’s true: no matter what $x$ the first player picks, the second player just chooses $x/2$ for $y$.

Now look at the statement with the quantifiers in the opposite order: $\exists y\forall x(x=2y)$. This time it’s the first player who is picking something, namely a number $y$, and he wins if no matter what $x$ the second player chooses, that $x=2y$. Equivalently, the second player wins if she can find an $x$ that makes the statement $x=2y$ false. And of course she always can, no matter what $y$ the first player chose, whether we’re talking about integers or about real numbers. In either domain the quantified statement $\exists y\forall x(x=2y)$ is false.

On the other hand, $\exists y\forall x(x+y=x)$ is true in both domains: the first player just has to pick $y=0$.

  • 0
    @Fumler: You’re very welcome.2012-09-26
1

Try reading any good intro logic text, where it introduces quantifiers. You are spoilt for choice. But Paul Teller's excellent Primer is now freely available online at http://tellerprimer.ucdavis.edu/ His first three or four (short) chapters on predicate logic should make everything very clear, not just on this question.