English to First order Logic

Question

I was doing one of the exercises from Artificial Intelligence modern Approach book.

Here was the question : Convert English to FOL

Politicians can fool some of the people all of the time, and they can fool all of the people
some of the time, but they can’t fool all of the people all of the time.

And, here is the answer given to it.

∀ x Politician(x) ⇒
(∃ y ∀ t Person(y) ∧ Fools(x, y, t)) ∧
(∃ t ∀ y Person(y) ⇒ Fools(x, y, t)) ∧
¬(∀ t ∀ y Person(y) ⇒ Fools(x, y, t))

My doubt is.

We normally use Implication with Universal Quantifier, but here they used

(∃ y ∀ t Person(y) ∧ Fools(x, y, t))

for this part of question - can fool some of the people all of the time

isn't this wrong?

But, in the second case

they can fool all of the people some of the time

they used implication.

I am confused for what should be the order for Existential and Universal Quantifiers.

Can someone clear my doubt?

Thank you.

Answer 1

We normally use Implication with Universal Quantifier

You have noticed a pattern, but it is not a rule, e.g.

There is always somebody worse off than yourself.

which your text book would formalize as:

∀t ∃x x is a person ∧ x is worse of than yourself at t

In a case like this, the conjunction that bothers you is necessitated just by the fact that the implied Universe of Discourse (the range of the variables) is all-encompassing - it is literally "everything" - so we're obliged to state that x is a person, as well as being worse of than yourself. In natural language the UoD is almost always restricted by the context of speech, or by explicitly restricting pronouns, such as somebody. It would be more natural in this case to restrict the UoD to people and formalize simply as:

∀t ∃p p is worse of than yourself at t

Isn't this wrong?

You are referring to:

∃ y ∀ t Person(y) ∧ Fools(x, y, t)

Yes, it is wrong. This says:

There is something y such that, at any time t, y is a person and y is
fooled by x at t.

But when we say that a politician can fool some of the people all the time, and all of the people some of the time, we don't actually mean there exists any particular person who is perpetually fooled by our politician. Clearly, we don't even mean to imply there is any particular fool whose life spans the whole political life of any given politician, and an artificial intelligence that drew that inference would be a flop. We actually mean that, all of the time, there are some people who are fooled by our politician, and some of the time, everybody is fooled by our politician. That is:

∀ t ∃ y Person(y) ∧ Fools(x, y, t)

and:

∃ t ∀ y Person(y) ⇒ Fools(x, y, t)

This example makes the important point that to formalize intelligently a statement or argument expressed in a natural language you need to formalize what it means, in its context, and not simply "what it looks like". x fools some of the people all of the time looks like your text book's version:

∃ y ∀ t Person(y) ∧ Fools(x, y, t)

because "some" is mentioned before "all". But natural languages rate quanitificational precision very low, and the mainstream of proficient English speakers do not think this proverb means what the text book says. (I'm sure even the authors of the book would agree, if it were brought to their notice.)

So you are right to be bothered by the ordering of existential and universal quantifiers.

∀ y ∃ x F(x,y)

says:

For anything y, there is something x such that F(x,y)

and:

∃ x ∀ y F(x,y)

says:

There is something x such that, for anything y, F(x,y)

and they are not usually interchangeable. Compare (with UoD = people):

Everyone has a mother
∀ x ∃ y Mother(y,x)

and

∃ y ∀ x Mother(y,x)
Someone is the mother of everyone.