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
    But this sounds like you *have* it in your head. Do yo know why $\exists y, \forall x, x=2y$ is wrong?2012-09-26
  • 0
    I suppose I forgot to mention that in my original post, I have problem figuring out why, indeed. Sorry.2012-09-26
  • 0
    I think I figured it out. Every x is so that there exists an y where x = 2y, so for example if you have x = 3 there is no y-counterpart. You have 2*1, 2*2, 2*3 etc, so for all odd numbers you won't have a counterpart, would this be correct?2012-09-26
  • 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
    This is an amazing explanation, thank you kind sir!2012-09-26
  • 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.