Set Theory
Russell's paradox, countable vs. uncountable infinities, Cantor's diagonalization, and how all this leads directly to undecidable problems in computer science.
Set basics (quick recap)
| Symbol | Meaning |
|---|---|
| $x \in A$ | $x$ is an element of $A$ |
| $A \subseteq B$ | $A$ is a subset of $B$: $\forall x\,(x\in A \to x\in B)$ |
| $A \subset B$ | Proper subset (subset but $A\neq B$) |
| $\emptyset$ | Empty set (no elements) |
| $P(A)$ or $\mathcal{P}(A)$ | Power set: set of all subsets of $A$. $|\mathcal{P}(A)| = 2^{|A|}$ |
| $A \cup B$, $A \cap B$, $A\setminus B$ | Union, intersection, difference |
| $|A|$ | Cardinality (size). For infinite sets, see below. |
Set-builder notation
$\{x \in X : P(x)\}$ — the set of $x$ in $X$ such that $P(x)$ holds. Examples: $\{n \in \mathbb{N} : n \text{ is prime}\}$, $\{x \in \mathbb{R} : x^2 \leq 1\} = [-1, 1]$.
Inclusion–exclusion (3 sets)
3.1 Russell's Paradox
Naive set theory says: any property defines a set. Russell (1901) shattered this idea with one example.
The paradox
Ask the question: is $R \in R$?
- Case 1: $R \in R$. Then $R$ satisfies the membership criterion of $R$, which is "does not contain itself." So $R \notin R$. Contradiction.
- Case 2: $R \notin R$. Then $R$ does satisfy the property "$R \notin R$," so $R$ qualifies for membership in $R$, meaning $R \in R$. Contradiction.
Both cases contradict themselves, so no such set $R$ can exist. The "set of all sets that do not contain themselves" is not a valid set.
Why does this matter?
It shows naive comprehension — "for any property $P$, $\{x : P(x)\}$ is a set" — is inconsistent. Modern mathematics uses ZFC (Zermelo–Fraenkel + Axiom of Choice), where you can only form a set as $\{x \in A : P(x)\}$ (the axiom of separation): subsets of already-existing sets. This forbids $R$ from being constructed.
Analog: the barber paradox
"In a town, the barber shaves every man who does not shave himself." Does the barber shave himself? Same paradox in everyday language.
3.2 Countability
How do you compare sizes of infinite sets? Not by counting — by matching. Two sets have the same size iff there's a bijection between them.
- Finite set: bijects with $\{1, 2, \ldots, n\}$ for some $n$.
- Countably infinite set: bijects with $\mathbb{N} = \{1, 2, 3, \ldots\}$. (Some texts use $\mathbb{N}_0 = \{0,1,2,\ldots\}$.)
- Countable = finite or countably infinite.
- Uncountable = infinite but not countably infinite.
Bijections in plain terms
A function $f: A \to B$ is a bijection iff:
- Injective (one-to-one): $f(a_1) = f(a_2) \Rightarrow a_1 = a_2$.
- Surjective (onto): for every $b \in B$, there's some $a \in A$ with $f(a) = b$.
If a bijection $A \leftrightarrow \mathbb{N}$ exists, you can "list" the elements of $A$ as $a_1, a_2, a_3, \ldots$. That's the intuitive meaning of countable.
Classic countably infinite sets
The integers $\mathbb{Z}$ are countable. List as $0, 1, -1, 2, -2, 3, -3, \ldots$. Formally $$f(n) = \begin{cases}n/2 & n \text{ even}\\ -(n-1)/2 & n \text{ odd}\end{cases}$$ gives a bijection $\mathbb{N} \to \mathbb{Z}$.
The even integers are countable. $f(n) = 2n$ for $n \geq 1$ — yes, a proper infinite subset can have the same cardinality. Welcome to infinity.
$\mathbb{N} \times \mathbb{N}$ is countable. Use the diagonal traversal: list pairs by sum $i+j$: $(1,1)$; $(1,2),(2,1)$; $(1,3),(2,2),(3,1)$; ... Every pair appears in some finite-index position.
The rationals $\mathbb{Q}$ are countable. Write each positive rational $p/q$ in lowest terms; arrange $\mathbb{Q}^+$ in a grid with rows $p$ and columns $q$, then traverse diagonally, skipping non-lowest-terms entries. Add 0 and the negatives. Done.
Useful theorems about countable sets
- A subset of a countable set is countable.
- A countable union of countable sets is countable.
- A finite product (Cartesian) of countable sets is countable.
- If there's an injection $A \to \mathbb{N}$, then $A$ is countable.
- If there's a surjection $\mathbb{N} \to A$, then $A$ is countable.
The set of all finite strings over a finite alphabet $\Sigma$ is countable.
Listing: $\Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup \ldots$ Each $\Sigma^k$ is finite (size $|\Sigma|^k$). Countable union of finite sets = countable.
Application: the set of all programs in any programming language (Python, C, Java, Turing machines, $\ldots$) is countable, because programs are finite strings.
3.3 Uncountability — Cantor's Diagonal Argument
Not every infinite set is countable. The reals $\mathbb{R}$ are bigger.
The argument
Proof (diagonalization). Suppose, for contradiction, that $(0,1)$ is countable. Then we can list its elements: $r_1, r_2, r_3, \ldots$. Write each in its decimal expansion (avoiding ambiguous repetitions ending in all 9s): $$r_1 = 0.d_{11}d_{12}d_{13}\ldots$$ $$r_2 = 0.d_{21}d_{22}d_{23}\ldots$$ $$r_3 = 0.d_{31}d_{32}d_{33}\ldots$$ $$\vdots$$ Now construct a new number $x = 0.x_1 x_2 x_3 \ldots$ by $$x_i = \begin{cases} 5 & \text{if } d_{ii} \neq 5\\ 6 & \text{if } d_{ii} = 5 \end{cases}$$ (any rule works, as long as $x_i \neq d_{ii}$ and we don't pick 0 or 9 to avoid the ambiguity).
Then $x \in (0,1)$, but for every $n$, $x$ differs from $r_n$ in the $n$-th decimal place. So $x$ isn't in the list — contradicting completeness of the listing. Hence no such enumeration exists. ∎
The diagonal pattern
Whenever you want to show a set is uncountable: assume a listing, build an element that differs from the $n$-th listed element in the $n$-th position, conclude the new element isn't in the list. This template appears all over CS.
Other uncountable sets
$\{0,1\}^\mathbb{N}$ (set of infinite binary strings) is uncountable. Same diagonal argument: flip the $n$-th bit of the $n$-th listed string.
The power set $\mathcal{P}(\mathbb{N})$ is uncountable. Bijects with $\{0,1\}^{\mathbb{N}}$ via the characteristic function $\chi_S(n) = 1$ iff $n \in S$. So $|\mathcal{P}(\mathbb{N})| = |\{0,1\}^\mathbb{N}|$, uncountable.
The set of functions $f: \mathbb{N} \to \{0,1\}$ is uncountable. A function is determined by its sequence of values $f(1), f(2), \ldots$, an infinite binary string.
Cantor's theorem (general). For any set $S$, $|\mathcal{P}(S)| > |S|$. Even infinite sets have bigger sets. There is no "largest" infinity.
Proof sketch. Suppose $f: S \to \mathcal{P}(S)$. Let $D = \{x \in S : x \notin f(x)\}$. If $D = f(d)$ for some $d$, then $d \in D \iff d \notin f(d) = D$ — contradiction. So $f$ isn't surjective. ∎ (Notice the Russell-style flavour.)
3.4 Applications: Computability & Undecidability
Here's where countability collides with computer science.
The counting argument: most functions aren't computable
- The set of all programs (in any fixed programming language) is countable — programs are finite strings over a finite alphabet.
- So the set of all computable functions $\mathbb{N} \to \mathbb{N}$ is countable.
- But the set of all functions $\mathbb{N} \to \{0, 1\}$ is uncountable (we just proved it).
- Therefore: most functions $\mathbb{N} \to \mathbb{N}$ are not computable. There simply aren't enough programs.
Theorem. There exist non-computable functions $f: \mathbb{N} \to \mathbb{N}$.
Proof. Programs form a countable set $\mathcal{P} = \{p_1, p_2, \ldots\}$. Each program $p_i$ computes some (possibly partial) function $f_i$. The set of computable functions $\{f_i\}$ is countable. The set of all $\mathbb{N} \to \{0,1\}$ functions is uncountable, so some function is in the latter but not the former. ∎
The Halting Problem
An explicit uncomputable problem. Define $$\text{Halt}(P, x) = \begin{cases} 1 & \text{if program } P \text{ halts on input } x \\ 0 & \text{if } P \text{ runs forever on } x \end{cases}$$ Claim: Halt is not computable.
Proof (diagonalization). Suppose a program $H$ computes Halt. Build a new program $D$ that takes a program $P$ as input and:
D(P):
if H(P, P) returns 1: # i.e., P halts on input P
loop forever
else:
haltNow ask: does $D$ halt on input $D$?
- If yes ($D$ halts on $D$): then $H(D, D) = 1$, so $D$ enters the infinite loop — doesn't halt. ⚡
- If no: $H(D, D) = 0$, so $D$ halts immediately. ⚡
Contradiction either way. Hence no such $H$ exists. ∎
This is the foundational uncomputable problem; many others ("does this program output 'hello'?", "are these two programs equivalent?") reduce to it.
Cardinality & automata
- The set of finite-state automata (with finite alphabet) is countable — each is a finite string.
- The set of regular languages over $\Sigma$ is countable.
- But the set of all languages over $\Sigma$ (subsets of $\Sigma^*$) is $\mathcal{P}(\Sigma^*)$, which is uncountable.
- Hence most languages are not regular — and indeed most aren't decidable by any computer.
Problem Bank — Set Theory
Determine each: (a) $0 \in \emptyset$, (b) $\emptyset \in \{0\}$, (c) $\{0\} \subset \emptyset$, (d) $\emptyset \subset \{0\}$, (e) $\{\emptyset\} \subseteq \{\emptyset\}$.
Show solution
- (a) False. $\emptyset$ has no elements.
- (b) False. $\{0\}$ contains only $0$, not $\emptyset$.
- (c) False. $\{0\}$ isn't even a subset of $\emptyset$.
- (d) True. The empty set is a (proper) subset of every nonempty set.
- (e) True. Any set is a subset of itself.
Prove $\mathcal{P}(A) \subseteq \mathcal{P}(B) \iff A \subseteq B$.
Show solution
($\Leftarrow$). Suppose $A \subseteq B$. Take $S \in \mathcal{P}(A)$, i.e., $S \subseteq A$. Then $S \subseteq A \subseteq B$, so $S \in \mathcal{P}(B)$.
($\Rightarrow$). Suppose $\mathcal{P}(A) \subseteq \mathcal{P}(B)$. Note $A \in \mathcal{P}(A)$, so $A \in \mathcal{P}(B)$, i.e., $A \subseteq B$. ∎
$|A|=10, |B|=12, |C|=14$, $|A\cap B|=5$, $|B\cap C|=6$, $|C\cap A|=4$, $|A\cap B\cap C|=2$, and $U = A\cup B\cup C$. Find $|U|$, number in exactly two, and exactly one.
Show solution
$|U| = 10+12+14 - 5 - 6 - 4 + 2 = 23.$
Exactly two sets: $(|A\cap B| - |A\cap B\cap C|) + (|B\cap C| - |A\cap B\cap C|) + (|C\cap A| - |A\cap B\cap C|) = 3 + 4 + 2 = 9$.
Exactly one: $|U| - (\text{exactly two}) - |A\cap B\cap C| = 23 - 9 - 2 = 12$.
In a class of 100 students, 73 study PSP, 80 study Maths, 52 study SnW. Some study none. Find max − min of (number studying all three).
Show solution
Let $x = |P \cap M \cap S|$.
Maximum. $x \leq \min(|P|, |M|, |S|) = 52$.
Minimum. Using inclusion-exclusion lower bound: $|P\cap M\cap S| \geq |P| + |M| + |S| - 2\cdot 100 = 73+80+52 - 200 = 5$. (Achieved when as many students as possible are outside.) So min $= 5$.
Difference $= 52 - 5 = 47$.
$A_i = \{1, 2, \ldots, i\}$. Find $\bigcup_{i=1}^n A_i$ and $\bigcap_{i=1}^n A_i$.
Show solution
The $A_i$ form a chain $A_1 \subset A_2 \subset \cdots \subset A_n$. So $\bigcup A_i = A_n = \{1,\ldots,n\}$ and $\bigcap A_i = A_1 = \{1\}$.
$A_i = \{\ldots, -2, -1, 0, 1, \ldots, i\}$ for $i\geq 1$. Find $\bigcup A_i$ and $\bigcap A_i$ over $i=1\ldots n$.
Show solution
Each $A_i = \{x \in \mathbb{Z} : x \leq i\}$. Again a chain. Union $= A_n = \{x \in \mathbb{Z} : x \leq n\}$. Intersection $= A_1 = \{x\in\mathbb{Z}:x\leq 1\}$.
Find $\bigcup_{i=1}^\infty A_i$ and $\bigcap_{i=1}^\infty A_i$ where (a) $A_i = \{i, i+1, \ldots\}$, (b) $A_i = \{0, i\}$, (c) $A_i = (0, i)$ in $\mathbb{R}$, (d) $A_i = (i, \infty)$.
Show solution
- (a) Union $= \{1,2,3,\ldots\} = \mathbb{N}$. Intersection $= \emptyset$ (no integer is $\geq$ every $i$).
- (b) Union $= \{0\} \cup \{1, 2, 3, \ldots\} = \{0,1,2,\ldots\}$. Intersection $= \{0\}$ (only 0 is in every $A_i$).
- (c) Union $= (0, \infty)$. Intersection $= (0, 1)$ (the smallest interval).
- (d) Union $= (1, \infty)$. Intersection $= \emptyset$ (no real is greater than every $i$).
For subsets $A, B$ of $U$ with characteristic functions $f_A, f_B$, show:
(a) $f_{A\cap B}(x) = f_A(x)f_B(x)$, (b) $f_{A\cup B}(x) = f_A(x) + f_B(x) - f_A(x)f_B(x)$, (c) $f_{\bar A}(x) = 1 - f_A(x)$, (d) $f_{A\oplus B}(x) = f_A(x) + f_B(x) - 2f_A(x)f_B(x)$.
Show solution
All follow by examining the four cases of $(f_A(x), f_B(x)) \in \{0,1\}^2$:
| $f_A$ | $f_B$ | $f_A f_B$ | $f_A+f_B-f_Af_B$ | $1-f_A$ | $f_A+f_B-2f_Af_B$ |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 |
Verify by matching: $f_{A\cap B} = 1$ iff $x\in A \land x\in B$; $f_{A\cup B} = 1$ iff at least one; etc. ∎
Determine finite/countably infinite and provide bijections with $\mathbb{N}$ where applicable:
(a) negative integers, (b) even integers, (c) integers $< 100$, (d) positive integers $< 10^9$, (e) integers that are multiples of 7.
Show solution
- (a) Countably infinite. $f(n) = -n$.
- (b) Countably infinite. $f(1)=0, f(2)=2, f(3)=-2, f(4)=4, f(5)=-4, \ldots$ — pair off positives and negatives.
- (c) Countably infinite. $f(1)=99, f(2)=98, \ldots, f(100)=0, f(101)=-1, \ldots$
- (d) Finite with $10^9 - 1$ elements.
- (e) Countably infinite. Multiples of 7 are $\ldots,-14,-7,0,7,14,\ldots$. Use $f(n) = 7\cdot g(n)$ where $g$ bijects $\mathbb{N} \to \mathbb{Z}$.
Show the set of real solutions of $ax^2 + bx + c = 0$ with $a,b,c \in \mathbb{Z}$ is countable.
Show solution
The set of integer triples $(a,b,c)$ is $\mathbb{Z}^3$, which is countable (finite product of countable). Each triple yields at most 2 real roots. The solution set is therefore the image of a countable set under a finite-valued map — countable union of finite sets — hence countable. ∎
(a) Show the set of all computer programs in a programming language is countable.
(b) Show the set of functions $f: \mathbb{N} \to \{0,\ldots,9\}$ is uncountable.
(c) Conclude that uncomputable functions exist.
Show solution
(a) Programs are finite strings over a finite alphabet. There are $|\Sigma|^k$ strings of length $k$; the total set is $\bigcup_{k=0}^\infty \Sigma^k$, a countable union of finite sets — countable.
(b) Map a real $r = 0.d_1 d_2 d_3 \ldots \in [0,1)$ to the function $f_r(n) = d_n$. This is one-to-one. $[0,1)$ is uncountable, hence so is its image, hence the set of such functions is uncountable.
(c) Each program computes at most one function, so the set of computable functions $\mathbb{N}\to\{0,\ldots,9\}$ is countable. But the set of all such functions is uncountable. So there's a function with no program computing it. ∎
(a) Accommodate finitely many new guests in a fully-booked Hilbert Hotel.
(b) After even-numbered rooms close, fit all current guests.
(c) Add a second infinite hotel; spread current guests across both.
(d) Accommodate countably many new guests.
(e) Countably many buses, each with countably many guests, arrive — accommodate all.
Show solution
- (a) $k$ guests. Move each guest in room $n$ to room $n+k$. Rooms $1, \ldots, k$ free up.
- (b) Move guest in room $n$ to room $2n - 1$. All guests now in odd rooms. ✓
- (c) Move guest in room $n$ of the original to room $2n - 1$. Move guest from second hotel's room $n$ to room $2n$. ✓
- (d) Move every existing guest from room $n$ to room $2n$; place new guest $k$ in room $2k - 1$.
- (e) Cantor pairing. Move existing guest $n$ to room $2n - 1$ (odd rooms). Number new guests by (bus $b$, seat $s$). Assign them via a bijection $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ to the even rooms. Concretely, pair $(b,s) \mapsto 2 \cdot \frac{(b+s-1)(b+s-2)}{2} + 2s$. Or just diagonalize.
Is $G = \{g : \mathbb{N} \to \{0,1\} \mid g \text{ is a function}\}$ countable or uncountable? Justify.
Show solution
Uncountable. Each $g \in G$ corresponds to an infinite binary string $g(1)g(2)g(3)\ldots$. Suppose, for contradiction, $G = \{g_1, g_2, \ldots\}$ is enumerable.
Define $h: \mathbb{N} \to \{0,1\}$ by $h(n) = 1 - g_n(n)$ (flip the diagonal bit). Then $h \in G$ but $h \neq g_n$ for any $n$ (they differ at position $n$). Contradiction. ∎
(a) Define Russell's set $R$ in set-builder form. (b) Show that the existence of $R$ leads to a contradiction in both cases $R \in R$ and $R \notin R$.
Show solution
(a) $R = \{S : S \notin S\}$.
(b)
- Case $R \in R$: by the definition of $R$, $R$ must satisfy $R \notin R$. Contradiction.
- Case $R \notin R$: then $R$ satisfies the membership criterion of $R$ (namely "$\cdot \notin \cdot$"), so $R \in R$. Contradiction.
Prove that the set of all infinite-length binary strings is uncountable.
Show solution
Identical to Cantor's diagonal in binary. Suppose the set is countable, listed as $s_1, s_2, s_3, \ldots$ with $s_i = b_{i1}b_{i2}b_{i3}\ldots$ Construct $t = t_1 t_2 t_3\ldots$ with $t_n = 1 - b_{nn}$. Then $t$ differs from each $s_n$ in position $n$, so $t$ is not in the list. Contradiction. ∎
Sketch the proof that the Halting Problem is undecidable.
Show solution
Suppose $H(P, x)$ decides whether $P$ halts on $x$. Construct
D(P): if H(P, P) = 1 then loop forever; else halt.If $D(D)$ halts, then by the if-branch, $H(D,D)=1$, so $D$ loops — doesn't halt. ⚡
If $D(D)$ doesn't halt, then $H(D,D)=0$, so $D$ halts. ⚡
Both branches contradict; $H$ cannot exist. ∎
Prove $|\mathcal{P}(S)| > |S|$ for every set $S$ (Cantor's theorem).
Show solution
It suffices to show no $f: S \to \mathcal{P}(S)$ is surjective. Given any such $f$, define $$D = \{x \in S : x \notin f(x)\} \in \mathcal{P}(S).$$ Suppose $D = f(d)$ for some $d \in S$. Then $d \in D \iff d \notin f(d) = D$, contradiction. So $D \notin \text{range}(f)$, hence $f$ isn't surjective. ∎
- Russell's paradox kills naive comprehension. Modern axiomatization (ZFC) only allows $\{x \in A : P(x)\}$, not $\{x : P(x)\}$.
- Countable ≠ small. $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{N}\times\mathbb{N}$ are all countable. Countable union of countable sets is countable.
- Uncountable signature: diagonal argument. Reals, infinite binary strings, $\mathcal{P}(\mathbb{N})$, functions $\mathbb{N}\to\{0,1\}$.
- Programs are countable, functions are not — therefore uncomputable functions exist. Halting Problem is a concrete one.
- Show countability by either (a) constructing an explicit bijection / list, or (b) an injection into $\mathbb{N}$, or (c) a surjection from $\mathbb{N}$.