| Cantor's Diagonal Argument |
Article Index for Cantor's |
Website Links For Diagonal |
Information AboutCantor's Diagonal Argument |
|
Cantor's diagonal argument is a Proof devised by Georg Cantor to demonstrate that the Real Number s are not Countably Infinite . (It is also called the ''diagonalization argument'' or the ''diagonal slash argument'' or the ''diagonal method''.) The diagonal argument was not Cantor's first proof of the uncountability of the real numbers, but was published three years after his first proof. 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 {Link without Title} is not countably infinite. The Proof By Contradiction proceeds as follows: # Assume (for the sake of argument) that the interval {Link without Title} is countably infinite. # There must then exist a Sequence M in the form ( ''r''1, ''r''2, ''r''3, ... ) that enumerates all numbers in this interval. # We may represent each of these numbers as an infinite Decimal Expansion . In the case of numbers with two decimal expansions, like 0.499 ... = 0.500 ..., we pick the one ending in nines. # We arrange the numbers in a list. Assume, for example, that the decimal expansions of the beginning of the sequence, M, are as follows: #: ''r''1 = 0 . 5 1 0 5 1 1 0 ... #: ''r''2 = 0 . 4 1 3 2 0 4 3 ... #: ''r''3 = 0 . 8 2 4 5 0 2 6 ... #: ''r''4 = 0 . 2 3 3 0 1 2 6 ... #: ''r''5 = 0 . 4 1 0 7 2 4 6 ... #: ''r''6 = 0 . 9 9 3 7 8 3 8 ... #: ''r''7 = 0 . 0 1 0 5 1 3 5 ... #: ... # We shall now construct a real number ''x'' in {Link without Title} by considering the ''k''th digit after the decimal point of the Decimal Expansion of ''r''k. The digits we will consider are underlined and in bold face, illustrating why this is called the diagonal proof. #: ''r''1 = 0 . 5 1 0 5 1 1 0 ... #: ''r''2 = 0 . 4 1 3 2 0 4 3 ... #: ''r''3 = 0 . 8 2 4 5 0 2 6 ... #: ''r''4 = 0 . 2 3 3 0 1 2 6 ... #: ''r''5 = 0 . 4 1 0 7 2 4 6 ... #: ''r''6 = 0 . 9 9 3 7 8 3 8 ... #: ''r''7 = 0 . 0 1 0 5 1 3 5 ... #: ... # From these digits we define the digits of ''x'' as follows.
# We know then, that for any possible sequence M, there exists a number ''x'' which is clearly a real number (since all decimal expansions represent real numbers) in {Link without Title} . For the above sequence, for example, we obtain the following decimal expansion: #: ''x'' = 0 . 4 5 5 5 5 5 4 ... # Hence we must have ''r''''n'' = ''x'' for some ''n'', since we have assumed that ( ''r''1, ''r''2, ''r''3, ... ) enumerates all real numbers in 1 . # However, because of the way we have chosen 4's and 5's as digits in step (6), ''x'' differs in the ''n''th decimal place from ''r''''n'', so ''x'' is not in the sequence ( ''r''1, ''r''2, ''r''3, ... ). # This sequence is therefore not an enumeration of the set of all reals in the interval {Link without Title} . This is a contradiction. # Hence the assumption (1) that the interval {Link without Title} 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 {Link without Title} 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 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 WHY THIS DOES NOT WORK ON INTEGERS The proof cannot be adapted to the integers to show that they too are uncountable, because an infinite sequence of non-zero digits, as might be created by dropping the decimal point from a decimal expansion of a real number, does not represent an integer. This is the reason for step (7) above. GENERAL SETS A generalized form of the diagonal argument was used by Cantor to prove ''S'' the Power Set of ''S'', i.e., the set of all Subset s 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 Comprehension in which cannot in general be shown to exist. (where |
|
|