206 METHODS OF MATHEMATICAL PROOF, PART II Chapter 6
Note that we do not need to repeat the argument just given with the
roles of x and y reversed; that is, we do not need to prove also that if xy =
0 and y # 0, then x = 0. In deriving a conclusion q v r from p, we may
assume the negation of whichever of q or r is more convenient, and try to
derive the remaining one. Doing it both ways is n-@ necessary.
The preceding method may be convenient for proofs of set inclusion, in
which we are trying to prove that a set A is a subset of the union of two
sets X and Y. In this situation our desired conclusion has the form "either
x E X or x E Y."
EXAMPLE 2 Prove that if A, B, and C are sets, then (A u B) n C G
A u (B n C) [recall Exercise 4(a), Article 5.31.Solution Proceeding by the choose method, let x be an arbitrary element
of (A u B) n C. To show x E A u (B n C), we must prove that either
x E A or x E B n C. Suppose x 4 A. Our theorem will be proved if we
can show that x E B n C, that is, x E B and x E C. Since our "new" con-
clusion involves only conjunction, we may derive it by proving its two-
component statements, one at a time. To show x E C, we note simply
that since x E (A u B) n C (by assumption), then x E C. So the real
problem, and the place where we presumably will have to use our sup-
position x $ A, must be in proving x E B. Now since x E (A u B) n C,
then x E A u B; that is, either x E A or x E B. But, by our supposition,
we know x 4 A. Hence we must have x E B, as desired.Note that the tautology [(p v q) A --p] -* q [Theorem 2(k), Article 2.31
was used implicitly in the second sentence from the end of the solution to
Example 2. We will see further examples of use of the indirect technique
of deriving a conclusion involving disjunction later in the text.
PROOF BY CONTRAPOSITIVE
In Articles 5.2 and 5.3 we considered the problem of deriving a conclusion
of the form (Vx)(p(x) -+ q(x)) from a given set of hypotheses. You will re-
call our guiding rule of focusing first on that conclusion and setting up the
proof, by using the choose method, letting x be an arbitrary object for
which p(x) is true. The goal then is to prove that q(x) is true for this x,
where the hypotheses are incorporated into the proof after the initial setting-
up is completed.
One of the situations we wish to consider, as we study proof by contra-
position, is a "mirror image" of the one just described. Suppose the hypo-
thegs of our conjecture has the logical form (Vx)(p(x) -* q(x)). Suppose, in
addition, that our desired conclusion is a simple statement. This situation
can be difficult, if not impossible, to deal with by direct methods.