ńņš. 58 |

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 |