Let all sets referred to below be subsets of a universal set U.

1. Union with Æ (Æ acts as an identity for U): For all sets A,
   A È Æ = A.
2. Intersection and union with the complement: For all sets A,
   a) A Ç A^c = Æ and b) A È A^c = U.
3. Intersection with Æ (Æ acts as the universal bound for Ç ): For all sets A,
   A Ç Æ = Æ .
4. Complement of U and Æ :
   a) U^c = Æ and b) Æ ^c = U.

Example 5.3.3 p. 261
Use the set properties, Theorems. 5.2.1-3 and 5.3.3 to prove that for all sets A and B,

A-(A Ç B) = A-B

Proof: Suppose A and B are sets. Then

For computer programming it is beneficial to divide sets up into nonoverlapping (or disjoint) pieces called partitions.

Definition: Two sets are disjoint iff they have no elements in common.
Symbolically: A and B are disjoint « A Ç B = Æ .

Definition: A collection of nonempty sets {A₁, A₂,... , A_n} is a partition of a set A iff:

1. A = A₁ È A₂ È ... È A_n;
2. A₁, A₂,..., A_n are mutually disjoint (have no elements in common).

Example
Let Z be the set of all integers
Let T₀ = {n Î Z | n = 4k for some integer k}
Let T₁ = {n Î Z | n = 4k + 1 for some integer k}
Let T₂ = {n Î Z | n = 4k + 2 for some integer k}
Let T₃ = {n Î Z | n = 4k + 3 for some integer k}
Is {T₀, T₁, T₂, T₃} a partition of Z?
Answer

Sometimes we want to consider the set of all subsets of a particular set. The power set axiom guarantees that this is a set.

Definition: Given a set A, the power set P(A) is the set of all subsets of A.

Example Find the power set of the set {x, y, z}. What is the cardinality of P({x, y, z})? Answer

Theorem 5.3.5 For all sets A and B, if A Í B then P(A) Í P(B).
Proof is based on the transitive property for subsets Theorem 5.2.1 #3.
Proof: Suppose A and B are sets such that A Í B. [We must show that P(A) Í P(B).] Suppose X Î P(A). [We must show X Î P(B).] Since X Î P(A), X Í A by definition of power set. But A Í B. Hence X Í B by the transitive property for subsets. It follows that X Î P(B) by definition of power set [as was to be shown.] Thus P(A) Í P(B) by definition of subset.

Theorem 5.3.6 If a set has n elements, then its power set has 2ⁿ elements.
Proof (MI): Proposition: If a set has n elements, then its power set has 2ⁿ elements.

The only set with zero elements is Æ and the only subset of Æ is Æ itself, thus when n = 0 there is 2⁰ = 1 subset. Thus the proposition is true for n = 0 elements.
Observe that:

1. The subsets X can be split into two groups: those that do not contain z and those that do contain z.
2. The subsets that do not contain z are the same as the subsets of X-{z}.
3. There is a one-to-one mapping from the subsets that do not contain z to the subsets that do contain z. For each subset A that does not contain z match it to the subset A È {z} that contains z. Thus there are as many subsets X that contain z as there are subsets that do not contain z.

Now suppose any set with k elements has 2^k subsets [inductive hypothesis]. We must show that a set with k + 1 elements has 2^k + 1 subsets. By the preceding argument, adding z to the set X-{z} gives us twice the number of subsets as was in X-{z}. So the number of subsets of X = 2× |X-{z}| = 2× 2^k = 2^k + 1.//

Come prepared to go over 5.3 #21-28 &35 next class. Row 1 #27, row 2 #22, row 3 #28, row 4 #24, row 5 #25, row 6 # 26.