Zeta-0/Revamp

This is Zeta-0

Primordial
Zeta-0/Revamp is a primordial page!. Primordial pages need to be protected, so if there is vandalism, it needs to be reverted ASAP!
"I vandalized this" - some random guy (fg kid)

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. 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

$x_1,x_2,x_3$, ... 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.

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:

• 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.

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 proof

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 + |a_0| + |a_1| + \cdots + |a_n|$, where $a_0, a_1, \cdots a_n$ 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.

Second theorem

Only the first part of Cantor's second theorem needs to be proved. It states: Given any sequence of real numbers x₁, x₂, x₃, ... 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 a₁ and the larger by b₁. Similarly, find the first two numbers of the given sequence that are in (a₁, b₁). Denote the smaller by a₂ and the larger by b₂. Continuing this procedure generates a sequence of intervals (a₁, b₁), (a₂, b₂), (a₃, b₃), ... 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 a₁, a₂, a₃, ... is increasing and the sequence b₁, b₂, b₃, ... is decreasing.

Either the number of intervals generated is finite or infinite. If finite, let (a_L, b_L) be the last interval. If infinite, take the limits a_∞ = lim_{n → ∞} a_n and b_∞ = lim_{n → ∞} b_n. Since a_n < b_n for all n, either a_∞ = b_∞ or a_∞ < b_∞. Thus, there are three cases to consider:

1. Case 1: There is a last interval (a_L, b_L). Since at most one x_n can be in this interval, every y in this interval except x_n (if it exists) is not in the given sequence.
2. Case 2: a_∞ = b_∞. Then a_∞ is not in the sequence since for all n : a_∞ is in the interval (a_n, b_n) but x_n does not belong to (a_n, b_n). In symbols: a_∞ ∈ (a_n, b_n) but x_n ∉ (a_n, b_n).

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).

• Case 3: a_∞ < b_∞. Then every y in [a_∞, b_∞] is not contained in the given sequence since for all n : y belongs to (a_n, b_n) but x_n does not.

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: 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 (a_n, b_n). The second column lists the terms visited during the search for the first two terms in (a_n, b_n). These two terms are in red.

Generating a number using Cantor's construction

Interval	Finding the next interval	Interval (decimal)

(1/3, 1/2)	2/3, 0.25, 3/4, etcetra.	(0.3333...., 0.500....)
(2/5, 3/7)	4,7, ... 1/12, 5/12, etcetra	(0.4285... 0.400...)
(7/12, 5/12)	8/17, etc	(0.4117... etc)
(12/29, 17/41)	18/41 etc	(0.4137... etc)
(41/99, 29/70)	43/99,..., 69/169 etc	(0.4141... etc)

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

Proof that the number generated is √2 − 1
The proof uses Farey sequences and continued fractions. The Farey sequence Fn  is the increasing sequence of completely reduced fractions whose denominators are $\leq n$. If $\frac{a}{b}$and are adjacent in a Farey sequence, the lowest denominator fraction between them is their mediant $\frac{a+c}{b+d}$, This mediant is adjacent to both $\frac{a}{b} \And \frac{c}{d}$in the Farey sequence Fb+d

This is still WIP by the way.