Diagonal argument

A proof technique that constructs an object differing from every object in a purported complete list. It establishes that the list omits at least one possible object.

Cantor's diagonal argument: A proof that the real numbers in the interval from zero to one cannot be listed as a complete sequence. Its digit-by-digit construction is the best-known instance of the diagonal method.
Uncountability of the real numbers: The result that no sequence can contain every real number in the interval from zero to one. Cantor's diagonal construction directly rules out every proposed enumeration of these reals.
Georg Cantor: A German mathematician who founded modern set theory and developed the arithmetic of infinite cardinalities. Cantor used diagonal reasoning to show that real numbers cannot be enumerated.
Cantor's first proof of the uncountability of the real numbers: Cantor's 1874 proof that algebraic numbers are countable while real numbers are not, using interval subdivision. It proves uncountability without the later digit-by-digit diagonal construction.
Cantor's theorem: The theorem that every set has fewer elements than its power set. The diagonal construction proves that no function from a set onto its power set can be surjective.
Halting problem: The problem of deciding, for every program and input, whether the program eventually stops. A diagonal argument shows that no algorithm solves this decision problem for all programs.
Richard Dedekind: A German mathematician whose work helped establish the modern foundations of number and set theory. His correspondence with Cantor formed part of the mathematical setting in which diagonal reasoning developed.
Pigeonhole principle: The principle that placing more objects than containers forces at least one container to hold multiple objects. It proves some counting impossibilities directly, whereas diagonal arguments construct an object missing from a list.
Russell's paradox: A contradiction arising from the set of all sets that do not contain themselves. Its self-referential construction resembles diagonal reasoning but exposes a contradiction in naive set theory.
Gödel's incompleteness theorems: Results showing that sufficiently expressive, consistent formal systems cannot prove every arithmetic truth or establish their own consistency. Gödel uses formal self-reference, built with diagonal reasoning, to produce an unprovable sentence.

Linked from 11 pages