Cantor's First Uncountability Proof - Is Cantor's Proof of The Existence of Transcendentals Constructive or Non-constructive?

Is Cantor's Proof of The Existence of Transcendentals Constructive or Non-constructive?

Some mathematicians claim that Cantor's proof of the existence of transcendental numbers is constructive—that is, it provides a method of constructing a transcendental number. For example, Irving Kaplansky writes:

It is often said that Cantor's proof is not "constructive," and so does not yield a tangible transcendental number. This remark is not justified. If we set up a definite listing of all algebraic numbers … and then apply the diagonal procedure …, we get a perfectly definite transcendental number (it could be computed to any number of decimal places) … (I owe these remarks to R. M. Robinson.)

Other mathematicians claim that Cantor's proof is non-constructive. According to Ian Stewart:

… The set of real numbers is uncountable. There is an infinity bigger than the infinity of natural numbers! The proof is highly original. Roughly, the idea is to assume that the reals are countable, and argue for a contradiction. … Building on this, Cantor was able to give a dramatic proof that transcendental numbers must exist. … Cantor showed that the set of algebraic numbers is countable. Since the full set of reals is uncountable, there must exist numbers that are not algebraic. End of proof (which is basically a triviality); collapse of audience in incredulity. In fact Cantor's argument shows more: it shows that there must be uncountably many transcendentals! There are more transcendental numbers than algebraic ones; and you can prove it without ever exhibiting a single example of either.

As the above examples show, these two groups of mathematicians are discussing different but related proofs—one proof is constructive while the other is non-constructive. Both proofs use a construction that takes a sequence of real numbers and produces a real number not belonging to this sequence. This construction is either the one in Cantor's 1874 article, or it uses his diagonal method. The proofs differ in how they use this construction.

The constructive proof applies it to the sequence of real algebraic numbers, thus producing a transcendental number. Cantor gave this proof in his article (see "The article").

The non-constructive proof starts by assuming that the set of real numbers is countable, or equivalently: the real numbers can be written as a sequence. Applying the construction to this sequence produces a real number not in the sequence, which contradicts the assumption that this sequence contains all real numbers. Hence, the set of real numbers is uncountable. Since the set of algebraic numbers is countable, transcendental numbers must exist. This proof does not construct a single transcendental number.

Cantor's constructions have been used to write computer programs that generate transcendental numbers. These programs show that his constructions produce computable numbers. The program that uses Cantor's diagonal method computes the digits of a transcendental number in polynomial time, while the program that uses his 1874 construction requires at least sub-exponential time.

The constructive nature of Cantor's work is easily demonstrated by using his two methods to construct irrational numbers. Both constructions start with the same sequence of rational numbers between 0 and 1. This sequence is formed by ordering these rational numbers by increasing denominators, and ordering those with the same denominator by increasing numerators.

The table below constructs an irrational number x by using Cantor's diagonal method. The strategy is to construct the decimal representation of a number that differs from the decimal representation of every rational number in our sequence. We choose the n-th digit of x so that it differs from the n-th digit of the n-th member of our sequence. If the latter digit is between 0 and 7, add 1 to obtain the n-th digit of x; otherwise, let the n-th digit of x be 0. So the decimal representation for x differs from every decimal in our sequence. Also, x is between 0 and 1, and its decimal representation does not contain the digit 9. Hence, x is irrational.

Generating an Irrational x
1/2 = 0.5 . . .
1/3 = 0.33 . . .
2/3 = 0.666 . . .
1/4 = 0.2500 . . .
3/4 = 0.75000 . . .
• • •
x = 0.64711 . . .

The next table constructs an irrational number by using Cantor's 1874 construction. The strategy is to construct a sequence of nested intervals such that every rational number is excluded from the interior of some interval. Cantor's construction starts by finding the first two numbers in our sequence that belong to the interior of our starting interval . These numbers are 1/2 and 1/3, and they form the interval . Next we find the next two numbers in our sequence that belong to the interior of . Continuing this process generates a sequence of nested intervals. This sequence does not terminate since we can always find two rational numbers belonging to the interior of an interval.

In our table, the first column contains the interval, and the last column lists the rationals excluded in our search for the first two rationals belonging to this interval's interior. These excluded rationals are in the same order as our original sequence with one exception—namely, one of the endpoints of the next interval. For example, the exception in the first row is 2/5, and it is the first number excluded in the next row. Every rational number is excluded from some interval's interior because the sequence of intervals does not terminate and the interior of every interval excludes at least two rational numbers (the interval's endpoints). Thus, a real number belonging to the interior of every interval is irrational. In his proof, Cantor constructs such a real number by taking the limits of the endpoints of the intervals.

Generating an irrational using Cantor's 1874 construction
Interval Interval (decimal) Rational numbers outside interval's interior
1/2, 1/3; 2/3, 1/4, 3/4, 1/5, 3/5, 4/5, 1/6, 5/6, 1/7, 2/7
2/5, 3/7; 4/7, …, 1/12, 7/12, …, 6/17
5/12, 7/17; 8/17, …, 11/29, 13/29, …, 16/41
12/29, 17/41; 18/41, …, 27/70, 31/70, …,40/99
29/70, 41/99; 43/99, …, 69/169, 71/169, …, 98/239

Read more about this topic:  Cantor's First Uncountability Proof

Famous quotes containing the words proof, existence and/or constructive:

    He who has never failed somewhere, that man can not be great. Failure is the true test of greatness. And if it be said, that continual success is a proof that a man wisely knows his powers,—it is only to be added, that, in that case, he knows them to be small.
    Herman Melville (1819–1891)

    During a walk or in a book or in the middle of an embrace, suddenly I awake to a stark amazement at everything. The bare fact of existence paralyzes me... To be alive is so incredible that all I can do is to lie still and merely breathe—like an infant on its back in a cot. It is impossible to be interested in anything in particular while overhead the sun shines or underneath my feet grows a single blade of grass.
    W.N.P. Barbellion (1889–1919)

    Friendship among nations, as among individuals, calls for constructive efforts to muster the forces of humanity in order that an atmosphere of close understanding and cooperation may be cultivated.
    Franklin D. Roosevelt (1882–1945)