Sets and set operations
Sets are the basic containers of mathematics. Nearly every structure in discrete math, from graphs to databases, is built from them.
What a set is
A set is an unordered collection of distinct objects, called elements. We write \(A = \{1, 2, 3\}\) and \(2 \in A\). Order and repetition do not matter: \(\{1, 2, 2\} = \{2, 1\}\). Sets can be described by listing or by a rule, as in \(\{x \in \mathbb{Z} : x > 0\}\), the positive integers.
Important sets
\(\mathbb{N}\) (natural numbers), \(\mathbb{Z}\) (integers), \(\mathbb{Q}\) (rationals), and \(\mathbb{R}\) (reals) are standard. The empty set \(\varnothing\) has no elements. The universal set \(U\) contains everything under discussion. Two sets are equal when they have exactly the same elements.
Subsets and power sets
\(A \subseteq B\) means every element of \(A\) is in \(B\). Every set is a subset of itself, and \(\varnothing\) is a subset of every set. The power set \(\mathcal{P}(A)\) is the set of all subsets; a set with \(n\) elements has \(2^n\) subsets, since each element is either in or out.
|\mathcal{P}(A)| = 2^{|A|}Set operations
Union \(A \cup B\) contains elements in either set; intersection \(A \cap B\) contains elements in both; difference \(A - B\) contains elements of \(A\) not in \(B\); the complement \(\overline{A}\) contains everything in \(U\) not in \(A\). Venn diagrams make these operations visual.
Set identities
Set operations obey laws mirroring logic: commutative, associative, distributive, and De Morgan's laws, \(\overline{A \cup B} = \overline{A} \cap \overline{B}\). This mirrors \(\neg(p \vee q) \equiv \neg p \wedge \neg q\) exactly, because 'x is in A' is a proposition.
\overline{A \cup B} = \overline{A} \cap \overline{B}Cartesian products
The Cartesian product \(A \times B\) is the set of ordered pairs \((a, b)\) with \(a \in A\), \(b \in B\). If \(|A| = 3\) and \(|B| = 4\), then \(|A \times B| = 12\). The coordinate plane is \(\mathbb{R} \times \mathbb{R}\), and database tables are subsets of Cartesian products.
Inclusion-exclusion
For finite sets, \(|A \cup B| = |A| + |B| - |A \cap B|\), subtracting the overlap counted twice. If 30 students take maths, 25 take physics, and 10 take both, then 45 take at least one. The principle extends to three or more sets with alternating signs.
|A \cup B| = |A| + |B| - |A \cap B|Worked example
Let \(U = \{1, \ldots, 10\}\), \(A = \{\text{evens}\}\), \(B = \{\text{multiples of } 3\}\). Then \(A \cap B = \{6\}\), \(A \cup B = \{2, 3, 4, 6, 8, 9, 10\}\), and \(\overline{A \cup B} = \{1, 5, 7\}\). Inclusion-exclusion checks: \(5 + 3 - 1 = 7\).
Key takeaways
Sets are unordered collections of distinct elements. A set of size \(n\) has \(2^n\) subsets. Union, intersection, difference, and complement obey laws mirroring logic, including De Morgan's. Cartesian products form ordered pairs. Inclusion-exclusion counts unions without double counting.
Flashcard
Unordered collection of distinct elements
Check your understanding
How many subsets does a set with 5 elements have?