Cantor Diagonal Method

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). It proceeds by first considering a countably infinite list of elements from a set $S$, each of which is an infinite set (in the case of the Reals, the decimal expansion of each Real). A new member $S'$ of $S$ is then created by arranging its $n$th term to differ from the $n$th term of the $n$th member of $S$. This shows that $S$ is not Countable, since any attempt to put it in one-to-one correspondence with the integers will fail to include some elements of $S$.

See also Cardinality, Continuum Hypothesis, Countable Set, Countably Infinite Set

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.

Penrose, R. The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics. Oxford, England: Oxford University Press, pp. 84-85, 1989.