On November 29th, 1873 mathematician Georg Cantor (1845-1918) sent a letter to Richard Dedekind (1831-1916) asking whether or not the collection of natural numbers and the collection of positive real numbers “can be corresponded so that each individual of one collection corresponds to one and only one individual of the other?”. Dedekind replied by writing that he did not know the answer, and that the question was not of much practical interest.

At this point in time, it seems Cantor agreed with Dedekind’s contention, stating that his interest in the matter was related to Joseph Liouville (1809-82)’s 1844 theorem proving the existence of transcendental numbers:

Halle, December 2nd 1873
”I was exceptionally pleased to receive your answer to my last letter. I put my question to you because I had wondered about it already several years ago, and was never certain whether the difficulty I found was subjective or whether it was inherent in the subject. Since you write that you too are unable to answer it, I may assume the latter. In addition, I should like to add that I have never seriously occupied myself with it, because it has no special practical interest for me. And I entirely agree with you when you say that for this reason it does not deserve much effort. But it would be good if it could be answered; e.g. if it could be answered with no, then one would have a new proof of Liouville's theorem that there are transcendental numbers.”

From Cantor’s next letter a few days later however it seems clear that his interest in the question was not quite as fleeting as he had expressed to Dedekind, although he at this time does not outline any particularly important implications:

Halle, December 7th 1873
"..In the last days I have had the time to pursue more thoroughly the conjecture I spoke to you about; only today do I believe myself to have finished with the thing; but if I should be deceiving myself, I should certainly find no more indulgent judge than you."

In the letter, Cantor next proceeds with the first draft of a proof of why the real numbers cannot be put in one-to-one correspondence with the natural numbers. That is, why there are more real numbers than there are natural numbers, | ℝ | > | ℕ |.

Not two days later, Cantor sends Dedekind a revised and simpler proof, along with his apologies for occupying his time with this “fleeting” matter:

Halle, December 9th 1873
I have already found a simplified proof of the theorem just proved, so that the decomposition of the sequence into (1),(2),(3), ... is no longer necessary. I show directly that if I start with a sequence

(i) ω₁, ω₂, ..., ωᵤ,

then in every given interval (α ... β) I can determine a number η that is not contained in (i). From this it follows at once that the totality (x) cannot be correlated one-to-one with the totality (u); and I infer that there exist essential differences among totalities and value-sets that I was until recently unable to fathom.

Now I must ask your forgiveness for having taken so much of your time with this question. Confirming the receipt of your friendly lines of the 8th of December, allow me to assure you that nothing can give me more pleasure than to have been lucky enough to arouse in you an interest for certain questions of analysis.

Dedekind’s notes from the period make clear the chronology of events:

Brunswick, December 7th 1873
Cantor communicates to me a rigorous proof, found on the same day, of the theorem that the totality of all positive numbers ω < 1 cannot be one-to-one correlated with the totality (n).

I answered this letter, received on the 8th of December, on the same day with congratulations for the fine success. At the same time, I rephrase much more simply the core of the proof (which was still quite complicated).

The Origins of Set Theory

The origins of set theory can be traced back to a single paper by Cantor, published the year after his above correspondence with Dedekind:

• Cantor, G. 1874. Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen, (“On a Property of the Collection of All Real Algebraic Numbers”). Journal für die Reine und Angewandte Mathematik 77, pp. 258-262.

The fundamental and most consequential result presented in the paper is the uncountability of real numbers, and as consequence, the invention of a distinction between numbers that belong to “the continuum” and those that belong to “a collection like the totality of real algebraic numbers”. Cantor’s paper appeared in Journal für die reine und angewandte Mathematik (“Crelle’s Journal”) just before he turned 30 years old. As he wrote to Dedekind about two weeks after arriving at his proof:

Berlin, December 25th 1873
"..Although I did not yet wish to publish the subject I recently for the first time discussed with you, I have nevertheless unexpectedly been caused to do so. I communicated my results to Herr Weierstrass on the 22nd; however, there was no time to go into details; already on the 23d I had the pleasure of a visit from him, at which I could communicate the proofs to him. He was of the opinion that I must publish the thing at least in so far as it concerns the algebraic numbers. So I wrote a short paper with the title: On a property of the set of all real algebraic numbers and sent it to Professor Borchardt to be considered for the Journal fur Math.

As you will see, your comments (which I value highly) and your manner of putting some of the points were of great assistance to me."

In five short pages, Cantor’s paper (the topic of this week’s newsletter) presents three important results:

1. The set of real algebraic numbers is countable; and

2. In every interval [a,b] there are infinitely many numbers not included in any sequence; which means that

3. The set of real numbers are uncountably infinite;

What is a Set?

“A set is a Many which allows itself to be thought of as a One” — Georg Cantor

A set is a collection of elements. The set consisting of the numbers 3,4 and 5 is denoted by {3, 4, 5}. For larger sets and the sake of simplicity, an ellipsis is often used if the reader can easily guess what the missing elements are. Cantor’s original definition of an “aggregate” (set), translated, went as follows:

Cantor's Definition of a Set. By a set we are to understand any collection into a whole M of definite and separate objects m of our intuition or our thought. These objects are called the "elements" of M.

Countability

A countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers.

The property of countability is an important one in set theory. An intuitive interpretation of countability is “listability”, that the elements of a set may be written down in a list. The most inherently countable set is the natural numbers ℕ, in that the elements of ℕ are the counting numbers themselves (1,2,3, …). As we know, they are infinite in number, and so termed “countably infinite”, or “denumerable”. For other sets, formally, by stating that a set is countable one means that the elements of the set can be put in one-to-one correspondence with elements of the set of natural numbers ℕ, i.e. that:

Countable sets
A set S is countable if there exists an injective function f from S to the natural numbers ℕ = {1,2,3, ...}. If such an f can be found that is also surjective (and therefor bijective), then S is called a countably infinite set, or denumerable.

For instance, for the set of even numbers (2n|n ∈ ℕ):

2 4 6 8 10 ... 2n
↓ ↓ ↓ ↓ ↓ ↓
1 2 3 4 5 ... n

We see that the elements of the two sets may be put in one-to-one correspondence with one other, and so we can determine that the set of even numbers is also countable.

The countability property makes it possible to compare sets in terms of the number of elements they contain without actually counting anything, and in this way make inferences about the relative sizes of both finite and infinite sets. For practical reasons let us illustrate the finite case by imagining a classroom with 100 seats. Filled with students, one can make an inference about the size of the set of students in relation to size of the set of seats. If seats are vacant, the set of seats is larger than the set of students. If no seats are vacant and some students are standing, the size of the set of students is larger than that of seats, and so on.

The Countability of Rational Numbers (1873)

Cantor’s first published investigation into the countability of sets occurred in 1873 when he proved that the rational numbers ℚ (fractions/ratios) are countable. His rather elegant and intuitive proof went as follows:

Proof of the Countability of the Rational numbers ℚLet us first propose that the set of rational numbers ℚ is countable. To prove this assertion, let us arrange all the rational numbers (ratios of natural numbers) in an infinite table as such:

1/1  1/2  1/3  1/4  1/5  ...
2/1  2/2  2/3  2/4  2/5  ...
3/1  3/2  3/3  3/4  3/5  ...
4/1  4/2  4/3  4/4  4/5  ...
5/1  5/2  5/3  5/4  5/5  ...
...    ...    ...    ...    ...

Next, starting in the upper lefthand corner, move through the diagonals from left to right at 45 degrees, starting with 1/1, then 1/2 and 2/1, then 3/1, 2/2 and 1/3 and so on. Write down every new number you come across. You will obtain the following ordering:

1/1, 1/2, 2/1, 3/1, 2/2,   ...

 ↓    ↓    ↓    ↓     ↓     ↓

 1     2     3     4     5     ...

Which is not just a well-ordering, but also in one-to-one correspondence with the natural numbers in their natural order. This proves the countability of the rational numbers ℚ.

The Countability of Real Algebraic Numbers (1874)

A year later, in his 1884 paper, Cantor showed that the real algebraic numbers are countable. Real algebraic numbers are real numbers ω which satisfy equations of the form: aₒ ωᵘ + a¹ωᵘ⁻¹ + … + aᵤ= 0. That is to say, real algebraic numbers are roots of non-zero real polynomials. They are countable, i.e:

The Countability of Real Algebraic Numbers
The collection of all algebraic reals can be written as an infinite sequence.

Cantor showed it in his 1874 paper by the following proof:

Proof of the Countability of Real Algebraic Numbers (1874)

For each polynomial equation of the form
aₒωᵘ + a₁ωᵘ⁻¹ + … + aᵤ = 0

with integer coefficients a, define its index to be the sum of the absolute values of the coefficients plus the degree of the equation:

|aₒ|+|a₁|+ ... +|aᵤ|

The only equation of index 2 is ω = 0, so its solution, 0, is the first algebraic number. The four equations of index 3 are 2x = 0, x + 1 = 0, x – 1 = 0, and x2 = 0. They have roots 0, –1, 1, so he included the new values –1 and 1 as the second and third entries on his list of algebraic numbers.

Observe that for each index there are only finitely many equations and that each equation only has finitely many roots. Listing the new roots by order of index and by increasing magnitude within each index, one establishes a systematic method for listing all the algebraic numbers. As with rationals, the one-to-one correspondence with the natural numbers proved that the set of algebraic numbers have to countably infinite.

The Uncountability of Real Numbers (1874)

Cantor’s most fruitful use of countability as a concept occurred in the third result of his 1874 paper when he demonstrated the uncountability of the real numbers — the first set shown to lack this property. A real number ℝ is a value of a continuous quantity that can represent a distance along a line. Any real number can be determined by a possibly infinite decimal representation, such as that of e.g. 8.632, 0.00001, 10.1 and so on, where each consecutive digit is measured in units one tenth the size of the previous one. The statement that the real numbers are uncountable is equivalent to the statement:

The Uncountability of Real Numbers
Given any sequence of real numbers and any interval [α ... β], one can determine a number η in [α ... β] that does not belong to the sequence. Hence, one can determine infinitely many such numbers η in [α ... β].

As we read in his letter exchanges with Dedekind in 1873, we know how Cantor worked towards the momentous result. His original proof (“Cantor’s First Uncountability Proof”) was based on the Bolzano-Weierstrass theorem. Seventeen years later, in 1891, he provided a simpler proof using what has become known as Cantor’s diagonal argument, first published in an 1891 paper entitled Über eine elementere Frage der Mannigfaltigkeitslehre (“On an elementary question of Manifold Theory”). I include it here for its elegance and simplicity. Generalized, the now famous argument goes as follows:

Proof: Cantor’s Diagonal Argument (1891)
In his paper, Cantor considers the set M of all infinite sequences of the binary numbers m and w. Sequences such as:

E₁ = (m, m, m, m, m, ...),
E₂ = (w, w, w, w, w, ...),
E₃ = (m, w, m, w, m, ...),
E₄ = (w, m, w, m, w, ...),
E₅ = (m, m, w, w, m, ...)

Cantor asserts that there exists a set M that does not have the “breath” of the series E₁, E₂, E₃ … , meaning M is of a different size than the sum of each sequence En, i.e. that even though M is constructed of all the infinite sequences of the binary numbers m and w, he can always construct a new sequence E₀ which “is both an element of M and is not an element of M.”

The new sequence E₀ is constructed using the complements of one digit from each sequence E₁, E₂, … En. A complement of a binary number is defined as the value obtained by inverting the bits in the representation of the number (swapping m for w and visa versa). So, the new sequence is made up of the complement the first digit from the sequence E₁ (m), the complement of the second digit from the sequence E₂ (w), the complement of the third digit from the sequence E₃ (m) and so on to finally the complement of the nth digit from the sequence En. From the example sequences above, the new sequence E₀ would then be:

E₀ = (w, m, w, w, w, ...)

By its construction, E₀ differs from each sequence En since their nth digits differ. Hence, E₀ cannot be one of the infinite sequences in the set M.

From Cantor’s correspondence with Dedekind around the time of the submission of the original proof in 1874, it seems clear that he was already in the process of pondering this particular implication of the result, although from known records he does not seem to explicitly state so to Dedekind. We do however see traces of his brilliantly creative and questioning mind in his letters from the same time, such as in this excerpt from January of 1874 about the sizes of sets of different dimensions:

Halle, January 5th 1874

“..Can a surface (say a square that includes the boundary) be uniquely referred to a line (say a straight line segment that includes the end points) so that for every point on the surface there is a corresponding point of the line and, conversely, for every point of the line there is a corresponding point of the surface? It still seems to me at the moment that the answer to this question is very difficult - although here too one is so impelled to say no that one would like to hold the proof to be almost superfluous.”

When Dedekind does not reply to the proposition directly, Cantor repeats the inquiry a few weeks later, indicating his awareness of the meaningful implications it has:

Halle, January 28th 1874

"..When you get around to answering me, I should be grateful to hear whether you had the same difficulty as I in answering the question I sent to you in January about the correlation of a line and a surface, or whether I am deceiving myself. In Berlin a friend to whom I presented the same problem told me the subject was somewhat absurd, because it is self-evident that two independent variables cannot be reduced to one."

From what we can deduce from known records, it would be three years until Dedekind and Cantor again spoke on the subject. From his letters, it is clear that Cantor’s sophistication on the topic of one-to-one correspondence between infinite sets at this point has grown, and that his understanding of its implications in 1877 run much deeper than before:

Halle, June 20th 1877

"..I should like to know whether you consider an inference-procedure that I use to be arithmetically rigorous.

The problem is to show that surfaces, bodies, indeed even continuous structures of p dimensions can be correlated one-to-one with continuous lines, i.e. with structures of only one dimension—so that surfaces, bodies, indeed even continuous structures of p dimensions have the same power as curves.

This idea seems to conflict with the one that is especially prevalent among the representatives of modern geometry, who speak of simply infinite, doubly, triply, . . . ρ-fold infinite structures.

(Sometimes you even find the idea that the infinity of points of a surface or a body is obtained by as it were squaring or cubing the infinity of points of a line.)"

Applying Cantor’s Diagonal Argument to prove the uncountability of the real numbers, we proceed as follows:

Proof of the Uncountability of the Real numbers ℝ
This proof is by contradiction, i.e. we will assume that the real numbers ℝ are countable and derive a contradiction. If the reals are countable, then they could be listed:

1. 657.853260...
2. 2.313333...
3. 3.141592...
4. .000307...
5. 49.494949...
6. .873257...
...
To obtain a contradiction, it suffices to show that there exists some real α that is missing from the list. The construction of such an α works by making its first decimal place different from the first decimal place of the first number of the list, by making the second decimal place different from the second decimal place of the second number, and in general by making the nth decimal place different from the nth decimal place of the nth number on the list.
Even simpler, for our α we'll make the nth decimal place 1 unless it is already 1, in which case we'll make it 2. By this process, for our example list of numbers, we obtain:

α = .122111...

Which, by construction cannot be a member of the list we created. And so, by contradiction, our list of all reals cannot contain every number, and so must be uncountable.

The conclusions of both proofs (1874 and 1891) are the same — although both the natural numbers and the real numbers are infinite in number and so go on forever, there “aren’t enough” natural numbers to create a one-to-one correspondence between them and the real numbers. Cantor’s brilliant discovery, in other words, showed rigorously that infinity comes in different sizes, some of which are larger than others.

Cantor and Dedekind exchanged letters over a period of many years. The mathematical portions of their letters were later published by Noether and Cavailleès (1937) and are now kept at the University of Evansville in Indiana. The best book for those interested in reading more about their contents, in my opinion, is however:

• Ewald, W. 1996. From Kant to Hilbert: A Source Book in the Foundations of Mathematics. Volume II*. Oxford University Press

Sincerely,

Jørgen

About

The Privatdozent newsletter currently goes out to 7,276 subscribers via Substack.

* This essay contains Amazon affiliate links