home | alphabetical index | |||||

## Cantor's diagonal argumentCantor'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 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: - (1) Assume that the interval (0,1) is countably infinite.
- (2) We may then enumerate the numbers in this interval as a sequence, {
*r*_{1},*r*_{2},*r*_{3}, ... } - (3) We shall now construct a real number
*x*between 0 and 1 by considering the*n*^{th}digit after the decimal point of the decimal expansion of*r*_{n}. Assume, for example, that the decimal expansions of the beginning of the sequence are as follows.
x as follows.
- if the
*n*^{th}digit of*r*_{n}is 0 then the*n*^{th}digit of*x*is 1 - if the
*n*^{th}digit of*r*_{n}is not 0 then the*n*^{th}digit of*x*is 0
- if the
x is clearly a real number between 0 and 1.
- (4) However, it differs in the
*n*^{th}decimal place from*r*_{n}, so*x*is not in the set {*r*_{1},*r*_{2},*r*_{3}, ... }. - (5) This set is therefore not an enumeration of all the reals in the interval (0,1).
- (6) This contradicts with (2), so the assumption (1) that the interval (0,1) is countably infinite must be false.
Note: Strictly speaking, this argument only shows that the number of decimal expansions of real numbers between 0 and 1 is not countably infinite. But since there are expansions such as 0.01999... and 0.02000... that represent the same real number, this does not immediately imply that the corresponding set of real numbers is also not countably infinite. This can be remedied by disallowing the decimal expansions that end with an infinite series of 9's. In that case it can be shown that for every real number there is a unique corresponding decimal expansion. It is easy to see that the proof then still works because the number x contains only 1's and 0's in its decimal expansion.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.
A generalized form of the diagonal argument was used by Cantor to prove Cantor's theorem: for every set
Let
T is in the range of f, then for some t ε S we have T = f(t). Either t ε T or not.
If t ε T, then t ε f(t), but, by definition of T, that implies t not ε T. On the other hand, if t not ε T, then t not ε f(t), and by definition of T, that implies t ε T. Either way, we have a contradition.
Note the similarity between the construction of P() would at the same time be bigger than S and a subset of S. SAnalogues 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
| |||||

copyright © 2004 FactsAbout.com |