Bridge to Abstract Mathematics: Mathematical Proof and Structures

1 ELEMENTARY APPLICATIONS OF LOGIC Chapter 4

EXAMPLE 9 Given sets A and B, prove that A n B = A if and only if A E B.

Solution Using the tautology, (p * q) * [(p + q) A (q + p)] [Theorem

l(m), Article 2.31, we approach this proof, as we will most proofs of "iff"

statements, by splitting the proof of a biconditional into two separate

proofs of conditionals. That is, we will prove:

1. IfAnB=A,thenAcB.


2. If A c B, then A n B = A.
   Note that (2), in turn, is a proof of set equality that will, in its own right,
   require a proof of containment each of two directions.
   Proof of (I): To prove A G B, let x E A be given. We must prove
   x E B. Since x E A and A = A n B, then x E A n B. Since A n B c B,
   by Example 4, we conclude x E B, as desired.
   Proof of (2): To prove A n B = A, we must prove that A n B E A
   and A r A n B. The first of these was proved earlier, in Example 4, so
   we are left with only A G A n B to be derived from the hypothesis A c B.
   To prove A c A n B, let x E A. To show x E A n B, we must prove
   x E A and x E B. Since we already know x E A, this amounts to proving
   x E B. But since x E A and A E B, we have x E B, completing the proof.
   0

Sometimes the proof of an iff statement can be carried through by using

a string of valid biconditional statements, thereby eliminating the need to

write two distinct proofs, as we did in Example 9. An example of this type

of proof follows.

EXAMPLE 10 Prove that, for any sets A, B, and C, A n (B u C) =
(A n B) u (A n C) [Fact 4(27), Article 1.4-"intersection distributes over
union'7.
Solution Rather than proving mutual inclusion, we note that, for any object
x, we have:
XEA~(BUC)(XEA)A(XEBUC)
(XE A)A[(x E B)v(x E C)1

• [(x E A)A(x E B)] v [(x E A)A(x E C)1
  -(x~An B)v(xEAnC)
  -xE(AnB)u(AnC)
  The third step uses the tautology p A (q v r) * (p A q) v (p A r). Supply
  justifications for the remaining steps. 0

PROOFS INVOLVING THE EMPTY SET

Among the proofs we have seen thus far, the only one for which the choose

method cannot be employed, and that therefore depends entirely on the

logical structure of the formal definition of A E B, is the proof that the