Bridge to Abstract Mathematics: Mathematical Proof and Structures

4.1 APPLICATIONS OF LOGIC TO SET THEORY--SOME PROOFS 119

In addition to its basic structure, involving the choose method, the other
important aspect of the proof in Example 7 is the conclusion "x E B from
the statements "x E A" and "A E B." The validity of this step follows ulti-
mately from the logical principle modus ponens, [p A (p + q)] + q [Theo-.
rem 2(e), Article 2.31. Given that x E A is true and that the statement
(Vy)[(y E A) -+ (y E B)] is true, from which we may conclude that the state-
ment (x E A) + (x E B) is true for the given x, we have (x E A) A ((x E A) +
(x E B)), and hence, by modus ponens, the conclusion x E B.
One final remark on Example 7: This is the first theorem we've proved
in which a conclusion of set containment (i.e., A E C) is preceded by some
hypotheses (namely, A c B and B c C). An important rule of procedure
in setting up a proof in such a situation is at the start of the proof to focus
on the desired conclusion, rather than on the hypotheses. The starting point
of our proof was to pick an arbitrary element of A, with the stated hope
of proving that it is also an element of C. The motivation for beginning
the proof in this manner was solely the form of the conclusion of the theo-
rem. The hypotheses are brought into play only in the course of the proof.
This principle will be discussed and demonstrated in much more detail in
Article 5.2.

PROVING SET EQUALITY

Combining the elementhood method of proving set inclusion with the result

of Example 3, we see that a basic way to approach a proof of set equality

is to prove mutual inclusion. This procedure involves two distinct proofs,

one of containment in each direction.

EXAMPLE 8 Assuming the theorem "for all real numbers x and y, if xy = 0,

then x = 0 or y = 0," prove that the set A = 15, -7) equals the set

B = {x E R(x2 + 2x - 35 = 0).

Solution To prove A = B, we prove mutual inclusion; that is, we prove

A G B and B G A. We approach each of these proofs, in turn, by the

choose method.

(a) To prove A G B, let a E A be given. To prove a E B, we must

prove that a is a real number satisfying a2 + 2a - 35 = 0. Now since

a~ A,theneithera=5ora= -7. Ifa=5,thena~~anda~+2a-35=

(5)2 + (2)(5) - 35 = 25 + 10 - 35 = 0, as required. On the other hand,

if a= -7, then again a E R and ~~+2~-35=(-7)~+(2)(-7)-35=0.

In either case we have a E B, as desired.

(b) Conversely, to prove B c A, suppose x E B, so that x is a real

number satisfying x2 + 2x - 35 = 0. But then, 0 = x2 + 2x - 35 =

(x - 5)(x + 7) so that, by the assumed theorem, either x = 5 or x = - 7.

Thus x E (5,7) = A, as desired. 0

In part (a) of the proof in Example 8 we used the technique of division

of an argument into cases. We will elaborate on this important proof

writing technique in Article 5.3.