Cantor’s diagonal argument is a method of mathematical proof that constructs an object differing from every object in a proposed enumeration. Its characteristic step is to change the entry in the (n)th position of the (n)th object, ensuring that the constructed object cannot equal any listed object. Introduced by Georg Cantor, it establishes the existence of uncountable sets and, in its general form, proves that every set has strictly smaller cardinality than its power set. (onepagepapers.com)
Historical origin
Cantor’s first proof that the real numbers cannot be enumerated appeared in 1874 and used a different construction. His diagonal method belongs to the paper Über eine elementare Frage der Mannigfaltigkeitslehre, associated with the German Mathematical Society’s September 1891 meeting at Halle. Conventionally cited as an 1891 paper, it appeared in the society’s report printed in 1892. (plato.stanford.edu)
The original argument concerned infinite sequences formed from two distinct symbols, rather than decimal expansions. Cantor then extended the reasoning to collections of two-valued functions on an arbitrary set. This extension gives the result now called Cantor’s theorem. (onepagepapers.com)
Countability and enumeration
A countable set is finite or can be placed in one-to-one correspondence with the natural numbers. For an infinite set, countability means that its elements can be listed as
[ x_1,x_2,x_3,\ldots ]
with every element appearing at some finite position. Such a listing is a mathematical assignment of an object to each index, not a process that must physically finish. An enumeration may also allow repetitions, provided it includes every element. (builds.openlogicproject.org)
An uncountable set has no such enumeration. Diagonalization proves this by taking an arbitrary proposed list and identifying an object it omits. Crucially, the argument applies to every possible list, not merely to one particular ordering. (builds.openlogicproject.org)
The proof for binary sequences
Let
[ B={0,1}^{\mathbb N} ]
be the set of all infinite binary sequences. Suppose a list of members of (B) is given, with (a_{ij}) denoting the (j)th entry of sequence (s_i):
[ \begin{array}{c|ccccc} &1&2&3&4&\cdots\ \hline s_1&a_{11}&a_{12}&a_{13}&a_{14}&\cdots\ s_2&a_{21}&a_{22}&a_{23}&a_{24}&\cdots\ s_3&a_{31}&a_{32}&a_{33}&a_{34}&\cdots\ s_4&a_{41}&a_{42}&a_{43}&a_{44}&\cdots\ \vdots&\vdots&\vdots&\vdots&\vdots \end{array} ]
Define a new sequence (d) by
[ d_n=1-a_{nn}. ]
Thus (d) reverses every entry along the main diagonal. For each (n), its (n)th entry differs from the (n)th entry of (s_n), so (d\ne s_n). Yet (d) is itself an infinite binary sequence. The proposed list therefore omits an element of (B), proving that (B) is uncountable. (onepagepapers.com)
The construction may be presented as a proof by contradiction: assume the list contains all binary sequences and derive an omitted sequence. Equivalently, it directly shows that every map from (\mathbb N) to (B) fails to be a surjection. (openlogicproject.org)
Application to real numbers
A familiar version assumes that all numbers in ((0,1)) have been listed in decimal form:
[ x_n=0.a_{n1}a_{n2}a_{n3}\ldots. ]
Define
[ y=0.b_1b_2b_3\ldots, \qquad b_n= \begin{cases} 2,&a_{nn}=1,\ 1,&a_{nn}\ne1. \end{cases} ]
Then (y) lies in ((0,1)) and differs from (x_n) at position (n), for every (n). Consequently, no proposed enumeration contains every real number in that interval. (cs.stanford.edu)
Decimal representations require care because distinct digit strings can denote the same number, as in (0.5000\ldots=0.4999\ldots). Using only digits (1) and (2) for the constructed number avoids this ambiguity: its expansion is neither terminating nor eventually all (9)s. Merely changing digits without controlling alternative representations would leave a gap in the proof. (cs.stanford.edu)
Binary sequences can also be embedded into the reals through
[ (a_n)\longmapsto \sum_{n=1}^{\infty}\frac{2a_n}{3^n}. ]
If two sequences first differ at position (k), the contribution (2/3^k) exceeds the largest possible opposing contribution from later positions, (1/3^k). Their images are therefore different. This gives an injection into the Cantor set and another route from binary-sequence uncountability to real-number uncountability. (builds.openlogicproject.org)
Generalization to power sets
For any set (A), its power set (\mathcal P(A)) consists of all its subsets. Given any function
[ f:A\longrightarrow\mathcal P(A), ]
define the diagonal subset
[ D={a\in A:a\notin f(a)}. ]
For every (a\in A),
[ a\in D\quad\Longleftrightarrow\quad a\notin f(a). ]
Thus (D\ne f(a)): the two subsets disagree about whether they contain (a). Since (D\in\mathcal P(A)), the function (f) is not surjective. No bijection between (A) and (\mathcal P(A)) can exist. Meanwhile, (a\mapsto{a}) is an injection from (A) into (\mathcal P(A)), so
[ |A|<|\mathcal P(A)|. ]
This proof works for finite, countable, and uncountable sets; it does not require a literal table or an enumeration by natural numbers. (builds.openlogicproject.org)
Consequences and related methods
Within set theory, repeatedly applying Cantor’s theorem produces sets of successively larger cardinalities:
[ |A|<|\mathcal P(A)| <|\mathcal P(\mathcal P(A))|<\cdots. ]
There is consequently no largest set cardinality. The proof is available in Zermelo–Fraenkel set theory without the axiom of choice. (builds.openlogicproject.org)
In computability theory, related diagonal reasoning establishes the undecidability of the halting problem. Suppose an algorithm correctly determines whether any program halts on any input. Construct a program that, on input a program description (p), loops if the alleged algorithm predicts that (p) halts on itself, and halts otherwise. Applied to its own description, the constructed program contradicts either prediction. Here diagonalization concerns self-application and opposite behavior, rather than infinite digit strings. (builds.openlogicproject.org)
Scope and common misunderstandings
Adding the missing object does not complete a list. The diagonal object depends on the proposed enumeration. After inserting it into a revised enumeration, the same construction yields an object missing from that revised list. The theorem does not identify one object excluded from every conceivable list. (onepagepapers.com)
The construction is not necessarily an effective computation. Defining an entry from the corresponding diagonal entry does not guarantee that an algorithm can obtain those entries. Mathematical enumeration and computable enumeration are different notions. (builds.openlogicproject.org)
Two diagonal techniques serve different purposes. Traversing a grid along successive finite diagonals can enumerate pairs of natural numbers and help establish the countability of the rational numbers. Cantor’s anti-diagonal construction instead changes entries to escape an enumeration. (builds.openlogicproject.org)
Uncountability does not settle the continuum hypothesis. Diagonalization proves that the real numbers are more numerous than the natural numbers, but not whether a cardinality lies strictly between them. The continuum hypothesis denies the existence of such an intermediate cardinality; assuming consistency, it is independent of the usual Zermelo–Fraenkel axioms with choice. (plato.stanford.edu)
References
- Ueber eine elementare Frage der Mannigfaltigkeitslehre, the textonepagepapers.com
- The Early Development of Set Theoryplato.stanford.edu
- The Size of Setsbuilds.openlogicproject.org
- Set Theory. An Open Introductionbuilds.openlogicproject.org
- CS103 Course Textcs.stanford.edu
- Revisions to enumerability and size of sets sectionsopenlogicproject.org
- The Open Logic Textbuilds.openlogicproject.org
- The Continuum Hypothesisplato.stanford.edu