234
Sets, Combinatorics, and Probability
■
PraCtiCe 18 Prove identity 4a.
Basic set identities
1a. A c B = B c A
1b. A d B = B d A
(commutative
properties)
2a. (A c B) c C = A c (B c C  )
2b. (A d B) d C = A d (B d C  )
(associative
properties)
3a. A c (B d C  ) = (A c B) d (A c C  )
3b. A d (B c C  ) = (A d B) c (A d C  )
(distributive
properties)
4a. A c [ = A
4b. A d S = A
(identity
properties)
5a. A c A′= S
5b. A d A′= [
(complement
properties)
(Note that 2a allows us to write A c B c C with no need for parentheses; 2b allows
us to write A d B d C.)
example 19
Let’s prove identity 3a. We might draw Venn diagrams for each side of the equation and see that they look the same. However, identity 3a is supposed to hold for
all subsets A, B, and C, and whatever one picture we draw cannot be completely
general. Thus, if we draw A and B disjoint, that’s a special case, but if we draw A
and B not disjoint, that doesn’t take care of the case where A and B are disjoint.
To do a proof by Venn diagrams requires a picture for each possible case, and the
more sets involved (A, B, and C in this problem), the more cases there are. To avoid
drawing a picture for each case, let’s prove set equality by proving set inclusion in
each direction. Thus, we want to prove
A c (B d C  ) # (A c B) d (A c C  )
and also
(A c B) d (A c C  ) # A c (B d C  )
To show that A c (B d C  ) # (A c B) d (A c C  ), we let x be an arbitrary member
of A c (B d C  ). Then we can proceed as follows:
x [ A c (B d C  ) S x [ A or x [ (B d C  )
S x [ A or (x [ B and x [ C  )
S (x [ A or x [ B) and (x [ A or x [ C  )
S x [ (A c B) and x [ (A c C  )
S x [ (A c B) d (A c C  )
To show that (A c B) d (A c C  ) # A c (B d C  ), we reverse the above argument.