# Difference of these two First Order Logic statements

1) $(\forall x)(\exists y)x{\le}y$

2) $(\exists y)(\forall x)x{\le}y$

Assume that the domain of the variable is $D={0,1,2,...,99}$

These two statements says two things in natural language. I just cannot distinguish two translations. Can some one help me?

• I want to write that in english. That's what I want. – Samitha Nanayakkara Jun 4 '16 at 14:39
• The first one says: "for any number $n$ there is number $m$ (not necessarily distinct form $n$) such that $m$ is greater or equal to $n$". – Mauro ALLEGRANZA Jun 4 '16 at 15:57
• The second one says: "there is number $m$ that is greater or equal to every number $n$". – Mauro ALLEGRANZA Jun 4 '16 at 15:58
• For me, both gives the same meaning. What's the difference? For given domain which is correct and which is not? Please explain. – Samitha Nanayakkara Jun 4 '16 at 18:47
• Consider as domain the set $\mathbb N$ of natural numbers: do you think that the second holds ? – Mauro ALLEGRANZA Jun 4 '16 at 18:57

"$$\forall x\ ( P(x) )$$" means "For any $$x$$, it is true that $$P(x)$$", equivalently "$$P(x)$$ is true for every $$x$$". If you claim this statement, then you're effectively claiming that:

No matter what $$x$$ I give you, you can show me that $$P(x)$$ is true.

"$$\exists x\ ( P(x) )$$" means "For some $$x$$, it is true that $$P(x)$$", equivalently "$$P(x)$$ is true for at least one $$x$$". If you claim this statement, then you're effectively claiming that:

You can give me some $$x$$ and then show me that $$P(x)$$ is true.

$$\forall x\ ( \exists y\ ( P(x,y) ) )$$.

$$\exists y\ ( \forall x\ ( P(x,y) ) )$$.

It should be clear from my definition that they say different things. You should slowly expand the quantifiers one by one to see why. For example the first one expands to:

For any $$x$$, it is true that $$\exists y\ ( P(x,y) )$$.

and then:

For any $$x$$, it is true that ( for some $$y$$, it is true that $$P(x,y)$$ ).

which if you claim it means that:

No matter what $$x$$ I give you, you can give me some $$y$$ and then show me that $$P(x,y)$$ is true.

Note that the $$y$$ that you give me is after I give you the $$x$$, so you are free to choose a different $$y$$ if I give you a different $$x$$.

In contrast the second expands to:

For some $$y$$, it is true that $$\forall x\ ( P(x,y) )$$.

and then:

For some $$y$$, it is true that ( for every $$x$$, it is true that $$P(x,y)$$ ).

which if you claim it means that:

You can give me some $$y$$ and then show me that, no matter what $$x$$ I give you, you can show me that $$P(x,y)$$ is true.

Note that the $$y$$ that you give me is before I give you the $$x$$, so that single $$y$$ must work for every $$x$$ that I give you.

• Unless you know what you're doing, don't write the quantifiers the way you've been doing it. The way I've written it is not only completely precise as to what is under the scope of each quantifier, but also is a common convention and will be universally understood. – user21820 Jun 4 '16 at 15:13
• Sorry. This doesn't make any sense for me. Can you simply explain with natural english which is true and which is false for given domain D? I spent lots of hours to understand this and This still gives me no sense at all. – Samitha Nanayakkara Jun 4 '16 at 17:54
• @User9125: I've fully expanded the definitions, and added one useful way of understanding quantifiers. If it is still unclear, tell me specifically which point in my answer you get lost. The point is that once you grasp the quantifiers in full generality, it will be trivial for you to understand all instances, so I don't want to be bogged down by your specific example. – user21820 Jun 5 '16 at 1:58
• Both meanings which I get after translation seems so equal to me. Can you tell me clearly what's the difference clearly. – Samitha Nanayakkara Jun 5 '16 at 2:15
• @User9125: I've already explained the difference using the game interpretation. Please think through it slowly. Play the game with an imaginary opponent, using the domain of natural numbers. If you can ensure a win, then the claim is true. If your opponent can ensure a win, then the claim is false. – user21820 Jun 5 '16 at 2:17