Ready to start juggling with both hands? We now turn to the important case
in which universal and existential quantiļ¬ers get mixed together. Letā™s start
with the following sentence:
āx [Cube(x) ā’ āy (Tet(y) ā§ LeftOf(x, y))]
This sentence shouldnā™t throw you. It has the overall Aristotelian form
āx [P(x) ā’ Q(x)], which we have seen many times before. It says that every
cube has some property or other. What property? The property expressed
294 / Multiple Quantifiers
Figure 11.1: A circumstance in which āx āy Likes(x, y) holds versus one in which
āy āx Likes(x, y) holds. It makes a big diļ¬erence to someone!
by āy (Tet(y) ā§ LeftOf(x, y)), that is, the property of being left of a tetrahe-
dron. Thus our ļ¬rst-order sentence claims that every cube is to the left of a
This same claim could also be expressed in a number of other ways. The
most important alternative puts the quantiļ¬ers all out front, in prenex form.
Though the prenex form is less natural as a translation of the English, Every
cube is left of some tetrahedron, it is logically equivalent:
āx āy [Cube(x) ā’ (Tet(y) ā§ LeftOf(x, y))]
When we have a sentence with a string of mixed quantiļ¬ers, the order of
the quantiļ¬ers makes a diļ¬erence. This is something we havenā™t had to worry
order of quantiļ¬ers
about with sentences that contain only universal or only existential quantiļ¬ers.
Clearly, the sentence āx āy Likes(x, y) is logically equivalent to the sentence
where the order of the quantiļ¬ers is reversed: āy āx Likes(x, y). They are both
true just in case everything in the domain of discourse (say, people) likes
everything in the domain of discourse. Similarly, āx āy Likes(x, y) is logically
equivalent to āy āx Likes(x, y): both are true if something likes something.
This is not the case when the quantiļ¬ers are mixed. āx āy Likes(x, y) says
that everyone likes someone, which is true in both circumstances shown in Fig-
ure 11.1. But āy āx Likes(x, y) says that there is some lucky devil who everyone
likes. This is a far stronger claim, and is only true in the second circumstance
shown in Figure 11.1. So when dealing with mixed quantiļ¬ers, you have to be
very sensitive to the order of quantiļ¬ers. Weā™ll learn more about getting the
order of quantiļ¬ers right in the sections that follow.
Mixed quantifiers / 295
You try it
1. Open the ļ¬les Mixed Sentences and KĀØnigā™s World. If you evaluate the two
sentences, youā™ll see that the ļ¬rst is true and the second false. Weā™re going
to play the game to see why they arenā™t both true.
2. Play the game on the ļ¬rst sentence, specifying your initial commitment as
true. Since this sentence is indeed true, you should ļ¬nd it easy to win.
When Tarskiā™s World makes its choice, all you need to do is choose any
block in the same row as Tarskiā™s.
3. Now play the game with the second sentence, again specifying your ini-
tial commitment as true. This time Tarskiā™s World is going to beat you
because youā™ve got to choose ļ¬rst. As soon as you choose a block, Tarski
chooses a block in the other row. Play a couple of times, choosing blocks
in diļ¬erent rows. See whoā™s got the advantage now?
4. Just for fun, delete a row of blocks so that both of the sentences come out
true. Now you can win the game. So there, Tarski! She who laughs last
laughs best. Save the modiļ¬ed world as World Mixed 1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Congratulations
Have you noticed that switching the order of the quantiļ¬ers does something order of variables
quite diļ¬erent from switching around the variables in the body of the sentence?
For example, consider the sentences
āx āy Likes(x, y)
āx āy Likes(y, x)
Assuming our domain consists of people, the ļ¬rst of these says that everybody
likes somebody or other, while the second says everybody is liked by somebody
or other. These are both very diļ¬erent claims from either of these:
āy āx Likes(x, y)
āy āx Likes(y, x)
Here, the ļ¬rst claims that there is a (very popular) person whom everybody
likes, while the second claims that there is a (very indiscriminate?) person
who likes absolutely everyone.
In the last section, we saw how using two existential quantiļ¬ers and the
identity predicate, we can say that there are at least two things with a par-
ticular property (say cubes):
āx āy (x = y ā§ Cube(x) ā§ Cube(y))
296 / Multiple Quantifiers
With mixed quantiļ¬ers and identity, we can say quite a bit more. For example,
consider the sentence
āx (Cube(x) ā§ āy (Cube(y) ā’ y = x))
This says that there is a cube, and furthermore every cube is identical to it.
Some cube, in other words, is the only cube. Thus, this sentence will be true
if and only if there is exactly one cube. There are many ways of saying things
like this in fol; weā™ll run across others in the exercises. We discuss numerical
claims more systematically in Chapter 14.
When you are dealing with mixed quantiļ¬ers, the order is very important.
āx āy R(x, y) is not logically equivalent to āy āx R(x, y).
11.8 If you skipped the You try it section, go back and do it now. Submit the ļ¬le World Mixed 1.
11.9 (Simple mixed quantiļ¬er sentences) Open Hilbertā™s Sentences and Peanoā™s World. Evaluate the
Ć‚ sentences one by one, playing the game if an evaluation surprises you. Once you understand
the sentences, modify the false ones by adding a single negation sign so that they come out
true. The catch is that you arenā™t allowed to add the negation sign to the front of the sentence!
Add it to an atomic formula, if possible, and try to make the claim nonvacuously true. (This
wonā™t always be possible.) Make sure you understand both why the original sentence is false
and why your modiļ¬ed sentence is true. When youā™re done, submit your sentence list with the
11.10 (Mixed quantiļ¬er sentences with identity) Open Leibnizā™s World and use it to evaluate the
Ć‚ sentences in Leibnizā™s Sentences. Make sure you understand all the sentences and follow any
instructions in the ļ¬le. Submit your modiļ¬ed sentence list.
11.11 (Building a world) Create a world in which all ten sentences in Arnaultā™s Sentences are true.
Ć‚ Submit your world.
11.12 (Name that object) Open Carrollā™s World and Herculeā™s Sentences. Try to ļ¬gure out which objects
Ć‚ have names, and what they are. You should be able to ļ¬gure this out from the sentences, all
of which are true. Once you have come to your conclusion, add the names to the objects and
check to see if all the sentences are true. Submit your modiļ¬ed world.
Mixed quantifiers / 297
The remaining three exercises all have to do with the sentences in the ļ¬le Buridanā™s Sentences and build
on one another.
11.13 (Building a world) Open Buridanā™s Sentences. Build a world in which all ten sentences are true.
Ć‚ Submit your world.
11.14 (Consequence) These two English sentences are consequences of the ten sentences in Buridanā™s
1. There are no cubes.
2. There is exactly one large tetrahedron.
Because of this, they must be true in any world in which Buridanā™s sentences are all true. So
of course they must be true in World 11.13, no matter how you built it.
ā—¦ Translate the two sentences, adding them to the list in Buridanā™s Sentences. Name the
expanded list Sentences 11.14. Verify that they are all true in World 11.13.
ā—¦ Modify the world by adding a cube. Try placing it at various locations and giving it
various sizes to see what happens to the truth values of the sentences in your ļ¬le. One or
more of the original ten sentences will always be false, though diļ¬erent ones at diļ¬erent
times. Find a world in which only one of the original ten sentences is false and name it
ā—¦ Next, get rid of the cube and add a second large tetrahedron. Again, move it around and
see what happens to the truth values of the sentences. Find a world in which only one of
the original ten sentences is false and name it World 11.14.2.
Submit your sentence ļ¬le and two world ļ¬les.
11.15 (Independence) Show that the following sentence is independent of those in Buridanā™s Sentences,
Ć‚ that is, neither it nor its negation is a consequence of those sentences.
āx āy (x = y ā§ Tet(x) ā§ Tet(y) ā§ Medium(x) ā§ Medium(y))
You will do this by building two worlds, one in which this sentence is false (call this
World 11.15.1) and one in which it is true (World 11.15.2)ā”but both of which make all of
Buridanā™s sentences true.
298 / Multiple Quantifiers
The step-by-step method of translation
When an English sentence contains more than one quantiļ¬ed noun phrase,
translating it can become quite confusing unless you approach it in a very
systematic way. It often helps to go through a few intermediate steps, treating
the quantiļ¬ed noun phrases one at a time.
Suppose, for example, we wanted to translate the sentence Each cube is
to the left of a tetrahedron. Here, there are two quantiļ¬ed noun phrases: each
cube and a tetrahedron. We can start by dealing with the ļ¬rst noun phrase,
temporarily treating the complex phrase is-to-the-left-of-a-tetrahedron as a
single unit. In other words, we can think of the sentence as a single quantiļ¬er
sentence, on the order of Each cube is small. The translation would look like
āx (Cube(x) ā’ x is-to-the-left-of-a-tetrahedron)
Of course, this is not a sentence in our language, so we need to translate the
expression x is-to-the-left-of-a-tetrahedron. But we can think of this expression
as a single quantiļ¬er sentence, at least if we pretend that x is a name. It has
the same general form as the sentence b is to the left of a tetrahedron, and
would be translated as
āy (Tet(y) ā§ LeftOf(x, y))
Substituting this in the above, we get the desired translation of the original
āx (Cube(x) ā’ āy (Tet(y) ā§ LeftOf(x, y)))
This is exactly the sentence with which we began our discussion of mixed
This step-by-step process really comes into its own when there are lots of
quantiļ¬ers in a sentence. It would be very diļ¬cult for a beginner to trans-
late a sentence like No cube to the right of a tetrahedron is to the left of a
larger dodecahedron in a single blow. Using the step-by-step method makes it
straightforward. Eventually, though, you will be able to translate quite com-
plex sentences, going through the intermediate steps in your head.
The step-by-step method of translation / 299
11.16 (Using the step-by-step method of translation)
Ć‚ ā—¦ Open Montagueā™s Sentences. This ļ¬le contains expressions that are halfway between En-
glish and ļ¬rst-order logic. Our goal is to edit this ļ¬le until it contains translations of
the following English sentences. You should read the English sentence below, make sure
you understand how we got to the halfway point, and then complete the translation by
replacing the hyphenated expression with a wļ¬ of ļ¬rst-order logic.
1. Every cube is to the left of every tetrahedron. [In the Sentence window, you
see the halfway completed translation, together with some blanks that need to
be replaced by wļ¬s. Commented out below this, you will ļ¬nd an intermediate
āsentence.ā Make sure you understand how we got to this intermediate stage of
the translation. Then complete the translation by replacing the blank with
āy (Tet(y) ā’ LeftOf(x, y))