TOPICS
Search

Cantor Diagonal Method


The Cantor diagonal method, also called the Cantor diagonal argument or Cantor's diagonal slash, is a clever technique used by Georg Cantor to show that the integers and reals cannot be put into a one-to-one correspondence (i.e., the uncountably infinite set of real numbers is "larger" than the countably infinite set of integers). However, Cantor's diagonal method is completely general and applies to any set as described below.

Given any set S, consider the power set T=P(S) consisting of all subsets of S. Cantor's diagonal method can be used to show that T is larger than S, i.e., there exists an injection but no bijection from S to T. Finding an injection is trivial, as can be seen by considering the function from S to T which maps an element s of S to the singleton set {s}. Suppose there exists a bijection phi from S to T and consider the subset D of S consisting of the elements d of S such that phi(d) does not contain d. Since phi is a bijection, there must exist an element x of S such that phi(x)=D. But by the definition of D, the set D contains x if and only if phi(x)=D does not contain x. This yields a contradiction, so there cannot exist a bijection from S to T.

Cantor's diagonal method applies to any set S, finite or infinite. If S is a finite set of cardinality n, then T=P(S) has cardinality 2^n, which is larger than n. If S is an infinite set, then T=P(S) is a bigger infinite set. In particular, the cardinality c of the real numbers R, which can be shown to be isomorphic to P(N), where N is the set of natural numbers, is larger than the cardinality aleph_0 of N. By applying this argument infinitely many times to the same infinite set, it is possible to obtain an infinite hierarchy of infinite cardinal numbers.


See also

Cardinal Number, Continuum Hypothesis, Countable Set, Countably Infinite

Explore with Wolfram|Alpha

References

Courant, R. and Robbins, H. What Is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 81-83, 1996.Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, pp. 220-223, 1998.Penrose, R. The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics. Oxford, England: Oxford University Press, pp. 84-85, 1989.

Referenced on Wolfram|Alpha

Cantor Diagonal Method

Cite this as:

Weisstein, Eric W. "Cantor Diagonal Method." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CantorDiagonalMethod.html

Subject classifications