Note 11: To Infinity And Beyond
Bijections · Countability · Cantor's Diagonalization · Power Sets · Orders of Infinity
Infinity is not one thing. There are different sizes of infinity, and some infinite sets are genuinely larger than others. This note makes that precise using the concept of a bijection. The key theorem — Cantor's diagonalization — is one of the most elegant proofs in all of mathematics, and it has deep connections to computability and the limits of what computers can do.
Bijections and Cardinality
- Injective (one-to-one): $f(x) = f(y) \Rightarrow x = y$. Distinct inputs have distinct outputs.
- Surjective (onto): Every $b \in B$ has at least one preimage $a \in A$ with $f(a) = b$.
- Bijective: Both injective and surjective. A perfect pairing between $A$ and $B$.
For finite sets, this just means they have the same number of elements. For infinite sets, bijections reveal surprising equalities: sets that look different in size can actually have the same cardinality.
Countable Sets
Key Examples
| Set | Why countable | Bijection to $\mathbb{N}$ |
|---|---|---|
| $\mathbb{Z}^+$ | Subset of $\mathbb{N}$ | $f(n)=n+1$ |
| $\mathbb{Z}$ (all integers) | Interleave positive/negative | $f(n)=n/2$ if even, $-(n+1)/2$ if odd |
| $2\mathbb{N}$ (even naturals) | Easy bijection | $f(n)=2n$ |
| $\mathbb{Q}$ (rationals) | Spiral through $\mathbb{Z}\times\mathbb{Z}$ | Cantor pairing |
| $\{0,1\}^*$ (binary strings) | List by length | $f(n) = $ $n$-th binary string |
| All polynomials over $\mathbb{N}$ | Encode coefficients as ternary string | Injection into $\{0,1,2\}^*$ |
📘 Bijection $\mathbb{N} \to \mathbb{Z}$: All integers are countable
The bijection $f: \mathbb{N} \to \mathbb{Z}$:
$$f(n) = \begin{cases} n/2 & \text{if } n \text{ is even} \\ -(n+1)/2 & \text{if } n \text{ is odd} \end{cases}$$Listing: $f(0)=0, f(1)=-1, f(2)=1, f(3)=-2, f(4)=2, f(5)=-3, f(6)=3, \ldots$
So the sequence $0, -1, 1, -2, 2, -3, 3, \ldots$ covers every integer exactly once. This is the "interleaving" trick.
$|\mathbb{N}| = |\mathbb{Z}|$ — there are "as many" natural numbers as integers.📘 Why $\mathbb{Q}$ is countable (Cantor's spiral)
Every rational $a/b$ (in lowest terms) corresponds to the point $(a,b)$ in $\mathbb{Z} \times \mathbb{Z}$. The set $\mathbb{Z} \times \mathbb{Z}$ is countable (we can enumerate it via a diagonal/spiral path):
$(0,0) \to (1,0) \to (1,1) \to (0,1) \to (-1,1) \to \ldots$ — each pair appears exactly once at some finite step $n$.
Since $\mathbb{Q} \subseteq \mathbb{Z}\times\mathbb{Z}$ (excluding $b=0$), and $\mathbb{Z}\times\mathbb{Z}$ is countable, $\mathbb{Q}$ is countable. Combined with $|\mathbb{N}| \leq |\mathbb{Q}|$ (since $\mathbb{N} \subset \mathbb{Q}$), by Cantor-Bernstein: $|\mathbb{N}| = |\mathbb{Q}|$.
$\mathbb{Q}$ is countable. Surprising, since between any two integers there are infinitely many rationals!Cantor's Diagonalization: $\mathbb{R}$ is Uncountable
Now comes the most important proof in this note. Despite all the sets above being countable, the real numbers are genuinely bigger. No bijection between $\mathbb{N}$ and $\mathbb{R}$ exists.
The Proof by Diagonalization
We prove the contrapositive via contradiction. Suppose $\mathbb{R}[0,1]$ were countable. Then we could list all real numbers in $[0,1]$ as an infinite sequence:
| Digit 1 | Digit 2 | Digit 3 | Digit 4 | ... | |
|---|---|---|---|---|---|
| $f(0)$ | 5 | 2 | 1 | 4 | ... |
| $f(1)$ | 1 | 4 | 1 | 6 | ... |
| $f(2)$ | 9 | 4 | 7 | 8 | ... |
| $f(3)$ | 5 | 3 | 0 | 9 | ... |
| $\vdots$ | ... | ... | ... | ... | ... |
Yellow diagonal: $r = 0.5479\ldots$ Construct $s$ by changing each diagonal digit (add 2 mod 10): $s = 0.7691\ldots$
Claim: $s \notin \{f(0), f(1), f(2), \ldots\}$.
Why: $s$ differs from $f(n)$ in position $n+1$ (the diagonal position), for every $n$. So $s \neq f(n)$ for all $n$.
But we assumed the list contains all real numbers in $[0,1]$. Contradiction! Therefore $\mathbb{R}[0,1]$ is uncountable.
Why Diagonalization Fails for $\mathbb{Q}$
If we apply the same argument to a list of rationals, the "diagonal number" we construct has no reason to be rational — its decimal expansion is unlikely to be periodic. So we cannot conclude a contradiction. The argument only works for $\mathbb{R}$ because any real number with an infinite decimal expansion is a valid real number.
Power Sets and Higher Infinities
Proof by diagonalization: Suppose there were a bijection $f: \mathbb{N} \to \mathcal{P}(\mathbb{N})$. Represent each subset $f(n)$ as an infinite binary string (bit $k$ = 1 iff $k \in f(n)$). Look at the diagonal: construct a new set $D$ by flipping each diagonal bit: $D = \{n : n \notin f(n)\}$. This set $D$ cannot equal $f(n)$ for any $n$ (since $D$ and $f(n)$ differ at position $n$). So $f$ is not surjective — contradiction.
This gives an infinite tower of infinities: $$|\mathbb{N}| = \aleph_0 \;\;<\;\; |\mathcal{P}(\mathbb{N})| = 2^{\aleph_0} = |\mathbb{R}| = \mathfrak{c} \;\;<\;\; |\mathcal{P}(\mathbb{R})| \;\;<\;\; \cdots$$ Continuum Hypothesis: Is there a set with cardinality strictly between $\aleph_0$ and $\mathfrak{c}$? This is famously undecidable from standard axioms of set theory.
The Cantor Set
The Cantor set is a remarkable construction: obtained by repeatedly removing the middle third of $[0,1]$. After infinitely many steps, the "measure" (total length) is 0, yet the set is uncountably infinite. It consists exactly of all real numbers in $[0,1]$ whose ternary (base-3) representation contains only digits 0 and 2.
Hard Practice Problems
Problem: Is the set of all functions $f: \mathbb{N} \to \{0,1\}$ (functions from natural numbers to $\{0,1\}$) countable or uncountable? Prove your answer.
📋 Solution to Hard Problem 1
Answer: Uncountable.
- Each function $f: \mathbb{N} \to \{0,1\}$ is determined by its values $f(0), f(1), f(2), \ldots$ — an infinite binary sequence. So the set of all such functions is in bijection with the set of all infinite binary sequences.
- We claim this set is uncountable, by diagonalization. Suppose it were countable and we could list all such functions: $f_0, f_1, f_2, \ldots$
- Define a new function $g: \mathbb{N} \to \{0,1\}$ by $g(n) = 1 - f_n(n)$ (flip the $n$-th value of the $n$-th function).
- Then $g \neq f_n$ for all $n$ (they differ at position $n$). So $g$ is not in our list. Contradiction.
Alternatively: there is a bijection between $\{0,1\}^\mathbb{N}$ (infinite binary sequences) and $\mathcal{P}(\mathbb{N})$ (subsets of $\mathbb{N}$), which is uncountable by Cantor's theorem. The bijection: a function $f$ corresponds to the set $\{n : f(n)=1\}$.
The set of all $f:\mathbb{N}\to\{0,1\}$ is uncountable. ∎Problem: Let $A$ and $B$ be countably infinite sets. Prove that $A \times B = \{(a,b) : a \in A, b \in B\}$ is also countably infinite. (Hint: Use the fact that $\mathbb{N} \times \mathbb{N}$ is countable, which follows from the spiral argument for $\mathbb{Q}$.)
📋 Solution to Hard Problem 2
Solution:
- Since $A$ is countably infinite, there is a bijection $f: \mathbb{N} \to A$. Since $B$ is countably infinite, there is a bijection $g: \mathbb{N} \to B$.
- Define $h: \mathbb{N} \times \mathbb{N} \to A \times B$ by $h(m,n) = (f(m), g(n))$. Since $f$ and $g$ are bijections, $h$ is a bijection.
- It remains to show $\mathbb{N} \times \mathbb{N}$ is countably infinite. Define a bijection via the "diagonal" path: list all pairs $(m,n)$ with $m+n=0$, then $m+n=1$, then $m+n=2$, etc. This gives: $(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),\ldots$ — every pair appears exactly once.
- Composing: $\mathbb{N} \xrightarrow{\sim} \mathbb{N}\times\mathbb{N} \xrightarrow{h} A\times B$. The composition is a bijection $\mathbb{N} \to A\times B$.