Diagonalization

Diagonalization is a proof technique that constructs an object differing from every item in a proposed enumeration at a selected position. It establishes that the enumeration cannot contain all objects of the relevant kind.

Cantor's diagonal argument: A proof that the real numbers in the unit interval cannot be listed as a sequence. It is the classic construction: change the nth digit of the nth listed number.
Uncountability of the real numbers: The result that no sequence can contain every real number in the unit interval. Cantor's digit-changing construction proves this central application.
Pigeonhole principle: A counting principle stating that placing more objects than containers forces at least one container to hold multiple objects. It proves some impossibility results by counting, rather than constructing a missing diagonal object.
Countable set: A set that is finite or can be placed in one-to-one correspondence with the natural numbers. Diagonal arguments test whether a proposed sequence really exhausts a set.
Diagonal lemma: A logical result that lets a sentence assert a property of its own code. It formalizes self-reference, a structure used in several diagonal proofs.
Undecidability: The property of a decision problem for which no algorithm always returns the correct yes-or-no answer. Diagonalization is a standard method for proving that some problems have no algorithmic solution.
Cantor–Bernstein–Schröder theorem: A theorem stating that injections in both directions between two sets imply a bijection between them. It compares cardinalities through injections instead of refuting a proposed enumeration by diagonal construction.
Power set: The set of all subsets of a given set. The diagonal subset is formed by checking whether each element belongs to its corresponding listed subset.
Self-reference: A statement or object that refers to itself, directly or through a coding scheme. Diagonal constructions often encode a reference to the item at the matching position.
Rice's theorem: A theorem stating that every nontrivial semantic property of programs is undecidable. Its proof uses self-reference and diagonal reasoning to rule out general program analyzers.

Linked from 13 pages