Cantor’s 1874 Proof of Non-Denumerability - English Translation
This is an English translation of Cantor’s 1874 Proof of the Non-Denumerability
of the real numbers. The original German text can be seen at:
It was published in the Journal für die Reine und Angewandte Mathematik,
commonly known as Crelle’s Journal; Vol 77 (1874), pages 258-262.
There is also a PDF version of this translation available: Cantor’s 1874 Proof of Non-Denumerability.
On a Property of the Set of all Real Algebraic Numbers
by Georg Cantor, 1874
By a real algebraic number one understands a real number ω which satisfies a non-constant equation of the form:
(1) a0ωn + a1ωn -1 + … + an = 0
where n, a0 , a1 , … an are integers: here the numbers n and a0 are positive, and the coefficients a0 , a1 , … an do not have any common factors, and the equation (1) is irreducible; with these stipulations it is the case, in accordance with known principles of arithmetic and algebra, equation (1), which is satisfied by a real algebraic number, is fully determinate; conversely, if n is the degree of an equation of the form (1), then the equation is satisfied by at no more than n real algebraic numbers ω. The real algebraic numbers constitute in their entirety a set of numbers (ω); it is clear that (ω) has the property that in every vicinity of any given number α there are infinitely many numbers of (ω) that lie within it. So it is likely that at first glance that it appears that one should be able to correlate the set (ω) one-to-one with the set (ν) of all positive integers ν in such a way that to every algebraic number w there corresponds a definite positive integer, and, conversely, to every positive integer v there corresponds an entirely definite real algebraic number ω. In other words, the set (ω) can be thought of in the form of an infinite ordered sequence
(2) ω1, ω2, … ων, …
in which all the individual real numbers of (ω) occur, and each such number occurs in (2) at a definitive position, which is given by the subscripts. Given that one has a definition by which such a correlation is defined, it can be modified at will; so in §1 I shall describe a correlation which seems to me the least complicated. In order to give an application of this property of the set of all real algebraic numbers I show in §2 that, given any arbitrarily chosen sequence of real numbers of the form (2), then in any given interval (α … β), I can define that there are numbers η which are not contained in (2); if one combines the results of these last two paragraphs, then one has a new proof of the theorem, first proved by Liouville, that in any given interval (α … β) there are infinitely many transcendental (i.e., not algebraic) real numbers. Further, the theorem in §2 turns out to be the reason why sets of real numbers which form a so-called continuum (concerning all real numbers which are ≥0 and ≤1) cannot be correlated one-to-one onto the set (ν); I have uncovered the essential difference between a so-called continuum and a set such as the set of all real algebraic numbers.
Let us return to equation (1), which is satisfied by an algebraic number ω and which, under the given conditions, is fully determined. Then the sum of the absolute values of its coefficients, plus the number n - 1 (where n is the degree of ω) shall be called the height of the number ω. Let it be designated by N. That is, in the usual notation:
(3) N = n - 1 + |a0| + |a1| + … + |an|
The height N is thus for every real algebraic number ω a definite positive integer; conversely, for any given positive integral value of N there are only finitely many algebraic real numbers with the height N; if we call this number be Φ(N), then, for example, Φ(1) = 1; Φ(2) = 2; Φ(3) = 4, and so on. The numbers of the set (ω), that is, the set of all algebraic real numbers, can then be set in order in the following way: take for the first number ω1 the single number with the height N = 1; for Φ(2), there are 2 algebraic real numbers with the height N = 2, so they are ordered according to their size, and we designate them by ω2, ω3 ; next, for Φ(3), there are 4 numbers with height N = 3, which are set in order according to size; in general, after all the numbers in (ω) up to a certain height N = N1 have been enumerated and assigned to a definite position, the real algebraic numbers with the height N = N1 + 1 follow them according to size; thus one obtains the set (ω) of all real algebraic numbers in the form:
ω1, ω2, … ων, …
One can, with respect to this ordering, refer to the νth real algebraic number; not a single member of the set has been omitted.
Given any definition of an infinite sequence of mutually distinct real numbers,
(4) ω1, ω2, … ων, …
then in any given interval (α … β) there is a number η (and consequently infinitely many such numbers) where it can be shown that it does not occur in the series (4); this shall now be proved.
We go to the end of the interval (α … β), which has been chosen arbitrarily and in which α < β; the first two numbers of our sequence (4) which lie in the interior of this interval (with the exception of the boundaries), can be designated by α′, β′ , letting α′ < β′; similarly let us designate the first two numbers of our sequence which lie in the interior of (α′ … β′) by α″, β″ and let α″ < β″; and in the same way we determine the next interval (α‴ … β‴ ) and so on. It follows that α′, α″, … are by definition determinate numbers of our sequence (4), whose indices are continually increasing; the same applies for the sequence β′, β″, … ; furthermore, the numbers α′, α″, … are always increasing in size, while the numbers β′, β″, … are always decreasing in size. Of the intervals (α′ … β′), (α″ … β″), (α‴ … β‴ ), … each encloses all of those following.
There are two conceivable cases:
Either the number of intervals formed is finite; in which case, let the last such interval be (α(ν) … β(ν)). Since in its interior there can be at most one number of the sequence (4), a number ν can be chosen from this interval which is not contained in (4), thereby proving the theorem for this case.
Or the number of intervals formed is infinite. Then the numbers α, α′, α″, … because they are always increasing in size without growing infinitely large, have a determinate limiting value α∞; the same holds for the numbers β, β′, β″, … because they are always decreasing in size, have a limiting value be β ∞; also α∞ = β ∞ (such a case always occurs with the set (ω) of all real algebraic numbers), so one is readily satisfied, by looking back at the definition of the intervals, that the number η = α∞ = β ∞ cannot be contained in our sequence; (Footnote: If the number η were contained in our sequence, then one would have η = ωp , where p is a specific index. But this is not possible, for ωp does not lie in the interior of the interval (α(p) … β(p)), while by definition the number η does lie in the interior of the interval. ) but if α∞ < β ∞ then every number η in the interior of the interval (α∞ … β ∞) or at its endpoints satisfies the requirement that it not be contained in the sequence (4).
The theorems proved in this article admit of extensions in various directions, only one of which will be mentioned here:
“If ω1, ω2, … ωn, … is a finite or infinite sequence of numbers which are linearly independent of each another (so that no equation of the form a1ω1 + a2ω2 + … + anωn = 0 is possible with integral coefficients which do not all vanish) and if one imagines the set (Ω) of all those numbers Ω which can be represented as rational functions with integral coefficients of the given numbers ω, then in every interval (α … β) there are infinitely many numbers which are not contained in (Ω).”
In fact one can be satisfied through a method of proof similar to that in §1 that the set (Ω) can be conceived in the sequential form
Ω1, Ω2, … Ων, …
from which, in view of §2, the truth of the theorem follows.
A quite special case of the theorem cited here (in which the sequence ω1, ω2, … ωn, … is finite and the degree of the rational functions, which yield the set (Ω), is predetermined) has been proved, by recourse to Galoisian principles, by Herr B. Minnigerode (See Math. Annalen, Vol. 4, p. 497).