Chapter 8: Sets — Key Takeaways
A one-page, exam-ready reference. A set is an unordered collection of distinct elements, defined entirely by which objects belong to it. Almost everything below is a logical statement about the membership relation $\in$, so when a set fact stumps you, translate it to logic.
Notation at a glance
| Symbol | Read as | Means |
|---|---|---|
| $x \in A$ / $x \notin A$ | "$x$ in / not in $A$" | $x$ is / is not an element of $A$ |
| $\{1,2,3\}$ | roster notation | the set whose elements are listed |
| $\{x \mid P(x)\}$ | set-builder, "such that" | all $x$ making predicate $P$ true |
| $\emptyset$ or $\{\}$ | the empty set | the unique set with no elements |
| $\lvert A \rvert$ | cardinality | number of distinct elements (finite) |
| $A \subseteq B$ / $A \subset B$ | subset / proper subset | $\forall x(x\in A\to x\in B)$ / and $A\ne B$ |
| $A = B$ | equality | same elements (extensional) |
| $\mathcal{P}(S)$ | power set | the set of all subsets of $S$ |
| $(a,b)$ | ordered pair | order matters: $(a,b)=(c,d)\iff a=c\land b=d$ |
| $A \times B$ | Cartesian product | $\{(a,b)\mid a\in A,\ b\in B\}$ |
Standard sets: $\mathbb{N}=\{0,1,2,\dots\}$ (includes 0), $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$.
Operations = logical connectives on membership
| Operation | Symbol | $x$ is in it iff… | Connective | Python |
|---|---|---|---|---|
| Union | $A\cup B$ | $x\in A \lor x\in B$ | or | A \| B |
| Intersection | $A\cap B$ | $x\in A \land x\in B$ | and | A & B |
| Difference | $A\setminus B$ | $x\in A \land x\notin B$ | and-not | A - B |
| Complement | $\overline{A}$ | $x\notin A$ (need universe $U$) | not | U - A |
| Symmetric diff | $A\triangle B$ | in exactly one | xor | A ^ B |
$A,B$ are disjoint when $A\cap B=\emptyset$.
Formulas to memorize
| Quantity | Formula |
|---|---|
| Power-set size | $\lvert \mathcal{P}(S)\rvert = 2^{\lvert S\rvert}$ |
| Cartesian product size | $\lvert A\times B\rvert = \lvert A\rvert\cdot\lvert B\rvert$ |
| $n$-tuples over $A$ | $\lvert A^{n}\rvert = \lvert A\rvert^{n}$ (e.g. $\lvert\{0,1\}^n\rvert = 2^n$) |
| Inclusion–exclusion (2 sets, preview Ch. 15) | $\lvert A\cup B\rvert = \lvert A\rvert+\lvert B\rvert-\lvert A\cap B\rvert$ |
Core set identities (each is a logic law in disguise)
| Identity | Name |
|---|---|
| $A\cup B=B\cup A$; $\;A\cap B=B\cap A$ | Commutative |
| $A\cup(B\cup C)=(A\cup B)\cup C$ | Associative |
| $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$ | Distributive |
| $\overline{A\cup B}=\overline{A}\cap\overline{B}$; $\;\overline{A\cap B}=\overline{A}\cup\overline{B}$ | De Morgan |
| $A\cup\emptyset=A$; $\;A\cap U=A$ | Identity |
| $A\cup\overline{A}=U$; $\;A\cap\overline{A}=\emptyset$ | Complement |
| $\overline{\overline{A}}=A$ | Double complement |
| $A\cup A=A$; $\;A\cap A=A$ | Idempotent |
| $A\cup(A\cap B)=A$ | Absorption |
| $A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C)$ | Difference–De Morgan |
How to prove a set identity (decision aid)
- First, conjecture with a Venn diagram or a tiny example. (A diagram is never a proof.)
- Element method (safest): to prove $A=B$, show $A\subseteq B$ and $B\subseteq A$. Take an arbitrary $x$, unfold each set operation into its connective, apply a logic equivalence (Ch. 1), fold back. A chain of $\iff$ proves both inclusions at once.
- Set-builder algebra (faster): rewrite $\{x\mid \dots\}$ expressions, citing logic laws.
- To disprove, find one counterexample (one $x$ in one side but not the other).
The engine: membership → logic → apply equivalence → logic → membership. Every identity proof is this loop.
Common pitfalls
| Pitfall | Reality |
|---|---|
| $\emptyset = \{\emptyset\} = \{0\}$? | No. $\lvert\emptyset\rvert=0$, $\lvert\{\emptyset\}\rvert=1$, $\lvert\{0\}\rvert=1$; all different. |
| $a \in \mathcal{P}(\{a,b\})$? | No — elements of a power set are sets: $\{a\}\in\mathcal{P}$, but $a\notin\mathcal{P}$. |
| $A\times B = B\times A$? | No (not commutative); only $\lvert A\times B\rvert=\lvert B\times A\rvert$. |
| $\{a,a\}$ has 2 elements? | No — duplicates collapse: $\{a,a\}=\{a\}$. (But $(a,a)$ is a valid pair.) |
| A Venn diagram proves it | No — it only checks "generic" circles; misses special cases. |
{} is an empty set in Python |
No — {} is an empty dict; use set(). |
Sets in Python
| Need | Use | Why |
|---|---|---|
Fast membership x in s |
set |
$O(1)$ average (hash table) vs. $O(n)$ for a list |
| Remove duplicates | set(seq) |
distinctness is built in |
| Set of sets (e.g. power set) | frozenset inner |
set is unhashable; frozenset is immutable + hashable |
| Indexing / order / repeats | list |
sets have no order, no index, no duplicates |
Operators: | & - ^ for $\cup,\cap,\setminus,\triangle$; s.isdisjoint(t), s.issubset(t),
len(s) for $\lvert s\rvert$.
Toolkit additions (dmtoolkit/sets.py)
| Function | Returns | Definition implemented |
|---|---|---|
union(a, b) |
set | $\{x\mid x\in a\lor x\in b\}$ |
intersection(a, b) |
set | $\{x\mid x\in a\land x\in b\}$ |
difference(a, b) |
set | $\{x\mid x\in a\land x\notin b\}$ |
cartesian(a, b) |
set of pairs | $\{(x,y)\mid x\in a, y\in b\}$ |
power_set(s) |
set of frozensets | $\{A\mid A\subseteq s\}$; doubles each pass → $2^{\lvert s\rvert}$ |
power_set = the $2^n$ proof as an algorithm: start with {∅}, then for each element keep every
subset with and without it (the binary include/exclude choice), doubling the count $n$ times.
The one thing to remember
Set theory is logic with a universe attached. Every operation is a connective on $\in$; every identity is a logical equivalence. Master that translation and the whole chapter (and much of Chapters 9, 12, 15, and 27) follows from Part I.