Bridge to Abstract Mathematics: Mathematical Proof and Structures

5.3 PROOF BY SPECIALIZATION AND DIVISION INTO CASES 173

situations), may work to our advantage. Other situations will be demon-

strated in subsequent examples.

In order to use "division into cases" correctly, we must keep two key

ideas in mind. The first involves the terms "mutually exclusive" and

"exhaustive." The former means that categories are nonoverlapping; no

specific example falls into more than one category. The latter term means

that categories include all possibilities; each specific example falls into at

least one category. The cases in an argument in which the technique under

discussion is employed must be exhaustive; often, but not always, cases are

mutually exclusive. Thus in dealing with real numbers, we find that the

division into rational and irrational is a valid approach, but the division

into positive and negative is inadequate, failing to be exhaustive (zero is

left out). A division into nonpositive and nonnegative, being overlapping

or not mutually exclusive (since zero occurs twice), may lead to difficulties.

The second key idea is that if an argument is going to be divided into cases,

something should be gained in the proof through such a division. The

argument leading to the desired conclusion under Case I should be different

from that under Case I1 and all other cases. In particular, the argument

within each case should contain statements that are valid for that case only.

Indeed, any two cases for which the arguments are identical should be

combined into a single case.

We demonstrate some of these ideas by considering the problem pre-

sented at the beginning of this article, under Example 2.

Solution to Example 2 Recall we have been given sets A, B, and X satisfying

A n X c B n X and A n X' G B n X'. In order to prove A E B, our

desired conclusion, we began, in the discussion following Example 2, by

letting x be an arbitrary element of A. We must prove that x E B; our

difficulty is in determining how to make use of the given hypotheses

and, in particular, how to involve the third set X in the argument. The

key is to recall the elementary theorems of set theory, X u X' = U and

X n X' = 0. Our chosen element x is either in X or in X' and may

not be in both X and X'. Since we have no way of knowing whether

x E X or x E X', we consider both instances, in the hope that, within

each case, we can derive the desired conclusion.

Case I: If x E-X, then since x E A, we have x E A n X. But A n X

s B n X, thus since x E A n X, we may conclude x E B n X.

Since B n X r B, this leads directly to the desired conclusion x E B.

Case 11: If XEX', then XE A n X'. Since A n X's B n X', then XE

B n XI, so that x E B, again as desired.

Note that the argument under each case concluded with the desired result

x E B. Note also that the arguments given under the two cases differed in

an essential way; Case I used one hypothesis exclusively whereas Case I1

h