<<

. 68
( 107 .)



>>

5. There is a single large cube. No dodecahedron is in back of it.

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

<<

. 68
( 107 .)



>>