204 METHODS OF MATHEMATICAL PROOF, PART II Chapter 6
6.2 Indirect Proofs
An indirect proof is a proof in which we establish the truth of a statement
distinct from, but logically equivalent to, the desired result. Most indirect
proofs that you might either read or have to write at the undergraduate
level fall into one of three categories, each corresponding to an important
tautology from the propositional calculus.
Derivation of a conclusion involving the disjunction of two statements.
According to the tautology [p -+ (q v r)] * [(p A - q) -, r] [Theorem
l(p), Article 2.31, we may derive a conclusion of the form q v r from a
hypothesis p by assuming true the negation of one part of the conclusion,
that is, by adding -q to our list of hypotheses, and by trying, on that
basis, to establish the truth of the other part, that is, to prove r.
Proof by contrapositive. According to the tautology (p q) t,
(-q -+ -p) [Theorem l(n), Article 2.3; see also Theorem 2(f), Article
2.31, we may prove that a conclusion q follows from a hypothesis p by
showing that the truth of the negation of q implies that the hypothesis
is false; that is, -p is true.
Proof by contradiction, also known as reductio ad absurdum. Accord-
ing to the tautology [--p -+ (q A -q)] -, p [Theorem 2(g), Article 2.31,
we may establish p by proving that the assumption of the negation of
p leads to a logical impossibility, that is, a contradiction.It is important to understand the logical basis of these approaches and
to know how to write proofs in these forms; equally important, however,
is the ability to recognize when an indirect approach is appropriate, as
opposed to direct methods outlined thus far in the text. We stress at the
outset that the methods of this article are intended to supplement, not sub-
stitute for, direct methods. As a general rule, most mathematicians regard
a direct proof as preferable, from the point of view of both clarity and aes-
thetic appeal, to an indirect proof, when the former is possible. Putting it
differently you should try to develop a sense of the situations in which an
indirect approach (particularly contrapositive and contradiction) is the route
to take; do not fall into a habit of overusing these methods.
We now consider in sequence the three cases just outlined.DERIVATION OF CONCLUSIONS INVOLVING DISJUNCTION
In Article 5.3 we considered the situation of a hypothesis having the form
of a disjunction p, v p, v -.. v p, of statements. In that instance we sug-
gested that a division of an argument into cases is often an appropriate
and fruitful path. Now we wish to consider the situation in which the &
sired conclusion is a disjunction. This can present difficulties, because most
arguments in mathematics are geared toward a single conclusion at a time.
Indeed, if our conclusion is a conjunction q, A q, A -. A q,, we most often