know. So how should we proceed? What we could do is give a temporary name

temporary names

to one of the boys who is at home, and refer to him using that name, as long

as we are careful not to use a name already used in the premises or the desired

conclusion.

This sort or reasoning is used in everyday life when we know that someone

(or something) satis¬es a certain condition, but do not know who (or what)

satis¬es it. For example, when Scotland Yard found out there was a serial

killer at large, they dubbed him “Jack the Ripper,” and used this name in

reasoning about him. No one thought that this meant they knew who the

killer was; rather, they simply introduced the name to refer to whoever was

doing the killing. Note that if the town tailor were already called Jack the

Ripper, then the detectives™ use of this name would (probably) have been a

gross injustice.

This is a basic strategy used when giving proofs in fol. If we have correctly

proven that ∃x S(x), then we can give a name, say c, to one of the objects

satisfying S(x), as long as the name is not one that is already in use. We may

then assume S(c) and use it in our proof. This is the rule known as existential

existential elimination

(instantiation) instantiation or existential elimination.

Generally, when existential instantiation is used in a mathematical proof,

this will be marked by an explicit introduction of a new name. For example,

the author of the proof might say, “So we have shown that there is a prime

number between n and m. Call it p.” Another phrase that serves the same

function is: “Let p be such a prime number.”

Let™s give an example of how this rule might be used, by modifying our

preceding example. The desired conclusion is the same but one of the premises

is changed.

Chapter 12

The method of general conditional proof / 323

∀x [Cube(x) ’ Large(x)]

∀x [Large(x) ’ LeftOf(x, b)]

∃x Cube(x)

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

The ¬rst two premises are the same but the third is weaker, since it does not

tell us which block is a cube, only that there is one. We would like to eliminate

the ∃ in our third premise, since then we would be back to the case we have

already examined. How then should we proceed? The proof would take the

following form:

Proof: We ¬rst note that the third premise assures us that there is at

least one cube. Let “e” name one of these cubes. We can now proceed

just as in our earlier reasoning. Applying the ¬rst premise, we see

that e must be large. (What steps are we using here?) Applying

the second premise, we see that e must also be left of c. Thus, we

have shown that e is both large and left of c. Our desired conclusion

follows (by what inference step?) from this claim.

In applying existential instantiation, it is very important to make sure you an important condition

use a new name, not one that is already in use or that appears in the conclusion

you wish to prove. Looking at the above example shows why. Suppose we had

thoughtlessly used the name “b” for the cube e. Then we would have been

able to prove ∃x LeftOf(x, x), which is impossible. But our original premises

are obviously satis¬able: they are true in many di¬erent worlds. So if we do

not observe this condition, we can be led from true premises to false (even

impossible) conclusions.

Section 12.3

The method of general conditional proof

One of the most important methods of proof involves reasoning about an

arbitrary object of a particular kind in order to prove a universal claim about

all such objects. This is known as the method of general conditional proof. It

is a more powerful version of conditional proof, and similar in spirit to the

method of existential instantiation just discussed.

Let™s start out with an example. This time let us assume that the domain

of discourse consists of students at a particular college. We suppose that we

are given a bunch of information about these students in the form of premises.

Section 12.3

324 / Methods of Proof for Quantifiers

Finally, let us suppose we are able to prove from these premises that Sandy,

a math major, is smart. Under what conditions would we be entitled to infer

that every math major at the school is smart?

At ¬rst sight, it seems that we could never draw such a conclusion, unless

there were only one math major at the school. After all, it does not follow

from the fact that one math major is smart that all math majors are. But

what if our proof that Sandy is smart uses nothing at all that is particular to

Sandy? What if the proof would apply equally well to any math major? Then

it seems that we should be able to conclude that every math major is smart.

How might one use this in a real example? Let us suppose that our argu-

ment took the following form:

Anyone who passes Logic 101 with an A is smart.

Every math major has passed Logic 101 with an A.

Every math major is smart.

Our reasoning proceeds as follows.

Proof: Let “Sandy” refer to any one of the math majors. By the

second premise, Sandy passed Logic 101 with an A. By the ¬rst

premise, then, Sandy is smart. But since Sandy is an arbitrarily

chosen math major, it follows that every math major is smart.

This method of reasoning is used at every turn in doing mathematics. The

general form is the following: Suppose we want to prove ∀x [P(x) ’ Q(x)] from

general conditional

proof some premises. The most straightforward way to proceed is to choose a name

that is not in use, say c, assume P(c), and prove Q(c). If you are able to do

this, then you are entitled to infer the desired result.

Let™s look at another example. Suppose we wanted to prove that every

prime number has an irrational square root. To apply general conditional

proof, we begin by assuming that p is an arbitrary prime number. Our goal is

√

to show that p is irrational. If we can do this, we will have established the

general claim. We have already proven that this holds if p = 2. But our proof

relied on speci¬c facts about 2, and so the general claim certainly doesn™t

follow from our proof. The proof, however, can be generalized to show what

we want. Here is how the generalization goes.

Proof: Let p be an arbitrary prime number. (That is, let “p” refer

to any prime number.) Since p is prime, it follows that if p divides a

square, say k 2 , then it divides k. Hence, if p divides k 2, p2 also divides

√

k 2 . Now assume, for proof by contradiction, that p is rational. Write

√

it in lowest terms as p = n/m. In particular, we can make sure that

Chapter 12

The method of general conditional proof / 325

p does not divide both n and m without remainder. Now, squaring

both sides, we see that

n2

p= 2

m

and hence

pm2 = n2

But then it follows that p divides n2, and so, as we have seen, p

divides n and p2 divides n2 . But from the latter of these it follows

that p2 divides pm2 so p divides m2. But then p divides m. So we

have shown that p divides both n and m, contradicting our choice of

√

n and m. This contradiction shows that p is indeed irrational.

It is perhaps worth mentioning an aspect of mathematical discourse illus-

trated in this proof that often confuses newcomers to mathematics. In math-

ematics lectures and textbooks, one often hears or reads “Let r (or n, or f ,

etc.) be an arbitrary real number (natural number, function, etc.).” What is

confusing about this way of talking is that while you might say “Let Sandy

take the exam next week,” no one would ever say “Let Sandy be an arbitrary

student in the class.” That is not the way “let” normally works with names

in English. If you want to say something like that, you should say “Let™s use

˜Sandy™ to stand for any student in the class,” or “Let ˜Sandy™ denote any

student in the class.” In mathematics, though, this “let” locution is a stan-

dard way of speaking. What is meant by “Let r be an arbitrary real number”

is “Let ˜r™ denote any real number.” In the above proof we paraphrased the

¬rst sentence to make it clearer. In the future, we will not be so pedantic.

Universal generalization

In formal systems of deduction, the method of general conditional proof is

usually broken down into two parts, conditional proof and a method for prov-

ing completely general claims, claims of the form ∀x S(x). The latter method

is called universal generalization or universal introduction. It tells us that if universal introduction

(generalization)

we are able to introduce a new name c to stand for a completely arbitrary

member of the domain of discourse and go on to prove the sentence S(c), then

we can conclude ∀x S(x).

Here is a very simple example. Suppose we give an informal proof that the

following argument is valid.

∀x (Cube(x) ’ Small(x))

∀x Cube(x)

∀x Small(x)

Section 12.3

326 / Methods of Proof for Quantifiers

In fact, it was the ¬rst example we looked at back in Chapter 10. Let™s give a

proof of this argument.

Proof: We begin by taking a new name d, and think of it as stand-

ing for any member of the domain of discourse. Applying universal

instantiation twice, once to each premise, gives us

1. Cube(d) ’ Small(d)

2. Cube(d)

By modus ponens, we conclude Small(d). But d denotes an arbitrary

object in the domain, so our conclusion, ∀x Small(x), follows by uni-

versal generalization.

Any proof using general conditional proof can be converted into a proof

universal generalization

and general conditional using universal generalization, together with the method of conditional proof.

proof Suppose we have managed to prove ∀x [P(x) ’ Q(x)] using general conditional

proof. Here is how we would go about proving it with universal generalization

instead. First we would introduce a new name c, and think of it as standing

for an arbitrary member of the domain of discourse. We know we can then

prove P(c) ’ Q(c) using ordinary conditional proof, since that is what we did

in our original proof. But then, since c stands for an arbitrary member of the

domain, we can use universal generalization to get ∀x [P(x) ’ Q(x)].

This is how formal systems of deduction can get by without having an

explicit rule of general conditional proof. One could equally well think of uni-

versal generalization as a special case of general conditional proof. After all,

if we wanted to prove ∀x S(x) we could apply general conditional proof to

the logically equivalent sentence ∀x [x = x ’ S(x)]. Or, if our language has

the predicate Thing(x) that holds of everything in the domain of discourse,

we could use general conditional proof to obtain ∀x [Thing(x) ’ S(x)]. (The

relation between general conditional proof and universal generalization will

become clearer when we get to the topic of generalized quanti¬ers in Sec-

tion 14.4.)

We have chosen to emphasize general conditional proof since it is the

method most often used in giving rigorous informal proofs. The division of this

method into conditional proof and universal generalization is a clever trick,

but it does not correspond well to actual reasoning. This is at least in part

due to the fact that universal noun phrases of English are always restricted by

some common noun, if only the noun thing. The natural counterparts of such

statements in fol have the form ∀x [P(x) ’ Q(x)], which is why we typically

prove them by general conditional proof.

Chapter 12

The method of general conditional proof / 327

We began the discussion of the logic of quanti¬ed sentences in Chapter 10

by looking at the following arguments:

1. ∀x (Cube(x) ’ Small(x))

∀x Cube(x)

∀x Small(x)

2. ∀x Cube(x)

∀x Small(x)

∀x (Cube(x) § Small(x))

We saw there that the truth functional rules did not su¬ce to establish these

arguments. In this chapter we have seen (on page 326) how to establish the

¬rst using valid methods that apply to the quanti¬ers. Let™s conclude this

discussion by giving an informal proof of the second.

Proof: Let d be any object in the domain of discourse. By the ¬rst

premise, we obtain (by universal elimination) Cube(d). By the second

premise, we obtain Small(d). Hence we have (Cube(d) § Small(d)).

But since d is an arbitrary object in the domain, we can conclude

∀x (Cube(x) § Small(x)), by universal generalization.

Exercises

The following exercises each contain a formal argument and something that purports to be an informal

proof of it. Some of these proofs are correct while others are not. Give a logical critique of the purported

proof. Your critique should take the form of a short essay that makes explicit each proof step or method

of proof used, indicating whether it is valid or not. If there is a mistake, see if can you patch it up by

giving a correct proof of the conclusion from the premises. If the argument in question is valid, you

should be able to ¬x up the proof. If the argument is invalid, then of course you will not be able to ¬x

the proof.

12.1 ∀x [(Brillig(x) ∨ Tove(x)) ’ (Mimsy(x) § Gyre(x))]

∀y [(Slithy(y) ∨ Mimsy(y)) ’ Tove(y)]

∃x Slithy(x)

∃x [Slithy(x) § Mimsy(x)]

Purported proof: By the third premise, we know that something in the domain of