$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 5.S: Set Theory (Summary)

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

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.  