Learn · The Concrete Discrete Math of Real Systems

seedling

The List Writes Its Own Missing Entry

Hand me any claimed complete list of infinite bit strings and I can manufacture the one it missed — a counterexample that proves some infinities are larger and later returns as the limit of computation.

discrete-math, infinity, countability, diagonalization, cantor, learn

The essence of mathematics lies precisely in its freedom.

— Georg Cantor, Grundlagen einer allgemeinen Mannigfaltigkeitslehre, 1883

Chapter 5 counted by exact pairing. This chapter asks whether every infinite collection can be paired with the positive integers. You will distinguish countable from merely infinite, execute Cantor's diagonal construction on any proposed enumeration, prove that a set has strictly fewer members than its power set, and recognize diagonalization as the same counterexample move that later proves the halting problem.

A list that promises everything

Chapter 5 treated a bijection as a counting certificate. For infinite sets, the same idea becomes surprising. The positive integers and the even integers pair perfectly: send $n$ to $2n$ . The evens are a proper part of the integers and still have the same cardinality.

Call a set countable when its members can be placed in a list $x_1,x_2,x_3,\ldots$ so that every member appears at some finite position. The integers are countable. The rational numbers are too, although no simple increasing list reaches them all: arrange fractions in a grid and walk finite diagonals, skipping repeats.

Countable — finite, or pairable with the positive integers. An infinite countable set admits an enumeration: every member appears at a finite numbered position. Learn more.

Now consider every infinite sequence of bits:

1: 0 0 0 0 0 0 ...
2: 1 1 1 1 1 1 ...
3: 0 1 0 1 0 1 ...
4: 1 0 1 0 1 0 ...
   ...

Suppose someone claims this list—continued forever—contains every possible infinite bit sequence. Do not search for an omission. Build one.

Commit to the construction. Which rule guarantees disagreement with every numbered row?

If the first row's first bit is 0, choose 1. If the second row's second bit is 1, choose 0. Continue. Call the resulting sequence $d$ .

$d$ is not row 1 because their first bits differ. It is not row 2 because their second bits differ. For any proposed row $n$ , $d$ differs at position $n$ . Therefore $d$ occurs nowhere in the list.

The list may have been chosen by the cleverest possible algorithm. The construction does not care. It accepts the entire proposed enumeration as input and returns a certified omission.

The diagonal law. Every enumeration of infinite binary sequences omits at least one sequence: flip the $n$th bit of its $n$th row.

The set of all infinite binary sequences is uncountable.

Assume it is countable. Then some list contains all infinite binary sequences. Construct $d$ by setting its $n$th bit opposite to the $n$th bit of row $n$ . The sequence $d$ is an infinite binary sequence, so the supposedly complete list must contain it at some row $k$ . But $d$ differs from row $k$ at bit $k$ . Thus $d$ both is and is not row $k$ , a contradiction. No complete enumeration exists.

In plain English: a list has one row per position. Use position $n$ to make the new object disagree with row $n$ . Infinity gives every row a turn, and no row survives its turn.

Note

The person behind the diagonal. Georg Cantor (1845–1918), born in Saint Petersburg and working for most of his career at Halle, reached set theory through problems about trigonometric series. His 1891 paper published this diagonal construction. Cantor had already proved the real numbers uncountable in 1874 by a different argument; “Cantor's diagonal argument” names the later proof, not his first discovery of unequal infinities.

Every subset is a bit string

The diagonal result is larger than binary sequences. For any set $A$ , describe a subset $S$ by one bit per element of $A$ : 1 when the element belongs to $S$ , 0 otherwise. Subsets of $A$ and Boolean membership functions on $A$ are the same space in two costumes.

The collection of all subsets is the power set of $A$ . For a finite $A$ with $n$ elements, it has $2^n$ members. Cantor's theorem says the strict inequality survives infinity.

Power set — the set of every subset of $A$ , including the empty set and $A$ itself. We will write it $\mathrm{P}(A)$ . Learn more.

No function from a set $A$ onto its power set can reach every subset.

Take any function $f:A \to \mathrm{P}(A)$ . Build the diagonal subset

$D=\{x \in A : x \notin f(x)\}.$

Suppose $D=f(a)$ for some $a$ . If $a$ belongs to $D$ , the definition of $D$ says $a$ does not belong to $f(a)=D$ . If $a$ does not belong to $D$ , the definition says it does belong to $f(a)=D$ . Either choice reverses itself. Therefore no $a$ maps to $D$ , so $f$ is not onto.

In plain English: form the club of everyone who did not put themselves in their assigned club. No person can have been assigned exactly that club, because their own membership flips the answer.

The proof does not depend on numbers, order, or notation. It says that for every attempted catalog of subsets indexed by the original set, the catalog itself supplies instructions for constructing a missing subset.

Why this is not a machine for new integers

A common objection asks why diagonalization cannot prove the integers uncountable. Write integers as finite strings and flip one digit from each row: the result is an infinite string, not necessarily an integer representation. The constructed object must remain inside the set under discussion. Infinite binary sequences are closed under the coordinate-by-coordinate construction; finite strings are not.

This is Chapter 3's domain warning at full scale. A counterexample outside the quantified space proves nothing.

The honest limits

Uncountable does not mean physically large or unrepresentable in every sense. Programs manipulate symbolic descriptions of functions and real numbers constantly. The theorem says no enumeration contains every member individually; it does not forbid finite descriptions for useful subsets.

Nor does diagonalization tell us which real numbers matter to a numerical application. Most computation works inside deliberately countable representations such as finite strings and floating-point values. Restricting the space is often the engineering victory. Chapter 16 will make that move explicit when diagonalization returns to show that some questions admit no program.

Lessons

Infinite sets have sizes compared by bijection, not by where a list appears to end.
The integers, evens, and rationals are countable; infinite binary sequences are not.
Diagonalization constructs a counterexample tailored to an entire proposed enumeration, differing from row $n$ at coordinate $n$ .
Every set has strictly fewer members than its power set.
A diagonal construction works only when the constructed object stays inside the claimed domain.

Practice

Retrieval — the prior chapter's certificate.

Discrimination — why the diagonal must stay in bounds.

Transfer — diagonalize a catalog.

Certainty before probability

Some collections escape every list. Return now to a finite container: more requests than unique IDs, more keys than buckets, more sessions than possible fingerprints. Before probability estimates anything, arithmetic may already force a collision.

How can finite counting prove that two objects must meet?

References

Cantor. “Ueber eine elementare Frage der Mannigfaltigkeitslehre.” Jahresbericht der Deutschen Mathematiker-Vereinigung, 1891. — the original diagonal paper, including the power-set form of the argument
O'Connor & Robertson. “Georg Cantor.” MacTutor History of Mathematics. — institutional biography and the route from trigonometric series to set theory
Jourdain, translator. “Contributions to the Founding of the Theory of Transfinite Numbers.” Open Court, 1915. — early English translations of Cantor's mature work
Moschovakis. “Notes on Set Theory.” Springer, 2006. — a rigorous next treatment of countability, ordinals, and cardinality

Chapter 6 of The Concrete Discrete Math of Real Systems — countability, Cantor diagonalization, power sets, and a constructive proof that no enumeration contains every infinite binary sequence.