<<

. 58
( 107 .)



>>



Exercises


11.39 (Translation) Open Peirce™s World. Look at it in 2-D to remind yourself of the hidden objects.
‚ Start a new sentence ¬le where you will translate the following English sentences. Again, be
sure to check each of your translations to see that it is indeed a true sentence.
1. Everything is either a cube or a tetrahedron.
2. Every cube is to the left of every tetrahedron.
3. There are at least three tetrahedra.
4. Every small cube is in back of a particular large cube.
5. Every tetrahedron is small.
6. Every dodecahedron is smaller than some tetrahedron. [Note: This is vacuously true in
this world.]

Now let™s change the world so that none of the English sentences are true. (We can do this by
changing the large cube in front to a dodecahedron, the large cube in back to a tetrahedron,
and deleting the two small tetrahedra in the far right column.) If your answers to 1“5 are
correct, all of your translations should be false as well. If not, you have made a mistake in
translation. Make further changes, and check to see that the truth values of your translations
track those of the English sentences. Submit your sentence ¬le.

11.40 (More translations for practice) This exercise is just to give you more practice translating
‚ sentences of various sorts. They are all true in Skolem™s World, in case you want to look while
translating.
—¦ Translate the following sentences.

1. Not every cube is smaller than every tetrahedra.
2. No cube is to the right of anything.
3. There is a dodecahedron unless there are at least two large objects.
4. No cube with nothing in back of it is smaller than another cube.
5. If any dodecahedra are small, then they are between two cubes.
6. If a cube is medium or is in back of something medium, then it has nothing to
its right except for tetrahedra.
7. The further back a thing is, the larger it is.
8. Everything is the same size as something else.
9. Every cube has a tetrahedron of the same size to its right.
10. Nothing is the same size as two (or more) other things.
11. Nothing is between objects of shapes other than its own.




Chapter 11
Some extra translation problems / 317



—¦ Open Skolem™s World. Notice that all of the above English sentences are true. Verify that
the same holds of your translations.

—¦ This time, rather than open other worlds, make changes to Skolem™s World and see
that the truth value of your translations track that of the English sentence. For ex-
ample, consider sentence 5. Add a small dodecahedron between the front two cubes.
The English sentence is still true. Is your translation? Now move the dodecahedron
over between two tetrahedra. The English sentence is false. Is your translation? Now
make the dodecahedron medium. The English sentence is again true. How about your
translation?

Submit your sentence ¬le.

11.41 Using the symbols introduced in Table 1.2, page 30, translate the following into fol. Do
‚ not introduce any additional names or predicates. Comment on any shortcomings in your
translations.
1. No student owned two pets at a time.
2. No student owned two pets until Claire did.
3. Anyone who owns a pet feeds it sometime.
4. Anyone who owns a pet feeds it sometime while they own it.
5. Only pets that are hungry are fed.

11.42 Translate the following into fol. As usual, explain the meanings of the names, predicates, and
 function symbols you use, and comment on any shortcomings in your translations.
1. You should always except the present company.
2. There was a jolly miller once
Lived on the River Dee;
He worked and sang from morn till night
No lark more blithe than he.
3. Man is the only animal that blushes. Or needs to.
4. You can fool all of the people some of the time, and some of the people all of the time,
but you can™t fool all of the people all of the time.
5. Everybody loves a lover.

11.43 Give two translations of each of the following and discuss which is the most plausible reading,
 and why.
1. Every senior in the class likes his or her computer, and so does the professor. [Treat
“the professor” as a name here and in the next sentence.]
2. Every senior in the class likes his or her advisor, and so does the professor.
3. In some countries, every student must take an exam before going to college.
4. In some countries, every student learns a foreign language before going to college.




Section 11.8
318 / Multiple Quantifiers


11.44 (Using DeMorgan™s Laws in mathematics) The DeMorgan Laws for quanti¬ers are quite helpful
 in mathematics. A function f on real numbers is said to be continuous at 0 if, intuitively, f (x)
can be kept close to f(0) by keeping x close enough to 0. If you have had calculus then you
will probably recognize the following a way to make this de¬nition precise:

∀ > 0 ∃δ > 0 ∀x (| x |< δ ’| f (x) ’ f (0) |< )

Here “∀ > 0(. . .)” is shorthand for “∀ ( > 0 ’ . . .)”. Similarly, “∃δ > 0(. . .)” is shorthand
for “∃δ(δ > 0 § . . .)”. Use DeMorgan™s Laws to express the claim that f is not continuous at 0
in prenex form. You may use the same kind of shorthand we have used. Turn in your solution.

11.45 Translate the following two sentences into fol:
 1. If everyone comes to the party, I will have to buy more food.
2. There is someone such that if he comes to the party, I will have to buy more food.

The natural translations of these turn out to have forms that are equivalent, according to the
equivalence in Problem 11.33. But clearly the English sentences do not mean the same thing.
Explain what is going on here. Are the natural translations really correct?




Chapter 11
Chapter 12

Methods of Proof for Quanti¬ers

In earlier chapters we discussed valid patterns of reasoning that arise from
the various truth-functional connectives of fol. This investigation of valid
inference patterns becomes more interesting and more important now that
we™ve added the quanti¬ers ∀ and ∃ to our language.
Our aim in this chapter and the next is to discover methods of proof that
allow us to prove all and only the ¬rst-order validities, and all and only the
¬rst-order consequences of a given set of premises. In other words, our aim
is to devise methods of proof su¬cient to prove everything that follows in
virtue of the meanings of the quanti¬ers, identity, and the truth-functional
connectives. The resulting deductive system does indeed accomplish this goal,
but our proof of that fact will have to wait until the ¬nal chapter of this book.
That chapter will also discuss the issue of logical consequence when we take
into account the meanings of other predicates in a ¬rst-order language.
Again, we begin looking at informal patterns of inference and then present
their formal counterparts. As with the connectives, there are both simple proof
steps and more substantive methods of proof. We will start by discussing the
simple proof steps that are most often used with ∀ and ∃. We ¬rst discuss
proofs involving single quanti¬er sentences and then explore what happens
when we have multiple and mixed quanti¬er sentences.


Section 12.1
Valid quanti¬er steps
There are two very simple valid quanti¬er steps, one for each quanti¬er. They
work in opposite directions, however.

Universal elimination

Suppose we are given as a premise (or have otherwise established) that ev-
erything in the domain of discourse is either a cube or a tetrahedron. And
suppose we also know that c is in the domain of discourse. It follows, of course,
that c is either a cube or a tetrahedron, since everything is.
More generally, suppose we have established ∀x S(x), and we know that c
names an object in the domain of discourse. We may legitimately infer S(c).



319
320 / Methods of Proof for Quantifiers


After all, there is no way the universal claim could be true without the speci¬c
claim also being true. This inference step is called universal instantiation or
universal elimination
(instantiation) universal elimination. Notice that it allows you to move from a known result
that begins with a quanti¬er ∀x (. . . x . . .) to one (. . . c . . .) where the quanti¬er
has been eliminated.

Existential introduction

There is also a simple proof step for ∃, but it allows you to introduce the
quanti¬er. Suppose you have established that c is a small tetrahedron. It
follows, of course, that there is a small tetrahedron. There is no way for the
speci¬c claim about c to be true without the existential claim also being
true. More generally, if we have established a claim of the form S(c) then we
may infer ∃x S(x). This step is called existential generalization or existential
existential introduction
(generalization) introduction.
In mathematical proofs, the preferred way to demonstrate the truth of
an existential claim is to ¬nd (or construct) a speci¬c instance that satis¬es
the requirement, and then apply existential generalization. For example, if
we wanted to prove that there are natural numbers x, y, and z for which
x2 + y 2 = z 2 , we could simply note that 32 + 42 = 52 and apply existential
generalization (thrice over).
The validity of both of these inference steps is not unconditional in English.
presuppositions
of these rules They are valid as long as any name used denotes some object in the domain
of discourse. This holds for fol by convention, as we have already stressed,
but English is a bit more subtle here. Consider, for example, the name Santa.
The sentence
Santa does not exist
might be true in circumstances where one would be reluctant to conclude
There is something that does not exist.
The trouble, of course, is that the name Santa does not denote anything. So
we have to be careful applying this rule in ordinary arguments where there
might be names in use that do not refer to actually existing objects.
Let™s give an informal proof that uses both steps, as well as some other
things we have learned. We will show that the following argument is valid:

∀x [Cube(x) ’ Large(x)]
∀x [Large(x) ’ LeftOf(x, b)]
Cube(d)
∃x [Large(x) § LeftOf(x, b)]



Chapter 12
Valid quantifier steps / 321



This is a rather obvious result, which is all the better for illustrating the
obviousness of these steps.

Proof: Using universal instantiation, we get

Cube(d) ’ Large(d)

and

Large(d) ’ LeftOf(d, b)

Applying modus ponens to Cube(d) and the ¬rst of these conditional
claims gives us Large(d). Another application of modus ponens gives
us LeftOf(d, b). But then we have

Large(d) § LeftOf(d, b)

Finally, applying existential introduction gives us our desired con-
clusion:

∃x [Large(x) § LeftOf(x, b)]

Before leaving this section, we should point out that there are ways to prove
existential statements other than by existential generalization. In particular,
to prove ∃x P(x) we could use proof by contradiction, assuming ¬∃x P(x) and
deriving a contradiction. This method of proceeding is somewhat less satis-
fying, since it does not actually tell you which object it is that satis¬es the
condition P(x). Still, it does show that there is some such object, which is all
that is claimed. This was in fact the method we used back on page 131 to
prove that there are irrational numbers x and y such that xy is rational.

Remember

1. Universal instantiation: From ∀x S(x), infer S(c), so long as c denotes
an object in the domain of discourse.

2. Existential generalization: From S(c), infer ∃x S(x), so long as c denotes
an object in the domain of discourse.




Section 12.1
322 / Methods of Proof for Quantifiers


Section 12.2
The method of existential instantiation
Existential instantiation is one of the more interesting and subtle methods of
proof. It allows you to prove results when you are given an existential state-
ment. Suppose our domain of discourse consists of all children, and you are
told that some boy is at home. If you want to use this fact in your reasoning,
you are of course not entitled to infer that Max is at home. Neither are you
allowed to infer that John is at home. In fact, there is no particular boy about

<<

. 58
( 107 .)



>>