Bridge to Abstract Mathematics: Mathematical Proof and Structures

208 METHODS OF MATHEMATICAL PROOF, PART II Chapter 6

The result in Example 5 is of interest in its own right, since it is an

important tool for proving uniqueness, in connection with limits. We will

employ it in Article 6.3.

In some situations in which a desired conclusion is of the form

(Vx)(p(x) -+ q(x)), the relationship between this conclusion and the hypo-

theses may be such as to make it advantageous to prove the equivalent

form (Vx)(-q(x) -, -p(x)) of the conclusion instead. This situation oc-

curred in Exercise 6(c), Article 5.2, as we now demonstrate.

EXAMPLE 6 Prove that iff is increasing on an interval I, then f is one to

one on I.

Solution By definition of "one to one," we must show that if x, and x, are

real numbers with f(x,) = f(x,), then x, = x,. Our hypothesis that f

is increasing has, however, the reverse format, namely, if x, < x,, then

f(x,) < f(x,). Thus it is easier for us to derive the conclusion by assum-

ing x, # x2 and trying to prove f(x,) # f(x,). A division into cases

presents itself immediately. If x, # x,, then either x, < x,, in which case

f(xJ < f(~2) SO fhatfb,) Z f(x2), or x, > x,, so that f(x1) > f(x2) and

again f (x ,) # f (x,), as desired.

We could also have deduced the result in Example 6 using a full contra-

position argument. That is, assume f is not one to one and prove that f

cannot be increasing. This approach is left for Exercise 5(a).

A very common application of proof by contrapositive arises when a

theorem of the form (p A q) -, r is known, and we are asked to prove the

corresponding statement of the form (p A - r) -+ - q. In fact, the two state-

ment forms are logically equivalent [Exercise 9(a)], so that the latter state-

ment can always be proved. In specific applications a brief and routine

argument by contrapositive is the best approach, as the next example

demonstrates.

EXAMPLE 7 Suppose that a subset C of R x R is symmetric with respect to

the y axis, but not with the origin. Use the result of Exercise 8(a), Article

5.3, to prove that C is symmetric with respect to the x axis.

Solution Suppose C were symmetric with respect to the x axis. By the

cited exercise, since C- is symmetric with respect to both the x axis (by

assumption) and the y axis (by hypothesis), then C is symmetric with

respect to the origin. This establishes the negation of the hypothesis

"but not with the origin" and so proves the theorem.

At the outset of this article, overzealousness in applying indirect methods

of proof was discouraged. Proof by contrapositive is particularly subject

to overuse. The reason for this, perhaps, is that starting a proof is often a

1 difficult step, and the approach "assume the conclusion false" is an easy

(^1) way of at least getting started. But this approach, when used instead of a