6.2 INDIRECT PROOFS 209readily available direct argument, can lead nowhere or to a convoluted
argument or at best to an argument that is not so well presented as it could
be. In Exercise 15 you are asked to examine difficulties that can arise if the
approach of contraposition is taken to theorems proved by direct methods
earlier in the text.
We conclude our consideration of proof by contrapositive with a re-
minder that such a proof always begins with the assumption of the negation
of the desired conclusion; it is never appropriate to begin a proof by assum-
ing the negation of one or more of the hypotheses.
PROOF BY CONTRADICTION
This method of proof is based on the principle "if the negation of a state-
ment leads to a logical impossibility, the statement must be true." Actually,
proof by contradiction has already been employed at two earlier stages of
the text. The more recent was in the preceding section; proof by contra-
positive can be viewed as a special instance of proof by contradiction. In
a proof by contrapositive that p implies q, we have p as a hypothesis and
assume - q. If we can derive - p from - q, we then have p A -- p, a contra-
diction. An earlier instance of proof by contradiction occurred in Article
4.1 (Example 1 I), in connection with proofs that a given set equals the
empty set. Here is another example in this category.EXAMPLE 8 Prove that if A and B are sets such that (B n A') u (B' n A) =
B, then A = (a. [Recall Exercise 3(f), Article 5.1. How is that result
related to the one just stated?]
Solution Assume A # a, so that there exists x such that x E A. We will
try to arrive at a contradiction. Clearly we must find some way to
involve the set B in the argument; indeed, if the existence of this element
x is going to lead to a contradiction, we will have to find some way to
relate x to B. Now what can we say about this relationship? Do we
know x E B, for example? No, we do not; nor do we know that x 4 B.
What we do know is that either x E B or x 4 B (i.e., x E B'). Let us divide
the argument into cases according to those two possibilities:
Case I: If x E B, then either x E B n A' or x E B' n A, by the equation
B = (B n A') u (B' n A). But x 4 B' n A, since x # B', so x E B n A',
which means x E A'. Since x E A, we have the contradiction x E
A n A' = 0.
Case ll: If x E B', then since x E A, we have x E B' n A. Since B' n A s
(B' n A) u (B n A') = B, then x E B. Thus we have x E B n B' = 0,
again a contradiction.
Since both cases lead to a contradiction, and since these two cases
are clearly exhaustive, our assumption A # 0 must be false. We may
conclude A = 0, as desired.