A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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.[1] 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.[2] 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.[A] 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.[3] 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.[4]
Cantor's second theorem works with a closed interval , 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 , there is a number in that is not contained in the given sequence. Hence, there are infinitely many such numbers.[5]
Cantor observes that combining his two theorems yields a new proof of Liouville's theorem that every interval contains infinitely many transcendental numbers.[5]
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 (ν) ; thus I have found the clear difference between a so-called continuum and a collection like the totality of real algebraic numbers.[6]
This remark contains Cantor's uncountability theorem, which only states that an interval 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.[7]
| 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 can be put into one-to-one correspondence with the set of positive integers, or equivalently: The real numbers in can be written as a sequence in which each real number appears only once. Applying Cantor's second theorem to this sequence and produces a real number in that does not belong to the sequence. This contradicts the original assumption and proves the uncountability theorem.[8] |
Cantor only states his uncountability theorem. He does not use it in any proofs.[3]
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.[9]
| Cantor's enumeration of the real algebraic numbers | ||
|---|---|---|
| Real algebraic number |
Polynomial |
Height of polynomial |
| x1 = 0 | x | 1 |
| x2 = −1 | x + 1 | 2 |
| x3 = 1 | x − 1 | 2 |
| x4 = −2 | x + 2 | 3 |
| x5 = −1/2 | 2x + 1 | 3 |
| x6 = 1/2 | 2x − 1 | 3 |
| x7 = 2 | x − 2 | 3 |
| x8 = −3 | x + 3 | 4 |
| x9 = −1 − √5/2 | x2 + x − 1 | 4 |
| x10 = −√2 | x2 − 2 | 4 |
| x11 = −1/√2 | 2x2 − 1 | 4 |
| x12 = 1 − √5/2 | x2 − x − 1 | 4 |
| x13 = −1/3 | 3x + 1 | 4 |
| x14 = 1/3 | 3x − 1 | 4 |
| x15 = −1 + √5/2 | x2 + x − 1 | 4 |
| x16 = 1/√2 | 2x2 − 1 | 4 |
| x17 = √2 | x2 − 2 | 4 |
| x18 = 1 + √5/2 | 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 , there is a number in that is not contained in the given sequence.[B]
To find a number in 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.[10]
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).
Proof that for all n : xn ∉ (an, bn) 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).[C]
- Case 3: a∞ < b∞. Then every y in is not contained in the given sequence since for all n : y belongs to (an, bn) but xn does not.[11]
The proof is complete since, in all cases, at least one real number in has been found that is not contained in the given sequence.[D]
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.[12]
Example of Cantor's construction
An example illustrates how Cantor's construction works. Consider the sequence: 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, ... 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.[13]
| Interval | Finding the next interval | Interval (decimal) |
|---|---|---|
