<<

. 54
( 107 .)



>>




Section 11.2
Mixed quanti¬ers

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



Section 11.2
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
tetrahedron.
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.




Chapter 11
Mixed quantifiers / 295



You try it
................................................................
1. Open the ¬les Mixed Sentences and K¨nig™s World. If you evaluate the two
o
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))



Section 11.2
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.
exactly one
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.

Remember

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).



Exercises


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
changes.

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.




Chapter 11
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
‚ Sentences.
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
World 11.14.1.

—¦ 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.




Section 11.2
298 / Multiple Quantifiers


Section 11.3
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
this:

∀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
English sentence:

∀x (Cube(x) ’ ∃y (Tet(y) § LeftOf(x, y)))

This is exactly the sentence with which we began our discussion of mixed
quanti¬ers.
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.




Chapter 11
The step-by-step method of translation / 299



Exercises


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))

<<

. 54
( 107 .)



>>