Lecture 2 - Diagonalization and Countability

Why Count the Infinite?

The deepest results in this course are impossibility results: problems no program can solve, resources no algorithm can avoid. This lecture builds the first impossibility tool, and it comes from a surprising place: comparing the sizes of infinite sets. By the end we will prove that some collections are strictly bigger than others even though both are infinite, and then cash that in for the course's first big theorem: there are more problems than there are programs, so some problems have no program at all. The technique that powers all of it, diagonalization, will return in Lecture 11 to point at a specific unsolvable problem, and again in Lecture 19 to separate complexity classes. One idea, three of the biggest theorems we will see.

Same Size, Without Counting

How do you compare the sizes of two sets you cannot count? Match their elements. Two shepherds with no number system can still check whose flock is bigger: pair the sheep off one against one and see which flock runs out first. If the pairing comes out even, the flocks are the same size. The same idea is the only one that survives the jump to infinite sets, so we take it as the definition.

Definition. A set $S$ is countable if it is finite or its elements can be arranged in a single infinite list $s_1, s_2, s_3, \ldots$ in which every element of $S$ appears at some finite position. A set that is not countable is uncountable.

A list is exactly a pairing with the positive integers: position 1, position 2, and so on. So "countable" means "no bigger than the counting numbers." The burden in a countability proof is the phrase every element appears at some finite position: you must be able to point at an arbitrary element and say where in the list it shows up. (Lecture 3 does pairings, that is, functions and bijections, carefully; for today the list picture is all we need.)

Example 1: the even natural numbers are countable

Claim. The set $\{0, 2, 4, 6, \ldots\}$ of even natural numbers is countable.

Proof. List them in increasing order: $s_1 = 0$ , $s_2 = 2$ , $s_3 = 4$ , and in general $s_i = 2(i-1)$ . Every even natural number $2k$ appears at the finite position $i = k + 1$ , so this list contains every element of the set. $\blacksquare$

What to notice

The even numbers are a proper part of the naturals, yet the definition says the two sets are the same size. Infinite sets do this; "part of" and "smaller than" come apart.

Example 2: the integers are countable

Claim. The set $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$ is countable.

Proof. Listing the integers in increasing order doesn't work: there is no smallest integer to put first. Instead, we interleave outward from zero:

0,\; 1,\; -1,\; 2,\; -2,\; 3,\; -3,\; \ldots

Every integer appears at a finite position: $0$ at position 1, and for $k \geq 1$ , the integer $k$ at position $2k$ and the integer $-k$ at position $2k + 1$ . $\blacksquare$

What to notice

Countability is about the existence of some list. When the natural ordering fails, reorder. This move gets stronger in the next example.

Example 3: the positive rationals are countable

Claim. The set of positive rational numbers is countable.

Proof. Arrange the positive rationals in an infinite grid: row $a$ , column $b$ holds the fraction $a/b$ .

\begin{array}{ccccc} 1/1 & 1/2 & 1/3 & 1/4 & \cdots \\ 2/1 & 2/2 & 2/3 & 2/4 & \cdots \\ 3/1 & 3/2 & 3/3 & 3/4 & \cdots \\ 4/1 & 4/2 & 4/3 & 4/4 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{array}

Walking one row at a time never finishes the first row, so instead walk the short diagonals: first every fraction with $a + b = 2$ (just $1/1$ ), then every fraction with $a + b = 3$ (namely $2/1, 1/2$ ), then $a + b = 4$ , and so on, skipping any fraction equal to one already listed (skip $2/2$ because $1/1$ is already there). Each diagonal is finite, and the fraction $a/b$ lies on diagonal number $a + b - 1$ , so it is reached after finitely many finite diagonals: a finite position. Every positive rational appears, so the list works. $\blacksquare$

What to notice

The trick is to sweep by a finite quantity (here $a + b$ ) so that no infinite row blocks the walk. This scheduling move is called dovetailing, and it is not just for counting: in Unit 2 we will run infinitely many computations "in parallel" by dovetailing their steps, using exactly this picture.

Cantor's Diagonal Argument

Everything so far says infinite sets keep turning out countable if you list them cleverly enough. Cantor's discovery is that this streak ends. The cleanest uncountable set, and the one this course actually needs, is the set of infinite binary sequences.

Definition. An infinite binary sequence is an unending string of bits, one bit for each position $1, 2, 3, \ldots$ (for example $010110\cdots$ ).

Example 4: the infinite binary sequences are uncountable

Claim. The set of all infinite binary sequences is uncountable.

Proof. Suppose, for the sake of contradiction, that the set is countable. Then there must be a list $s_1, s_2, s_3, \ldots$ in which every infinite binary sequence appears at some finite position. Write the list as a table, one sequence per row, one bit position per column. For instance, it might begin:

\begin{array}{c|ccccc} & 1 & 2 & 3 & 4 & \cdots \\ \hline s_1 & \mathbf{0} & 1 & 0 & 1 & \cdots \\ s_2 & 1 & \mathbf{1} & 0 & 0 & \cdots \\ s_3 & 0 & 0 & \mathbf{0} & 1 & \cdots \\ s_4 & 1 & 0 & 1 & \mathbf{1} & \cdots \\ \vdots & & & & & \ddots \end{array}

Build a new sequence $d$ by walking down the diagonal (bolded above) and flipping every bit: the $n$ -th bit of $d$ is defined to be the opposite of the $n$ -th bit of $s_n$ . In the table above, $d$ begins $1, 0, 1, 0, \ldots$

Now $d$ is an infinite binary sequence, so by assumption it appears somewhere in the list, say $d = s_n$ . But $d$ was built to differ from $s_n$ at position $n$ : one of them has a $0$ there and the other has a $1$ . A sequence cannot differ from itself at any position, which is impossible. Therefore no such list exists, and the set is uncountable. $\blacksquare$

What to notice

The diagonal is what lets one new object rule out every row at once: $d$ differs from row $n$ at position $n$ , so $d$ equals no row. The proof does not say where $d$ is missing from the list. It says $d$ is missing from any proposed list, which is why no cleverness in building the list can help.

Common misunderstandings

First, flipping bits somewhere other than the diagonal: $d$ must differ from $s_n$ at position $n$ specifically, or the " $d = s_n$ is impossible" step collapses. Second, concluding only that one particular list fails; the proof starts from an arbitrary list, so it rules out all of them. Third, "the set is infinite, so it is uncountable": Examples 1 through 3 are infinite and countable.

More Problems Than Programs

Now we arrive at the promised impossibility result: there are more problems than there are programs, so some problems have no program at all. The diagonal argument is the tool that makes proving this possible.

Example 5: the finite binary strings are countable

Claim. The set of all finite binary strings $\{\varepsilon, 0, 1, 00, 01, 10, 11, 000, \ldots\}$ is countable (where $\varepsilon$ is the empty string).

Proof. List the strings in order of length, and within each length alphabetically, exactly as written in the claim. There are $2^\ell$ strings of length $\ell$ , a finite number, so the strings of each length occupy a finite stretch of the list, and a string of length $\ell$ appears after the $2^0 + 2^1 + \cdots + 2^{\ell - 1}$ strings shorter than it, at a finite position. $\blacksquare$

What to notice

Same move as Example 3: sweep by a finite quantity (there, $a + b$ ; here, length) so nothing infinite blocks the walk. Listing all strings alphabetically without the length sweep fails the same way the rationals did: $0, 00, 000, \ldots$ never finishes, and $1$ never gets a position.

A program in any programming language is, in the end, a finite string of characters, and characters can be encoded in binary, so a program is a finite binary string. By Example 5, there are countably many programs. This is not a fact about today's languages, but much more general. Any notion of program in which a program is a finite description gives a countable set.

A decision problem over binary inputs asks a yes/no question about every finite binary string: given a string, does it have the property or not. Describing a problem completely means giving its answer for every string, and there is a compact way to do that. Fix the Example 5 listing of all finite binary strings $x_1, x_2, x_3, \ldots$ (so $x_1 = \varepsilon$ , $x_2 = 0$ , $x_3 = 1$ , $x_4 = 00$ , and so on), and write down the problem's answers in that fixed order, one bit per string: bit $n$ is $1$ if the answer on $x_n$ is yes, and $0$ if it is no. The result is an infinite binary sequence, the problem's answer sequence. For example, the problem "does the string have even length?" has answer sequence $1, 0, 0, 1, 1, 1, 1, 0, \ldots$ : the answer is yes on $x_1 = \varepsilon$ (length 0), no on the two strings of length 1, yes on all four strings of length 2, no on the strings of length 3, and so on.

This is a pairing in the shepherds' sense from the start of the lecture. Each decision problem is matched with exactly one infinite binary sequence (its answer sequence), and each infinite binary sequence is matched with exactly one decision problem (the problem whose answer on $x_n$ is the sequence's bit $n$ ). Two different problems disagree about at least one string $x_n$ , so their answer sequences differ at bit $n$ . So by Example 4, there are uncountably many decision problems.

Example 6: some problems no program solves

Claim. There is a decision problem that no program solves.

Proof. Suppose, for the sake of contradiction, that every decision problem is solved by some program. Each program solves at most one decision problem (the problem defined by its yes answers), so listing all programs $p_1, p_2, p_3, \ldots$ (countable, by Example 5) and replacing each program with the answer sequence of the problem it solves produces a list of infinite binary sequences containing, by assumption, every decision problem's answer sequence. That is a countable list containing all infinite binary sequences, contradicting Example 4. $\blacksquare$

What to notice

Pure counting, no computation: we never looked inside a program. The argument is also unsettlingly non-constructive; it proves unsolvable problems exist without naming even one. Naming one is genuinely harder, and it is exactly what Lecture 11 does, by running today's diagonal argument with programs as the rows and inputs as the columns. When you get there, this table is the picture to have in mind.

Exercises

These are not collected or graded; they are your study material, and the exams will look like them. Each exercise echoes an example above; if one feels unfamiliar, find the example it echoes and re-read its "What to notice" box.

Exercise 1

Prove that the set of all pairs $(a, b)$ of positive integers is countable (Example 3's grid, without the duplicate-skipping wrinkle).

Solution

Arrange the pairs in a grid: row $a$ , column $b$ holds $(a, b)$ . Walk the short diagonals: first all pairs with $a + b = 2$ , then $a + b = 3$ , then $a + b = 4$ , and so on. Each diagonal holds finitely many pairs ( $a + b = k$ has $k - 1$ of them), and the pair $(a, b)$ lies on diagonal $a + b - 1$ , so it appears after finitely many finite diagonals: a finite position. Unlike Example 3, no two pairs are equal, so nothing is skipped. $\blacksquare$

Exercise 2

Prove that the union of two countable sets is countable (Example 2's interleaving move).

Solution

Let $A$ and $B$ be countable, with lists $a_1, a_2, \ldots$ and $b_1, b_2, \ldots$ (if either is finite, repeat its last element forever, or simply append the other list after it and be done). Interleave: $a_1, b_1, a_2, b_2, a_3, b_3, \ldots$ , skipping any element already listed (an element of both sets appears only once). Every $a_i$ appears at position at most $2i - 1$ and every $b_j$ at position at most $2j$ , both finite. Every element of $A \cup B$ is some $a_i$ or some $b_j$ , so it appears at a finite position. $\blacksquare$

Exercise 3

Prove that the set of all finite subsets of the positive integers is countable (Example 5's sweep, with a twist: find the right finite quantity to sweep by).

Solution

Sweep by maximum element. For each $m \geq 1$ , the finite sets whose largest element is $m$ are the subsets of $\{1, \ldots, m-1\}$ with $m$ added, and there are $2^{m-1}$ of them, a finite number. List the empty set first, then the sets with maximum 1, then maximum 2, and so on, in any fixed order within each group. A finite set $S$ with maximum $m$ appears within the first $1 + 2^0 + 2^1 + \cdots + 2^{m-1}$ positions, which is finite. $\blacksquare$

An alternative solution encodes each finite subset $S$ as the finite binary string whose $i$ -th bit is 1 exactly when $i \in S$ (dropping trailing zeros); distinct finite sets get distinct strings, and the finite binary strings are countable by Example 5.

Exercise 4

Let $f_1, f_2, f_3, \ldots$ be any list of functions from the positive integers to the positive integers. Construct a function $g$ that appears nowhere in the list, and prove it (Example 4 with numbers instead of bits).

Solution

Define $g(n) = f_n(n) + 1$ for every positive integer $n$ ; this is a function from positive integers to positive integers. Suppose, for the sake of contradiction, that $g$ appears in the list, say $g = f_n$ . Then in particular $g(n) = f_n(n)$ . But by construction $g(n) = f_n(n) + 1 \neq f_n(n)$ , which is impossible. So $g$ is not any $f_n$ . The diagonal here is "evaluate function $n$ at input $n$ "; adding 1 plays the role of flipping the bit. $\blacksquare$

Exercise 5

Is the set of infinite binary sequences that contain only finitely many 1s countable or uncountable? Prove your answer. Be careful: Example 4 is about all infinite binary sequences, and the diagonal it builds may not live in this smaller set.

Solution

Countable. A sequence with finitely many 1s is completely determined by the finite set of positions where its 1s occur, and distinct sequences give distinct finite sets. So the set in question matches up with (a subset of) the finite subsets of the positive integers, which is countable by Exercise 3; listing those finite sets and writing down each one's sequence lists every sequence in our set at a finite position. $\blacksquare$

This is why the warning in Example 4 matters: you cannot conclude uncountability just because the objects are infinite sequences. Running the diagonal argument on a list of these sequences does produce a sequence not in the list, but that diagonal sequence may have infinitely many 1s, in which case it was never required to be in the list, and there is no contradiction.

Exercise 6

Where does the diagonal argument break if you run it on Example 5's list of all finite binary strings? Point at the exact step that fails (compare the $\sqrt{4}$ question from Lecture 1).

Solution

The construction of $d$ still "works": flip the $n$ -th bit of the $n$ -th string (where defined). But $d$ has a bit at every position $n$ , so $d$ is an infinite binary sequence, not a finite binary string. The contradiction step "d must appear in the list" fails because the list only promised to contain every finite string, and $d$ is not one. No contradiction, no theorem; the finite strings stay countable. The lesson, same as $\sqrt{4}$ : a proof technique is not a ritual, and checking where an argument stops working tells you what it was really using, here that the diagonal object must be a member of the set being listed. $\blacksquare$

Updated Jul 27, 2026