Cheatsheet 02 - Sets
Mathematics for Master Students
Set Notation
A set is an unordered collection of distinct elements: \(\{1, 2, 3\} = \{3, 1, 2\}\) and \(\{1, 2, 2\} = \{1, 2\}\).
| Symbol | Meaning | Example |
|---|---|---|
| \(a \in A\) | \(a\) is an element of \(A\) | \(5 \in \{1, 5, 9\}\) |
| \(a \notin A\) | \(a\) is not an element of \(A\) | \(7 \notin \{1, 5, 9\}\) |
| \(\emptyset\) | Empty set: no elements | \(\emptyset = \{\}\), \(\;|\emptyset| = 0\) |
| \(|A|\) | Cardinality: number of elements | \(|\{1, 5, 9\}| = 3\) |
Two ways to describe a set: listing \(A = \{2, 4, 6\}\), or set-builder (a filter: base set + condition, “\(:\)” reads such that):
\[\{x \in \mathbb{N} : x \leq 4\} = \{1, 2, 3, 4\} \qquad\quad [0, 500] = \{x \in \mathbb{R} : 0 \leq x \leq 500\}\]
Element vs subset: \(\in\) relates an element to a set, \(\subseteq\) relates two sets. For \(A = \{1, 2, 3\}\):
| Symbol | Meaning | Example (true) |
|---|---|---|
| \(\in\) | Element of | \(2 \in A\) |
| \(\subseteq\) | Subset (equality allowed, like \(\leq\)) | \(\{1, 3\} \subseteq A\), \(\;A \subseteq A\), \(\;\emptyset \subseteq A\) |
| \(\subset\) | Proper subset (\(\subseteq\) and \(\neq\), like \(<\)) | \(\{1, 3\} \subset A\), but not \(A \subset A\) |
Set equality: \(A = B \Leftrightarrow A \subseteq B\) and \(B \subseteq A\). Check both inclusions.
Set Operations
All inside a universal set \(U\) (state it first!). Tiny examples with \(A = \{1, 4\}\), \(B = \{4, 7\}\), \(U = \{1, 4, 7, 9\}\):
| Symbol | Name | Definition | Example |
|---|---|---|---|
| \(A \cup B\) | Union (“or”) | \(\{x : x \in A \text{ or } x \in B\}\) | \(\{1, 4, 7\}\) |
| \(A \cap B\) | Intersection (“and”) | \(\{x : x \in A \text{ and } x \in B\}\) | \(\{4\}\) |
| \(A \setminus B\) | Difference | \(\{x : x \in A \text{ and } x \notin B\}\) | \(\{1\}\) |
| \(A^c\) | Complement | \(\{x \in U : x \notin A\} = U \setminus A\) | \(\{7, 9\}\) |
\(A\) and \(B\) are disjoint if \(A \cap B = \emptyset\). Order matters in differences: \(A \setminus B \neq B \setminus A\) in general.
De Morgan’s laws: the complement flips \(\cup\) into \(\cap\) and vice versa:
\[(A \cup B)^c = A^c \cap B^c \qquad\qquad (A \cap B)^c = A^c \cup B^c\]
Distributive law: \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
Inclusion-exclusion: don’t count the intersection twice:
\[|A \cup B| = |A| + |B| - |A \cap B|\]
Complement & Inclusion
Complement reverses inclusion (the set version of the contrapositive):
\[A \subseteq B \quad\Rightarrow\quad B^c \subseteq A^c\]
\(A \subseteq B \Rightarrow A^c \subseteq B^c\) is false in general. The smaller set has the bigger complement.
Products & Power Sets
Ordered pair \((a, b)\): order matters. \((a, b) \neq (b, a)\) unless \(a = b\); but \(\{a, b\} = \{b, a\}\) always.
\[A \times B = \{(a, b) : a \in A, \, b \in B\} \qquad\qquad |A \times B| = |A| \cdot |B|\]
Power set \(\mathcal{P}(A)\) = the set of all subsets of \(A\), including \(\emptyset\) and \(A\) itself:
\[\mathcal{P}(\{a, b\}) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\} \qquad\qquad |\mathcal{P}(A)| = 2^{|A|}\]
Its elements are themselves sets: \(\{a\} \in \mathcal{P}(A)\), but \(a \notin \mathcal{P}(A)\).
Logic ↔︎ Sets Dictionary
Set operations are logic on membership statements, one pattern, two languages:
| Logic (Session 1) | Sets (Session 2) |
|---|---|
| \(p \vee q\) (or) | \(A \cup B\) (union) |
| \(p \wedge q\) (and) | \(A \cap B\) (intersection) |
| \(\neg p\) (not) | \(A^c\) (complement) |
| \(p \Rightarrow q\) (implies) | \(A \subseteq B\) (subset) |
| \(\neg(p \vee q) \Leftrightarrow \neg p \wedge \neg q\) | \((A \cup B)^c = A^c \cap B^c\) |
Common Pitfalls
- \(\emptyset \neq \{0\}\): the empty set has no elements; \(\{0\}\) has one.
- \(\{2\} \in \{1, 2, 3\}\) is false, \(\{2\} \subseteq \{1, 2, 3\}\) is true. Element or set, decide first.
- Adding \(|A| + |B|\) double-counts \(A \cap B\). Always subtract it once.
- A complement \(A^c\) is meaningless until the universal set \(U\) is stated.
- Mixed \(\cup\) and \(\cap\) need parentheses: \(A \cap (B \cup C) \neq (A \cap B) \cup C\) in general.