= Cantor's diagonal argument
{c}
{title2=$b_n=1-a^{(n)}_n$}
{wiki}
= Cantor diagonal argument
{c}
{synonym}
Cantor's diagonal argument shows that the <set> of all infinite <binary sequences> is an <uncountable set>. Suppose a proposed enumeration is $a^{(1)},a^{(2)},\ldots$, where $a^{(n)}_j\in\{0,1\}$ is coordinate $j$ of row $n$. Construct a new <binary sequence> by
$$
b_n=1-a^{(n)}_n\qquad(n\geq1).
$$
It differs from row $n$ at coordinate $n$, for every $n$. It is consequently absent from the entire proposed list, regardless of how that list was chosen. The failure of an enumeration of all <binary sequences> follows from this precise point of disagreement, rather than from a claim that the list looks too small.
\Image[/cantor-diagonal-sequences.png]
{title=Flipping the nth coordinate of the nth row constructs a binary sequence missing from every proposed row}
For the displayed window, the first six diagonal bits are $1,0,0,0,1,1$, so the new sequence starts $0,1,1,1,0,0$. The drawing shows only finitely many rows, but the rule defines every coordinate and excludes every row of an infinite list. This distinguishes the argument from the <Cantor pairing function>: that construction lists all pairs of finite indices, whereas this one concerns an entire infinite <sequence> as each object to be listed. Finite <binary strings> form a <countable set>; all infinite <binary sequences> do not.
The connection with <power sets> is exact: a <subset> $A\subseteq\mathbb N$ corresponds to its <indicator function>, with a one in position $n$ exactly when $n\in A$. Changing the diagonal membership bit is the same mechanism as the <Cantor's theorem> construction $D=\{x:x\notin f(x)\}$. This reusable method turns a purported complete list into an explicit omitted object.
In his paper https://onepagepapers.com/cantor-diagonal/read/[Cantor, Ueber eine elementare Frage der Mannigfaltigkeitslehre, pp. 75–78]{ref}, presented in 1891 and printed in the 1890–91 volume in 1892, Cantor uses infinite sequences of two symbols for the diagonal construction and then gives the broader comparison of cardinalities. The binary notation here is a modern presentation of that construction.
Back to article page
