Section Progress:

 

27.1 Same Quantifiers

So far we’ve concentrated on sentences with one quantifier. But applications of logic, from everyday life to reasoning in mathematics, we often encounter sentences with multiple quantifiers.

The simplest case is when a sentence has two quantifiers, but they don’t really interact in any way.

For example, consider: “There is a dog and there is a cat.” This sentence has two quantifiers in it, which tells us we need two quantifiers in our FOL translation.

We just translate this as:

ExD(x)&ExC(x)

or, equivalently, as

ExD(x)&EyC(y)

Since the scope of the quantifiers don’t overlap, we don’t even have to use different variables.

Even though it has two quantifiers in it, the quantifiers here don’t really interact. The sentence is just a combination of single-quantifier sentences.

Even if you have quantifiers of different types, like in “There is a dog or everything is hungry”, if they don’t interact then the translation is straightforward.

ExD(x)vAxH(x)

It is more complicated when quantifiers are related to each other. For example, if we have a relation likes Likes(x,y), then the quantifiers must have overlapping scope, because they both have to bind variables in this relation.

For example, if we said: “Somebody likes somebody”, it would be:

ExEyLikes(x,y)

As you know from Chapter 24, we could equivalently write:

EyExLikes(x,y)

Multiple quantifiers all of the same type is fairly straightforward: order doesn’t matter.

Quantifier Reorder (QRe):
AxAyL(x,y) ⇔ AyAxL(x,y)
ExEyL(x,y) ⇔ EyExL(x,y)

If they are all stacked up in front, you can reorder them and preserve equivalence.

Sometimes multiple quantifiers are needed even if the English doesn’t clearly have two quantifiers.

For example, consider this one.

Different quantifiers and different variables don’t necessarily pick out different objects.

As that problem shows, different quantifiers do not necessarily pick out different objects.

ExD(x)&ExD(x)

says “There is a dog and there is a dog.” If you think about it, this is just an example of idempotence from BOOL. The two different Ex are true even if there is one dog.

Even if the variables are different, it still says the same thing. For example, both

ExEy(D(x)&D(y))

and

ExEy(D(x)&D(y))

still say: “There is a dog and there is a dog.”

So even different variables don’t necessarily pick out different things.

In order to say there are two dogs, we need to say that “There is a dog and there is a different dog.”

This is the key role of identity in logic. Identity allows us to say two things are different, like the two dogs, even if we don’t have names for them.

Non-identities like ~(x=y) are distinctness clauses. If you want to say there (at least) three dogs, you just have to add enough non-identities to make sure they are all distinct.

27.1 Same Quantifiers