# Day #15: Cantor´s Dreams

Q: When does George Cantor present for the first time his new and transcendental ideas about the different infinitudes of sets??…

A: Georg Cantor’s first set theory article was published in 1874 and contains the first theorems of transfinite set theory, which studies infinite sets and their properties.[1] One of these theorems is “Cantor’s revolutionary discovery” that the set of all real numbers is uncountably, rather than countably, infinite.[2] This theorem is proved using Cantor’s first uncountability proof, which differs from the more familiar proof using his diagonal argument. The title of the article, “On a Property of the Collection of All Real Algebraic Numbers,” refers to its first theorem: the set of real algebraic numbers is countable.

Cantor’s article also contains a proof of the existence of transcendental numbers.

## The Article

Cantor’s article is short, just 4 1/3 pages. It begins with a discussion of the real algebraic numbers and a statement of his first theorem: The set of real algebraic numbers can be put into one-to-one correspondence with the set of positive integers. Cantor restates this theorem in terms more familiar to mathematicians of his time: The set of real algebraic numbers can be written as an infinite sequence in which each number appears only once.[6]

Cantor’s second theorem works with a closed interval [ab], which is the set of real numbers ≥ a and ≤ b. The theorem states: Given any sequence of real numbers x1, x2, x3, … and any interval [ab], there is a number in [ab] that is not contained in the given sequence. Hence, there are infinitely many such numbers.[7]

The first part of this theorem implies the “Hence” part. For example, let [0, 1] be the interval, and consider its pairwise disjoint subintervals [0, 1/2], [3/47/8], [15/1631/32], …. Applying the first part of the theorem to each subinterval produces infinitely many numbers in [0, 1] that are not contained in the given sequence.

Cantor observes that combining his two theorems yields a new proof of the theorem that every interval [ab] contains infinitely many transcendental numbers. This theorem was first proved by Joseph Liouville.[7]

Cantor then remarks that his second theorem is:

the reason why collections of real numbers forming a so-called continuum (such as, all real numbers which are ≥ 0 and ≤ 1) cannot correspond one-to-one with the collection (ν) [the collection of all positive integers]; thus I have found the clear difference between a so-called continuum and a collection like the totality of real algebraic numbers.[8]

This remark contains Cantor’s uncountability theorem, which only states that an interval [ab] cannot be put into one-to-one correspondence with the set of positive integers. It does not state that this interval is an infinite set of larger cardinality than the set of positive integers. Cardinality is defined in Cantor’s next article, which was published in 1878.[9]

Cantor does not explicitly prove his uncountability theorem, which follows easily from his second theorem. To prove it, we use proof by contradiction. Assume that the interval [ab] can be put into one-to-one correspondence with the set of positive integers, or equivalently: The real numbers in [ab] can be written as a sequence in which each real number appears only once. Applying Cantor’s second theorem to this sequence and [ab] produces a real number in [ab] that does not belong to the sequence. This contradicts the original assumption, and proves the uncountability theorem.

Cantor only states his uncountability theorem. He does not use it in any proofs.[6]

### First Theorem

To prove that the set of real algebraic numbers is countable, define the height of a polynomial of degree n with integer coefficients as: n − 1 + |a0| + |a1| + … + |an|, where a0, a1, …, an are the coefficients of the polynomial. Order the polynomials by their height, and order the real roots of polynomials of the same height by numeric order. Since there are only a finite number of roots of polynomials of a given height, these orderings put the real algebraic numbers into a sequence. Cantor went a step further and produced a sequence in which each real algebraic number appears just once. He did this by only using polynomials that are irreducible over the integers.

### Second Theorem

Only the first part of Cantor’s second theorem needs to be proved. It states: Given any sequence of real numbers x1, x2, x3, … and any interval [ab], there is a number in [ab] that is not contained in the given sequence. We simplify Cantor’s proof by using open intervals. The open interval (ab) is the set of real numbers > a and < b.

To find a number in [ab] that is not contained in the given sequence, construct two sequences of real numbers as follows: Find the first two numbers of the given sequence that are in (ab). Denote the smaller of these two numbers by a1 and the larger by b1. Similarly, find the first two numbers of the given sequence that are in (a1b1). Denote the smaller by a2 and the larger by b2. Continuing this procedure generates a sequence of intervals (a1b1), (a2b2), (a3b3), … such that each interval in the sequence contains all succeeding intervals—that is, it generates a sequence of nested intervals. This implies that the sequence a1, a2, a3, … is increasing and the sequence b1, b2, b3, … is decreasing.

Either the number of intervals generated is finite or infinite. If finite, let (aNbN) be the last interval. If infinite, take the limits a = limn → ∞ an and b = limn → ∞ bn. Since an < bn for all n, either a = b or a < b. Thus, there are three cases to consider:

• Case 1: There is a last interval (aNbN). Since at most one xn can be in this interval, every y in this interval except xn (if it exists) is not contained in the given sequence.
• Case 2: a = b. Then a is not contained in the given sequence since for all n: a belongs to (anbn) but xn does not. Cantor states without proof that xn ∉ (anbn); this will be proved below.
• Case 3: a < b. Then every y in [ab] is not contained in the given sequence since for all n: y belongs to (anbn) but xn does not.

Case 1: Last interval (aN, bN)

Case 2: a = b

Case 3: a < b

The proof is complete since, in all cases, at least one real number in [ab] has been found that is not contained in the given sequence.[A]

### The Development of Cantor’s Ideas

The development leading to Cantor’s article appears in the correspondence between Cantor and Richard Dedekind. On November 29, 1873, Cantor asked Dedekind whether the collection of positive integers 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?” Cantor added that collections having such a correspondence include the collection of positive rational numbers, and collections of the form (an1n2, . . . , nν) where n1, n2, . . . , nν, and ν are positive integers.[15]

Dedekind replied that he was unable to answer Cantor’s question, and said that it “did not deserve too much effort because it has no particular practical interest.” Dedekind also sent Cantor a proof that the set of algebraic numbers is countable.[16]

On December 2, Cantor responded that his question does have interest: “It would be nice if it could be answered; for example, provided that it could be answered no, one would have a new proof of Liouville’s theorem that there are transcendental numbers.”[17]

On December 7, Cantor sent Dedekind a proof by contradiction that the set of real numbers is uncountable. Cantor starts by assuming the real numbers can be written as a sequence. Then he applies a construction to this sequence to produce a real number not in the sequence, thus contradicting his assumption.[18] The letters of December 2 and 7 lead to a non-constructive proof of the existence of transcendental numbers.

On December 9, Cantor announced the theorem that allowed him to construct transcendental numbers as well as prove the uncountability of the set of real numbers:

(I)     ω1, ω2, … , ωn, …
I can determine, in every given interval [α, β], a number η that is not included in (I).[19]

This is the second theorem in Cantor’s article. It comes from realizing that his construction can be applied to any sequence, not just to sequences that supposedly enumerate the real numbers. So Cantor had a choice between two proofs that demonstrate the existence of transcendental numbers: one proof is constructive, but the other is not. We now compare the proofs assuming that we have a sequence consisting of all the real algebraic numbers.

The constructive proof applies Cantor’s construction to this sequence and the interval [ab] to produce a transcendental number in this interval.

The non-constructive proof uses two proofs by contradiction:

1. The proof by contradiction used to prove the uncountability theorem (see “The article” section above). It assumes that the real numbers in [ab] can be written as a sequence, applies Cantor’s construction to obtain a contradiction, and concludes that the real numbers in [ab] cannot be written as a sequence.
2. Assume that there are no transcendental numbers in [ab]. Then all the real numbers in [ab] are algebraic, which implies that they form a subsequence of the sequence of all real algebraic numbers. This contradicts what was proved in 1. Thus, the assumption that there are no transcendental numbers in [ab] is false. Therefore, there is a transcendental number in this interval.

#### The influence of Weierstrass and Kronecker on Cantor’s article

##### Karl Weierstrass
Leopold Kronecker, 1865
##### Cantor restricted his first theorem to the set of real algebraic numbers even though Dedekind had sent him a proof that handled all algebraic numbers.[16] Cantor did this for expository reasons and because of “local circumstances.”[42] This restriction simplifies the article because the second theorem works with real sequences. Hence, the construction in the second theorem can be applied directly to the enumeration of the real algebraic numbers to produce “an effective procedure for the calculation of transcendental numbers.” This procedure would be acceptable to Weierstrass.[43]

The Legacy of Cantor’s Article

Cantor’s article introduced the uncountability theorem and the concept of countability. Both would lead to significant developments in mathematics.

The uncountability theorem demonstrated that one-to-one correspondences can be used to analyze infinite sets. In 1878, Cantor used them to define and compare cardinalities. He also constructed one-to-one correspondences to prove that the n-dimensional spaces Rn (where R is the set of real numbers) and the set of irrational numbers have the same cardinality as R.[51][C]

In 1883, Cantor extended the natural numbers with his infinite ordinals. This extension was necessary for his work on the Cantor-Bendixson theorem. Cantor discovered other uses for the ordinals—for example, he used sets of ordinals to produce an infinity of sets having different infinite cardinalities.[52] His work on infinite sets together with Dedekind’s set-theoretical work created set theory.[53]

The concept of countability led to countable operations and objects that are used in various areas of mathematics. For example, in 1878, Cantor introduced countable unions of sets.[54] In the 1890s, Émile Borel used countable unions in his theory of measure, and René Baire used countable ordinals to define his classes of functions.[55] Building on the work of Borel and Baire, Henri Lebesgue created his theories of measure and integration, which were published from 1899 to 1901.[56]

Countable models are used in set theory. In 1922, Thoralf Skolem proved that if the axioms of set theory are consistent, then they have a countable model. Since this model is countable, its set of real numbers is countable. Skolem explained why this does not contradict Cantor’s uncountability theorem: the model considers its set of real numbers to be uncountable because it contains no one-to-one correspondence between this set and its set of positive integers. The one-to-one correspondence between these sets exists outside the model.[57] In 1963, Paul Cohen used countable models to prove his independence theorems.[58]

Source: WikipediA