<<

. 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
‚ assertions that Alex made about this world. Evaluate Alex™s claims. If you have trouble with
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
your sentence ¬le.

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



>>