Cantor's diagonal argument (nonfiction)

From Gnomon Chronicles
Jump to navigation Jump to search
An illustration of Cantor's diagonal argument (in base 2) for the existence of uncountable sets. The sequence at the bottom cannot occur anywhere in the enumeration of sequences above.

In set theory, Cantor's diagonal argument, also called the diagonalization argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers.

Such sets are now known as uncountable sets, and the size of infinite sets is now treated by the theory of cardinal numbers which Cantor began.

The diagonal argument was not Cantor's first proof of the uncountability of the real numbers, which appeared in 1874. However, the diagonal argument demonstrates a powerful and general technique that has since been used in a wide range of proofs, including the first of Gödel's incompleteness theorems and Alan Turing's answer to the Entscheidungsproblem.

Diagonalization arguments are often also the source of contradictions like Russell's paradox and Richard's paradox.

Historically, the diagonal argument first appeared in the work of Paul du Bois-Reymond in 1875.

In the News

Fiction cross-reference

Nonfiction cross-reference

External links: