Cantor's diagonal argument |
Note: in order to fully understand this article you may want to refer to the set theory portion of the Table of mathematical symbols.
Cantor's diagonal argument is a proof
devised by Georg Cantor to demonstrate that the real numbers are not countably
infinite. (It is also called the diagonalization argument or the diagonal slash argument.)
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.
Real numbers
Cantor's original proof shows that the interval
[0,1] is not countably infinite.
The proof by contradiction proceeds as follows:
- (1) Assume that the interval [0,1] is countably infinite.
- (2) We may then enumerate the numbers in this interval as a sequence, {
r1, r2, r3, ... }
- (3) We shall now construct a real number x in [0,1] by considering the nth digit after the
decimal point of the decimal expansion of rn.
In the case of numbers with two decimal expansions, like 0.499 ... = 0.500 ..., we chose the one ending in nines.
Assume, for example, that the decimal expansions of the beginning of the sequence are as follows.
r1 = 0 . 5 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 5 ...
...
- The digits we will consider are indicated in bold. From these digits we define the digits of x as follows.
-
- if the nth digit of rn is 5 then the nth digit of
x is 4
- if the nth digit of rn is not 5 then the nth digit of
x is 5
- For the example above this will result in the following decimal expansion.
x = 0 . 4 5 5 5 5 5 4 ...
- The number x is clearly a real number in [0,1].
- (4) However, it differs in the nth decimal place from rn, so x is
not in the set { r1, r2, r3, ... }.
- (5) This set is therefore not an enumeration of all the reals in the interval [0,1].
- (6) This is true for any such enumeration sequence and therefore contradicts (2), so the assumption (1) that the interval
[0,1] is countably infinite must be false.
It is a direct corollary of this result that the set R of all real numbers is uncountable. If R were countable,
we could enumerate all of the real numbers in a sequence, and then get a sequence enumerating [0, 1] by removing all of the real
numbers outside this interval. But we have just shown that this latter list cannot exist. Alternatively, we could show that [0,
1] and R are the same size by constructing a bijection between them. This
is slightly awkward to do, though possible, for the closed interval [0, 1]; for the open interval (0, 1) we might use defined by .
General sets
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
-
If T is in the range of f, then for some t in S we have T =
f(t). Either t is in T or not. If t is in T, then t is in
f(t), but, by definition of T, that implies t is not in T. On the other hand, if
t is not in T, then t is not in f(t), and by definition of T, that implies
t is in T. Either way, we have a contradiction.
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.
The above proof fails for W. V. Quine's "New Foundations" set theory,
which has a different version of the axiom of separation in
which cannot be
expressed. In fact New Foundations has a "universal set" U such that U =
P(U).
For a more concrete account of this proof that is possibly easier to understand see Cantor's theorem.
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.
|