Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
But this sounds like you have it in your head. Do yo know why $\exists y, \forall x, x=2y$ is wrong? –  Hagen von Eitzen Sep 26 '12 at 21:08
    
I suppose I forgot to mention that in my original post, I have problem figuring out why, indeed. Sorry. –  Fumler Sep 26 '12 at 21:10
    
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? –  Fumler Sep 26 '12 at 21:15
    
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$. –  Hagen von Eitzen Sep 26 '12 at 21:22
add comment

2 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
This is an amazing explanation, thank you kind sir! –  Fumler Sep 26 '12 at 21:19
    
@Fumler: You’re very welcome. –  Brian M. Scott Sep 26 '12 at 21:23
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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