Fascination and repulsion have been my two most common reactions to the transfinite mathematics originated by German mathematician / philosopher Georg Cantor (1845-1918), because on the one hand the possibility of multiple infinities of different sizes is fascinating; but on the other hand the idea that one infinity could be bigger than another, or that there could exist different degrees of boundlessness, or that one limitlessness could be more unlimited than another limitlessness seems intuitively absurd. To the nonmathematical intuition it seems obvious that infinity is infinity, a unique unlimitedness which nothing finite can express and of which nothing greater can be imagined.
But this latter infinity of which nothing greater can be imagined is what Cantor called absolute infinity, and it must be remembered also that he coined the term transfinite specifically to indicate that his new numbers were to be thought of as greater than any finitude but not so great as this absolute infinity. Take a look at the specific question he was grappling with as he wrote it to Dedekind in a letter dated November 29, 1873 [1]:
Take the totality of all positive whole-numbered individuals n and designate it by (n). And imagine say the totality of all positive real numerical quantities x and designate it by (x). The question is simply, can (n) be correlated to (x) in such a way that to each individual of the one totality there corresponds one and only one of the other?While it is tempting to reword the question to the seemingly simpler "is the number of positive points on the real line equal to the number of positive integers 1, 2, 3, 4, ...?", if we do this we lose the precise mathematical definition of counting to which Cantor is referring: the one-to-one correspondence, or bijection. In terms of set theory, to count is to put the counted items into a one-to-one correspondence with a subset of the natural numbers N = {1, 2, 3, 4, ...}. For example, how many moons does the planet Mars have? The answer is 2 because of the correspondence
2 ⇔ Deimos
in which we have shown that the set of Mars' moons is the same size as the subset {1, 2} of N. The shorthand way to write this same correspondence is simply to subscript the elements of the set being counted with their natural number counterparts: i.e. {Phobos1, Deimos2}. So it is obvious that the set of Pacific coast US states {AK1, WA2 , OR3, CA4} has 4 elements, and the set of all even prime numbers {21} has 1 element, etc.
The set-theoretical term for how many elements are in a set is cardinality. So for example if set P = {2, 3, 5, 7, 11, 13} then the cardinality of P is six, which we write as n(P)=6. Likewise if set W = {234, π−1, 10500} then n(W)=3, and so in general n(A)=n if A = {x1, x2, x3, ..., xn} where n is an element of N.
And the point of formalizing counting in such a precise manner is to enable the extension of the concept into infinite sets. If we let R equal the set of all positive real numbers then we can restate Cantor's question to Dedekind very briefly: is the equality n(N)=n(R) true? "At first glance one says to oneself no, it is not possible," Cantor said in the very same letter, "for N consists of discrete parts while R forms a continuum."
But first of all, what is the value of n(N)? How many natural numbers are there? Since for any element x in N the number x+1 is also in N we know at least that there are infinitely many. But since Cantor was investigating the possibility of infinities of different sizes he set the value of n(N) equal to ℵ0 (aleph-null), and defined the cardinality of any set which can be put into one-to-one correspondence with N to be ℵ0 also. To get a sense of the strange behavior of ℵ0 take a look at the following theorems proved by Cantor in 1895 (where n is any element of N) [2]:
ℵ0 + ℵ0 = ℵ0
ℵ0 × n = ℵ0
ℵ0 × ℵ0 = ℵ0
ℵ0n = ℵ0
As an example of the second theorem ℵ0 + ℵ0 = ℵ0 let E be the set of all even numbers {2, 4, 6, 8, ...} and F be the set of all odd numbers {1, 3, 5, 7, ...}. Since the evens can be generated by the simple formula 2n and the odds by the related formula 2n−1 then we know that there exists a one-to-one correspondence between E and N as well as between F and N. That is, the nth element of E is always 2n and the nth element of F is always 2n−1:
N | E | F | ||
1 | ⇔ | 2 | ⇔ | 1 |
2 | ⇔ | 4 | ⇔ | 3 |
3 | ⇔ | 6 | ⇔ | 5 |
... | ⇔ | ... | ⇔ | ... |
n | ⇔ | 2n | ⇔ | 2n−1 |
... | ⇔ | ... | ⇔ | ... |
From the correspondences set up above it is clear that both n(E) and n(F) equal ℵ0, and thus when we recombine the two sets E and F to form N we can see that ℵ0 + ℵ0 = ℵ0.
Next we turn to the set Q of all positive rational numbers, defined as those that can be expressed in the form x/y where x and y are elements of N: i.e. 1/1, 1/2, 2/5, 3/4, etc. Note that Q also includes all elements of N since any element of N can be expressed as a rational by simply putting 1 as the denominator: i.e. 1 = 1/1, 2 = 2/1, 3 = 3/1, etc. While this might seem to suggest that there are more elements in Q than in N, in fact it is possible to set up a one-to-one correspondence between Q and N using the matrix
in which the rows and columns are numbered with elements of N and the entries are the elements of Q formed using the row numbers (pink) as numerators and the column numbers (blue) as denominators. The path of the arrows is then followed to order the elements of Q in such a way that every element appears exactly once and thus corresponds to one and only one element of N: 1/11, 2/12, 1/23, 1/34, 3/15, 4/16, and so on. The crossed-out matrix entries are excluded because they are duplicates (not in lowest terms): viz. 2/2 is the same as 1/1, 2/4 is the same as 1/2, 4/2 is the same as 2/1, etc. And since it is clear that no element of Q is missing from the matrix [for any rational x/y imaginable will appear at row x, column y] this constitutes a proof that n(Q) = ℵ0.
At last we turn to the irrational numbers, those which cannot be expressed in the form x/y where x and y are elements of N: i.e. √2, φ, e, π, etc. Basically, if you were to construct a number line consisting only of elements of Q, then that line would not exhibit the property of continuity; it would not be continuous. In other words, it would have gaps; very specific gaps corresponding precisely to the irrational points (or measurements) on the line. Hence to conceive of the real line, or the continuum R, it is necessary to take the rational line and imagine all of its gaps being filled by irrational numbers. We then arrive at the property which intuitively captures the essence of continuity, gaplessness, as well as the significant corollary resulting from this property: any real line segment − no matter how small − contains infinitely many real numbers.
In 1874 Cantor published a paper entitled On a Property of the Set of Real Algebraic Numbers [1], in which he presented his first proof that R cannot be put into one-to-one correspondence with N, and with which his intuition regarding his question to Dedekind in the previous year's letter was confirmed. Although presentations of this proof exist elsewhere, I have chosen to reproduce it here in my own way because (a) personally working through Cantor's original proof has finally helped me to fully comprehend his groundbreaking theorem, and (b) different presentations of the same mathematical material always create the possibility of someone understanding it who did not understand it before.
We begin with an infinite sequence of real numbers (call it S) given according to any law and where the numbers are distinct from each other.
Then we imagine any given interval (α . . . β) on the real line where α < β. Now begin to build the sequence S from the nested intervals (α′ . . . β′), (α′′ . . . β′′), (α′′′ . . . β′′′), ... such that each interval is contained in the previous one and all are contained in the original interval (α . . . β); viz. x1 = α′, x2 = β′, x3 = α′′, x4 = β′′, x5 = α′′′, x6 = β′′′, and so on, where by definition α′ < α′′ < α′′′ < ... and β′ > β′′ > β′′′ > ... [that is, successive α values are always increasing while successive β values are always decreasing].
Now, if the number of intervals is finite, then denote the last one as (α(v) . . . β(v)) where (v) is some number of nesting superscripts, indicating the (v)th interval. Then in the interior of (α(v) . . . β(v)) there can be at most one number of the sequence S, for if there were two or more then another nested interval would be possible [contradicting the statement that (α(v) . . . β(v)) is the last interval]; but we know that any real line segment contains infinitely many real numbers [the gapless corollary], therefore (α(v) . . . β (v)) must contain infinitely many real numbers not listed in the sequence S.
On the other hand, if the number of intervals is infinite, then the numbers α′, α′′, α′′′, ..., "because they increase without growing into the infinite" [1] must have an upper boundary α∞; and likewise for β′, β′′, β′′′, ..., which must have a lower boundary β∞. Now, in the case of α∞ = β∞ the value y such that y = α∞ = β∞ is certainly not listed in S. But why? Because if
where y is the value toward which all α's increase and all β's decrease, so that their shared boundary is the single point y, meaning that (α∞ . . . β∞ ) is then NOT an interval at all [since a point is not an interval], then by our sequence construction neither α∞ nor β∞ and hence not y either can occur in S.
Finally, if α∞ < β∞, then (α∞ . . . β∞) IS an interval and so the infinitely many real numbers y such that α∞ < y < β∞ are not listed in the sequence S; viz. since (α∞ . . . β∞) is a segment and not a point we know from the gapless corollary that between α∞ and β∞ exist infinitely many reals not in S.
Hence from the logic of the real line we have shown that the elements of R are in essence unlistable, and because of this there can exist no way of putting them into a one-to-one correspondence with the elements of N. Therefore, despite the fact that both N and R are infinite sets, there must exist more elements in R than in N, viz.
Cantor's uncountability theorem basically states that natural infinity (the number of elements in the discrete set N) is smaller in magnitude than real infinity (the number of elements in the continuous set R). And R's greater infiniteness − as Cantor had originally intuited − is a result of its continuity.
Sometimes those who wish to preserve the intuitive uniqueness of infinity (my past self included) imagine that proofs such as the above can apply to the rational numbers as well, a scenario which if true would invalidate the proof: i.e. the case of (α . . . β) being an interval on the rational line instead of the real line. While it is easily proveable [3] that in between any two rational numbers there are infinitely many more, this everywhere denseness [as Cantor called it] or dense order [as it is modernly called] does not imply continuity; for as we saw earlier when conceptualizing the irrationals, the rational line is not without gaps. And as it turns out, without the gaplessness of true continuity as well as the gapless corollary that results, the nested intervals proof presented above is not applicable. Hence it does not work for Q or for any other set which is not truly continuous.
Most of the time when ℵ0 < n(R) is encountered in books or on the web, a different and later proof − Cantor's diagonalization of 1891 − is presented, presumably because it is more economical, more elegant, or simpler to explain. However, I much prefer his original nested intervals proof of 1874 since it operates directly within the logic of the real line, allowing one to almost visualize the gaplessness and continuity involved which necessitate the existence of the greater infinity.
Consequently, now that I have come to actually understand the uncountability theorem, I no longer doubt that diagonalization is valid; but in case you are doubting it as I once did and are thinking about attempting to apply it to rationals or other discrete sets I recommend reading Samuel C. Hsieh's Two Answers to a Common Question on Diagonalization [arXiv:1501.01207] for a good explanation of why it won't work. Also, for anyone who finds both the nested interval proof as well as diagonalization unconvincing for whatever reason, and who happens also to know what supremums and open rays are (these concepts are as yet beyond my knowledge) Eliahu Levy's An Unusual Proof that the Reals are Uncountable [arXiv:0901.0446] may be of interest.
Finally, if this material is brand new to you and you would like to read more, I recommend Joseph Warren Dauben's Georg Cantor: His Mathematics and Philosophy of the Infinite [goodreads:1513062] and Mary Tiles' The Philosophy of Set Theory: An Historical Introduction to Cantor's Paradise [goodreads:145036]. Dauben's book is an expertly written mathematical biography, very enjoyable and informative; and Tiles' is more of a philosophical reflection on the infinite and the wider implications of Cantor's work.
[1] ^ Ewald, William B., ed. (1996) From Kant to Hilbert: A Source Book in the Foundations of Mathematics, Volume 2. Oxford University Press.
[2] ^ Cantor, Georg (1915), Philip Jourdain, ed., Contributions to the Founding of the Theory of Transfinite Numbers. New York: Dover.
[3] ^ Let α and β be any two rationals such that α < β, then the expression
α + (β − α)/n is a unique rational number between α and β for each n > 1 in N.