Bridge to Abstract Mathematics: Mathematical Proof and Structures

154 METHODS OF MATHEMATICAL PROOF, PART I Chapter 5

1 solution Let x,y, and z be given. Then
Ix - zI = (x + (-y + y) - zl
= I(x - Y) + (Y - z)J
5 IX - yl + ly - z(, as desired.

EXAMPLE 8 Assume the theorem, for any sets A, X, and Y, if X c Y, then

A n X G A n Y. Use this fact, along with an appropriate distributive

property, to prove that, for any three sets A, B, and C,

An(BuC)c(An B)u C

Solution Let A, B, and C be given sets. Then

(A n B) u C = (A u C) n (B u C) (by distributivity)

2An(BuC)

where the latter step follows from the fact that A c A u C and the

theorem assumed in the statement of the example. 0

In the discussion following Example 2 we noted a common pitfall, namely,

trying to prove a universally quantified statement by giving a specific exam-

ple or by enumerating cases. As with all general rules, the principle of prov-

ing statements by a deductive general argument can be carried too far,

being applied where it shouldn't be. In particular, suppose we wish to @&-

prove the assertion that subtraction of real numbers is associative; that is,

a - (b - c) = (a - b) - c for all real numbers a, b, and c. A common, but

logically incorrect approach, is to argue

But recall from Article 3.3 that the negation of a statement (Vx)(p(x)) is

(3x)(-p(x)). That is, to disprove a universally quantified statement, we

must prove that the predicatein question is false for some substitution for

x. Generally, this is best done by producing a specific object a from U for

which p(a) is false; such a specific object is called a counterexample to the

statement (Vx)(p(x)). This is a situation in which proof (or actually disproof)

by example is not only p&-rnissible, but is in fact the correct approach. We

reemphasize: to establish that a universally quantijed predicate is false, display

a counterexample!

In the preceding situation we may, for instance, let a = 7, b = 4, and

c=2. Then a-(b-c)=7-(4-2)=7-2=5 and (a-b)-c=

(7 - 4) - 2 = 3 - 2 = 1. Since 5 # 1, our goal is accomplished.

There is one other situation in which proof by example(s) or by enumerat-

ing cases may be a viable approach to theorem-proving. If the domain of

discourse for a universally quantified predicate happens to be finite, it may