6.2 INDIRECT PROOFS 205break up the proof into n separate derivations, each of which establishes
one of the components q,, that is, we derive each component of the con-
clusion separately [see Exercise 3(c)]. No such luxury is generally available
when disjunction is involved in the conclusion, since the hypothesis usually
does not need to imply any components of the conclusion, taken individually.
(Note: Exercise 4 illustrates an exception to this statement.) A simple exam-
ple of this difficulty occurs in the following theorem about real numbers:
EXAMPLE 1 Assume it is known that multiplication of real numbers is asso-
ciative, that nonzero real numbers have multiplicative inverses, and that
a -0 = 0 for any real number a. Prove that if x and y are real numbers
with xy = 0, then x = 0 or y = 0.
Discussion Our theorem involves one simple hypothesis and a conclusion
involving the disjunction of two statements. Approaching the proof di-
rectly, we seem to have no way of getting at the desired conclusion. In
particular, neither specialization nor division into cases, the two methods
of adapting a hypothesis toward a desired conclusion that we studied
in Article 5.3, appears applicable here. We will return to this problem
shortly.
A more or less standard approach to problems of the type presented in
Example 1 is to take advantage of a generalization of Theorem l(p), Article
2.3. You may verify that, for any positive integer n, the statement form
[P + (41 vq2vS. .vqn)] ++ [(PA -ql A -q2Aa. .A mqn-1) --t qn]
is a tautology. We may approach the derivation of q, v q, v.. v q, from
p by assuming as true the negation of all but one (any one) of the com-
ponents of the conclusion, and then trying, on the basis of these additional
assumptions, to prove that the one remaining component must be true.
This approach has a dual advantage: (1) to replace a logically complicated
desired conclusion by a relatively simple one and (2) to give us one or
more additional hypotheses. Let us now return to Example 1.Solution to Example 1 This specific problem was alluded to in Article 2.1,
where we suggested the approach to be carried out now. To derive the
conclusion "either x = 0 or y = 0" from the hypothesis "xy = 0," we
begin by assuming x # 0. We will try to use the hypothesis xy = 0 and
the supposition x # 0 to prove that y = 0. If we can do this, our proof
is complete, according to the tautology quoted earlier. What is the sig-
nificance of a nonzero value for x? One fact that is true about a nonzero
real number x but is not true about zero is that the multiplicative inverse
(i.e., reciprocal) x-I exists. Note that, on the one hand, x-'(xy) =
x- '(0) = 0. On the other hand, however, x- '(xy) = (x- lx)y = 1. y = y.
Combining these two strings of equations into a single string, we have a
proof by transitivity, y = 1. y = (x- lx)y = x- '(xy) = x- '(0) = 0, of the
desired conclusion y = 0. 0