26 CHAPTER 1 Sets, Proof Templates, and Induction
statement is normally not equivalent to its inverse or to its converse, but the converse and
inverse are always equivalent to each other.1.3.3 New Proof Templates
The first new proof idea was used in Theorem 4 (Section 1.3.1). In Theorem 4(a) there were
two possibilities in the hypothesis. We needed to prove that regardless of which possibility
was true, the conclusion followed. The proof was actually two proofs! In general, there can
be any number of cases. The proof technique is outlined in Template 1.8.To prove a theorem by cases:- List all possible cases that will cover every circumstance in which the hypothesis
might hold. - For each possible case, prove the conclusion separately.
The proof of Theorem 4 is a simple proof by cases; we will present more complicated
examples later. As you proceed, be aware of the following recommendations in using a
proof by cases:- Make sure you need to use a proof by cases. If you break a proof into cases, you must
normally treat each case separately, which tends to make your proof long. If you don't
need to break the proof into cases, your proof will often be shorter. If only one step
of your proof needs to be broken into cases, then break only that step into cases. Even
more risky is breaking cases into subcases. Suppose you write a proof breaking into four
cases, and each case breaks into four subcases, and each subcase breaks into four sub-
subcases. That gives you 4.4.4 = 64 cases in all to prove, and that almost inevitably
makes your proof longer than it otherwise might be. - Make sure you list all possible cases. The proof of Theorem 4(a) in Section 1.3.1, con-
sisted of only two possible cases, and they were obvious from the problem. However,
problems sometimes break down into more than two cases, and when they do, it is easy
to miss some cases. - You need to prove that your list of cases covers all possible cases.
- When claiming that two cases are analogous, make sure that one case is truly analogous
to another. There may well be logical subtleties that arise in one case that didn't arise
in an earlier case. (Indeed, that is often why we break a problem into cases in the first
place!) Before saying that two cases are analogous, think carefully through the details
to make sure they are!
The discussion following Theorem 4 pointed out another proof technique. In dis-
cussing the statement of Theorem 4(a), it was pointed out that it is useful to understand
what a theorem does not say. Quite often, it is not true that what seems intuitively to be