<< Ļšåäūäółą’ ńņš. 53(čē 107 ńņš.)ĪĆĖĄĀĖÅĶČÅ Ńėåäóžłą’ >>

Section 10.5
288 / The Logic of Quantifiers

of geometry. Some follow from others by logic alone. Might it not be possible
to choose a few, relatively clear observations as basic, and derive all the others
by logic? The starting truths are accepted as axioms, while their consequences
axioms and theorems
are called theorems. Since the axioms are supposed to be obviously true, and
since the methods of proof are logically valid, we can be sure the theorems
are true as well.
This general procedure for systematizing a body of knowledge became
known as the axiomatic method. A set of axioms is chosen, statements which
we are certain hold of the āworldsā or ācircumstancesā under consideration.
Some of these may be meaning postulates, truths that hold simply in virtue
of meaning. Others may express obvious facts that hold in the domain in
question, facts like our fourth shape axiom. We can be sure that anything
that follows from the axioms by valid methods of inference is on just as ļ¬rm
a footing as the axioms from which we start.

Exercises

10.30 If you skipped the You try it section, go back and do it now. Submit the ļ¬le Proof Axioms 1.
Ć‚

10.31 Suppose we state our four basic shape axioms in the following schematic form:
 1. Ā¬āx (R(x) ā§ P(x))
2. Ā¬āx (P(x) ā§ Q(x))
3. Ā¬āx (Q(x) ā§ R(x))
4. āx (P(x) āØ Q(x) āØ R(x))

We noted that any valid argument involving just the three shape predicates remains valid
when you substitute other predicates, like the Tarskiā™s World size predicates, that satisfy these
axioms. Which of the following triplets of properties satisfy the axioms in the indicated domain
(that is, make them true when you substitute them for P, Q, and R)? If they donā™t, say which
axioms fail and why.

1. Red, yellow, and blue in the domain of automobiles.
2. Entirely red, entirely yellow, and entirely blue in the domain of automobiles.
3. Small, medium, and large in the domain of Tarskiā™s World blocks.
4. Small, medium, and large in the domain of physical objects.
5. Animal, vegetable, and mineral in the domain of ātwenty questionsā solutions.

Chapter 10
Chapter 11

Multiple Quantiļ¬ers

So far, weā™ve considered only sentences that contain a single quantiļ¬er symbol.
This was enough to express the simple quantiļ¬ed forms studied by Aristotle,
but hardly shows the expressive power of the modern quantiļ¬ers of ļ¬rst-order
logic. Where the quantiļ¬ers of fol come into their own is in expressing claims
which, in English, involve several quantiļ¬ed noun phrases.
Long, long ago, probably before you were even born, there was an advertis-
ing campaign that ended with the tag line: Everybody doesnā™t like something,
but nobody doesnā™t like Sara Lee. Now thereā™s a quantiļ¬ed sentence! It goes
without saying that this was every logicianā™s favorite ad campaign. Or con-
sider Lincolnā™s famous line: You may fool all of the people some of the time;
you can even fool some of the people all of the time; but you canā™t fool all of
the people all of the time. Why, the mind reels!
To express claims like these, and to reveal their logic, we need to juggle
more than one quantiļ¬er in a single sentence. But it turns out that, like
juggling, this requires a fair bit of preparation and practice.

Section 11.1
Multiple uses of a single quantiļ¬er

When you learn to juggle, you start by tossing balls in a single hand, not
crossing back and forth. Weā™ll start by looking at sentences that have multiple
instances of ā, or multiple instances of ā, but no mixing of the two. Here are
a couple of sentences that contain multiple quantiļ¬ers:

āx āy [Cube(x) ā§ Tet(y) ā§ LeftOf(x, y)]
āx āy [(Cube(x) ā§ Tet(y)) ā’ LeftOf(x, y)]

Try to guess what these say. You shouldnā™t have any trouble: The ļ¬rst says
that some cube is left of a tetrahedron; the second says that every cube is left
of every tetrahedron.
In these examples, all the quantiļ¬ers are out in front (in what weā™ll later
call prenex form) but there is no need for them to be. In fact the same claims
could be expressed, perhaps more clearly, by the following sentences:

289
290 / Multiple Quantifiers

āx [Cube(x) ā§ āy (Tet(y) ā§ LeftOf(x, y))]
āx [Cube(x) ā’ āy (Tet(y) ā’ LeftOf(x, y))]
The reason these may seem clearer is that they show that the claims have
an overall Aristotelian structure. The ļ¬rst says that some cube has the prop-
erty expressed by āy (Tet(y) ā§ LeftOf(x, y)), namely, being left of some tetra-
hedron. The second says that every cube has the property expressed by
āy (Tet(y) ā’ LeftOf(x, y)), namely, being left of every tetrahedron.
It is easy to see that these make the same claims as the ļ¬rst pair, even
though, in the case of the universal claim, the structure of the fol sentence
has changed considerably. The principles studied in Chapter 10 would allow
us to prove these equivalences, if we wanted to take the time.
There is one tricky point that arises with the use of multiple existential
quantiļ¬ers or multiple universal quantiļ¬ers. Itā™s a simple one, but there isnā™t
a logician alive who hasnā™t been caught by it at some time or other. Itā™ll catch
you too. Weā™ll illustrate it in the following Try It.

You try it
................................................................
1. Suppose you are evaluating the following sentence in a world with four
cubes lined up in the front row:

āx āy [(Cube(x) ā§ Cube(y)) ā’ (LeftOf(x, y) āØ RightOf(x, y))]

Do you think the sentence is true in such a world?

2. Open Cantorā™s Sentences and Cantorā™s World, and evaluate the ļ¬rst sentence
in the world. If you are surprised by the outcome, play the game committed
to the truth of the sentence.

3. It is tempting to read this sentence as claiming that if x and y are cubes,
then either x is left of y or x is right of y. But there is a conversational
implicature in this way of speaking, one that is very misleading. The use of
the plural ācubesā suggests that x and y are distinct cubes, but this is not
part of the claim made by the ļ¬rst-order sentence. In fact, our sentence is
false in this world, as it must be in any world that contains even one cube.

4. If we really wanted to express the claim that every cube is to the left or
right of every other cube, then we would have to write

āx āy [(Cube(x) ā§ Cube(y) ā§ x = y) ā’ (LeftOf(x, y) āØ RightOf(x, y))]

Modify the ļ¬rst sentence in this way and check it in the world.

Chapter 11
Multiple uses of a single quantifier / 291

5. The second sentence in the ļ¬le looks for all the world like it says there are
two cubes. But it doesnā™t. Delete all but one cube in the world and check
to see that itā™s still true. Play the game committed to false and see what
happens.
6. See if you can modify the second sentence so it is false in a world with only
one cube, but true if there are two or more. (Use = like we did above.)
Save the modiļ¬ed sentences as Sentences Multiple 1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Congratulations
In general, to say that every pair of distinct objects stands in some relation, identity and
variables
you need a sentence of the form āx āy (x = y ā’ . . . ), and to say that there
are two objects with a certain property, you need a sentence of the form
āx āy (x = y ā§ . . . ). Of course, other parts of the sentence often guarantee the
distinctness for you. For example if you say that every tetrahedron is larger
than every cube:
āx āy ((Tet(x) ā§ Cube(y)) ā’ Larger(x, y))
then the fact that x must be a tetrahedron and y a cube ensures that your
claim says what you intended.
Remember

When evaluating a sentence with multiple quantiļ¬ers, donā™t fall into the
trap of thinking that distinct variables range over distinct objects. In fact,
the sentence āx āy P(x, y) logically implies āx P(x, x), and the sentence
āx P(x, x) logically implies āx āy P(x, y)!

Exercises

11.1 If you skipped the You try it section, go back and do it now. Submit the ļ¬le Sentences Multiple
Ć‚ 1.
11.2 (Simple multiple quantiļ¬er sentences) The ļ¬le Fregeā™s Sentences contains 14 sentences; the ļ¬rst
Ć‚ seven begin with a pair of existential quantiļ¬ers, the second seven with a pair of universal
quantiļ¬ers. Go through the sentences one by one, evaluating them in Peirceā™s World. Though
you probably wonā™t have any trouble understanding these sentences, donā™t forget to use the
game if you do. When you understand all the sentences, modify the size and location of a single
block so that the ļ¬rst seven sentences are true and the second seven false. Submit the resulting
world.

Section 11.1
292 / Multiple Quantifiers

11.3 (Getting fancier) Open up Peanoā™s World and Peanoā™s Sentences. The sentence ļ¬le contains 30
any, play the game (several times if necessary) until you see where you are going wrong. Then
change each of Alexā™s false claims into a true claim. If you can make the sentence true by
adding a clause of the form x = y, do so. Otherwise, see if you can turn the false claim into
an interesting truth: donā™t just add a negation sign to the front of the sentence. Submit your
corrected list of sentences.

11.4 (Describing a world) Letā™s try our hand describing a world using multiple quantiļ¬ers. Open
Ć‚ Finslerā™s World and start a new sentence ļ¬le.
1. Notice that all the small blocks are in front of all the large blocks. Use your ļ¬rst
sentence to say this.
2. With your second sentence, point out that thereā™s a cube that is larger than a tetra-
hedron.
3. Next, say that all the cubes are in the same column.
4. Notice, however, that this is not true of the tetrahedra. So write the same sentence
about the tetrahedra, but put a negation sign out front.
5. Every cube is also in a diļ¬erent row from every other cube. Say this.
6. Again, this isnā™t true of the tetrahedra, so say that itā™s not.
7. Notice there are diļ¬erent tetrahedra that are the same size. Express this fact.
8. But there arenā™t diļ¬erent cubes of the same size, so say that, too.

Are all your translations true in Finslerā™s World? If not, try to ļ¬gure out why. In fact, play
around with the world and see if your ļ¬rst-order sentences always have the same truth values
as the claims you meant to express. Check them out in KĀØnigā™s World, where all of the original
o
claims are false. Are your sentences all false? When you think youā™ve got them right, submit

11.5 (Building a world) Open Ramseyā™s Sentences. Build a world in which sentences 1ā“10 are all true
Ć‚ at once (ignore sentences 11ā“20 for now). These ļ¬rst ten sentences all make either particular
claims (that is, they contain no quantiļ¬ers) or existential claims (that is, they assert that things
of a certain sort exist). Consequently, you could make them true by successively adding objects
to the world. But part of the exercise is to make them all true with as few objects as possible.
You should be able to do it with a total of six objects. So rather than adding objects for each
new sentence, only add new objects when absolutely necessary. Again, be sure to go back and
check that all the sentences are true when you are ļ¬nished. Submit your world as World 11.5.
[Hint: To make all the sentences true with six blocks, you will have to watch out for some
intentionally misleading implicatures. For example, one of the objects will have to have two
names.]

Chapter 11
Mixed quantifiers / 293

11.6 (Modifying the world) Sentences 11-20 of Ramseyā™s Sentences all make universal claims. That is,
Ć‚ they all say that every object in the world has some property or other. Check to see whether the
world you have built in Exercise 11.5 satisļ¬es the universal claims expressed by these sentences.
If not, modify the world so it makes all 20 sentences true at once. Submit your modiļ¬ed world
as World 11.6. (Make sure you submit both World 11.5 and World 11.6 to get credit for both
exercises.)

11.7 (Block parties) The interaction of quantiļ¬ers and negation gives rise to subtleties that can be
Ć‚| pretty confusing. Open LĀØwenheimā™s Sentences, which contains eight sentences divided into two
o
sets. Suppose we imagine a column containing blocks to be a party and think of the blocks in
the column as the attendees. Weā™ll say a party is lonely if thereā™s only one block attending it,
and say a party is exclusive if thereā™s any block whoā™s not there.
1. Using this terminology, give simple and clear English renditions of each of the sentences.
For example, sentence 2 says some of the parties are not lonely, and sentence 7 says thereā™s
only one party. Youā™ll ļ¬nd sentences 4 and 9 the hardest to understand. Construct a lot
of worlds to see what they mean.

2. With the exception of 4 and 9, all of the sentences are equivalent to other sentences on the
list, or to negations of other sentences (or both). Which sentences are 3 and 5 equivalent
to? Which sentences do 3 and 5 negate?

3. Sentences 4 and 9 are logically independent: itā™s possible for the two to have any pattern
of truth values. Construct four worlds: one in which both are true (World 11.7.1), one
in which 4 is true and 9 false (World 11.7.2), one in which 4 is false and 9 true (World
11.7.3), and one in which both are false (World 11.7.4).

Submit the worlds youā™ve constructed and turn the remaining answers in to your instructor.
 << Ļšåäūäółą’ ńņš. 53(čē 107 ńņš.)ĪĆĖĄĀĖÅĶČÅ Ńėåäóžłą’ >>