Section Progress:

27.2 Mixed Quantifiers

As you learned in the last section, having many quantifiers in a sentence is not necessarily complex or difficult, as long as the quantifiers are all of the same type.

Rule: pick objects for quantifiers from left to right (wide to narrow).

Mixed quantifiers, though, is a whole different story. Just one quantifier of each type creates complexity.

The key rule for mixed quantifiers is that you pick objects for the quantifiers from left to right (wide to narrow).

Here’s what we mean. Say we have the sentence

∃x∀y(Dog(x)&BarkedAt(x,y))

The literal translation is: For some x, for all y: x is a dog and x barked at y.

In order to understand the sentence, we have to start at the left. There exists some object x, which we know is a dog.

Next comes the universal: we know that dog barked at everything. The universal quantifier comes only after we’ve picked the x (the dog). That’s how we know there is some dog that barked at everything.

For the universal quantifier, we can pick each object in the domain in turn: we know the dog barked at the first object, and the second object, etc.

But we pick each of those objects in turn only after we’ve picked the dog, because the ∃x came first.

Contrast this sentence:

∀y∃x(Dog(x)&BarkedAt(x,y))

Only the order of the quantifiers have changed.

But it makes a big difference, because we have to pick from left to right.

First we pick each object in the domain in turn, for the universal quantifier. For example, pick the first object in the domain. Let’s just call it “a” for now.

Next, for “a”, we know there exists a dog that barked at “a”.

Then we move on to the next object from the domain, call it “b”. After we’ve picked “b”, when then know there exists a dog that barked at it.

Since we are picking the objects for ∀y first, we don’t know that the dog barking at “a” is the same one as the dog barking at “b”.

Here’s the key: since we are picking the objects for ∀y first, we don’t know that the dog barking at “a” is the same one as the dog barking at “b”.

But when we had the other sentence,

∃x∀y(Dog(x)&BarkedAt(x,y))

we picked the dog first. When the ∃x is wide scope, we do know there is a single dog that barked at everything.

That means that order matters: ∃x∀y and ∀y∃x do not say the same thing.

Nonetheless there is a relation between them: one of them logically entails the other. See if you can figure out which.

X is stronger than Y: X entails Y, but Y does not entail X.

In logic we say that one sentence is “stronger” than another just in case it entails the other, but not vice versa.

So ∃x∀y is always stronger than ∀y∃x.

The logic gets even more complicated when we add more quantifiers.

∃x∀y∃z(Dog(x)&(BarkedAt(x,y)→(Cat(z)&y=z))

This says: There is some dog, such that everything it barks at is a cat.

But here’s the question you have to be able to answer if you understand that sentence.

Since we pick the universal quantifier∀y before the existential ∃z (the cat), we know that there could be different cats.

So what that sentence says is: some dog only barked at cats.

But if we change the order of the quantifiers:

∃x∃z∀y(Dog(x)&(BarkedAt(x,y)→(Cat(z)&y=z))

now it says something different.

This says there is some dog, such that anything it barks at is some specific cat. It says that because, moving from left to right, we have to pick ∃z, the cat, before ∀y.

Here’s one more example.

∀x∃y∀z(Likes(x,y)&Likes(y,z))

This says: “Everything likes something that likes everything.”

But as you can hopefully tell, it does not say that there is some specific thing, such that everything likes it and it likes everything.

27.2 Mixed Quantifiers