Bridge to Abstract Mathematics: Mathematical Proof and Structures

42 SETS Chapter 1

FACT 8

The following statements of equivalence, that is, involving "if and only if," can

be proved to be theorems of set theory. For all sets X and Y in any universal

set U:

53. X c Y if and only if Y' c X'


54. X s Y if and only if X u Y = Y


55. X E Y if and only if X n Y = X


56. X c Y if and only if X - Y = 0
    57. X G Y if and only if X n Y' = (21
    58. X G Y if and only if X' u Y = U

FACT 9

The following statements of implication, that is, involving "if... then," can be

proved to be theorems of set theory. For all sets X, Y, and Z in any universal

set U:

59. If X G Y and X c Z, then X G Y n Z


60. If X G Z and Y c Z, then X u Y G Z


61. If X G Y, then Y = X u (Y - X)


62. If Xc Z, then Xu (Y n Z) = (Xu Y) n Z


63. If Xn Y=XnZand Xu Y=XuZ, then Y=Z


64. If Xn Y=XnZand X'n Y=X'nZ, then Y=Z


65. If Xu Y=XuZand X'u Y=X'uZ, then Y=Z


66. If X n Y = 0, then X A Y = X u Y


67. If X x Y = X x Z and X # 0, then Y = Z


68. If X x Y = Y x X, X # fa, and Y # 0, then X = Y


69. If Y x Z = 0, then Y = 0 or Z = (21

Exercise

Compare the list of possible theorems of set theory compiled in Exercise 1, Article
1.3, with the theorems stated in Article 1.4.
--_

1.5 Counting Properties of Finite Sets (Optional)

At various stages of an introduction to advanced mathematics, it is impor-

tant to be acquainted with both certain formulas for counting the number

of elements in finite sets and methods of proof known as counting arguments.

The latter are important, for example, in abstract algebra, with the proof

of the famous theorem of Lagrange from group theory a case in point.

The material in this article may be familiar to readers who have studied

elementary probability.