—¦ Open Peano™s World. Note that all of the English sentences are true in this world. Check

to see that your translations are as well.

Section 14.1

372 / More about Quantification

—¦ Open Bolzano™s World. Here sentences 1, 3, and 5 are the only true ones. Verify that your

translations have the right truth values in this world.

—¦ Open Skolem™s World. Only sentence 5 is true in this world. Check your translations.

—¦ Finally, open Montague™s World. In this world, sentences 2, 3, and 5 are the only true

ones. Check your translations.

14.4 (Saying more complicated things) Open Skolem™s World. Create a ¬le called Sentences 14.4 and

‚ describe the following features of Skolem™s World.

1. Use your ¬rst sentence to say that there are only cubes and tetrahedra.

2. Next say that there are exactly three cubes.

3. Express the fact that every cube has a tetrahedron that is to its right but is neither

in front of or in back of it.

4. Express the fact that at least one of the tetrahedra is between two other tetrahedra.

5. Notice that the further back something is, the larger it is. Say this.

6. Note that none of the cubes is to the right of any of the other cubes. Try to say this.

7. Observe that there is a single small tetrahedron and that it is in front of but to neither

side of all the other tetrahedra. State this.

If you have expressed yourself correctly, there is very little you can do to Skolem™s World without

making at least one of your sentences false. Basically, all you can do is “stretch” things out,

that is, move things apart while keeping them aligned. To see this, try making the following

changes.

1. Add a new tetrahedron to the world. Find one of your sentences that comes out false.

Move the new tetrahedron so that a di¬erent sentence comes out false.

2. Change the size of one of the objects. What sentence now comes out false?

3. Change the shape of one of the objects. What sentence comes out false?

4. Slide one of the cubes to the left. What sentence comes out false?

5. Rearrange the three cubes. What goes wrong now?

14.5 (Ambiguity and numerical quanti¬cation) In the Try It on page 305, we saw that the sentence

‚

At least four medium dodecahedra are adjacent to a medium cube.

is ambiguous, having both a strong and a weak reading. Using Tarski™s World, open a new

sentence ¬le and translate the strong and weak readings of this sentence into fol as sentences

(1) and (2). Remember that Tarski™s World does not understand our abbreviation for “at least

four” so you will need to write this out in full. Check that the ¬rst sentence is true in Anderson™s

First World but not in Anderson™s Second World, while the second sentence is true in both worlds.

Make some changes to the worlds to help you check that your translations express what you

intend. Submit your sentence ¬le.

Chapter 14

Numerical quantification / 373

14.6 (Games of incomplete information) As you recall, you can sometimes know that a sentence

‚ is true in a world without knowing how to play the game and win. Open Mostowski™s World.

Translate the following into ¬rst-order logic. Save your sentences as Sentences 14.6. Now, with-

out using the 2-D view, make as good a guess as you can about whether the sentences are true

or not in the world. Once you have assessed a given sentence, use Verify to see if you are right.

Then, with the correct truth value checked, see how far you can go in playing the game. Quit

whenever you get stuck, and play again. Can you predict in advance when you will be able to

win? Do not look at the 2-D view until you have ¬nished the whole exercise.

1. There are at least two tetrahedra.

2. There are at least three tetrahedra.

3. There are at least two dodecahedra.

4. There are at least three dodecahedra.

5. Either there is a small tetrahedron behind a small cube or there isn™t.

6. Every large cube is in front of something.

7. Every tetrahedron is in back of something.

8. Every small cube is in back of something.

9. Every cube has something behind it.

10. Every dodecahedron is small, medium, or large.

11. If e is to the left of every dodecahedron, then it is not a dodecahedron.

Now modify the world so that the true sentences are still true, but so that it will be clear how

to play the game and win.

14.7 (Satis¬ability) Recall that a set of sentences is satis¬able if there is world in which it is true.

‚| Determine whether the following set of sentences is satis¬able. If it is, build a world. If it is

not, use informal methods of proof to derive a contradiction from the set.

1. Every cube is to the left of every tetrahedron.

2. There are no dodecahedra.

3. There are exactly four cubes.

4. There are exactly four tetrahedra.

5. No tetrahedron is large.

6. Nothing is larger than anything to its right.

7. One thing is to the left of another just in case the latter is behind the former.

14.8 (Numbers of variables) Tarski™s World only allows you to use six variables. Let™s explore what

‚| kind of limitation this imposes on our language.

1. Translate the sentence There are at least two objects, using only the predicate =. How

many variables do you need?

2. Translate There are at least three objects. How many variables do you need?

Section 14.1

374 / More about Quantification

3. It is impossible express the sentence There are at least seven objects using only = and

the six variables available in Tarski™s World, no matter how many quanti¬ers you use.

Try to prove this. [Warning: This is true, but it is very challenging to prove. Contrast

this problem with the one below.] Submit your two sentences and turn in your proof.

14.9 (Reusing variables) In spite of the above exercise, there are in fact sentences we can express

‚ using just the six available variables that can only be true in worlds with at least seven objects.

For example, in Robinson™s Sentences, we give such a sentence, one that only uses the variables

x and y.

1. Open this ¬le. Build a world where there are six small cubes arranged on the front

row and test the sentence™s truth. Now add one more small cube to the front row, and

test the sentence™s truth again. Then play the game committed (incorrectly) to false.

Can you see the pattern in Tarski™s World™s choice of objects? When it needs to pick

an object for the variable x, it picks the leftmost object to the right of all the previous

choices. Then, when it needs to pick an object for the variable y, it picks the last object

chosen. Can you now see how the reused variables are working?

2. Now delete one of the cubes, and play the game committed (incorrectly) to true. Do

you see why you can™t win?

3. Now write a sentence that says there are at least four objects, one in front of the next.

Use only variables x and y. Build some worlds to check whether your sentence is true

under the right conditions. Submit your sentence ¬le.

Section 14.2

Proving numerical claims

Since numerical claims can be expressed in fol, we can use the methods of

proof developed in previous chapters to prove numerical claims. However, as

you may have noticed in doing the exercises, numerical claims are not always

terribly perspicuous when expressed in fol notation. Indeed, expressing a

numerical claim in fol and then trying to prove the result is a recipe for

disaster. It is all too easy to lose one™s grasp on what needs to be proved.

Suppose, for example, that you are told there are exactly two logic class-

rooms and that each classroom contains exactly three computers. Suppose you

also know that every computer is in some logic classroom. From these assump-

tions it is of course quite easy to prove that there are exactly six computers.

How would the proof go?

Proof: To prove there are exactly six computers it su¬ces to prove

that there are at least six, and at most six. To prove that there are

Chapter 14

Proving numerical claims / 375

at most six, we simply note that every computer must be in one of

the two classrooms, and that each classroom contains at most three,

so there can be at most six altogether, since 2 — 3 = 6. To prove that

there are at least six, we note that each classroom contains at least

three. But now we need another assumption that was not explicitly

stated in the exercise. Namely, we need to know that no computer

can be in two classrooms. Given that, we see that there must be at

least six computers, and so exactly six.

This may seem like making pretty heavy weather of an obvious fact, but it

illustrates two things. First, to prove a numerical claim of the form there exist

exactly n objects x such that P (x), which we agreed to abbreviate as ∃!n x P(x),

you need to prove two things: that there are at least n such objects, and that

there are at most n such objects.

The proof also illustrates a point about fol. If we were to translate our formal proofs of

numerical claims

premises and desired conclusion into fol, things would get quite complicated.

If we then tried to prove our fol conclusion from the fol premises using the

rules we have presented earlier, we would completely lose track of the basic

fact that makes the proof work, namely, that 2 — 3 = 6. Rather than explicitly

state and use this fact, as we did above, we would have to rely on it in a hidden

way in the combinatorial details of the proof. While it would be possible to

give such a proof, no one would really do it that way.

The problem has to do with a syntactic shortcoming of fol. Not having

quanti¬ers that directly express numerical claims in terms of numbers, such

claims must be translated using just ∀ and ∃. If we were to add numerical

quanti¬ers to fol, we would be able to give proofs that correspond much

more closely to the intuitive proofs. Still, the theoretical expressive power of

the language would remain the same.

We can think of the above proof as illustrating a new method of proof. a new method of proof

When trying to prove ∃!n x P(x), prove two things: that there are at least n

objects satisfying P(x), and that there are at most n such objects.

A particularly important special case of this method is with uniqueness

claims, those of the form ∃!x P(x), which say there is exactly one object with

some property. To prove such a claim, we must prove two things, existence

and uniqueness. In proving existence, we prove that there is at least one

object satisfying P(x). Given that, we can then show uniqueness by show-

ing that there is at most one such object. To give an example, let us prove

∃!x [Even(x) § Prime(x)].

Proof: We ¬rst prove existence, that is, that there is an even prime.

This we do simply by noting that 2 is even and a prime. Thus,

Section 14.2

376 / More about Quantification

by existential generalization, there is an even prime. Next we prove

uniqueness. That is, we prove that for any number x, if x is an even

prime, then x = 2, by general conditional proof. Suppose x is an even

prime. Since it is even, it must be divisible by 2. But being prime, it

is divisible only by itself and 1. So x = 2. This concludes our proof

of uniqueness.

With one signi¬cant exception (induction, which we take up in Chap-

ter 16), we have now introduced all the major methods of proof. When these

are used in mathematical proofs, it is common to suppress a lot of detail,

including explicit mention of the methods being used. To a certain extent,

we have already been doing this in our proofs. From now on, though, we will

present proofs in a more abbreviated fashion, and expect you to be able to ¬ll

in the details. For example, here is a more abbreviated version of our proof

that there is exactly one even prime. You should check to see that you could

have ¬lled in the details on your own.

Proof: We ¬rst prove existence, that is, that there is an even prime.

This we do simply by noting that 2 is even and a prime. We then

prove uniqueness, by proving that any even prime must be 2. First,

since it is even, it must be divisible by 2. But being prime, if it is

divisible by 2, it is 2.

Since the numerical quanti¬ers are really shorthand for more complicated

expressions in our language, there is no real need to introduce rules that

speci¬cally apply to them. Of course the same could have been said for ’,

but we saw that it was much more convenient to have rules of proof for ’

than to reduce things to ∨ and ¬ and use their rules of proof. But the situation

is di¬erent with numerical quanti¬ers. In practice, people rarely give formal

proofs of numerical claims expressed in fol, since they quickly become too

complex, with or without special rules for these quanti¬ers. With numerical

claims, informal proofs are the order of the day.

Remember

To prove ∃!n x P(x), prove two things:

—¦ that there are at least n objects satisfying P(x), and

—¦ that there are at most n objects satisfying P(x).

Chapter 14

Proving numerical claims / 377

Exercises

Use Fitch to give formal proofs of the following arguments. You may use Taut Con where it is con-

venient. We urge you to work backwards, especially with the last problem, whose proof is simple in

conception but complex in execution.

14.10 ∃x (Cube(x) § ∀y (Cube(y) ’ y = x))

‚

∃x ∀y (Cube(y) ” y = x)

14.11 ∃x ∀y (Cube(y) ” y = x)

‚

∃x (Cube(x) § ∀y (Cube(y) ’ y = x))

14.12 ∃x ∃y (Cube(x) § Cube(y) § x = y)