Math 224

Foundations of Mathematics

Dr. McLoughlin
Handout 9

§ 3.3 Algebra of Sets & Laws to Memorise After You Have Proven Them

Let U designate a well defined universe and A, B, and C sets within the universe. We shall denote the complement of the set A as A^C or as A¢

Law of the double complement      (A^C)^C = A

Note: recall from logic: (Ø (Ø P)   º  P ).  The student should verify these laws have corresponding laws of logic.

Lemma E:  "  set A Í U ,  ( Æ Í A )

Contrapositive form of subset      A Í  B   º  B' Í  A'   º  A'  Ê   B'

De Morgan Law (1)                          A'  Ç  B'   º   (A  È  B)'
De Morgan Law (2)                          A'  È  B'  Û (A  Ç  B)'

Law of the Excluded Middle (1)             x Î A Ç  A^C º always false
Law of the Excluded Middle (2)             x Î A È  A^C º always true
Law of the Excluded Middle (3)             A Ç A^C    = Æ
Law of the Excluded Middle (4)             A È  A^C    = U

Commutative Law  of  "or"  (1)        A  È  B  =    B  È A
Commutative Law  of  "and" (2)       A  Ç  B  =    B  Ç A

Associative Law  of  "or"  (1)           A  È  (B  È  C)   =  (A  È  B)  È C  =  A  È  B  È C
Associative Law  of  "and" (2)         (A  Ç  B)  Ç C =  (A  Ç  B)  Ç C =  (A  Ç  B)  Ç C

Distributive Law of "and over or" (1)      A  Ç  (B  È  C)   =  (A  Ç  B)  È  (A  Ç C)
Distributive Law of "or over and" (2)       A  È  (B  Ç  C)  =  (A  È  B)  Ç  (A  È C)

Idempotent Law (1)                                 A  È  A  = A
Idempotent Law (2)                                 A  Ç  A  =  A

Identity Law (1)                                  A  È U  = U
Identity Law (2)                                  A  Ç Æ   =  Æ
Identity Law (3)                                  A  Ç U  = A
Identity Law (4)                                  A  È Æ   =  A

Complement Law (1)                                                  U^C  = Æ
Complement Law (2)                                                 Æ^C   =  U

The Illustration of the Laws of Logic Applied to Set Theory:

Law of Addition                                     x Î A   Þ  x Î (A È  B)

Law of Simplification                              x Î A Ç B  Þ  x Î A

Modus Ponens                                      x Î A  Ù   A Í  B     Þ  x Î B

Modus Tollens                                     x Ï B Ù   A Í  B     Þ  x Ï A

Disjunctive Syllogism                             (x Î (A  È  B) ) Ù  ( x Ï B) Þ  x Î A

Hypothetical Syllogism                          A Í  B   Ù   B Í  C    Þ A Í  C
(Transitivity)

Statement:                                                        It’s Negation:

"  x Î U ,  (x Î A   Þ  x Î B)                   $  x Î U ,  (x Î A   Ù    x Ï B)

$  x Î U ,  (x Î A   Þ  x Î B)                 "  x Î U ,  (x Î A   Ù    x Ï B)

A Í  B                                                             A   B (NOT A Ë B which is too strong)

Page 100 of Barnier and Feldman:    S14 and S15 are wrong! Please correct them.

© 1995 - 2011. M. P. M. M. McLoughlin.