Bridge to Abstract Mathematics: Mathematical Proof and Structures

1.4 THEOREMS OF SET THEORY 41

FACT 4
The following distributive laws can be proved to be theorems of set theory. For
all sets XI Y, and Z in any universal set U:

26. X u (Y n Z) = (X u Y) n (X u Z) (union over intersection)


27. X n (Y u Z) = (X n Y) u (X n Z) (intersection over union)


28. X n (Y A Z) = (X n Y) A (X n z) (intersection over symmetric
    difference)

FACT 5

The following basic properties of set difference can be proved to be theorems

of set theory. For all sets X, Y, and Z in any universal set U:

29. X- Y= Xn Y'


30. X-@=X


31. 0- Y=@


32. XI- Y'= Y - X


33. (X- Y) -Z=(X-Z) -(Y-Z)

FACT 6

The following De Morgan's laws can be proved to be theorems of set theory.

For all sets XI Y, and Z in any universal set U:

34. (X n Y)' = X' u Y'


35. (X u Y)' = X' n Y'


36. X- (Y u Z) = (X- Y) n (X- Z)


37. X-(YnZ)=(X-Y)u(X-Z)

FACT 7
The following miscellaneous statements of equality or a subset relationship can
be proved to be theorems of set theory. For all sets X, Y, and Z in any universal
set U:
X = (X u Y) n (X u Y')
X = (X n Y) u (X n Y')
(X n Y) u (X' n Y) u (X n Y') u (X' n Y') = U
Xu(Y-X)=XuY
(X - Y)' = X' u Y
XAY=YAX (commutativity of symmetric difference)
X A (Y A Z) = (X A Y) A Z (associativity of symmetric difference)
XAX=@
xnu=xl
XA@=X
XA Y= (Xu Y) -(Xn Y)
YxQJ=QJxZ=@
(XuY)xZ=(XxZ)u(YxZ)
(XnY)xZ=(XxZ)n(YxZ)
(X-Y)xZ=(XxZ)-(Yxz)