Chapter 10: Cardinality and Infinity

"No one shall expel us from the paradise that Cantor has created for us." — David Hilbert

Overview

Your programs run on finite machines, but they reason about infinite things all the time. The set of all strings. The set of all valid JSON documents. The set of all functions of type int -> int. The set of all programs you could ever write. Every one of these is infinite, and a working programmer treats them casually — "iterate over all inputs," "for any string s," "consider every function."

This chapter asks a question that sounds like philosophy but turns out to be the most practical question in computer science: are all these infinities the same size? If they are, then in principle every problem could have a program, because there would be exactly as many programs as there are problems. If some infinity is strictly larger than another, then there must be problems with no program — tasks that are perfectly well-defined and yet impossible to compute, not because we are not clever enough, but because the arithmetic of infinity forbids it.

That second answer is the true one, and proving it is the goal of this chapter. The argument is due to Georg Cantor, and it is one of the most beautiful proofs in mathematics: a single, devastating trick called diagonalization that you will be able to run yourself by the end of section 10.3, and that reappears — almost verbatim — when we prove the halting problem unsolvable in Chapter 36. Cantor was attacked for these ideas in his lifetime. Today they are the foundation under every statement that begins "no algorithm can…".

The leap you have to make is this: size is not about counting, because you cannot count to infinity. Size is about matching. Two sets have the same size when you can pair their elements off perfectly — a bijection, the exact notion you built in Chapter 9. Once size means matching, infinite sets stop being a single fog called "infinity" and resolve into a precise hierarchy, with the integers near the bottom and the real numbers strictly above them.

In this chapter, you will learn to:

• Measure and compare set sizes by matching elements rather than counting them.
• Prove a set is countable by writing down an explicit way to list all its elements.
• Show that the integers and the rationals are countable — and feel why that is surprising.
• Run Cantor's diagonal argument to prove the real numbers are uncountable.
• Draw the consequence that uncomputable problems must exist, before we ever define "computable."
• Locate $\mathbb{N}$, $\mathbb{R}$, and the set of all programs in the hierarchy of infinities.

Throughout this chapter, $\mathbb{N} = \{0, 1, 2, 3, \dots\}$ — the natural numbers including 0. This convention matters here more than anywhere else in the book, because $\mathbb{N}$ is our measuring stick for "countable," and whether the stick starts at 0 or 1 changes nothing about its length but everything about clean notation.

Learning Paths

🏃 Fast Track: If you only have time for the headline result, read 10.1 (what "same size" means), then 10.3 (diagonalization — the heart of the chapter), then 10.4 (the CS payoff). Skim 10.2 for the claim that $\mathbb{Z}$ and $\mathbb{Q}$ are countable; you can take it on faith for now. Do the ⭐⭐ and ⭐⭐⭐ exercises.

📖 Standard Path: Read in order. The chapter is a single argument that builds: matching (10.1) → the countable infinities (10.2) → the first uncountable one (10.3) → the consequence for programs (10.4). Work every 🔄 Check Your Understanding before moving on, and try to construct the diagonalization in 10.3 yourself before reading ours.

🔬 Deep Dive: After the chapter, prove the Cantor–Schröder–Bernstein theorem's statement holds for the examples here, prove Cantor's theorem ($\lvert S \rvert < \lvert \mathcal{P}(S)\rvert$ for every set), and read ahead to how 10.4's counting argument becomes the formal undecidability proof in Chapter 36. Exercise set, Part E.

10.1 Sizing sets by matching

Start with something you already know cold. How do you know that the set $\{a, b, c\}$ and the set $\{1, 2, 3\}$ have the same size? The lazy answer is "count them — both have three elements." But counting is secretly doing something subtler. To count $\{a, b, c\}$ you point at one element and say "one," another and say "two," the last and say "three." You are building a pairing:

$$a \leftrightarrow 1, \qquad b \leftrightarrow 2, \qquad c \leftrightarrow 3.$$

Counting is matching the set against $\{1, 2, 3\}$. The number "three" is just the name of the yardstick you matched it to. This is worth pausing on, because it is the idea that survives the jump to infinity, where counting cannot follow.

💡 Intuition: A shepherd with no number words can still know whether every sheep came home: keep a bag of pebbles, one pebble per sheep. In the morning, pair each departing sheep with a pebble; in the evening, pair each returning sheep with a pebble. If the pebbles run out exactly, the flock is intact. The shepherd never counted — he matched. Matching needs no numbers, and that is why it reaches places numbers cannot.

Recall from Chapter 9 the three ways a function $f\colon A \to B$ can behave: it is injective (one-to-one — distinct inputs go to distinct outputs), surjective (onto — every element of $B$ is hit), or bijective (both at once — a perfect pairing with no element of either set left over and none used twice). A bijection is exactly the formal version of the shepherd's pebble-pairing.

🔗 Connection. A bijection $f\colon A \to B$ is invertible: $f^{-1}\colon B \to A$ exists and is also a bijection (Chapter 9, §9.4). That symmetry is why "same size" will behave the way an equality should — if $A$ matches $B$, then $B$ matches $A$.

The definition of "same size"

For finite sets, Chapter 8 gave you cardinality $\lvert S \rvert$ as the count of elements. We now extend the idea to all sets, finite or infinite, using matching instead of counting.

Definition (equinumerous / same cardinality). Two sets $A$ and $B$ are equinumerous, written $\lvert A \rvert = \lvert B \rvert$, if there exists a bijection $f\colon A \to B$. We say they have the same cardinality. More generally, $\lvert A \rvert \le \lvert B \rvert$ means there is an injection $A \to B$ (a copy of $A$ fits inside $B$), and $\lvert A \rvert < \lvert B \rvert$ means $\lvert A \rvert \le \lvert B \rvert$ but $\lvert A \rvert \ne \lvert B \rvert$ (a copy fits, but no bijection exists).

Notice what this definition does not require: it never mentions a number. For finite sets it agrees with counting — there's a bijection between $A$ and $B$ exactly when they have the same number of elements — so we lose nothing. But it keeps working when the sets are infinite, where "the number of elements" is not yet defined. We are about to discover that this is not a harmless extension. It forces conclusions that offended mathematicians for a generation.

The first surprise: a set the same size as a proper part of itself

Here is where infinity stops behaving like a big finite number.

Claim. The set $\mathbb{N} = \{0, 1, 2, \dots\}$ and the set of even naturals $E = \{0, 2, 4, \dots\}$ are equinumerous, $\lvert \mathbb{N} \rvert = \lvert E \rvert$ — even though $E$ is a proper subset of $\mathbb{N}$ (it is missing every odd number).

The strategy first. To prove two sets equinumerous, we do exactly one thing: build a bijection between them and check it is one. We do not argue about "how many" elements each has. The map that suggests itself is "double it" — every natural $n$ pairs with the even number $2n$.

Proof. Define $f\colon \mathbb{N} \to E$ by $f(n) = 2n$.

• Injective: if $f(m) = f(n)$ then $2m = 2n$, so $m = n$. Distinct inputs give distinct outputs.
• Surjective: take any even number $e \in E$. By definition $e = 2k$ for some $k \in \mathbb{N}$, and then $f(k) = 2k = e$. So every element of $E$ is hit.

Since $f$ is injective and surjective, it is a bijection, and therefore $\lvert \mathbb{N} \rvert = \lvert E \rvert$. $\blacksquare$

🚪 Threshold Concept. A finite set can never be the same size as a proper subset of itself — remove an element and it shrinks. Infinite sets can. In fact, this is the definition of infinite that Dedekind gave: a set is infinite exactly when it is equinumerous with a proper subset of itself. Infinity is not "a very large number." It is the regime where part can equal whole. Every strange result in this chapter flows from making peace with that one sentence — so sit with it before moving on.

⚠️ Common Pitfall: "But $E$ obviously has half as many elements as $\mathbb{N}$!" Your finite intuition says removing every other element should halve the size. For finite sets it does. For infinite sets, "half of infinity" is not smaller — the bijection $n \leftrightarrow 2n$ proves they match perfectly, with nothing left over on either side. The intuition you must drop is that a proper subset is always strictly smaller. The intuition to keep is: trust the bijection, not the picture. If you can build a perfect pairing, the sets are the same size, full stop.

Here is the same fact in code. We cannot enumerate an infinite set, but we can exhibit the rule of the bijection and verify it agrees on a finite window, which is exactly the "compute to test, prove to be sure" division of labor that runs through this book.

# The bijection f: N -> E (evens), f(n) = 2n, and its inverse g(e) = e // 2.
def f(n):  return 2 * n          # natural  -> even natural
def g(e):  return e // 2         # even natural -> natural

# Check f and g are inverse on a finite window (evidence, not proof):
print([f(n) for n in range(6)])          # the evens, in order
print(all(g(f(n)) == n for n in range(1000)))   # round-trip holds?
# Expected output:
# [0, 2, 4, 6, 8, 10]
# True

The True says: on the first thousand naturals, doubling then halving returns the original — evidence that $f$ and $g$ invert each other. The proof above settles it for all $n$ at once. (Theme four: computation tests the conjecture; the proof closes it.)

🔄 Check Your Understanding 1. To prove $\lvert A \rvert = \lvert B \rvert$, what single object must you produce, and what two properties must it have? 2. Is the function $h\colon \mathbb{N} \to \mathbb{N}$ given by $h(n) = n + 1$ a bijection from $\mathbb{N}$ to $\mathbb{N}$? What does your answer say about $\lvert \mathbb{N} \rvert$ versus $\lvert \mathbb{N} \setminus \{0\}\rvert$? 3. Why does the "doubling" argument not prove that the set $\{0, 2\}$ equals the set $\{0\}$ in size?

Answers

1. A function from $A$ to $B$ that is injective (one-to-one) and surjective (onto) — i.e., a bijection. 2. Yes: $h$ is injective ($m+1 = n+1 \Rightarrow m=n$) and surjective onto $\{1,2,3,\dots\}$. It is a bijection from $\mathbb{N}$ onto $\mathbb{N}\setminus\{0\}$, so those two sets are equinumerous — again a whole equals a proper part, the signature of an infinite set.
2. Because $\{0,2\}$ and $\{0\}$ are finite: any function from a 2-element set onto a 1-element set must send two inputs to the same output, so it cannot be injective. No bijection exists; the part-equals-whole trick is available only to infinite sets.

10.2 Countable sets: the integers and the rationals

We now have a yardstick. The most basic infinite set is $\mathbb{N}$ itself, and we give the sets that match it a name.

Definition (countably infinite, countable). A set $S$ is countably infinite if it is equinumerous with $\mathbb{N}$, i.e. there is a bijection $\mathbb{N} \to S$. A set is countable if it is finite or countably infinite. A set that is not countable is uncountable (the subject of 10.3).

Unwinding the definition gives a wonderfully concrete test. A bijection $f\colon \mathbb{N} \to S$ is the same thing as an infinite list with no repeats and no omissions: $$f(0),\ f(1),\ f(2),\ f(3),\ \dots$$ So: a set is countable exactly when you can arrange all of its elements in a single (possibly infinite) list $s_0, s_1, s_2, \dots$ such that every element appears exactly once. "Countable" really does mean "you could count them off, $0, 1, 2, \dots$, and eventually name any particular one." This list-based view is the one to carry into every proof below.

💡 Intuition: Countable = enumerable = "there is a program that, left running forever, would eventually print any given element." It does not mean the printing ever finishes (it can't — there are infinitely many). It means nothing is skipped: name an element, and it has a finite position in the list. That "every element shows up at some finite step" is the whole content of countability, and it is exactly what a generator function expresses in code.

The integers are countable

The integers $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$ run off to infinity in both directions. There is no "first" integer to start a list from, so the naive list $0, 1, 2, \dots$ misses everything negative. The fix is the one idea you need for all of countability: don't go straight to infinity in one direction — zig-zag.

Claim. $\mathbb{Z}$ is countably infinite.

The strategy first. We need a single list that catches every integer. List them by absolute value, alternating signs: $0, 1, -1, 2, -2, 3, -3, \dots$. Every integer clearly appears once. To turn that picture into a bijection we just need a formula for the function — but honestly, the list itself already is the proof; the formula is bookkeeping.

Proof. Define $f\colon \mathbb{N} \to \mathbb{Z}$ by $$f(n) = \begin{cases} n/2 & \text{if } n \text{ is even},\\[2pt] -(n+1)/2 & \text{if } n \text{ is odd}.\end{cases}$$ This produces $f(0)=0,\ f(1)=-1,\ f(2)=1,\ f(3)=-2,\ f(4)=2,\dots$ — the zig-zag list. We check it is a bijection. Every non-negative integer $k$ is $f(2k)$, and every negative integer $-k$ (with $k \ge 1$) is $f(2k-1)$, so $f$ is surjective. And no two inputs collide: even inputs produce the non-negative integers and odd inputs produce the negative ones (two disjoint ranges), and within each parity $f$ is clearly one-to-one. Hence $f$ is a bijection and $\mathbb{Z}$ is countably infinite. $\blacksquare$

# The zig-zag bijection N -> Z: 0, -1, 1, -2, 2, -3, 3, ...
def z(n):
    return n // 2 if n % 2 == 0 else -(n + 1) // 2

print([z(n) for n in range(7)])
# Expected output:
# [0, -1, 1, -2, 2, -3, 3]

🔗 Connection. "Zig-zag so you never get stranded at infinity" is not just a cute trick; it is the design principle behind fair scheduling. A web server interleaving infinitely many possible request streams, or an operating system round-robining processes, is doing exactly this: visiting sources in an order that guarantees no source waits forever. Countability arguments and fairness arguments are the same shape.

The rationals are countable (the genuinely surprising one)

Now brace yourself. The rationals $\mathbb{Q}$ are dense: between any two of them lie infinitely many more. Between $0$ and $1$ alone sit $\tfrac12, \tfrac13, \tfrac14, \dots$ and uncountably-looking swarms of fractions. Surely a set that crowded must be bigger than the sparse, evenly-spaced $\mathbb{N}$?

No. They are the same size.

Claim. $\mathbb{Q}$ is countably infinite.

The strategy first. We cannot list the rationals in increasing order — there is no "next" rational after $0$. Cantor's idea is to ignore size-order entirely and organize fractions in a grid: row $i$, column $j$ holds the fraction $i/j$. The grid is two-dimensional and infinite, but we can sweep it along diagonals, which are each finite. Sweeping diagonal by diagonal visits every cell of the grid in a single list — so it visits every fraction. (Skip cells whose fraction already appeared in lowest terms, to avoid repeats.) The headline: a countable union of countable sets is countable, and the grid is the picture of that fact.

Proof (sketch, positive rationals; the construction is the proof). Arrange the positive fractions in an infinite grid, with numerator $i \ge 1$ choosing the row and denominator $j \ge 1$ choosing the column:

            j=1    j=2    j=3    j=4    j=5   ...
   i=1      1/1    1/2    1/3    1/4    1/5
   i=2      2/1    2/2    2/3    2/4    2/5
   i=3      3/1    3/2    3/3    3/4    3/5
   i=4      4/1    4/2    4/3    4/4    4/5
    .
    .

Every positive rational $p/q$ sits somewhere in this grid (in row $p$, column $q$). Now traverse the grid along its anti-diagonals — the cells where $i + j$ is constant. The first anti-diagonal is just $1/1$; the next is $2/1, 1/2$; the next $3/1, 2/2, 1/3$; and so on. Each anti-diagonal is finite, so listing them in order $i+j = 2, 3, 4, \dots$ produces one infinite list: $$\tfrac11,\ \tfrac21,\ \tfrac12,\ \tfrac31,\ \tfrac22,\ \tfrac13,\ \tfrac41,\ \tfrac32,\ \tfrac23,\ \tfrac14,\ \dots$$ This list hits every cell, hence every positive rational — at a finite position. Discard any fraction whose value already appeared earlier in lowest terms (so $2/2$ is skipped because $1/1$ came first), and what remains is each positive rational exactly once: an enumeration. Adding $0$ and interleaving the negatives by the same zig-zag as for $\mathbb{Z}$ extends this to all of $\mathbb{Q}$. Therefore $\mathbb{Q}$ is countably infinite. $\blacksquare$

💡 Intuition: The diagonal sweep is the whole trick, and it is the opposite of the diagonalization we meet in 10.3. Here, going along diagonals lets us catch everything in one list (countability). In 10.3, going along a diagonal will let us escape any list someone proposes (uncountability). Same geometric word, two mirror-image uses — keep them straight and the chapter snaps into focus.

The grid argument generalizes to a theorem you will use again and again.

Theorem (countable unions). A union of countably many countable sets is countable.

Why: line the sets up as the rows of a grid (set $i$'s elements fill row $i$) and sweep the anti-diagonals exactly as above. Every element gets a finite position. We will lean on this in Chapter 36 to argue that the set of all programs is countable.

Here is the diagonal enumeration of grid positions in code — the engine behind "countable union of countables." It pairs each step $n = 0, 1, 2, \dots$ with a grid cell $(i, j)$, visiting them along anti-diagonals:

# Enumerate grid cells (i, j) along anti-diagonals: a bijection N -> N x N.
def cell(n):
    d = 0                      # find the anti-diagonal: largest d with d(d+1)/2 <= n
    while (d + 1) * (d + 2) // 2 <= n:
        d += 1
    k = n - d * (d + 1) // 2   # position within the diagonal
    return (d - k, k)          # (i, j) with i + j = d

print([cell(n) for n in range(6)])
# Expected output:
# [(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2)]

Read the output as: step 0 visits $(0,0)$; steps 1–2 visit the $i+j=1$ diagonal; steps 3–5 visit the $i+j=2$ diagonal. Every cell of the infinite grid gets a finite step number — which is precisely what "$\mathbb{N} \times \mathbb{N}$ is countable" means, and the same idea shows $\mathbb{Q}$ is countable.

🔄 Check Your Understanding 1. Restate "the set $S$ is countable" in terms of a list. What two properties must the list have? 2. Why can't we list the rationals "in order from smallest to largest" the way we might try to list $\{1, 2, 3, \dots\}$? 3. The anti-diagonal sweep visits cell $(i,j)$ at a finite step. Why is "finite step for every element" the entire requirement for countability — why don't we care that the list never ends?

Answers

1. $S$ is countable iff its elements can be arranged in a list $s_0, s_1, s_2, \dots$ with no repeats (injective) and no omissions (every element appears) — equivalently, a bijection $\mathbb{N} \to S$ (or onto a finite initial segment, if $S$ is finite). 2. Between any two rationals there are infinitely many more, so there is no "next" rational — an increasing list would have to skip the infinitely many values squeezed between consecutive entries. Order by position in a grid instead of by value. 3. Countability only asks that naming an element pins it to a finite position; the list running forever is fine because we never need to finish it, only to locate any particular element after finitely many steps. (This is exactly the behavior of a generator.)

10.3 Cantor's diagonalization: the real numbers are uncountable

Everything so far has pushed one way: $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{N} \times \mathbb{N}$ — all countable, all "the same size," all listable. You could be forgiven for guessing that every infinite set is countable, that "infinite" just means "countably infinite" and there is only one size of infinity. For roughly two thousand years of mathematics, that was the unspoken assumption.

Cantor shattered it in 1891 with two pages of reasoning. The real numbers $\mathbb{R}$ — or even just the reals between $0$ and $1$ — cannot be listed. There is no bijection $\mathbb{N} \to \mathbb{R}$, not because no one has been clever enough to find one, but because the existence of any such list leads to a contradiction. $\mathbb{R}$ is uncountable: strictly larger than $\mathbb{N}$.

The strategy first. This is a proof by contradiction (Chapter 5), and the move is the most elegant in the subject. Assume you have a complete list of all reals in $[0,1)$. We will then build a single real number that cannot be anywhere on your list — by walking down the diagonal of the list and disagreeing with each listed number in its own decimal place. The constructed number differs from the $n$-th listed number at digit $n$, so it can't equal the $n$-th number, for any $n$. Yet it is a perfectly good real in $[0,1)$, so the list was not complete after all. Since this defeats any proposed list, no complete list exists.

🔗 Connection. Look back at 10.2: we swept along diagonals to gather every element into a list. Here we walk down the diagonal to construct an element that evades every list. Cantor invented the diagonal sweep to prove countability and the diagonal dodge to prove uncountability — the same geometry, aimed in opposite directions. That symmetry is why both ideas share the name diagonalization.

Theorem (Cantor, 1891). The set of real numbers in the interval $[0, 1)$ is uncountable. Hence $\mathbb{R}$ is uncountable, and $\lvert \mathbb{N} \rvert < \lvert \mathbb{R} \rvert$.

Proof. Suppose, for contradiction, that $[0,1)$ is countable. Then its elements can be written as a list $r_0, r_1, r_2, \dots$ containing every real in $[0,1)$. Write each $r_n$ by its decimal expansion $r_n = 0.d_{n0}\,d_{n1}\,d_{n2}\,d_{n3}\dots$, where $d_{nk}$ is the $k$-th digit after the decimal point of the $n$-th number. (To make expansions unique, forbid those ending in an infinite tail of 9s, so e.g. we write $0.5000\dots$ rather than $0.4999\dots$.) Lay the list out as an infinite table; the diagonal digits $d_{00}, d_{11}, d_{22}, \dots$ are highlighted:

        digit 0   digit 1   digit 2   digit 3  ...
  r_0    [d00]      d01       d02       d03
  r_1     d10      [d11]      d12       d13
  r_2     d20       d21      [d22]      d23
  r_3     d30       d31       d32      [d33]
   .                                          .
   .                                            .

Now build a new number $x = 0.x_0 x_1 x_2 x_3 \dots$ by choosing each digit to differ from the diagonal. A clean rule (that also dodges the 9s-tail subtlety): $$x_k = \begin{cases} 5 & \text{if } d_{kk} \ne 5,\\ 4 & \text{if } d_{kk} = 5.\end{cases}$$ So every digit of $x$ is either 4 or 5, and crucially $x_k \ne d_{kk}$ for every $k$. The number $x$ is a legitimate element of $[0,1)$: its digits are well-defined, and since it never uses 9 (or 0) it has no ambiguous-expansion problem.

Where is $x$ on the list? It cannot be $r_0$, because $x$ and $r_0$ differ in digit $0$ (we made $x_0 \ne d_{00}$). It cannot be $r_1$, because they differ in digit $1$. In general, for every $n$, $$x \ne r_n \quad\text{because}\quad x_n \ne d_{nn}.$$ Two decimal numbers that disagree in even one digit are different numbers. So $x$ differs from every $r_n$ — it appears nowhere on the list. But the list was supposed to contain every real in $[0,1)$, and $x$ is such a real. Contradiction. Therefore no complete list exists: $[0,1)$ is uncountable. Since $[0,1) \subseteq \mathbb{R}$, the reals are uncountable too, and as $\mathbb{N}$ injects into $\mathbb{R}$ we have the strict inequality $\lvert \mathbb{N} \rvert < \lvert \mathbb{R}\rvert$. $\blacksquare$

🚪 Threshold Concept. There is more than one infinity, and they are not all reachable from one another. $\lvert \mathbb{N} \rvert < \lvert \mathbb{R} \rvert$ is a strict inequality between two infinite sizes — the countable and the uncountable. This single fact reorganizes computer science: any time you have a countable supply of tools (lists, programs, descriptions, proofs) and an uncountable supply of targets (real numbers, arbitrary functions, infinite behaviors), the pigeonhole of infinity guarantees most targets have no tool. We are about to cash exactly that in for programs in 10.4, and again — as the deepest theorem in the book — for the halting problem in Chapter 36. Diagonalization is the master key to every "no algorithm can…" result. Learn the shape of the argument, not just this instance.

⚠️ Common Pitfall: "Just add $x$ to the list!" The most common objection: "Fine, $x$ isn't on the list — so insert it at the front and now it is." This misreads the proof. The argument does not find one missing number from one list; it shows that every list, including your new patched one, misses something. Patch the list to include $x$ and re-run the diagonal construction on the new list: out pops a new $x'$ that the patched list misses. There is no list to fix, because the proof defeats all lists at once. (Compare 10.1's pitfall: trust the argument, not the picture of "almost complete.")

🐛 Find the Error. A student "disproves" Cantor by arguing: "$\mathbb{Q}$ is countable and dense, the reals are just limits of rationals, and a limit of listed things should still be listed — so $\mathbb{R}$ is countable too." Where is the flaw?

Answer

"A limit of listed things is still listed" is false, and it is precisely the gap the diagonal number $x$ exploits. Each $r_n$ on the list is a specific real, but the diagonal construction produces an $x$ that is the limit of no finite portion of the list and equals no entry. Density of $\mathbb{Q}$ guarantees rationals get arbitrarily close to every real, but "arbitrarily close" is not "equal" — a countable set can be dense in an uncountable one. (This is exactly why $\mathbb{Q}$ being countable and $\mathbb{R}$ being uncountable are both true and not in conflict.)

The same argument, made tangible in code

We cannot represent an infinite list of infinite-precision reals in a finite program. But we can demonstrate the mechanism: given any finite table of decimal digits, the diagonal rule produces a row that differs from every listed row. Running it on a finite sample makes the trick concrete — and makes clear that nothing about the argument depended on the particular numbers.

# Given rows of decimal digits, build a digit-string differing from each row on its diagonal.
def diagonal_escape(rows):
    out = []
    for k, row in enumerate(rows):
        out.append(4 if row[k] == 5 else 5)   # differ from digit k of row k
    return out

table = [[1, 2, 3, 4],      # r_0
         [5, 5, 5, 5],      # r_1
         [9, 8, 7, 6],      # r_2
         [0, 0, 5, 0]]      # r_3
x = diagonal_escape(table)
print(x)
print(all(x[k] != table[k][k] for k in range(4)))   # differs on every diagonal entry?
# Expected output:
# [5, 4, 5, 4]
# True

The diagonal entries are $table[0][0]=1,\ table[1][1]=5,\ table[2][2]=7,\ table[3][3]=0$, so the rule emits $5, 4, 5, 4$ — guaranteed to differ from row $k$ at position $k$. The True confirms $x$ dodges every row's diagonal digit. Now imagine the table is infinite and contains every real: the same rule still produces a number on no row. That is Cantor's proof, and that is uncountability.

🔄 Check Your Understanding 1. In the diagonal proof, exactly why can the constructed number $x$ not be equal to $r_{42}$? 2. The proof forbids decimal expansions ending in all 9s, and our digit rule only ever outputs 4 or 5. Why do those two precautions matter? 3. Someone says: "Cantor only proved that one specific list is incomplete." Correct them in one sentence.

Answers

1. Because $x$ was built so that its 42nd digit $x_{42}$ differs from $d_{42,42}$, the 42nd digit of $r_{42}$; two numbers differing in any digit are unequal. 2. The all-9s ban makes each real's decimal expansion unique (otherwise $0.4999\ldots = 0.5000\ldots$ could let $x$ secretly equal a listed number despite differing digit-wise); restricting $x$'s digits to $\{4,5\}$ keeps $x$ away from any 9s-or-0s ambiguity, so "different digits" genuinely means "different number." 3. The construction works on any list whatsoever — feed it a patched list and it produces a new escapee — so it proves no list can be complete, not merely that one isn't.

10.4 There are more problems than programs

Here is the payoff that makes this chapter computer science rather than pure mathematics. We have two infinite sets in tension:

• the set of all programs you could ever write, and
• the set of all problems you might want a program to solve.

We will show the first is countable and the second is uncountable. The inequality $\lvert \text{countable}\rvert < \lvert \text{uncountable}\rvert$ then forces the conclusion: there must exist problems that no program solves. Uncomputability is not a failure of engineering. It is a counting fact, provable before we ever say precisely what a program is.

Step 1: there are only countably many programs

A program — in Python, C, assembly, any fixed language — is ultimately a finite string of characters over a finite alphabet (the keyboard's symbols, say the 128 ASCII characters). So a program is just a finite sequence drawn from a finite set.

Claim. The set of all finite strings over a finite alphabet is countable. Hence the set of all programs is countable.

The strategy first. List the strings the only sane way: by length, and alphabetically within each length. Length 0 gives the empty string; length 1 gives each single character; length 2 gives each pair; and so on. There are finitely many strings of each length (if the alphabet has $a$ symbols, exactly $a^n$ of length $n$), so this is a countable union of finite sets — listable by the grid sweep of 10.2.

Proof. Order all strings first by length, then lexicographically within a length. The length-$n$ strings number $a^n$ (finite) for an alphabet of size $a$, so we can write them all down in a block. Concatenating the blocks for $n = 0, 1, 2, \dots$ yields one infinite list: $$\varepsilon,\ \text{(all length-1 strings)},\ \text{(all length-2 strings)},\ \dots$$ Every finite string has a definite length $n$ and a definite alphabetical rank within that length, so it sits at a finite position in this list — an enumeration. Therefore the set of finite strings is countable, and since every program is such a string, the programs are countable. $\blacksquare$

💡 Intuition: Even though there are infinitely many possible programs, you could in principle put them in a numbered list: program #0, program #1, program #2, … and eventually reach any specific program after finitely many steps. The set of programs is no bigger than $\mathbb{N}$. (Most strings on the list won't compile — but throwing some away only shrinks a countable set, which stays countable.)

Step 2: there are uncountably many problems

What is a "problem"? Take the simplest interesting kind: a decision problem is a yes/no question about natural numbers — equivalently, a function $f\colon \mathbb{N} \to \{0, 1\}$ assigning each input the answer 1 (yes) or 0 (no). "Is $n$ prime?", "Does the $n$-th Turing machine halt?", "Is $n$ a perfect square?" — each is such a function. So the set of decision problems is the set of all functions $\mathbb{N} \to \{0,1\}$.

Claim. The set of all functions $\mathbb{N} \to \{0,1\}$ is uncountable.

The strategy first. This is diagonalization again — the exact argument from 10.3, now with the table holding 0s and 1s instead of decimal digits. Assume the functions could be listed $f_0, f_1, f_2, \dots$. Build a new function $g$ that disagrees with $f_n$ at input $n$ by flipping the bit: $g(n) = 1 - f_n(n)$. Then $g$ differs from every $f_n$ and so is on no list. Same diagonal, same escape, same contradiction.

Proof. Suppose the functions $\mathbb{N} \to \{0,1\}$ formed a countable list $f_0, f_1, f_2, \dots$. Define $g\colon \mathbb{N} \to {0,1}$ by flipping the diagonal: $$g(n) = 1 - f_n(n).$$ For each $n$, $g(n) \ne f_n(n)$, so $g$ differs from $f_n$ at the input $n$ and therefore $g \ne f_n$ as functions. Thus $g$ is not on the list — yet $g$ is a perfectly good function $\mathbb{N} \to {0,1}$, which the list was supposed to contain. Contradiction. So no such list exists: the functions $\mathbb{N} \to \{0,1\}$ are uncountable. $\blacksquare$

🔗 Connection. A function $\mathbb{N} \to \{0,1\}$ is exactly an infinite binary string, which is exactly a subset of $\mathbb{N}$ (the inputs sent to 1), which is exactly an element of the power set $\mathcal{P}(\mathbb{N})$ from Chapter 8. We have therefore just proved a special case of Cantor's theorem: $\lvert \mathbb{N} \rvert < \lvert \mathcal{P}(\mathbb{N})\rvert$. The power set of any set is strictly bigger than the set — there is no largest infinity. The Deep Dive exercises prove the general theorem by the same diagonal flip.

Step 3: put them together

Each program computes at most one decision function. So "lining up programs with the problems they solve" is at best an injection from a subset of programs into the decision functions. But:

• the programs are countable (Step 1), so the functions they compute are countable too;
• the decision functions are uncountable (Step 2).

A countable set cannot be matched onto an uncountable one — there are strictly too few programs. So some decision functions are computed by no program.

Corollary (uncomputable problems exist). There exist decision problems $f\colon \mathbb{N} \to {0,1}$ for which no program computes $f$. In fact, since the computable problems are countable and all problems are uncountable, almost every decision problem is uncomputable.

🚪 Threshold Concept. Read that corollary again: almost every well-defined yes/no problem is uncomputable. The computable problems — the ones with programs — are a vanishingly thin countable sliver inside an uncountable ocean of problems with no program at all. We have not exhibited a single specific uncomputable problem (that takes the halting-problem diagonalization of Chapter 36); we have proven, by pure counting, that the ocean must exist. This is the most important consequence of Cantor's work for a programmer: the limits of computation are not about hardware, budget, or cleverness. They are baked into the arithmetic of infinity. Some things cannot be computed, and now you know why before you know which.

🧩 Productive Struggle. Before reading on: we proved uncomputable problems exist but named none. Try to feel why naming one is harder. A random infinite bit-string is uncomputable, but you can't write down a specific random string (writing it down would be a finite description — a program!). Chapter 36 will name a concrete one — "does program $p$ halt on input $p$?" — using the diagonal flip on programs themselves. Can you guess how the flip turns "halts" into a contradiction? Hold the question; it is the climax of the whole book.

🔄 Check Your Understanding 1. Why is the set of all Python programs countable, even though it is infinite? 2. In Step 2, what does flipping the diagonal bit ($g(n) = 1 - f_n(n)$) accomplish, and why does it prove the functions are uncountable? 3. The conclusion is "more problems than programs." Which set is larger, and which single comparison of cardinalities licenses the leap to "some problems are uncomputable"?

Answers

1. Every program is a finite string over a finite alphabet; ordering strings by length then alphabetically lists them all, putting each at a finite position — a countable enumeration. (That most strings don't compile only shrinks the set.) 2. It builds a function $g$ that differs from the $n$-th listed function at input $n$, so $g$ is on no list; since this defeats every proposed list, no enumeration of the functions exists, i.e. they are uncountable. 3. The problems (uncountable) are larger than the programs (countable); the strict inequality $\lvert \text{programs}\rvert = \aleph_0 < \lvert \text{problems}\rvert$ means no surjection from programs onto problems exists, so some problem has no program.

10.5 The hierarchy of infinities

We have found two sizes of infinity: the countable size of $\mathbb{N}$, and the strictly larger, uncountable size of $\mathbb{R}$. It is natural to ask how many sizes there are, and whether anything lives between them. The answers are striking, and we keep this section brief — it is culture and orientation, not machinery you will compute with.

Naming the countable infinity: aleph-null

Definition (aleph-null). The cardinality of any countably infinite set is denoted $\aleph_0$ (read "aleph-null" or "aleph-naught"), the smallest infinite cardinal. Thus $\lvert \mathbb{N}\rvert = \lvert \mathbb{Z}\rvert = \lvert \mathbb{Q}\rvert = \aleph_0$, while $\lvert \mathbb{R}\rvert > \aleph_0$.

The symbol $\aleph$ is the first Hebrew letter; Cantor chose it deliberately for a genuinely new kind of number. $\aleph_0$ obeys an arithmetic that mocks finite intuition: $\aleph_0 + 1 = \aleph_0$ (add an element — §10.1's "+1" bijection), $\aleph_0 + \aleph_0 = \aleph_0$ ($\mathbb{Z}$), and $\aleph_0 \cdot \aleph_0 = \aleph_0$ (the grid — $\mathbb{N}\times\mathbb{N}$). Absorbing a countable amount into a countable set changes nothing.

💡 Intuition (Hilbert's Hotel). Imagine a hotel with $\aleph_0$ rooms, all full. A new guest arrives — move everyone from room $n$ to room $n+1$, freeing room 0. A countably infinite coach of new guests arrives — move everyone from room $n$ to room $2n$, freeing all the odd rooms. Even infinitely many coaches, each with infinitely many guests, fit (room them by the diagonal grid sweep of §10.2). The full hotel always has room for more — as long as "more" is countable. But the reals would overflow it: no rooming scheme can seat uncountably many guests in countably many rooms. That is §10.3 in a parable.

The continuum, and a tower with no top

The cardinality of $\mathbb{R}$ has its own name.

Definition (the continuum). The cardinality of $\mathbb{R}$ is called the continuum, written $\mathfrak{c}$ (or $2^{\aleph_0}$, since $\mathbb{R}$ matches the set of infinite binary strings).

And the climb does not stop. §10.4's connection generalizes to Cantor's theorem: for every set $S$, $\lvert S \rvert < \lvert \mathcal{P}(S)\rvert$ — the power set is always strictly larger. Starting from $\mathbb{N}$ and repeatedly taking power sets gives an endless tower of ever-larger infinities: $$\aleph_0 = \lvert \mathbb{N}\rvert \ <\ \lvert \mathcal{P}(\mathbb{N})\rvert = \mathfrak{c}\ <\ \lvert \mathcal{P}(\mathcal{P}(\mathbb{N}))\rvert\ <\ \cdots$$ There is no largest infinity, just as there is no largest natural number. Infinity, it turns out, is not one thing but an unbounded ladder of distinct things.

🔗 Connection (an honest loose end). Is there a cardinality strictly between $\aleph_0$ and $\mathfrak{c}$? The conjecture that there is not — that $\mathfrak{c}$ is the next infinity after $\aleph_0$ — is the Continuum Hypothesis (CH). Astonishingly, Gödel (1940) and Cohen (1963) together proved that CH can be neither proved nor disproved from the standard axioms of set theory (ZFC): it is independent of them. This is the same flavor of limit as undecidability — a well-posed question that the system provably cannot settle — and it foreshadows the incompleteness and undecidability results of Part VI. We flag it as orientation, not as something you need to resolve. (Tier-1: Sipser, and standard set-theory references.)

🔄 Check Your Understanding 1. What is $\aleph_0$, and what is the value of $\aleph_0 + \aleph_0$? Which earlier set witnesses that value? 2. State Cantor's theorem in one line. What does it imply about a "largest infinity"? 3. In Hilbert's Hotel, why can the full hotel always absorb a countable coach of new guests but not an uncountable crowd?

Answers

1. $\aleph_0$ is the cardinality of any countably infinite set (the smallest infinite cardinal); $\aleph_0 + \aleph_0 = \aleph_0$, witnessed by $\mathbb{Z}$ (or by the evens-plus-odds bijection).
2. For every set $S$, $\lvert S\rvert < \lvert \mathcal{P}(S)\rvert$ — so there is no largest set and no largest infinity; the power-set operation always produces a strictly bigger cardinality.
3. A countable coach can be interleaved into the rooms (move guest $n \to 2n$, seat the coach in the odds) because a countable union of countables is countable; an uncountable crowd cannot, because there are only countably many rooms and no injection from an uncountable set into a countable one.

10.6 Why a programmer should care

It is fair to ask whether any of this touches code you will actually write. It does — directly, and in more places than you would guess. The thread that ties them together: wherever a countable resource must cover an uncountable demand, something is impossible, and knowing it saves you from chasing it.

• The limits of computation (Chapter 36). §10.4 already proved the headline: programs are countable, problems are uncountable, so uncomputable problems exist. Chapter 36 turns "exist" into "here is one" — the halting problem, "will this program halt on this input?", is uncomputable — and it does so with the very diagonal flip you just learned, applied to programs run on their own source code. When you understand why no general termination-checker, no perfect static analyzer, and no universal "is this code correct?" tool can exist, you are applying this chapter.

• Floating-point is a countable approximation of an uncountable line. There are only finitely many IEEE-754 double values (about $2^{64}$ of them) — utterly countable — but the reals they approximate are uncountable. Almost every real number is not representable, which is the deep reason rounding error is unavoidable and 0.1 + 0.2 != 0.3. You are not using a buggy number type; you are using a countable net cast over an uncountable sea.

• Most real numbers have no name. A definable or computable real is one with a finite description (a formula, an algorithm, a program that prints its digits). Descriptions are finite strings, hence countable; the reals are uncountable; so almost every real number is uncomputable and even undescribable — there is no formula, no algorithm, no name for it at all. The numbers you ever actually mention ($\pi$, $e$, $\sqrt 2$, every constant in every program ever written) are a countable, measure-zero dust in $\mathbb{R}$.

• No programming language is "universal" over all functions. A language defines a countable set of programs, computing a countable set of functions $\mathbb{N} \to \mathbb{N}$. But there are uncountably many such functions. So no language — however expressive — can express them all. Turing completeness is the ceiling, and even the ceiling leaves uncountably much out of reach.

💡 Intuition: Hold one image: a countable list is a sequence of named, reachable things — programs, decimals you can write, values a double can hold, sentences in a spec. An uncountable set is too vast to name — its elements escape every list by diagonalization. Computation lives entirely on the countable side. The uncountable side is the permanent frontier, and Cantor drew the border.

🔗 Connection. This chapter is the mathematical seed of the entire theory-of-computation arc. Chapter 5 gave you proof by contradiction; this chapter weaponized it into diagonalization; Chapter 36 will use diagonalization to prove the halting problem undecidable; Chapter 37 will refine "what's computable at all" into "what's computable efficiently" (P vs. NP). The line from "part can equal whole" (§10.1) to "some code can't be written" (Chapter 36) is one continuous argument, and you have just walked its first and hardest half.

Project Checkpoint: a countability demonstrator for the Toolkit

The recurring theme of this book is that computation and proof are complementary (theme four). Cantor's results are proofs about the uncomputable, but the mechanisms in them — pairing $\mathbb{N}$ with $\mathbb{N}\times\mathbb{N}$, escaping a table by its diagonal — are concrete enough to run. Let's add a small, self-contained cardinality.py to our growing dmtoolkit that makes the two engines of this chapter executable: a bijection witnessing countability, and a diagonal escape witnessing uncountability. (Like §6's seeding of recurrences.py, this module is a teaching companion to the chapter; it adds no signatures that conflict with the frozen API of §4.)

Create dmtoolkit/cardinality.py and add:

def cantor_pair(i, j):
    """Bijection N x N -> N (Cantor pairing). Witnesses |N x N| = |N| = aleph_0."""
    s = i + j
    return s * (s + 1) // 2 + j          # index along anti-diagonal i+j

def cantor_unpair(n):
    """Inverse: N -> N x N. Recovers (i, j) from the pairing index n."""
    s = 0
    while (s + 1) * (s + 2) // 2 <= n:   # find the anti-diagonal s
        s += 1
    j = n - s * (s + 1) // 2
    return (s - j, j)

def diagonal_escape(rows):
    """Given rows of digits, return a row differing from each on its diagonal.
    Witnesses uncountability: no finite/infinite table can list every row."""
    return [4 if row[k] == 5 else 5 for k, row in enumerate(rows)]

# Demonstration: the pairing round-trips, and the escape dodges every diagonal.
print(cantor_pair(2, 1), cantor_unpair(cantor_pair(2, 1)))
table = [[1, 2, 3], [5, 5, 5], [0, 0, 0]]
esc = diagonal_escape(table)
print(esc, all(esc[k] != table[k][k] for k in range(3)))
# Expected output:
# 7 (2, 1)
# [5, 4, 5] True

The first line shows the Cantor pairing sending $(2,1)$ to the index $7$ and unpairing back to $(2,1)$ — a verified bijection $\mathbb{N}\times\mathbb{N} \leftrightarrow \mathbb{N}$, the computational heart of "$\mathbb{Q}$ is countable." The second shows the diagonal escape producing $[5,4,5]$, which differs from row $k$ at position $k$ (True) — the computational heart of "$\mathbb{R}$ is uncountable." Two functions, the two ideas of the chapter, both runnable.

Toolkit so far: logic.py (Chapters 1–3), recurrences.py (begun Chapter 6), and now cardinality.py. The diagonal-escape function is the literal kernel of the undecidability proof you will write against the halting problem in Chapter 36 — there, the "rows" become programs and the escape becomes a program no enumeration of programs can contain. You are building the tool now and firing it at the deepest result in the book later.

Summary

Cardinality measures set size by matching, not counting, which lets "size" survive the jump to infinity — and reveals that not all infinities are equal.

Core definitions

Key results

The two diagonal moves (don't confuse them)

• Sweep along anti-diagonals ⟶ gather everything into one list ⟶ proves countability ($\mathbb{Q}$, $\mathbb{N}\times\mathbb{N}$, countable unions).
• Walk down the diagonal and disagree ⟶ construct something on no list ⟶ proves uncountability ($\mathbb{R}$, $\mathcal{P}(\mathbb{N})$, "more problems than programs").

Things finite intuition gets wrong about infinity

• A proper subset can be the same size as the whole (definition of infinite).
• "Half of infinity" ($E \subset \mathbb{N}$) is not smaller; $\aleph_0 + \aleph_0 = \aleph_0$.
• A countable set ($\mathbb{Q}$) can be dense in an uncountable one ($\mathbb{R}$).
• Patching a list with the missing diagonal element does not complete it.

Toolkit: cardinality.py — cantor_pair/cantor_unpair (a bijection $\mathbb{N}\times\mathbb{N} \leftrightarrow \mathbb{N}$) and diagonal_escape (the kernel of the Chapter 36 undecidability proof).

Spaced Review

Retrieval keeps knowledge available. Answer from memory before checking.

1. (Ch. 9) Cardinality comparison is defined entirely in terms of injective, surjective, and bijective functions. Define each of the three, and state which one witnesses $\lvert A\rvert = \lvert B\rvert$.
2. (Ch. 9) Every bijection $f$ has an inverse $f^{-1}$. Why does that fact make "equinumerous" behave symmetrically — i.e., why does $\lvert A\rvert = \lvert B\rvert$ immediately give $\lvert B\rvert = \lvert A\rvert$?
3. (Ch. 8) The set of decision problems is the power set $\mathcal{P}(\mathbb{N})$ in disguise. Explain the correspondence between a subset $S \subseteq \mathbb{N}$ and a function $\mathbb{N} \to \{0,1\}$.
4. (Ch. 8) For a finite set with $n$ elements, what is $\lvert \mathcal{P}(S)\rvert$, and how does that finite fact rhyme with this chapter's $\lvert S\rvert < \lvert\mathcal{P}(S)\rvert$?

Answers

1. Injective: distinct inputs map to distinct outputs ($f(x)=f(y)\Rightarrow x=y$). Surjective: every element of the codomain is an output. Bijective: both — a perfect pairing. A bijection witnesses $\lvert A\rvert = \lvert B\rvert$. 2. If $f\colon A\to B$ is a bijection, then $f^{-1}\colon B\to A$ is also a bijection (Ch. 9, §9.4), so a witness for "$B$ matches $A$" exists whenever one for "$A$ matches $B$" does — equinumerosity is symmetric. 3. A subset $S$ corresponds to its indicator function $\chi_S$ where $\chi_S(n)=1$ if $n\in S$ and $0$ otherwise; conversely any $f\colon \mathbb{N}\to{0,1}$ defines the subset ${n : f(n)=1}$. The correspondence is a bijection, so the two sets have the same cardinality. 4. $\lvert\mathcal{P}(S)\rvert = 2^n$ for $\lvert S\rvert = n$, and $2^n > n$ for all $n \ge 0$ — the finite shadow of Cantor's theorem $\lvert S\rvert < \lvert\mathcal{P}(S)\rvert$, which extends "the power set is strictly bigger" to infinite sets.

What's Next

You can now prove a set countable by listing it and prove a set uncountable by diagonalizing it, and you have seen the staggering consequence — most problems have no program — fall out of a pure counting argument. But cardinality is a coarse ruler: it tells you how many elements a set has, not how they are arranged or how fast you can work with them. The next chapters refine our view of structure and cost. Chapter 11 (Sequences and Summations) treats infinite lists as objects to manipulate and sum — giving us the tools to measure the work an algorithm does — and revisits our running Fibonacci thread as a sequence with a closed form on the horizon. The countable infinities you met here become the index sets over which those sums run. And far ahead, Chapter 36 will collect the debt this chapter incurred: diagonalization, sharpened into the proof that the halting problem cannot be solved. The frontier you glimpsed in §10.4 is where the book is headed.