Bridge to Abstract Mathematics: Mathematical Proof and Structures

6.2 INDIRECT PROOFS 207

EXAMPLE 3 Prove that if a linear function y = f (x) = Mx + B is increasing
on R, then M > 0.

Discussion You may recall the proof of the converse of this result from

Example 7, Article 5.2; a simple direct proof by the choose method suf-

ficed. In this case, however, the hypothesis has the form

whereas the conclusion is the simple statement M > 0. Since the con-

clusion is a simple statement (involving no quantifiers or connectives),

the only direct method applicable to deriving it is proof by transitivity.

But since the hypothesis is an "if... then" statement and so requires

the assumption xl < x, in order to "activate" its conclusion, it may not

be evident how to incorporate that hypothesis into such an argument.

Solution to Example 3 Because of the difficulty just described, we will give
a proof by contrapositive. Suppose M < 0. Let x, = 3 and x, = 5 and
note that x, < x,. But since M 10, then Mx, = 3M 2 5M = Mx,, so
that 3M + B 2 5M + B, and thus f(3) 2 f(5). We have proved the exis-
tence of real numbers x, and x, with x, < x,, but f (x,) 2 f (x,), thus
proving the negation of the original hypothesis.

EXAMPLE 4 Suppose that a set A (from a universal set U) has the property
that A c B for all B E U. Prove that A = @.

Solution Note again the simple logical form of the conclusion, compared
to the hypothesis which like the hypothesis in Example 3, involves both
the universal quantifier and implication arrow, the latter as part of the
definition of "subset." We will proceed by contraposition and begin by
assuming A # @. To contradict the hypothesis, we must prove that
there exists a set B E 9(U) such that A $ B. We take B = 0 and note
that since A # @, there exists an element x in A. Since B = @, then
x 4 B. Hence A $ B, as desired.

Proof by contrapositive can be useful in deriving results whose hypo-
thesis, although not necessarily of the form (Vx)(p(x) -, &)), is of a more
complicated logical structure than the conclusion.

EXAMPLE 5 Suppose that a is a real number satisfying the property
(Vp > O)(la( < p). Prove that a = 0.

Solution Suppose a # 0. Then flu1 > 0. Letting p = f lal, we note that

clearly p > 0, and also, since 1 > f, then la1 = (l)(lal) > *la1 = that is,

(3p > O)(lal > p) so that we have (3p > O)(lal 2 p), the logical negation of

the hypothesis.