Our website is made possible by displaying online advertisements to our visitors.
Please consider supporting us by disabling your ad blocker.

Responsive image

Cantor's diagonal argument

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.
An infinite set may have the same cardinality as a proper subset of itself, as the depicted bijection f(x)=2x from the 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[note 1]) is a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers – informally, that there are sets which in some sense contain more elements than there are positive integers. Such sets are now called uncountable sets, and the size of infinite sets is treated by the theory of cardinal numbers, which Cantor began.

Georg Cantor published this proof in 1891,[1][2]: 20– [3] but it was not his first proof of the uncountability of the real numbers, which appeared in 1874.[4][5] However, it demonstrates a general technique that has since been used in a wide range of proofs,[6] including the first of Gödel's incompleteness theorems[2] and Turing's answer to the Entscheidungsproblem. Diagonalization arguments are often also the source of contradictions like Russell's paradox[7][8] and Richard's paradox.[2]: 27 


Cite error: There are <ref group=note> tags on this page, but the references will not show without a {{reflist|group=note}} template (see the help page).

  1. ^ Georg Cantor (1891). "Ueber eine elementare Frage der Mannigfaltigkeitslehre". Jahresbericht der Deutschen Mathematiker-Vereinigung. 1: 75–78. English translation: Ewald, William B., ed. (1996). From Immanuel Kant to David Hilbert: A Source Book in the Foundations of Mathematics, Volume 2. Oxford University Press. pp. 920–922. ISBN 0-19-850536-1.
  2. ^ a b c Keith Simmons (30 July 1993). Universality and the Liar: An Essay on Truth and the Diagonal Argument. Cambridge University Press. ISBN 978-0-521-43069-2.
  3. ^ Rudin, Walter (1976). Principles of Mathematical Analysis (3rd ed.). New York: McGraw-Hill. p. 30. ISBN 0070856133.
  4. ^ Gray, Robert (1994), "Georg Cantor and Transcendental Numbers" (PDF), American Mathematical Monthly, 101 (9): 819–832, doi:10.2307/2975129, JSTOR 2975129
  5. ^ Bloch, Ethan D. (2011). The Real Numbers and Real Analysis. New York: Springer. p. 429. ISBN 978-0-387-72176-7.
  6. ^ Sheppard, Barnaby (2014). The Logic of Infinity (illustrated ed.). Cambridge University Press. p. 73. ISBN 978-1-107-05831-6. Extract of page 73
  7. ^ Russell's paradox. Stanford encyclopedia of philosophy. 2021.
  8. ^ Bertrand Russell (1931). Principles of mathematics. Norton. pp. 363–366.

Previous Page Next Page






حجة كانتور القطرية Arabic কান্টরের কর্ণ যুক্তি Bengali/Bangla Diagonalització de Cantor Catalan Cantorova diagonální metoda Czech Cantors diagonalbevis Danish Cantors zweites Diagonalargument German Diagonala argumento de Cantor EO Argumento de la diagonal de Cantor Spanish Cantori diagonaaltõestus ET Cantorren Argudio Diagonala EU

Responsive image

Responsive image