616 Appendix B • Sets and Functions(g) (Au B)c = N n B C. (de Morgan's law)
(h) (An B)c = Ac u BC. (de Morgan's law)(j) uc = 0; and 0c = U.
(k) B-A=BnN.
(1) NC= A.
(m) Au (Bu C) =(Au B) u C. (associative law for u)
(n) An (B n C) =(An B) n C. (associative law for n)
(o) An (BU C) =(An B) u (An C). (distributive law)
(p) AU (B n C) =(AU B) n (Au C). (distributive law)
Proof of (g):
Part 1: Suppose x E (AU B)c. Then x EU but x i AU B. Then it is not
true that x EA or x EB. By de Morgan's rule in logic, this means xi A and
x i B. That is, x E A c and x E BC; i.e., x E Ac n Be. Therefore, by B.1.6,
(AUB)c~AcnBc.
Part 2: Suppose x E Ac n Be. Then x E A c and x E BC; i.e., x i A and
x i B. By de Morgan's rule in logic, this means it is not true that x E A or
x E B. Then x EU but x i AU B ; i.e., x E (AU By. Therefore, by B.1.6,
AcnBc ~ (AUB)c.
By Parts 1 and 2, together with Part (a), (AU B)c =Ac n Be.Proof of (o):
Part 1: Suppose x E An (BUG). Then x EA and x E BUC. Then x EA
and (x E B or x E C). By the distributive law in logic (Theorem A.1.23, (a))
this means (x EA and x EB) or (x EA and x E C). That is, x EA n B or
x E An C. Thus, x E (An B) U (An C).
Part 2: Exercise 5. •While the above theorem summarizes the algebra of sets when only several
sets are involved, we need algebraic rules to cover situations in which many,
even infinitely many, sets are involved. The following definition and theorem
cover these situations.