Contrary to what many mathematicians believe, the diagonal argument was not Cantor's first proof of the uncountability of the real numbers, but was published three years later. His original argument did not mention decimal expansions, nor any other numeral system.
Since this technique was first used, similar proof constructions have been used many times in a wide range of proofs. These are also known as diagonal arguments by analogy with the argument used in this proof.
Cantor's original proof proceeds by showing that the interval (0,1), that is, the set of real numbers larger than 0 and smaller than 1, is not countably infinite.
The proof by contradiction proceeds as follows:
r1 = 0 . 0 1 0 5 1 1 0 ... r2 = 0 . 4 1 3 2 0 4 3 ... r3 = 0 . 8 2 4 5 0 2 6 ... r4 = 0 . 2 3 3 0 1 2 6 ... r5 = 0 . 4 1 0 7 2 4 6 ... r6 = 0 . 9 9 3 7 8 3 8 ... r7 = 0 . 0 1 0 5 1 3 0 ... ...
x = 0 . 1 0 0 1 0 0 1 ...
The diagonal argument is an example of reductio ad absurdum because it proves a certain proposition (the interval (0,1) is not countably infinite) by showing that the assumption of its negation leads to a contradiction.
Note:The above argument, as given, is fallacious, since the constructed x could be 0. However it does prove that [0,1) is uncountable. Given this we can easily deduce that (0,1) is uncountable: suppose that r1, r2, ... counted (0,1). Then set s1=0, s2 =r1, s3=r2, ... then the s sequence counts [0,1) which was shown impossible--so (0,1) is also uncountable.
A generalized form of the diagonal argument was used by Cantor to prove Cantor's theorem: for every set S the power set of S, i.e., the set of all subsets of S (here written as P(S)), is larger than S itself. This proof proceeds as follows:
Let f be any one-to-one function from S to P(S). It suffices to prove f cannot be surjective. That means that some member of P(S), i.e., some subset of S, is not in the image of f. That set is
Note the similarity between the construction of T and the set in Russell's paradox. Its result can be used to show that the notion of the set of all sets is an inconsistent notion in normal set theory; if S would be the set of all sets then P(S) would at the same time be bigger than S and a subset of S.
Analogues of the diagonal argument are widely used in mathematics to prove the existence or nonexistence of certain objects. For example, the conventional proof of the unsolvability of the halting problem is essentially a diagonal argument.
The diagonal argument shows that the set of real numbers is "bigger" than the set of integers. Therefore, we can ask if there is a set whose cardinality is "between" that of the integers and that of the reals. This question leads to the famous continuum hypothesis. Similarly, the question of whether there exists a set whose cardinality is between s and P(s) for some s, leads to the generalized continuum hypothesis.