Diagonalization for Infinite Binary Sequences

Binary Sequences and the Question of Enumeration

An infinite binary sequence is an endless string whose entries are each either $0$ or $1$. There are only two choices at each position, but a sequence makes a choice at every natural-number position. The question is whether all such sequences can be arranged in a list indexed by $\mathbb{N}$. A diagonal construction gives a direct answer: from any proposed list, it builds a sequence that the list misses.

We use $\mathbb{N}=\{1,2,3,\dots\}$. Formally, the set of infinite binary sequences is the set of all functions from $\mathbb{N}$ to $\{0,1\}$. We write $s(n)$ for the digit of a sequence $s$ in position $n$. Two sequences are equal exactly when their digits agree at every position.

Definition: An enumeration of a set $S$ is a sequence $(s_n)_{n\in\mathbb{N}}$ of elements of $S$ that includes every element of $S$. Equivalently, the function $f:\mathbb{N}\to S$ given by $f(n)=s_n$ is surjective. An enumeration may repeat elements; surjectivity, not the absence of repetitions, is the requirement.

To say that a set is countably infinite means that it can be put in bijection with $\mathbb{N}$, and in particular that it has an enumeration. The binary-sequence set is not finite: for each $m\in\mathbb{N}$, let $e_m$ have digit $1$ in position $m$ and digit $0$ in every other position. If $m\ne n$, then $e_m(m)=1$ while $e_n(m)=0$, so $e_m\ne e_n$. Thus there are infinitely many distinct binary sequences. It will therefore suffice to prove that no enumeration of them is possible.

The Diagonal Construction

Definition: Given a proposed list $(s_n)_{n\in\mathbb{N}}$ of binary sequences, its diagonal sequence $d$ is defined by changing the digit in position $n$ of row $s_n$: $$ d(n)=1-s_n(n)\qquad(n\in\mathbb{N}). $$ Since $s_n(n)$ is either $0$ or $1$, $d(n)$ is also either $0$ or $1$, so this rule defines an infinite binary sequence.

The word “diagonal” refers to the entries $s_1(1),s_2(2),s_3(3),\dots$: the first entry of the first row, the second entry of the second row, and so on. The construction changes each of these entries. In the resulting sequence, position $n$ differs from position $n$ in row $n$. That precise mismatch is what makes the proof work.

Theorem (Diagonalization for infinite binary sequences): There is no surjection from $\mathbb{N}$ onto the set of all infinite binary sequences. Consequently, the set of infinite binary sequences is uncountable.

Proof. Suppose, for a contradiction, that there is a surjection $f:\mathbb{N}\to\{0,1\}^{\mathbb{N}}$. Write $s_n=f(n)$, so every binary sequence must occur as some row $s_n$. Define $d$ by $d(n)=1-s_n(n)$ for each $n$. This is a binary sequence, because if $s_n(n)=0$, then $d(n)=1$, and if $s_n(n)=1$, then $d(n)=0$. Since $f$ is surjective, $d$ must equal $s_m$ for some $m\in\mathbb{N}$. But at position $m$, the definition gives $d(m)=1-s_m(m)$. If $s_m(m)=0$, then $d(m)=1\ne0=s_m(m)$; if $s_m(m)=1$, then $d(m)=0\ne1=s_m(m)$. In either case, $d\ne s_m$, contradicting $d=s_m$. Thus no such surjection exists. The set is infinite, as shown above, and a countably infinite set admits an enumeration; therefore this set is uncountable. $\square$

This argument does not require the proposed rows to be distinct. If a sequence occurs many times, the construction still disagrees with row $n$ at position $n$, for every $n$. Nor does it rely on guessing what the proposed list looks like. It applies to every possible list, which is why it proves that no enumeration can succeed.

Worked Diagonal Constructions

Worked Example: Reading a Finite Portion of a Proposed List

Consider these four rows, with their rules specified for every position $k\in\mathbb{N}$: $s_1(k)=0$ for all $k$; $s_2(k)=1$ for all $k$; $s_3(k)=0$ when $k$ is odd and $1$ when $k$ is even; and $s_4(k)=1$ when $k$ is divisible by $3$ and $0$ otherwise. The first four columns are:

\begin{array}{c|ccccc} &1&2&3&4&5\\ s_1&0&0&0&0&0\\ s_2&1&1&1&1&1\\ s_3&0&1&0&1&0\\ s_4&0&0&1&0&0 \end{array}

For the first four diagonal positions, read $s_1(1)=0$, $s_2(2)=1$, $s_3(3)=0$, and $s_4(4)=0$. Changing each digit gives $d(1)=1-0=1$, $d(2)=1-1=0$, $d(3)=1-0=1$, and $d(4)=1-0=1$. Thus the first four digits of the diagonal sequence are $1011$.

Check: At position $1$, $d$ has digit $1$ while $s_1$ has digit $0$. At position $2$, $d$ has $0$ while $s_2$ has $1$. At position $3$, $d$ has $1$ while $s_3$ has $0$. At position $4$, $d$ has $1$ while $s_4$ has $0$. This four-row display illustrates the method; it does not claim that four rows enumerate all infinite binary sequences.

Worked Example: A List That Repeats the Same Row

Let every row in a proposed list be the all-zero sequence: $s_n(k)=0$ for every $n,k\in\mathbb{N}$. For each position $n$, the diagonal entry is $s_n(n)=0$, so the construction gives $d(n)=1-0=1$. Therefore $d$ is the all-one sequence.

Check: For any row number $m$, $s_m(m)=0$ while $d(m)=1$, so $d\ne s_m$. This list plainly misses the all-one sequence, and the diagonal check verifies the omission row by row. Repetition in a list does not prevent the argument; it only makes this particular example especially visible.

Worked Example: The List of Single-Position Sequences

Use the sequences $e_n$ defined earlier: $e_n(k)=1$ if $k=n$, and $e_n(k)=0$ if $k\ne n$. In row $n$, the diagonal digit is $e_n(n)=1$. Hence the diagonal sequence has $d(n)=1-1=0$ for every $n$, so it is the all-zero sequence.

Check: Fix any proposed row $e_m$. Its digit in position $m$ is $e_m(m)=1$, whereas the all-zero sequence has digit $0$ in position $m$. Thus the diagonal sequence is not $e_m$, for every $m$. This confirms both that the $e_n$ are distinct and that the sequence produced by diagonalization is absent from this particular list.

Why the Contradiction Is Unavoidable

The contradiction is not that a row fails to match the diagonal sequence in some unspecified way. It is a specific disagreement: row $n$ and $d$ differ at coordinate $n$. If someone claims that $d=s_m$, the $m$th coordinate alone refutes the claim, because $d(m)\ne s_m(m)$. Every proposed row has its own designated coordinate that certifies the mismatch.

A finite table can show the first few such mismatches, but an enumeration must cover sequences of every infinite length. Looking at only the first four rows or columns cannot by itself prove that a list fails. The proof succeeds because the rule defines $d(n)$ for every natural number $n$, and then proves the mismatch for an arbitrary row number $m$, not merely for a finite sample.

Common pitfall: changing the wrong entry. Suppose a displayed table has row $2$ beginning $1,1,1,\dots$. A tempting but incorrect calculation is to change the first digit of row $2$, obtain $0$, and call that the second digit of the diagonal sequence. The diagonal rule uses the entry in row $2$, position $2$, namely $s_2(2)=1$, so the correct calculation is $d(2)=1-s_2(2)=1-1=0$. The answer happens to be the same in this row because both entries are $1$, but the procedure is still wrong; in the first worked example, row $3$ has $s_3(1)=0$ and $s_3(3)=0$, while row $4$ has $s_4(1)=0$ and $s_4(4)=0$, so these particular entries also do not expose it. A table where the distinction matters is the row $s(k)=1$ when $k=1$ and $s(k)=0$ for $k\ge2$: its first digit is $1$, but its second digit is $0$. If this is row $2$, the correct diagonal digit is $1-s_2(2)=1-0=1$; changing its first digit instead gives $1-1=0$, which is not the required diagonal entry.

The conclusion concerns enumeration, not the possibility of listing some binary sequences. Many particular sequences can be listed, as the examples show. What fails is the claim that one list indexed by $\mathbb{N}$ includes every infinite binary sequence. The diagonal construction takes any such proposed list and produces a sequence outside it.

Check Your Understanding

For each question, identify the row and coordinate used by the diagonal rule.

If $s_5(5)=0$, what is $d(5)$? If instead $s_5(5)=1$, what is $d(5)$?
Why does a repeated row in a proposed enumeration not invalidate the diagonal argument?
A proposed list has $s_n(k)=1$ exactly when $k=n$. Compute its diagonal sequence and verify that it differs from every row.
Why does checking the first four entries of a diagonal sequence not, by itself, prove that a proposed infinite list is incomplete?
In the contradiction proof, which assumption makes it necessary for the constructed sequence $d$ to equal some row $s_m$?

Diagonalization for Infinite Binary Sequences

What You'll Learn