Cantor's diagonal argument

Cantor's diagonal argument (among various similar names) is a <a href="/facts/Mathematical_proof/7ECDrU80">mathematical proof</a> that there are <a href="/facts/Infinite_set/9rTN0xGH">infinite sets</a> which cannot be put into <a href="/facts/Bijection/j4gTuTmW">one-to-one correspondence</a> with the infinite set of <a href="/facts/Natural_number/u65og8JE">natural numbers</a> – informally, that there are <a href="/facts/Set_(mathematics)/BfucfHMq">sets</a> which in some sense contain more elements than there are positive integers. Such sets are now called <a href="/facts/Uncountable_set/zl2WqyJQ">uncountable sets</a>, and the size of infinite sets is treated by the theory of <a href="/facts/Cardinal_number/ccoKwU4R">cardinal numbers</a>, which Cantor began.
<a href="/facts/Georg_Cantor/k5v1DvW4">Georg Cantor</a> published this proof in 1891,: 20–  but it was not <a href="/facts/Cantor%27s_first_uncountability_proof/Y0johEdb">his first proof</a> of the uncountability of the <a href="/facts/Real_number/R02gw5Pb">real numbers</a>, which appeared in 1874.
However, it demonstrates a general technique that has since been used in a wide range of proofs, including the first of <a href="/facts/G%C3%B6del%27s_incompleteness_theorems/du8PRu8g">Gödel's incompleteness theorems</a> and Turing's answer to the <a href="/facts/Entscheidungsproblem/y8LDal2X">Entscheidungsproblem</a>. Diagonalization arguments are often also the source of contradictions like <a href="/facts/Russell%27s_paradox/XupqWGYt">Russell's paradox</a> and <a href="/facts/Richard%27s_paradox/rtnqLApq">Richard's paradox</a>.: 27

Cantor's diagonal argument open-in-new

Cantor's diagonal argument