Cantor's first set theory article contains Georg Cantor's first theorems of transfinite set theory, which studies infinite sets and their properties. One of these theorems is his "revolutionary discovery" that the set of all real numbers is uncountably, rather than countably, infinite.. 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" ("Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen"), refers to its first theorem: the set of real algebraic numbers is countable. Cantor's article was published in 1874. In 1879, he modified his uncountability proof by using the topological notion of a set being dense in an interval.

Cantor's article also contains a proof of the existence of transcendental numbers. Both constructive and non-constructive proofs have been presented as "Cantor's proof." The popularity of presenting a non-constructive proof has led to a misconception that Cantor's arguments are non-constructive. Since the proof that Cantor published either constructs transcendental numbers or does not, an analysis of his article can determine whether or not this proof is constructive.. Cantor's correspondence with Richard Dedekind shows the development of his ideas and reveals that he had a choice between two proofs: a non-constructive proof that uses the uncountability of the real numbers and a constructive proof that does not use uncountability.

Historians of mathematics have examined Cantor's article and the circumstances in which it was written. For example, they have discovered that Cantor was advised to leave out his uncountability theorem in the article he submitted — he added it during proofreading. They have traced this and other facts about the article to the influence of Karl Weierstrass and Leopold Kronecker. Historians have also studied Dedekind's contributions to the article, including his contributions to the theorem on the countability of the real algebraic numbers. In addition, they have recognized the role played by the uncountability theorem and the concept of countability in the development of set theory, measure theory, and the Lebesgue integral.

The article Cantor's article is short, less than four and a half 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.. English translation: . 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.".

Cantor's second theorem works with a closed interval [a, b], 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 [a, b], there is a number in [a, b] that is not contained in the given sequence. Hence, there are infinitely many such numbers.. English translation: .

Cantor observes that combining his two theorems yields a new proof of Liouville's theorem that every interval [a, b] contains infinitely many transcendental numbers.

Cantor then remarks that his second theorem is:

This remark contains Cantor's uncountability theorem, which only states that an interval [a, b] 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..

Proof of Cantor's uncountability theorem Cantor does not explicitly prove his uncountability theorem, which follows easily from his second theorem. It can be proved by using proof by contradiction. Assume that the interval [a, b] can be put into one-to-one correspondence with the set of positive integers, or equivalently: The real numbers in [a, b] can be written as a sequence in which each real number appears only once. Applying Cantor's second theorem to this sequence and [a, b] produces a real number in [a, b] 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.

The proofs 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. The following table contains the beginning of Cantor's enumeration.. English translation: .

Cantor's enumeration of the real algebraic numbers Real algebraicnumber Polynomial Height ofpolynomial x1 = 0 x 1 x2 = −1 x + 1 2 x3 = 1 x − 1 2 x4 = −2 x + 2 3 x5 = − 2x + 1 3 x6 = 2x − 1 3 x7 = 2 x − 2 3 x8 = −3 x + 3 4 x9 = x2 + x − 1 4 x10 = − x2 − 2 4 x11 = − 2x2 − 1 4 x12 = x2 − x − 1 4 x13 = − 3x + 1 4 x14 = 3x − 1 4 x15 = x2 + x − 1 4 x16 = 2x2 − 1 4 x17 = x2 − 2 4 x18 = x2 − x − 1 4 x19 = 3 x − 3 4

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 [a, b], there is a number in [a, b] that is not contained in the given sequence.

To find a number in [a, b] 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 the open interval (a, b). 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 (a1, b1). Denote the smaller by a2 and the larger by b2. Continuing this procedure generates a sequence of intervals (a1, b1), (a2, b2), (a3, b3), ... 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.. English translation: .

Either the number of intervals generated is finite or infinite. If finite, let (aL, bL) 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 (aL, bL). Since at most one xn can be in this interval, every y in this interval except xn (if it exists) is not in the given sequence.

Case 2: a∞ = b∞. Then a∞ is not in the sequence since for all n: a∞ is in the interval (an, bn) but xn does not belong to (an, bn). In symbols: a∞ ∈ (an, bn) but xn ∉ (an, bn).

{| class="wikitable collapsible collapsed" ! style="background: f5f5f5;" |Proof that for all n:   |- style="text-align: left; vertical-align: top; background: white" | style="padding-left: 1em; padding-right: 1em" | This lemma is used by cases 2 and 3. It is implied by the stronger lemma: For all n, (an, bn) excludes x1, ..., x2n. This is proved by induction. Basis step: Since the endpoints of (a1, b1) are x1 and x2 and an open interval excludes its endpoints, (a1, b1) excludes x1, x2. Inductive step: Assume that (an, bn) excludes x1, ..., x2n. Since (an+1, bn+1) is a subset of (an, bn) and its endpoints are x2n+1 and x2n+2, (an+1, bn+1) excludes x1, ..., x2n and x2n+1, x2n+2. Hence, for all n, (an, bn) excludes x1, ..., x2n. Therefore, for all n, xn ∉ (an, bn).

Case 3: a∞ < b∞. Then every y in [a∞, b∞] is not contained in the given sequence since for all n: y belongs to (an, bn) but xn does not.. English translation: .

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

Cantor's proofs are constructive and have been used to write a computer program that generates the digits of a transcendental number. This program applies Cantor's construction to a sequence containing all the real algebraic numbers between 0 and 1. The article that discusses this program gives some of its output, which shows how the construction generates a transcendental..

Example of Cantor's construction An example illustrates how Cantor's construction works. Consider the sequence: , , , , , , , , , ... This sequence is obtained by ordering the rational numbers in (0, 1) by increasing denominators, ordering those with the same denominator by increasing numerators, and omitting reducible fractions. The table below shows the first five steps of the construction. The table's first column contains the intervals (an, bn). The second column lists the terms visited during the search for the first two terms in (an, bn). These two terms are in red..

+Generating a number using Cantor's construction Interval Finding the next interval Interval (decimal)

Since the sequence contains all the rational numbers in (0, 1), the construction generates an irrational number, which turns out to be  − 1..

Proof that the number generated is  − 1The proof uses Farey sequences and simple continued fractions. The Farey sequence is the increasing sequence of completely reduced fractions whose denominators are If and are adjacent in a Farey sequence, the lowest denominator fraction between them is their mediant This mediant is adjacent to both and in the Farey sequence .

Cantor's construction produces mediants because the rational numbers were sequenced by increasing denominator. The first interval in the table is Since and are adjacent in their mediant is the first fraction in the sequence between and Hence, In this inequality, has the smallest denominator, so the second fraction is the mediant of and which equals This implies: Therefore, the next interval is

We will prove that the endpoints of the intervals converge to the continued fraction This continued fraction is the limit of its convergents:

The and sequences satisfy the equations:.

First, we prove by induction that for odd n, the n-th interval in the table is:

and for even n, the interval's endpoints are reversed:

This is true for the first interval since:

Assume that the inductive hypothesis is true for the k-th interval. If k is odd, this interval is:

The mediant of its endpoints is the first fraction in the sequence between these endpoints.

Hence,

In this inequality, has the smallest denominator, so the second fraction is the mediant of and which equals

This implies:

Therefore, the (k + 1)-st interval is

This is the desired interval; is the left endpoint because k + 1 is even. Thus, the inductive hypothesis is true for the (k + 1)-st interval. For even k, the proof is similar. This completes the inductive proof.

Since the right endpoints of the intervals are decreasing and every other endpoint is their limit equals The left endpoints have the same limit because they are increasing and every other endpoint is As mentioned above, this limit is the continued fraction which equals .

Cantor's 1879 uncountability proof Everywhere dense In 1879, Cantor published a new uncountability proof that modifies his 1874 proof. He first defines the topological notion of a point set P being "everywhere dense in an interval":