<<

. 59
( 107 .)



>>

whom you can safely conclude that he is at home, at least if this is all you
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

<<

. 59
( 107 .)



>>