Editing Cantor's diagonal argument (section)

{{short description|Proof in set theory}}

{{Anchor|Lead}}[[Image:Diagonal argument 01 svg.svg|right|thumb|250px|An illustration of Cantor's diagonal argument (in base 2) for the existence of [[uncountable set]]s. The sequence at the bottom cannot occur anywhere in the enumeration of sequences above.]]
[[File:Aplicación 2 inyectiva sobreyectiva02.svg|right|thumb|250px|An [[infinite set]] may have the same [[cardinality]] as a proper [[subset]] of itself, as the depicted [[bijection]] ''f''(''x'')=2''x'' from the [[natural numbers|natural]] to the [[even numbers]] demonstrates. Nevertheless, infinite sets of different cardinalities exist, as Cantor's diagonal argument shows.]]

'''Cantor's diagonal argument''' (among various similar names<ref group="note">the '''diagonalisation argument''', the '''diagonal slash argument''', the '''anti-diagonal argument''', the '''diagonal method''', and '''Cantor's diagonalization proof'''</ref>) is a [[mathematical proof]] that there are [[infinite set]]s which cannot be put into [[bijection|one-to-one correspondence]] with the infinite set of [[natural number]]s{{snd}}informally, that there are [[Set (mathematics)|set]]s which in some sense contain more elements than there are positive integers.  Such sets are now called [[uncountable set]]s, and the size of infinite sets is treated by the theory of [[cardinal number]]s, which Cantor began.

[[Georg Cantor]] published this proof in 1891,<ref name="Cantor.1891">{{cite journal|author=Georg Cantor |title=Ueber eine elementare Frage der Mannigfaltigkeitslehre |journal=[[Jahresbericht der Deutschen Mathematiker-Vereinigung]] |volume=1 |pages=75–78 |year=1891|url=https://www.digizeitschriften.de/dms/img/?PID=GDZPPN002113910&physid=phys84#navi}} English translation: {{cite book |editor-last=Ewald |editor-first=William B.  |title=From Immanuel Kant to David Hilbert: A Source Book in the Foundations of Mathematics, Volume 2 |publisher=Oxford University Press |pages=920–922 |year=1996 |isbn=0-19-850536-1}}</ref><ref name="Simmons1993">{{cite book|author=Keith Simmons| author-link=Keith Simmons (philosopher)| title=Universality and the Liar: An Essay on Truth and the Diagonal Argument|url=https://books.google.com/books?id=wEj3Spept0AC&pg=PA20|date=30 July 1993|publisher=Cambridge University Press|isbn=978-0-521-43069-2}}</ref>{{rp|20–}}<ref name="Rubin1976">{{cite book|last1=Rudin|first1=Walter|title=Principles of Mathematical Analysis|date=1976|publisher=McGraw-Hill|location=New York|isbn=0070856133|page=[https://archive.org/details/principlesofmath00rudi/page/30 30]|edition=3rd|url-access=registration|url=https://archive.org/details/principlesofmath00rudi/page/30}}</ref> but it was not [[Cantor's first uncountability proof|his first proof]] of the uncountability of the [[real number]]s, which appeared in 1874.<ref>{{Citation |surname=Gray|given=Robert|year=1994 |url=http://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Gray819-832.pdf |title=Georg Cantor and Transcendental Numbers|journal=[[American Mathematical Monthly]]|volume=101|issue=9|pages=819–832 |doi=10.2307/2975129|jstor=2975129}}</ref><ref name="Bloch2011">{{cite book|last1=Bloch|first1=Ethan D.|title=The Real Numbers and Real Analysis|url=https://archive.org/details/realnumbersreala00edbl|url-access=limited|date=2011|publisher=Springer|location=New York|isbn=978-0-387-72176-7|page=[https://archive.org/details/realnumbersreala00edbl/page/n458 429]}}</ref>
However, it demonstrates a general technique that has since been used in a wide range of proofs,<ref>{{cite book |title=The Logic of Infinity |edition=illustrated |first1=Barnaby |last1=Sheppard |publisher=Cambridge University Press |year=2014 |isbn=978-1-107-05831-6 |page=73 |url=https://books.google.com/books?id=RXzsAwAAQBAJ}} [https://books.google.com/books?id=RXzsAwAAQBAJ&pg=PA73 Extract of page 73]</ref> including the first of [[Gödel's incompleteness theorems]]<ref name="Simmons1993"/> and Turing's answer to the ''[[Entscheidungsproblem]]''.  Diagonalization arguments are often also the source of contradictions like [[Russell's paradox]]<ref>{{cite book|url=http://plato.stanford.edu/entries/russell-paradox|title=Russell's paradox|year=2021 |publisher=Stanford encyclopedia of philosophy}}</ref><ref>{{cite book|author=Bertrand Russell|title=Principles of mathematics|pages=363–366|publisher=Norton|year=1931}}</ref> and [[Richard's paradox]].<ref name="Simmons1993"/>{{rp|27}}