Cantor's diagonal argument: some infinities are bigger
Sizes of infinite sets are compared by pairing. The integers and the fractions pair off with the counting numbers, and the real numbers provably do not.
AssumesProof by contradiction: why √2 is not a fractionSets, Venn diagrams and inclusion-exclusion
Are there more counting numbers $1, 2, 3, \dots$ than even numbers $2, 4, 6, \dots$? The obvious answer is yes, twice as many, since the even numbers leave out every other one. But join each number $n$ to its double $2n$, as in the animation. Every counting number gets a partner, every even number gets a partner, and nobody is used twice. If two crowds can be lined up one against one with nobody left over, it is hard to maintain that one crowd is bigger.
So two reasonable ways of comparing sizes disagree. The same conflict, with the square numbers $1, 4, 9, \dots$ in place of the even ones, puzzled Galileo, who concluded that “equal”, “greater” and “less” do not apply to infinite collections. In the 1870s Georg Cantor took the other way out: he chose one of the two ways, followed it strictly, and found that infinite sets do come in different sizes.
Notation: $\mathbb{N} = \{1, 2, 3, \dots\}$ is the set of counting numbers, $\mathbb{Z}$ the integers, $\mathbb{Q}$ the rational numbers (fractions $\frac{p}{q}$ of integers with $q \neq 0$) and $\mathbb{R}$ the real numbers. From the lesson on sets we use $\in$ and $\subseteq$, and from proof by contradiction the method of assuming the opposite and deriving an impossibility.
Size without counting
To check that a hall has as many chairs as people without counting either, ask everyone to sit. If no chair is empty and nobody is standing, the numbers agree. For finite sets this test and ordinary counting always give the same verdict; indeed counting is this test, a pairing of the objects with $1, 2, \dots, n$. The test has the advantage that it still makes sense when no number $n$ is available.
In the hall, $f$ sends each person to a chair. Injective says no chair holds two people, and surjective says no chair is empty.
The rival test, “a part is smaller than the whole”, is also correct for finite sets: a finite set cannot be paired off with a proper part of itself, which is the pigeonhole principle. For infinite sets the two tests conflict, as the opening showed, and we keep the pairing test. The first theorem records what the animation drew.
Hilbert’s hotel
David Hilbert dramatized this with a hotel that has one room for each counting number, all occupied. A new guest arrives.
No finite hotel can do this. Here the move $n \mapsto n + 1$ is a bijection from $\mathbb{N}$ to $\{2, 3, 4, \dots\}$, so the full hotel has the same size as itself with a room removed.
Pause and try
Now a bus arrives with infinitely many new guests, in seats numbered $1, 2, 3, \dots$, and the hotel is full. Find new rooms for everybody. (Moving each guest “infinitely many rooms along” is not an instruction anyone can follow.)
Show answerHide answer
Send the guest in room $n$ to room $2n$, and the passenger in seat $k$ to room $2k - 1$. The old guests fill the even rooms, once each, and the passengers fill the odd rooms, once each. Every room has exactly one occupant.
Countable sets: the integers
A bijection $f : \mathbb{N} \to S$ is the same thing as a list $f(1), f(2), f(3), \dots$ in which every element of $S$ appears exactly once. So the question “is $S$ the same size as $\mathbb{N}$?” becomes “can the elements of $S$ be written in a list that misses nothing?”
The integers go on forever in both directions, so listing them from left to right is hopeless: there is no leftmost one to start with. Listing all the positive ones first also fails, because then $-1$ would never be reached. A list must reach each element after finitely many steps. The fix is to start in the middle and alternate.
The fractions are countable too
The rationals look far more numerous. Between any two of them lies another (their average), so there is no “next” fraction after 0 and they cannot be listed in order of size. Many people expect this to be where countability fails.
The positive fractions can be laid out in a grid, with $\frac{p}{q}$ in column $p$ and row $q$. Reading along the rows fails for the reason that listing the positive integers first failed: the first row never ends. But the grid has another feature. The fractions with $p + q = 2$, then $p + q = 3$, then $p + q = 4$, lie along slanting lines, and each such line is finite.
The walk produces the list
with $\frac22$ skipped after $\frac31$ because its value, 1, is already listed.
Pause and try
Where is $\frac{3}{5}$ in this scheme: on which diagonal, and at most how many grid points does the walk visit before it must have reached it?
Show answerHide answer
$\frac35$ has $p + q = 8$, so it is on the diagonal $p + q = 8$, which is the seventh diagonal when $p + q = 2$ is counted as the first. The diagonal $p + q = s$ has $s - 1$ grid points, so the diagonals up to and including $p + q = 8$ hold $1 + 2 + \dots + 7 = 28$ points. The walk reaches $\frac35$ within its first 28 steps.
So the rationals, which are dense on the number line, are no more numerous than the counting numbers. At this point it is reasonable to suspect that every infinite set is countable, and that the definition has only one infinite size to offer.
The real numbers are not countable
Pause and try
Before reading on, commit to a guess. Can the real numbers between 0 and 1 be listed? If you think so, what would your scheme be? If not, how could anyone prove that no scheme works, given how many clever schemes there might be?
Show answerHide answer
They cannot. And the proof does not examine schemes one at a time: it takes an arbitrary list, whatever its origin, and builds from it a number that the list provably omits.
We will describe real numbers by their decimal expansions, and one technical point must be settled first. Some numbers have two expansions: $0.4999\ldots$ (nines forever) and $0.5000\ldots$ are the same number.
The expansion $0.4999\ldots$ means the limit of $0.49, 0.499, 0.4999, \dots$, and the number with $n$ nines differs from $0.5$ by exactly $\frac{1}{10^{n+1}}$, which is eventually smaller than any positive number you name. So the limit is $0.5$. (As a geometric series: $0.4 + \frac{9}{100}\left(1 + \frac1{10} + \frac1{100} + \dots\right) = 0.4 + \frac{9}{100} \cdot \frac{10}{9} = 0.5$.) This is the only way a number can have two expansions.
We use the first sentence as a known property of the real numbers. The second can be proved here.
Now take any list of real numbers between 0 and 1. The figure uses a particular list of seven; the method does not care what the list is.
Steps 1 and 4 are where the $0.4999\ldots = 0.5$ issue is paid for. Without them the argument has a hole: two expansions that differ in a digit can still be the same number, so “differs in the $n$th digit” would not give “is a different number”. Choosing the digits 5 and 6 keeps $x$ away from the only expansions that have this ambiguity.
Cantor first proved this in 1874 by a different method; the diagonal argument comes from a paper of 1891. It follows that $\mathbb{R}$ is uncountable as well: from a list of all real numbers we could strike out those outside $(0, 1)$ and be left with a list of all of $(0,1)$.
Cantor’s theorem: no largest infinity
The diagonal idea does not depend on decimals. For a set $A$, the power set $\mathcal{P}(A)$ is the set of all subsets of $A$. If $A = \{1, 2, 3\}$ then $\mathcal{P}(A)$ has the 8 elements $\varnothing, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}$. Try to pair the elements of $A$ with subsets of $A$, and describe each subset by a row of yes/no marks.
In the figure $D = \{2, 4\}$: it contains $a$ exactly when $f(a)$ does not. That one sentence is the whole proof, for every set.
For a finite set with $n$ elements the theorem says $n < 2^n$. For infinite sets it gives $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots$, an unending ladder, so there is no largest infinite size. The set $D$ is built the way Russell’s set was in the previous lesson, with $a \notin f(a)$ in place of $x \notin x$.
Worked examples
Common mistakes and edge cases
An edge case in the definitions: “uncountable” does not mean “infinite and hard to list”. The rationals have no listing in order of size, and they are countable all the same, because some other listing works. To prove a set uncountable you must defeat every possible list at once.
The continuum hypothesis
We now have two infinite sizes, $|\mathbb{N}|$ and $|\mathbb{R}|$. A further theorem, which we state without proof, says that $|\mathbb{R}| = |\mathcal{P}(\mathbb{N})|$; its proof describes a real number through its binary expansion, which is a set of positions holding a 1. Cantor asked whether anything lies in between.
Cantor believed it and could not prove it, and Hilbert put it first on his 1900 list of problems for the new century. Kurt Gödel showed in 1940 that the continuum hypothesis cannot be disproved from the standard axioms of set theory (called ZFC), and Paul Cohen showed in 1963 that it cannot be proved from them either, in both cases assuming those axioms are consistent. The hypothesis is independent of the axioms: adding it gives a consistent mathematics, and so does adding its negation.
Stepping back
The hard step was the first one, giving up “a part is smaller than the whole” in favor of pairing. After that, proving two sets the same size is a matter of exhibiting a list, and the craft is in arranging things so that every element is reached after finitely many steps: alternate, or sweep finite diagonals. Proving two sets different in size is harder, because it means defeating all pairings, and the diagonal construction is the tool: let the supposed pairing itself tell you how to build something it missed. The same construction gives Russell’s paradox and Cantor’s theorem, and in computer science it shows that some problems cannot be solved by any program.
Check yourself
Which of these sets is not countable?
Problems
Problems 1 to 3 repeat the moves of the lesson, 4 and 5 combine them, and 6 and 7 go further.
Problem 1
(a) Give a bijection from $\mathbb{N}$ to the set of odd counting numbers and prove that it is one. (b) Give a bijection from $\mathbb{N}$ to $\{10, 11, 12, \dots\}$.
Show solutionHide solution
(a) $f(n) = 2n - 1$. Injective: $2n - 1 = 2n' - 1$ gives $n = n'$. Surjective: an odd counting number is $m = 2k - 1$ for some counting number $k$ (namely $k = \frac{m+1}{2}$, an integer at least 1 because $m$ is odd and at least 1), and $f(k) = m$. (b) $g(n) = n + 9$, with $g(1) = 10$. If $n + 9 = n' + 9$ then $n = n'$, and each $m \geq 10$ is $g(m - 9)$ with $m - 9 \geq 1$.
Problem 2
In the listing $0, 1, -1, 2, -2, \dots$ of the integers, at which positions do $50$ and $-50$ appear? Which integer is at position 99?
Show solutionHide solution
By the formula in the proof, the positive integer $k$ is at position $2k$ and $-k$ is at position $2k + 1$. So 50 is at position 100 and $-50$ at position 101. Position 99 is odd, $99 = 2 \cdot 49 + 1$, so it holds $-49$.
Problem 3
Let $A = \{1, 2, 3\}$ and let $f : A \to \mathcal{P}(A)$ be given by $f(1) = \{2, 3\}$, $f(2) = \{2\}$, $f(3) = \varnothing$. Find the set $D$ from the proof of Cantor’s theorem and check directly that it is not an output of $f$.
Show solutionHide solution
$D = \{a \in A : a \notin f(a)\}$. Since $1 \notin \{2, 3\}$, $1 \in D$. Since $2 \in \{2\}$, $2 \notin D$. Since $3 \notin \varnothing$, $3 \in D$. So $D = \{1, 3\}$. It differs from $f(1) = \{2,3\}$ on the element 1, from $f(2) = \{2\}$ on the element 2 (which is in $f(2)$ and not in $D$), and from $f(3) = \varnothing$ on the element 3.
Problem 4
A list of real numbers begins $r_1 = 0.50000\ldots$, $r_2 = 0.25555\ldots$, $r_3 = 0.33333\ldots$, $r_4 = 0.12345\ldots$, $r_5 = 0.99995\ldots$ Find the first five digits of the diagonal number $x$ from the proof. You know only five digits of $x$ and five digits of $r_2$. Why can you already be sure that $x \neq r_2$?
Show solutionHide solution
The diagonal digits are $a_{11} = 5$, $a_{22} = 5$, $a_{33} = 3$, $a_{44} = 4$, $a_{55} = 5$. The rule gives $d_1 = 6$, $d_2 = 6$, $d_3 = 5$, $d_4 = 5$, $d_5 = 6$, so $x = 0.66556\ldots$ The expansion of $x$ differs from that of $r_2$ in the second digit (6 against 5). All digits of $x$ are 5 or 6, so $x$ has only one decimal expansion, and a number with only one expansion cannot equal a number whose expansion is different. The later digits do not matter.
Problem 5
Let $B$ be the set of all infinite sequences of 0s and 1s, such as $0, 1, 1, 0, 1, \dots$ (a) Prove that $B$ is uncountable. (b) Why is there no need to worry about a “$0.4999\ldots$ problem” here? (c) Show that the set of finite strings of 0s and 1s is countable.
Show solutionHide solution
(a) Let $f : \mathbb{N} \to B$ be any function, and write $f(n) = (b_{n1}, b_{n2}, b_{n3}, \dots)$. Define a sequence $t$ by $t_n = 1 - b_{nn}$. Then $t \in B$, and for each $n$ the sequences $t$ and $f(n)$ differ in the $n$th term, so $t \neq f(n)$. So $f$ is not surjective, and no bijection exists; $B$ is also infinite, so it is uncountable. (b) Two sequences are equal only when all their terms agree, by definition. The elements of $B$ are the sequences themselves, not numbers represented by them, so two different sequences are never the same element. (c) List the strings by length, and within each length in dictionary order: the empty string, then $0, 1$, then $00, 01, 10, 11$, and so on. There are $2^k$ strings of length $k$, a finite number, so every string is reached after finitely many steps and appears once.
Problem 6
A student argues: “The rationals between 0 and 1 are uncountable. Take any list of them, and form the diagonal number $x$. It is not on the list. So no list is complete.” Find the error. Then explain what, if anything, the argument does prove about $x$.
Show solutionHide solution
The diagonal construction produces a real number $x$ that is not on the list. To contradict “the list contains every rational in $(0,1)$” one would need $x$ to be rational, and nothing in the construction provides that. So there is no contradiction. In fact the rationals in $(0, 1)$ are countable, so a complete list exists, and for that list the argument proves that $x$ is irrational: $x$ is a real number in $(0, 1)$ different from every rational in $(0, 1)$.
Problem 7
(a) Let $S$ and $T$ be countably infinite sets with no element in common. Prove that $S \cup T$ is countably infinite. (b) Deduce that the set of irrational numbers is uncountable.
Show solutionHide solution
(a) Let $s_1, s_2, \dots$ and $t_1, t_2, \dots$ be lists of $S$ and $T$ in which each element appears once. Interleave them: $s_1, t_1, s_2, t_2, \dots$, that is, $h(2k - 1) = s_k$ and $h(2k) = t_k$. Every element of $S \cup T$ is some $s_k$ or some $t_k$, so it appears. No element appears twice, because the $s_k$ are distinct, the $t_k$ are distinct, and no $s_k$ equals a $t_j$ since the sets are disjoint. So $h$ is a bijection from $\mathbb{N}$ to $S \cup T$. (b) Suppose, for contradiction, that the set $I$ of irrational numbers is countable. It is not finite: the numbers $\sqrt 2 + n$ for $n = 1, 2, 3, \dots$ are all irrational (if $\sqrt 2 + n$ were a rational $r$, then $\sqrt 2 = r - n$ would be rational) and all different. So $I$ is countably infinite. The set $\mathbb{Q}$ is countably infinite, and $\mathbb{Q}$ and $I$ have no element in common. By part (a), $\mathbb{R} = \mathbb{Q} \cup I$ is countably infinite. But $\mathbb{R}$ is uncountable. This contradiction shows that $I$ is uncountable. In this sense almost all real numbers are irrational.