math – update

blogging & searching for true math …

Day #15: Cantor´s Dreams

Leave a comment

c-1

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.

As early as 1930, mathematicians have disagreed on whether this proof is constructive or non-constructive.[3] Books as recent as 2014 and 2015 indicate that this disagreement has not been resolved.[4] Since Cantor’s proof either constructs transcendental numbers or does not, an analysis of his article can determine whether his proof is constructive or non-constructive.[5] Cantor’s correspondence with Richard Dedekind shows the development of his ideas and reveals that he had a choice between two proofs, one that uses the uncountability of the real numbers and one that does not.
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 looked at the article’s legacy—namely, the impact of the uncountability theorem and the concept of countability on mathematics.

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]

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.[10]

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 show directly that if I start with a sequence
(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.
Cantor chose to publish the constructive proof, which not only produces a transcendental number but is also shorter and avoids two proofs by contradiction.
The non-constructive proof from Cantor’s correspondence is simpler than the one above because it works with all the real numbers rather than the interval [ab]. For example, this eliminates the subsequence step in the second proof by contradiction.

The influence of Weierstrass and Kronecker on Cantor’s article

Karl Weierstrass
    Leopold Kronecker, 1865
Historians of mathematics have discovered the following facts about Cantor’s article “On a Property of the Collection of All Real Algebraic Numbers”:
  • Cantor’s uncountability theorem was left out of the article he submitted. He added it during proofreading.[31]
  • The article’s title refers to the set of real algebraic numbers. The main topic in Cantor’s correspondence was the set of real numbers.[32]
  • The proof of Cantor’s second theorem does not state why some limits exist. The proof he was using does.[33]
  • Cantor restricted his first theorem to the set of real algebraic numbers. The proof he was using demonstrates the countability of the set of all algebraic numbers.[16]
To explain these facts, historians have pointed to the influence of Cantor’s former professors, Karl Weierstrass and Leopold Kronecker. Cantor discussed his results with Weierstrass on December 23, 1873.[34] Weierstrass was first amazed by the concept of countability, but then found the countability of the set of real algebraic numbers useful.[35] Cantor did not want to publish yet, but Weierstrass felt that he must publish at least his results concerning the algebraic numbers.[34]
From his correspondence, it appears that Cantor only discussed his article with Weierstrass. However, Cantor told Dedekind: “The restriction which I have imposed on the published version of my investigations is caused in part by local circumstances …”[34] Cantor biographer Joseph Dauben believes that “local circumstances” refers to Kronecker who, as a member of the editorial board of Crelle’s Journal, had delayed publication of an 1870 article by Eduard Heine. Cantor would submit his article to Crelle’s Journal.[36]
Weierstrass advised Cantor to leave his uncountability theorem out of the article he submitted, but Weierstrass also told Cantor that he could add it as a marginal note during proofreading, which he did.[31] It appears in a remark at the end of the article’s introduction.[37] The opinions of Kronecker and Weierstrass both played a role here. Kronecker did not accept infinite sets, and it seems that Weierstrass did not accept that two infinite sets could be so different, with one being countable and the other not.[38] Weierstrass changed his opinion later.[39] Without the uncountability theorem, the article needed a title that did not refer to this theorem. Cantor chose “On a Property of the Collection of All Real Algebraic Numbers,” which refers to the countability of the set of real algebraic numbers, the result that Weierstrass found useful.[40]
Kronecker’s influence appears in the proof of Cantor’s second theorem. Cantor used Dedekind’s version of the proof except he left out why the limits a = limn → ∞ an and b = limn → ∞ bn exist. Dedekind had used his “principle of continuity” to prove they exist. This principle (which is equivalent to the least upper bound property of the real numbers) comes from Dedekind’s construction of the real numbers, a construction Kronecker did not accept.[41]
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

Advertisements

Author: Math - Update

Updating Math In Our Mind & Heart!!...

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s