5.S: Set Theory (Summary)

Important Definitions

• Equal sets, page 55
• Subset, page 55
• Proper subset, page 218
• Power set, page 222
• Cardinality of a finite set, page 223
• Intersection of two sets, page 216
• Union of two sets, page 216
• Set difference, page 216
• Complement of a set, page 216
• Disjoint sets, page 236
• Cartesian product of two sets, pages 256
• Ordered pair, page 256
• Union over a family of sets, page 265
• Intersection over a family of sets, page 265
• Indexing set, page 268
• Indexed family of sets, page 268
• Union over an indexed family of sets, page 269
• Intersection over an indexed family of sets, page 269
• Pairwise disjoint family of sets, page 272

Important Theorems and Results about Sets

• Theorem 5.5. Let $n$ be a nonnegative integer and let $A$ be a subset of some universal set. If $A$ is a finite set with $n$ elements, then $A$ has $2^n$ subsets. That is, if $|A| = n$, then $|\mathcal{P}(A)| = 2^n$.
• Theorem 5.18. Let $A$, $B$, and $C$ be subsets of some universal set $U$. Then all of the following equalities hold.
  
  Properties of the Empty Set $A \cap \emptyset = \emptyset$ $A \cap U = A$
  and the Universal Set $A \cup \emptyset = A$ $A \cup U = U$
  
  Idempotent Laws $A \cap A = A$ $A \cup A = A$
  
  Commutative Laws. $A \cap B = B \cap A$ $A \cup B = B \cup A$
  
  Associative Laws $(A \cap B) \cap C = A \cap (B \cap C)$
  $(A \cup B) \cup C = A \cup (B \cup C)$
  
  Distributive Laws $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
  $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
• Theorem 5.20. Let $A$ and $B$ be subsets of some universal set $U$. Then the following are true:
  $$\begin{array} {ll} {\text{Basic Properties}} & & {(A^c)^c = A} \\ {} & & {A - B = A \cap B^c} \\ {\text{Empty Set, Universal Set}\ \ \ \ \ \ \ \ \ \ \ \ \ } & & {A - \emptyset = A \text{ and } A - U = \emptyset} \\ {} & & {\emptyset ^c = U \text{ and } U^c = \emptyset} \\ {\text{De Morgan's Laws}} & & {(A \cap B)^c = A^c \cup B^c} \\ {} & & {(A \cup B)^c = A^c \cap B^c} \\ {\text{Subsets and Complements}} & & {A \subseteq B \text{ if and only if } B^c \subseteq A^c.} \end{array}$$
• Theorem 5.25. Let $A$, $B$, and $C$ be sets. Then
  
  1. $A \times (B \cap C) = (A \times B) \cap (A \times C)$
  2. $A \times (B \cup C) = (A \times B) \cup (A \times C)$
  3. $(A \cap B) \times C = (A \times C) \cap (B \times C)$
  4. $(A \cup B) \times C = (A \times C) \cup (B \times C)$
  5. $A \times (B - C) = (A \times B) - (A \times C)$
  6. $(A - B) \times C = (A \times C) - (B \times C)$
  7. If $T \subseteq A$, then $T \times B \subseteq A \times B$.
  8. If $T \subseteq B$, then $A \times Y \subseteq A \times B$.
• Theorem 5.30. Let $\Lambda$ be a nonempty indexing set and let $\mathcal{A} = \{A_{\alpha}\ |\ \alpha \in \Lambda\}$ be an indexed family of sets. Then
  
  1. For each $\beta \in \Lambda$, $\bigcap_{\alpha \in \Lambda}^{} A_{\alpha} \subseteq A_{\beta}$.
  2. For each $\beta \in \Lambda$, $A_{\beta} \subseteq \bigcap_{\alpha \in \Lambda}^{} A_{\alpha}$.
  3. $(\bigcap_{\alpha \in \Lambda}^{} A_{\alpha})^c = \bigcup_{\alpha \in \Lambda}^{} A_{\alpha} ^c$
  4. $(\bigcup_{\alpha \in \Lambda}^{} A_{\alpha})^c = \bigcap_{\alpha \in \Lambda}^{} A_{\alpha} ^c$
  
  Parts(3) and (4) are known as De Morgan's Laws.
• Theorem 5.31. Let $\Lambda$ be a nonempty indexing set, let $\mathcal{A} = \{A_{\alpha}\ |\ \alpha \in \Lambda\}$ be an indexed family of sets, and let $B$ be a set. Then
  
  1. $B \cap (\bigcup_{\alpha \in \Lambda}^{} A_{\alpha}) = \bigcup_{\alpha \in \Lambda}^{} (B \cap A_{\alpha})$, and
  2. $B \cup (\bigcap_{\alpha \in \Lambda}^{} A_{\alpha}) = \bigcap_{\alpha \in \Lambda}^{} (B \cup A_{\alpha})$,

Important Proof Method

The Choose-an-Element Method
The choose-an-element method is frequently used when we encounter a universal quantifier in a statement in the backward process of a proof. This statement often has the form

For each element with a given property, something happens.

In the forward process of the proof, we then we choose an arbitrary element with the given property.

Whenever we choose an arbitrary element with a given property, we are not selecting a specific element. Rather, the only thing we can assume about the element is the given property.

For more information, see page 232.