Set Theory

🎯 Learning Objectives

• Define sets using roster and set-builder notation
• Perform set operations: $\cup$, $\cap$, $-$ (difference), $\overline{A}$ (complement)
• Prove set identities using element arguments
• Understand power sets and Cartesian products
• Compare finite and infinite cardinalities

5.1 Intuition: The Building Blocks of Mathematics

🔑 Key Insight: Two sets are equal iff they have exactly the same elements. Order and repetition don't matter.

5.2 Definitions

Basic Notation

• $A = \{1, 2, 3\}$ — roster notation
• $B = \{x \in \mathbb{N} : x > 5\}$ — set-builder notation
• $\emptyset$ — empty set (or $\{\}$)
• $a \in A$ — $a$ is an element of $A$
• $A \subseteq B$ — $A$ is a subset of $B$

Important Sets

• $\mathbb{N} = \{1, 2, 3, \dots\}$ — natural numbers
• $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$ — integers
• $\mathbb{Q} = \{\frac{p}{q} : p,q \in \mathbb{Z}, q \neq 0\}$ — rationals
• $\mathbb{R}$ — real numbers
• $\mathbb{C}$ — complex numbers

5.3 Set Operations

5.4 Set Identities

Proving Set Identities: Element Method

• Since $x \in B \cup C$, either $x \in B$ or $x \in C$.
• If $x \in B$, then $x \in A \cap B$, so $x \in (A \cap B) \cup (A \cap C)$.
• If $x \in C$, then $x \in A \cap C$, so $x \in (A \cap B) \cup (A \cap C)$. Proof ($\supseteq$): Let $x \in (A \cap B) \cup (A \cap C)$.
• Either $x \in A \cap B$ or $x \in A \cap C$.
• In either case, $x \in A$. And $x \in B$ or $x \in C$, so $x \in B \cup C$.
• Therefore $x \in A \cap (B \cup C)$. $\square$

5.5 Power Sets

5.6 Cartesian Products

5.7 Cardinality

• $|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}|$ (countably infinite)
• $|\mathbb{R}|$ is uncountably infinite (Cantor's diagonal argument)

✅ Practice Questions

Solution

$A \cup B = \{1,2,3,4\}$, $A \cap B = \{2,3\}$, $A - B = \{1\}$, $B - A = \{4\}$. Q2: Prove $\overline{A \cap B} = \overline{A} \cup \overline{B}$ using element argument. Solution

($\subseteq$): Let $x \in \overline{A \cap B}$. Then $x \notin A \cap B$, so $x \notin A$ or $x \notin B$. If $x \notin A$, then $x \in \overline{A} \subseteq \overline{A} \cup \overline{B}$. Similarly if $x \notin B$. ($\supseteq$): Let $x \in \overline{A} \cup \overline{B}$. Then $x \notin A$ or $x \notin B$, so $x \notin A \cap B$, hence $x \in \overline{A \cap B}$. Q3: How many subsets does $\{a,b,c,d\}$ have? Solution

$2^4 = 16$ subsets. Q4: Prove $A \subseteq B$ iff $A \cap B = A$. Solution

($\to$) Assume $A \subseteq B$. If $x \in A$, then $x \in B$, so $x \in A \cap B$. Thus $A \subseteq A \cap B$. Also $A \cap B \subseteq A$ always. So $A \cap B = A$. ($\leftarrow$) Assume $A \cap B = A$. If $x \in A$, then $x \in A \cap B$, so $x \in B$. Thus $A \subseteq B$. Q5: Show $|\mathbb{N}| = |\mathbb{Z}|$ by constructing a bijection. Solution

Define $f: \mathbb{N} \to \mathbb{Z}$ as:

This gives: $1 \to 0$, $2 \to 1$, $3 \to -1$, $4 \to 2$, $5 \to -2$, etc. It's bijective. Join Discord PreviousAdvanced ProofsNextSet Operation Proofs