Hilbert=s First Problem
Back to Contents
On 1900 Aug 08 in Paris, France, the German mathematician David Hilbert delivered a speech in which he laid out 23 problems for the mathematicians of the Twentieth Century to confront. Elsewhere on this website I have taken Hilbert=s Sixth Problem (Mathematical Treatment of the Axioms of Physics) as my subject (see The Map of Physics), but here I want to consider Hilbert= s First Problem, ACantor=s problem of the cardinal number of the continuum@:
ATwo systems, i.e. two assemblages of ordinary real numbers or points, are said to be (according to Cantor) equivalent or of equal cardinal number, if they can be brought into a relation with one another such that to every number of one assemblage corresponds one and only one definite number of the other. The investigations of Cantor on such assemblages of points suggest a very plausible theorem, which nonetheless, in spite of the most strenuous efforts, no one has succeeded in proving. This is the theorem:
Every system of infinitely many real numbers, i.e. every assemblage of numbers (or points), is either equivalent to the assemblage of natural integers, 1, 2, 3, ... or to the assemblage of all real numbers and therefore to the continuum, that is, to the points of a line; as regards equivalence there are, therefore, only two assemblages of numbers, the countable assemblage and the continuum.
From this theorem it would follow at once that the continuum has the next cardinal number beyond that of the countable assemblage; the proof of this theorem would, therefore, form a new bridge between the countable assemblage and the continuum.
Let me mention another very remarkable statement of Cantor=s which stands in the closest connection with the theorem mentioned and which, perhaps, offers the key to its proof. Any system of numbers is said to be ordered, if for every two numbers of the system it is determined which one is the earlier and which the later, and if at the same time this determination is of such a kind that, if a is before b and b is before c, then a always comes before c. The natural arrangement of numbers of a system is defined to be that in which the smaller precedes the larger. But there are, as is easily seen, infinitely many other ways in which the numbers of a system may be arranged.
If we think of a definite arrangement of numbers and select from them a particular system of these numbers, a so-called partial system or assemblage, this partial system will also prove to be ordered. Now Cantor considers a particular kind of ordered assemblage which he designates a well ordered assemblage and which is characterized in this way, that not only in the assemblage itself but also in every partial assemblage there exists a first number. The system of integers 1, 2, 3, ... in their natural order is evidently a well ordered assemblage. On the other hand the system of all real numbers, i.e. the continuum in its natural order, is evidently not well ordered. For, if we think of the points of a segment of a straight line, with its initial point excluded, as our partial assemblage, it will have no first element.
The question now arises whether the totality of all numbers may not be arranged in another manner so that every partial assemblage may have a first element, i.e., whether the continuum cannot be considered as a well ordered assemblage - a question which Cantor thinks must be answered in the affirmative. It appears to me most desirable to obtain a direct proof of this remarkable statement of Cantor=s, perhaps by actually giving an arrangement of numbers such that in every partial system a first number can be pointed out.@
Mathematicians call this the continuum problem. Hilbert drew it from a conjecture that Georg Cantor presented to his fellow mathematicians in 1878. If you look at the set of the real numbers, the numbers that we can use to label every point on a continuous line, then every infinite subset of that set will have a cardinal number either of the set of the natural numbers (Aleph-Null) or of the set of the real numbers (Aleph-One). Because we have already proven and verified the proposition that the name Aleph-One denotes an entity that does not exist in the realm of Mathematics, we have simply mooted Hilbert=s First Problem. But another look at how we do that may offer additional insights into the theory of numbers.
Cantor defined an infinite set as a set (what Hilbert called an assemblage) that we can put into a unique, bijective, one-to-one (ubijoto) relation with one of its proper subsets. We define a proper subset of a set S as any subset of S that does not equal S identically. We can use the set of the natural numbers (the positive integers) as our primary example of an infinite set. We know that the natural numbers give us an infinite set, because we know that we can never find a largest element of that set: the positive integers simply increase endlessly, which makes their set infinite. We can also prove and verify the infinity of the natural numbers by making an ubijoto match between the whole set and the proper subset of, say, the tens: we match one with ten, two with twenty, three with thirty, and so on. We know that we can never reach an end to that matching, because if someone points to one of the natural numbers and claims that a matching ten for it does not exist, we merely draw a zero between that number= s last digit and the implied decimal point. That new number is also an element of the set of the natural numbers, so we must match with its own ten-fold multiple, which is also an element of the set of the natural numbers. Thus we have another proof that the set of the natural numbers goes on without end.
That last statement reminds us that infinity denotes the mathematical concept of endlessness. In the light of that denotation we can see that Cantor=s infinities beyond Aleph-Null, the infinity of the natural numbers, come to us as endlessnesses more endless than endlessness. Describing the Alephs in that kind of hippie-dippie mystical gobble-honk, had anyone ever done it, might have raised in mathematicians minds more red flags than you would see at the May Day parade in Tienanman Square and led to an earlier discovery of the error that Cantor made in his proof of the statement that the set of the decimal extensions, the real numbers lying between zero and one, contains unmatchably more elements than does the set of the natural numbers.
Let=s take a fresh look at how Cantor proved the non-denumerability of the decimal fractions and how he went wrong in doing so. Imagine that we have written all of the natural numbers in their proper order in a column (and be very wary of that Aall of@). Next to each integer, on its right, we draw a decimal fraction chosen at random, never drawing the same one twice. If we claim that we now have an ubijoto match between the natural numbers and the decimal fractions, Cantor will claim that we don=t and he will prove his claim by showing us that he can generate a vast set of decimal fractions that don=t exist on our list. Actually he needs only to show us how to generate one of those numbers.
Cantor created his number in the following way: in the first place to the right of the decimal point he put a digit that differs from the first digit in the first fraction on our list. In the second place to the right of the decimal point he put a digit that differs from the second digit in the second fraction on our list. By that diagonalization procedure, making the n-th digit of his number different from the n-th digit of the n-th fraction on our list, Cantor claimed to have created a number that differs in at least one place from every fraction on our list. On that basis he inferred that the list of the decimal fractions would simply outrun the list of the natural numbers, even though that latter list extends infinitely, which necessarily meant that the infinity of the decimal fractions would have to differ from the infinity of the natural numbers. We have a straightforward way to prove and to verify the proposition that Cantor was wrong in that claim and inference.
Contemplate the fact that in our place-value system of representing numbers we can describe the set of the natural numbers as comprising all possible permutations of ten digits on an infinite set of places to the left of the decimal point. Likewise, we can describe the set of the decimal fractions as comprising all possible permutations of ten digits on an infinite set of places to the right of the decimal point. The mirror-like symmetry between those descriptions suggests a modification of Cantor=s list. Draw the set of the natural numbers in a column as before and then to the right of each integer draw the decimal fraction that represents the integer= s reflection through the decimal point; thus, next to 1 draw 0.1000..., next to 12 draw 0.21000..., next to 1024 draw 0.4201000..., and so on. There does not exist a decimal fraction that does not have a reflection in the natural numbers and there does not exist a positive integer that does not have a reflection in the decimal fractions. Thus we must infer that the list we just created gives us an ubijoto matching between the set of the natural numbers and the set of the decimal fractions, which necessarily means that the cardinality of the decimal fractions is the denumerable infinity of the natural numbers.
But Cantor=s diagonalization proof still seems reasonable, so how does it go wrong? Let=s try it with a finite list. Write down three numbers that extend only three places to the left of the decimal point (that=s right; I want to apply Cantor=s diagonalization to the set of the natural numbers to plant in your mind the thought that if Cantor=s process works for decimal fractions, it works equally well for the positive integers.). Now create a new number: in the first place to the left of the decimal point put a digit that differs from the first digit in the first number, then in the second place put a digit that differs from the second digit in the second number, and in the third place put a digit that differs from the third digit in the third number. You have thus created a number that does not exist on your list of three-digit numbers. But your list consists of three out of one thousand possible three-digit numbers, so the result does not surprise us. Cantor=s diagonalization argument only works if the number of entries on our list equals the number of digits in each entry. But even if we use binary numbers, the number of possible different entries far exceeds the number of digits in each entry and that fact remains true to Mathematics even if we let the number of digits go to infinity, so Cantor=s argument does not prove, much less verify, the proposition that the cardinality of the decimal fractions exceeds the cardinality of the natural numbers. In essence Cantor went wrong because, like all of us, he failed to understand fully the utter mind-boggling endlessness of infinity. But little by little we can correct the errors of our predecessors and gain a slightly better appreciation of the thoroughly bleak emptiness that extends far beyond the last number that we can name or draw, much less understand.
But we must still consider the full set of the real numbers. The set of the real numbers consists of every possible combination of a natural number united with a decimal fraction. Given that the sets of the natural numbers and of the decimal fractions each have a cardinality of infinity, we may feel a temptation to declare that the set of the real numbers has a cardinality of infinity squared, which must certainly be larger than infinity itself. But here we would be repeating the common error of taking infinity as representing a kind of number, however indeterminate, rather than representing the fact that an infinite set has no last member.
If we multiply every element of the set of decimal fractions by ten, we get a set of real numbers between zero and ten. Now we want to prove and verify the proposition that we have actually generated the complete set of the real numbers between zero and ten. As noted above, we can describe the set of the decimal fractions as the set containing all possible permutations of ten digits on an infinite string of places to the right of the decimal point. That fact allows us to take a subset of that set, say one whose elements all begin with the digit X in the first place to the right of the decimal point, and match its elements ubijotoly with the elements of the complete set of decimal fractions. That assertion must stand true to Mathematics because the elements of our subset consist of all instances of the digit X to which we have appended all possible permutations of ten digits on an infinite string of places to the right of X. Thus, if we multiply the elements of that subset by ten, the digit X becomes a natural number and the remaining fractional part comes into full coincidence with the set of the decimal fractions. It follows necessarily, then, that if we multiply the set of the decimal fractions by ten, we thereby generate the complete set of the real numbers lying between zero and ten. Q.E.D.
Knowing that, we now know that if we multiply the real numbers between zero and ten by ten, we obtain the set of all of the real numbers lying between zero and one hundred. If we multiply again by ten, we get all of the real numbers lying between zero and one thousand. We can continue those multiplications and thereby generate the full set of real numbers lying between zero and the appropriate power of ten without changing the cardinality of the set: we know that statement stands true to Mathematics because we only multiply already existing elements of the set and do not insert new ones. Indeed, we can apply that process endlessly and thereby generate the complete set of the real numbers. So now we know that we can make an ubijoto match between the set of the real numbers and the set of the decimal fractions, which we can put into an ubijoto relation with the set of the natural numbers. Thus we moot the first part of Hilbert=s problem by showing that the infinity of the counting numbers coincides identically with the infinity of the continuum, represented by the real numbers.
Finally we want to address the last part of Hilbert=s problem. Hilbert mentioned another statement that Cantor had made in regard to the continuum problem, one to the effect that Cantor believed that the set of the real numbers, representing the points on a continuous straight line extending to infinity, is a well-ordered set. Hilbert believed that, if true to Mathematics, that statement might provide the key to proving the previous theorem involving the continuum problem.
We have an ordered set of numbers if we can take any two numbers of the set and determine which of them comes earlier in the order and which comes later. We have the further requirement that for any numbers A, B, and C of the set we determine that, if A<B and B<C, then A<C always. We define the natural arrangement of numbers of a system to be that in which the smaller precedes the larger and our place-value system of representing numbers follows that plan. But we have infinitely many other ways in which we may arrange the numbers in a set and that fact opens up both challenges and opportunities.
Cantor went a step further and defined a well-ordered set as an ordered set that has a precisely defined first element. The set of the natural numbers gives a good example of a well-ordered set, one for which the first element is the number one. The set of the real numbers, on the other hand, does not give us a well-ordered set. If we think of the real numbers as the labels on the points comprising a segment of a straight line, the continuum, with its initial point excluded, then we have a set with no precisely defined first element.
With those facts in mind, Hilbert asked whether we might rearrange or re-conceive the complete set of the real numbers in such a manner that every subset would have a definite first element; that is, can we consider the continuum to constitute a well-ordered set? Cantor seems to have believed that we can answer that question in the affirmative and Hilbert wanted a proof, ideally a constructive proof in which we show the arrangement of the numbers in whose subsets we can point out the first elements.
As Hilbert noted, if we exclude the initial point of a straight line from the set of points comprising the line, the real numbers assigned to those points in proper order comprise an ordered set, but not a well-ordered set. The initial point on the line would take the number zero as its label, so absent zero, the first element of the continuum would have to take the smallest non-zero fraction as its label. Pick the smallest fraction that you can imagine: between that fraction and zero lies an infinite set of even smaller fractions. Attempting to find a smallest fraction gets us into the realm of the infinitesimals, the infinitely small (and the subject of a separate essay). Because we can never find a smallest fraction, just as we can never find a largest integer, we cannot find a precisely defined first element for the continuum, so the set of the real numbers, exclusive of zero, does not give us a well-ordered set.
If, on the other hand, we include zero in the set of the real numbers, then the set has a precisely defined first element and is, therefore, well-ordered. We can say in that case that we have a precisely defined first element because in place-value notation the number zero appears as an infinite string of zeros and only zeros to the right of the decimal point. If we can describe the fractional part of a number as an infinite string of a certain digit or cluster of digits (such as describing one-third as an infinite string of threes to the right of the decimal point), then we can make that number the first element of a subset of the real numbers, thereby making that subset well-ordered. We have an infinite array of numbers that match that description, so presumably we can satisfy Hilbert=s desire for a well-ordered set of well-ordered subsets of the real numbers.
Thus we have the answer to Hilbert=s First Problem. We haven=t so much solved the problem as we have mooted it. Instead of working out a solution of the continuum problem, we falsified one of the premises upon which Hilbert based it, proving and verifying the proposition that there exist no infinities beyond the infinity of the natural numbers. That=s not how we prefer to work in mathematics, but our knowledge of mathematics comes from human thought and humans make errors. It thus becomes incumbent upon us to correct the errors that we find.
Nor should we believe that Hilbert=s First Problem represents a wasted opportunity. Hilbert assumed that the process of answering the problem would improve our knowledge of mathematics and it has done so, though not in the way he expected or hoped. Nonetheless, we have achieved Hilbert=s goal and we can now put this problem away permanently.
Back to Contents