Bridge to Abstract Mathematics: Mathematical Proof and Structures

40 SETS Chapter 1

"conjectures." You should already have conjectured, based on earlier ex-
ercises, a large number of potential theorems. See which of your conjec-
tures are included in the following lists.

FACT 1

The following basic laws of set equality or of subsets can be proved to be theo-

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

1. X=X (reflexive property of equality)


2. XrX (reflexive property of
   the subset relation)


3. If X = Y, then Y = X (symmetric property of equality)


4. X = Y if and only if X c Y and Y G X (includes antisymmetric
   property of subset)


5. If X = Y and Y = Z, then X = Z (transitive property of equality)


6. If X E Y and Y c Z, then X E Z (transitive property of
   the subset relation)


7. 0cx


8. XcW

FACT 2

The following basic properties for union and intersection can be proved to be

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

9. XuX=X


10. XnX=X


11. Xu@=X


12. Xn U=X


13. Xn@=@


14. XuU=U


15. XuY=YuX


16. XnY=YnX


17. Xu(YuZ)=(XuY)uZ


18. Xn(YnZ)=(XnY)nZ


19. XcXu Y


20. Xn YGX

FACT 3

(idempotent law for union)

(idempotent law for intersection)

(identity for union)

(identity for intersection)

(commutative law for union)

(commutative law for intersection)

(asso$iative law for union)

(associative law for intersectiorl)

The following basic properties for set complement can be proved to be theorems

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

21. X" = X (law of double complementation)


22. XU X' = U


23. Xn X'= @
    24. V=@


24. a'= U