22 CHAPTER 1 Sets, Proof Templates, and Induction
Proof. (a) Show that (i) A _ A and (ii) A C A. To prove (i), suppose x E A. Then, x E U
and x € A. But, then x E A. To prove (ii), suppose x e A. Then, x G U, but x € A. So,
X E A.
(b) (•) Show that if A C B, then B C A. Prove the result by contradiction (see Template
1.3). Assume that for some subsets A and B of U, A C B and B 7 A, and derive a con-
tradiction. Since B 7 A, there is some x E B - A. Pick such an x. Since x 0 A, it follows
that x e A. Since A C B, we have x e B. But, it was assumed that x E B; hence, x has the
property that x 0 B. Since both x c B and x g B were proved, this gives a contradiction.
(.@) The proof is analogous to the proof of (•:) using (a).
(c) Exercise 11 in Section 1.4. UA Computer Representation for Sets
Let U = {1, 2, 3, 4, 5, 6} be a set, and let X C U. A bit representation for X is a six-digit
binary number x1x2x3x4x5x6 with bit xi for 1 < i < 6 defined as
10f if ( X
0 for i 0 XFor example, if B = (2, 3, 61, then B = 011001. The operations of union, intersection,
and complement can be carried out using operators UNION, INTER, DIFF, and COMPthat operate on binary numbers bit-by-bit. Let B, C c U with B = blb 2 b 3 b 4 b 5 b 6 and C =
c1c2c3c4c5C6. Define the union as UNION(B, C) = xix2x3x4x5x6 where for 1 < i < 6,1 if bi = I or ci = I
xi 0 otherwiseDefine the intersection as INTER(B, C) = X1X2X3X4X5X6, where for 1 < i < 6,1 ifbi = 1 and ci = 1
xi 0 otherwiseDefine the complement as COMP(B) =- XX2X3X4X5X6, where for 1 < i < 6,1 ifbi=0
Xi (^0) otherwise
Define the relative difference as DIFF(B, C) = X1X2X3X4X5X6, where for 1 < i < 6,
1 if bi = 1 Iand ci = 0
xi 0 otherwise
Example 6. Let B = {1, 2, 3, 4, 51 and C = {3, 4, 5, 6, 7, 81 be subsets of the universal
set U = [1, 2,..., 9). Find UNION(B, C), INTER(B, C), COMP(C), and DIFF(B, C).
Solution. BUC={1,2,3,4,5,6,7,8}. BfnC={3,4,51. C={1,2,9). B-C=
11, 21. Therefore,UNION(B, C) = 111111110
INTER(B, C) = 001110000
COMP(C) = 110000001DIFF(B, C) = (^110000000) U