Bridge to Abstract Mathematics: Mathematical Proof and Structures

4.1 APPLICATIONS OF LOGIC TO SET THEORY-SOME PROOFS 12l

empty set is a subset of any set (Example 1). Surely, we cannot begin a
proof that 0 c A by writing "let x E 0." Other theorems from Article 1.4
whose statement involves 0 may require something other than a direct
"containment" or "mutual inclusion" approach as well. In the next example
we consider problems that arise when we must prove that a given set is
empty (i.e., equals the empty set 0).

EXAMPLE 11 Prove that, for any set A, A n A' = (21 [Fact 3(23), Article

1.41.

Solution Seemingly, the straightfonvard way to approach a proof that a

set X equals (ZI is by mutual inclusion, that is, try to prove that 0 c X

and X c 0. But in any such proof the first of these is automatically

true (recall Example 1) and so does not need to be proved again. As

for the second part, can we attack the problem by beginning "Let x E X.

We will prove x E 0... ."? Obviously, the latter conclusion can never

be proved, so that this approach will not work. Instead, we use another

special method of proof, proof by contrudiction (which will be elaborated

on in Article 6.2). To prove that a set X equals 0, we begin by sup

posing that x E X (so that we are effectively assuming that X is non-

empty) and showing that this supposition leads to a contradiction. In

the case at hand, suppose that x E A n A'. Then x E A and x E A' so

that x E A and x $ A. Since the latter statement has logical form p A -p

(a contradiction), the supposition must be false and the desired theorem

thereby true.

U(AMPLE 12 Prove that, for any sets A and B, if A s B, then A n B' = f21

[Fact 8(57), Article 1-41.

Solution Assume A E B. Proceeding as in Example 11, let x E A n B'.

Our goal is to reach a contradiction. Since x E A n B', then the state-

ment (3x)[(x E A) A (x E B')l is true, as is the equivalent statement

(3x)[(x E A) A (x $ B)]. But the latter statement is the logical negation

of (Vx)[(x E A) + (x E B)], which happens to be the definition of A c B.

Hence our assumption "x E A n B"' contradicts the hypothesis A r B,

so we must conclude A n B' = 0, as desired.

Other proofs ihvolving 0, even for theorems not making an assertion

that a given set is empty, can be difficult to write out, and so must be ap

proached carefully.

EXAMPLE 13 Prove that, for any set X, X u 0 = X [Fact 2(I I), Article

1.41.

Solution We will prove that X G X u 0 and X u (21 c X. For the first

one, we note that X E X u Y is known to be true for any two sets X

and Y (recall Example 4). In particular, if Y = 0, we have X c X u 0.