HOME

TheInfoList



OR:

Cantor's first set theory article contains
Georg Cantor Georg Ferdinand Ludwig Philipp Cantor ( ; ;  – 6 January 1918) was a mathematician who played a pivotal role in the creation of set theory, which has become a foundations of mathematics, fundamental theory in mathematics. Cantor establi ...
's first theorems of transfinite
set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory – as a branch of mathema ...
, which studies
infinite set In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable. Properties The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only set ...
s and their properties. One of these theorems is his "revolutionary discovery" that the
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
of all
real number In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...
s is
uncountably In mathematics, an uncountable set, informally, is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger tha ...
, rather than
countably In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...
, infinite. This theorem is proved using Cantor's first uncountability proof, which differs from the more familiar proof using his
diagonal argument Diagonal argument can refer to: * Diagonal argument (proof technique), proof techniques used in mathematics. A diagonal argument, in mathematics, is a technique employed in the proofs of the following theorems: *Cantor's diagonal argument (the ea ...
. 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 In mathematics, an algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio (1 + \sqrt)/2 is an algebraic number, because it is a ...
is countable. Cantor's article was published in 1874. In 1879, he modified his uncountability proof by using the
topological Topology (from the Greek words , and ) is the branch of mathematics concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, wit ...
notion of a set being
dense Density (volumetric mass density or specific mass) is the ratio of a substance's mass to its volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' (or ''d'') can also be use ...
in an interval. Cantor's article also contains a proof of the existence of
transcendental number In mathematics, a transcendental number is a real or complex number that is not algebraic: that is, not the root of a non-zero polynomial with integer (or, equivalently, rational) coefficients. The best-known transcendental numbers are and . ...
s. 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 Julius Wilhelm Richard Dedekind (; ; 6 October 1831 – 12 February 1916) was a German mathematician who made important contributions to number theory, abstract algebra (particularly ring theory), and the axiomatic foundations of arithmetic. H ...
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 Proofreading is a phase in the process of publishing where galley proofs are compared against the original manuscripts or graphic artworks, to identify transcription errors in the typesetting process. In the past, proofreaders would place corr ...
. They have traced this and other facts about the article to the influence of
Karl Weierstrass Karl Theodor Wilhelm Weierstrass (; ; 31 October 1815 – 19 February 1897) was a German mathematician often cited as the " father of modern analysis". Despite leaving university without a degree, he studied mathematics and trained as a school t ...
and
Leopold Kronecker Leopold Kronecker (; 7 December 1823 – 29 December 1891) was a German mathematician who worked on number theory, abstract algebra and logic, and criticized Georg Cantor's work on set theory. Heinrich Weber quoted Kronecker as having said, ...
. 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 In mathematics, the concept of a measure is a generalization and formalization of geometrical measures (length, area, volume) and other common notions, such as magnitude (mathematics), magnitude, mass, and probability of events. These seemingl ...
, and the
Lebesgue integral In mathematics, the integral of a non-negative Function (mathematics), function of a single variable can be regarded, in the simplest case, as the area between the Graph of a function, graph of that function and the axis. 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 number In mathematics, an algebraic number is a number that is a root of a function, root of a non-zero polynomial in one variable with integer (or, equivalently, Rational number, rational) coefficients. For example, the golden ratio (1 + \sqrt)/2 is ...
s and a statement of his first theorem: The set of real algebraic numbers can be put into
one-to-one correspondence In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equivale ...
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 mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...
in which each number appears only once.". Cantor's second theorem works with a
closed interval In mathematics, a real interval is the set of all real numbers lying between two fixed endpoints with no "gaps". Each endpoint is either a real number or positive or negative infinity, indicating the interval extends without a bound. A real in ...
'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.. 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 number In mathematics, a transcendental number is a real or complex number that is not algebraic: that is, not the root of a non-zero polynomial with integer (or, equivalently, rational) coefficients. The best-known transcendental numbers are and . ...
s. 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 The thumb is the first digit of the hand, next to the index finger. When a person is standing in the medical anatomical position (where the palm is facing to the front), the thumb is the outermost digit. The Medical Latin English noun for thum ...
than the set of positive integers. Cardinality is defined in Cantor's next article, which was published in 1878. 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 In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
of degree ''n'' with integer
coefficient In mathematics, a coefficient is a Factor (arithmetic), multiplicative factor involved in some Summand, term of a polynomial, a series (mathematics), series, or any other type of expression (mathematics), expression. It may be a Dimensionless qu ...
s as: ''n'' − 1 + , ''a''0,  + , ''a''1,  + ... + , ''a''''n'', , where ''a''0, ''a''1, ..., ''a''''n'' are the coefficients of the polynomial. Order the polynomials by their height, and order the real
root In vascular plants, the roots are the plant organ, organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often bel ...
s 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''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. 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 In mathematics, a real interval is the set (mathematics), set of all real numbers lying between two fixed endpoints with no "gaps". Each endpoint is either a real number or positive or negative infinity, indicating the interval extends without ...
(''a'', ''b''). Denote the smaller of these two numbers by ''a''1 and the larger by ''b''1. Similarly, find the first two numbers of the given sequence that are in (''a''1, ''b''1). Denote the smaller by ''a''2 and the larger by ''b''2. Continuing this procedure generates a sequence of intervals (''a''1, ''b''1), (''a''2, ''b''2), (''a''3, ''b''3), ... such that each interval in the sequence contains all succeeding intervals—that is, it generates a sequence of
nested intervals In mathematics, a sequence of nested intervals can be intuitively understood as an ordered collection of Interval (mathematics), intervals I_n on the Interval (mathematics), real number line with natural number, natural numbers n=1,2,3,\dots as a ...
. This implies that the sequence ''a''1, ''a''2, ''a''3, ... is increasing and the sequence ''b''1, ''b''2, ''b''3, ... 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: :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. :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'' 
In mathematics, an element (or member) of a set is any one of the distinct objects that belong to that set. For example, given a set called containing the first four positive integers (A = \), one could say that "3 is an element of ", expressed ...
 (''a''''n'', ''b''''n'') but ''x''''n''   (''a''''n'', ''b''''n''). : :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.. 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 A computer program is a sequence or set of instructions in a programming language for a computer to Execution (computing), execute. It is one component of software, which also includes software documentation, documentation and other intangibl ...
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 number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (for example, The set of all ...
s 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. Since the sequence contains all the rational numbers in (0, 1), the construction generates an
irrational number In mathematics, the irrational numbers are all the real numbers that are not rational numbers. That is, irrational numbers cannot be expressed as the ratio of two integers. When the ratio of lengths of two line segments is an irrational number, ...
, which turns out to be  − 1.


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 Topology (from the Greek words , and ) is the branch of mathematics concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, wit ...
notion of a point set ''P'' being "everywhere
dense Density (volumetric mass density or specific mass) is the ratio of a substance's mass to its volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' (or ''d'') can also be use ...
in an interval": :If ''P'' lies partially or completely in the interval �, β then the remarkable case can happen that ''every'' interval �, δcontained in �, β ''no matter how small,'' contains points of ''P''. In such a case, we will say that ''P'' is ''everywhere dense in the interval'' �, β In this discussion of Cantor's proof: ''a'', ''b'', ''c'', ''d'' are used instead of α, β, γ, δ. Also, Cantor only uses his interval notation if the first endpoint is less than the second. For this discussion, this means that (''a'', ''b'') implies ''a'' < ''b''. Since the discussion of Cantor's 1874 proof was simplified by using open intervals rather than closed intervals, the same simplification is used here. This requires an equivalent definition of everywhere dense: A set ''P'' is everywhere dense in the interval 'a'', ''b''if and only if every open subinterval (''c'', ''d'') of 'a'', ''b''contains at least one point of ''P''. Cantor did not specify how many points of ''P'' an open subinterval (''c'', ''d'') must contain. He did not need to specify this because the assumption that every open subinterval contains at least one point of ''P'' implies that every open subinterval contains infinitely many points of ''P''.


Cantor's 1879 proof

Cantor modified his 1874 proof with a new proof of its second theorem: Given any sequence ''P'' 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 ''P''. Cantor's new proof has only two cases. First, it handles the case of ''P'' not being dense in the interval, then it deals with the more difficult case of ''P'' being dense in the interval. This division into cases not only indicates which sequences are more difficult to handle, but it also reveals the important role denseness plays in the proof.Since Cantor's proof has not been published in English, an English translation is given alongside the original German text, which is from . The translation starts one sentence before the proof because this sentence mentions Cantor's 1874 proof. Cantor states it was printed in Borchardt's Journal. Crelle's Journal was also called Borchardt's Journal from 1856-1880 when Carl Wilhelm Borchardt edited the journal (). Square brackets are used to identify this mention of Cantor's earlier proof, to clarify the translation, and to provide page numbers. Also, "" (manifold) has been translated to "set" and Cantor's notation for closed sets (α . . . β) has been translated to �, β Cantor changed his terminology from to (set) in his 1883 article, which introduced sets of
ordinal number In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the leas ...
s (). Currently in mathematics, a
manifold In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an n-dimensional manifold, or ''n-manifold'' for short, is a topological space with the property that each point has a N ...
is type of
topological space In mathematics, a topological space is, roughly speaking, a Geometry, geometrical space in which Closeness (mathematics), closeness is defined but cannot necessarily be measured by a numeric Distance (mathematics), distance. More specifically, a to ...
.
In the first case, ''P'' is not dense in 'a'', ''b'' By definition, ''P'' is dense in 'a'', ''b''if and only if for all subintervals (''c'', ''d'') of 'a'', ''b'' there is an ''x'' ∈ ''P'' such that . Taking the negation of each side of the "if and only if" produces: ''P'' is not dense in 'a'', ''b''if and only if there exists a subinterval (''c'', ''d'') of 'a'', ''b''such that for all ''x'' ∈ ''P'': . Therefore, every number in (''c'', ''d'') is not contained in the sequence ''P''. This case handles case 1 and case 3 of Cantor's 1874 proof. In the second case, which handles case 2 of Cantor's 1874 proof, ''P'' is dense in 'a'', ''b'' The denseness of sequence ''P'' is used to recursively define a sequence of nested intervals that excludes all the numbers in ''P'' and whose
intersection In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their ...
contains a single real number in 'a'', ''b'' The sequence of intervals starts with (''a'', ''b''). Given an interval in the sequence, the next interval is obtained by finding the two numbers with the least indices that belong to ''P'' and to the current interval. These two numbers are the endpoints of the next open interval. Since an open interval excludes its endpoints, every nested interval eliminates two numbers from the front of sequence ''P'', which implies that the intersection of the nested intervals excludes all the numbers in ''P''. Details of this proof and a proof that this intersection contains a single real number in 'a'', ''b''are given below.


The development of Cantor's ideas

The development leading to Cantor's 1874 article appears in the correspondence between Cantor and
Richard Dedekind Julius Wilhelm Richard Dedekind (; ; 6 October 1831 – 12 February 1916) was a German mathematician who made important contributions to number theory, abstract algebra (particularly ring theory), and the axiomatic foundations of arithmetic. H ...
. 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 (''a''''n''1, ''n''2, . . . , ''n''''ν'') where ''n''1, ''n''2, . . . , ''n''''ν'', and ''ν'' are positive integers. 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.. English translation: . 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." On December 7, Cantor sent Dedekind a
proof by contradiction In logic, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition by showing that assuming the proposition to be false leads to a contradiction. Although it is quite freely used in mathematical pr ...
that the set of real numbers is uncountable. Cantor starts by assuming that the real numbers in ,1/math> can be written as a sequence. Then, he applies a construction to this sequence to produce a number in ,1/math> that is not in the sequence, thus contradicting his assumption.. English translation: . Together, the letters of December 2 and 7 provide a non-constructive proof of the existence of transcendental numbers. Also, the proof in Cantor's December 7 letter shows some of the reasoning that led to his discovery that the real numbers form an uncountable set. Dedekind received Cantor's proof on December 8. On that same day, Dedekind simplified the proof and mailed his proof to Cantor. Cantor used Dedekind's proof in his article. The letter containing Cantor's December 7 proof was not published until 1937. 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: 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. These two proofs can be compared by starting with a sequence consisting of all the real algebraic numbers. The constructive proof applies Cantor's construction to this sequence and the interval 'a'', ''b''to produce a transcendental number in this interval. The non-constructive proof uses two proofs by contradiction: # The proof by contradiction used to prove the uncountability theorem (see Proof of Cantor's uncountability theorem). # The proof by contradiction used to prove the existence of transcendental numbers from the countability of the real algebraic numbers and the uncountability of real numbers. Cantor's December 2nd letter mentions this existence proof but does not contain it. Here is a proof: Assume that there are no transcendental numbers in 'a'', ''b'' Then all the numbers in 'a'', ''b''are algebraic. This implies that they form a
subsequence In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence \langle A,B,D \rangle is a ...
of the sequence of all real algebraic numbers, which contradicts Cantor's uncountability theorem. Thus, the assumption that there are no transcendental numbers in 'a'', ''b''is false. Therefore, there is a transcendental number in 'a'', ''b'' 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 'a'', ''b'' This eliminates the subsequence step and all occurrences of 'a'', ''b''in the second proof by contradiction.


A misconception about Cantor's work

Akihiro Kanamori is a Japanese-born American mathematician. He specializes in set theory and is the author of the monograph on large cardinals, '' The Higher Infinite''. He has written several essays on the history of mathematics, especially set theory. Kanamor ...
, who specializes in set theory, stated that "Accounts of Cantor's work have mostly reversed the order for deducing the existence of transcendental numbers, establishing first the uncountability of the reals and only then drawing the existence conclusion from the countability of the algebraic numbers. In textbooks the inversion may be inevitable, but this has promoted the misconception that Cantor's arguments are non-constructive.". Cantor's published proof and the reverse-order proof both use the theorem: Given a sequence of reals, a real can be found that is not in the sequence. By applying this theorem to the sequence of real algebraic numbers, Cantor produced a transcendental number. He then proved that the reals are uncountable: Assume that there is a sequence containing all the reals. Applying the theorem to this sequence produces a real not in the sequence, contradicting the assumption that the sequence contains all the reals. Hence, the reals are uncountable. The reverse-order proof starts by first proving the reals are uncountable. It then proves that transcendental numbers exist: If there were no transcendental numbers, all the reals would be algebraic and hence countable, which contradicts what was just proved. This contradiction proves that transcendental numbers exist without constructing any. The correspondence containing Cantor's non-constructive reasoning was published in 1937. By then, other mathematicians had rediscovered his non-constructive, reverse-order proof. As early as 1921, this proof was called "Cantor's proof" and criticized for not producing any transcendental numbers. In that year,
Oskar Perron Oskar Perron (7 May 1880 – 22 February 1975) was a German mathematician. He was a professor at the University of Heidelberg from 1914 to 1922 and at the University of Munich from 1922 to 1951. He made numerous contributions to differentia ...
gave the reverse-order proof and then stated: "... Cantor's proof for the existence of transcendental numbers has, along with its simplicity and elegance, the great disadvantage that it is only an existence proof; it does not enable us to actually specify even a single transcendental number." As early as 1930, some mathematicians have attempted to correct this misconception of Cantor's work. In that year, the set theorist
Abraham Fraenkel Abraham Fraenkel (; 17 February, 1891 – 15 October, 1965) was a German-born Israeli mathematician. He was an early Zionist and the first Dean of Mathematics at the Hebrew University of Jerusalem. He is known for his contributions to axiomatic ...
stated that Cantor's method is "... a method that incidentally, contrary to a widespread interpretation, is fundamentally constructive and not merely existential." In 1972,
Irving Kaplansky Irving Kaplansky (March 22, 1917 – June 25, 2006) was a mathematician, college professor, author, and amateur musician.O'Connor, John J.; Robertson, Edmund F., "Irving Kaplansky", MacTutor History of Mathematics archive, University of St And ...
wrote: "It is often said that Cantor's proof is not 'constructive,' and so does not yield a tangible transcendental number. This remark is not justified. If we set up a definite listing of all algebraic numbers ... and then apply the diagonal procedure ..., we get a perfectly definite transcendental number (it could be computed to any number of decimal places)." Cantor's proof is not only constructive, it is also simpler than Perron's proof, which requires the detour of first proving that the set of all reals is uncountable. Cantor's diagonal argument has often replaced his 1874 construction in expositions of his proof. The diagonal argument is constructive and produces a more efficient computer program than his 1874 construction. Using it, a computer program has been written that computes the digits of a transcendental number in
polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
. The program that uses Cantor's 1874 construction requires at least sub-exponential time.) steps to produce n digits. (.) The presentation of the non-constructive proof without mentioning Cantor's constructive proof appears in some books that were quite successful as measured by the length of time new editions or reprints appeared—for example: Oskar Perron's Irrationalzahlen (1921; 1960, 4th edition), Eric Temple Bell's '' Men of Mathematics'' (1937; still being reprinted), Godfrey Hardy and E. M. Wright's ''An Introduction to the
Theory of Numbers Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
'' (1938; 2008 6th edition),
Garrett Birkhoff Garrett Birkhoff (January 19, 1911 – November 22, 1996) was an American mathematician. He is best known for his work in lattice theory. The mathematician George Birkhoff (1884–1944) was his father. Life The son of the mathematician Ge ...
and Saunders Mac Lane's ''A Survey of Modern Algebra'' (1941; 1997 5th edition), and Michael Spivak's ''
Calculus Calculus is the mathematics, mathematical study of continuous change, in the same way that geometry is the study of shape, and algebra is the study of generalizations of arithmetic operations. Originally called infinitesimal calculus or "the ...
'' (1967; 2008 4th edition). Since 2014, at least two books have appeared stating that Cantor's proof is constructive, and at least four have appeared stating that his proof does not construct any (or a single) transcendental. Asserting that Cantor gave a non-constructive argument without mentioning the constructive proof he published can lead to erroneous statements about the
history of mathematics The history of mathematics deals with the origin of discoveries in mathematics and the History of mathematical notation, mathematical methods and notation of the past. Before the modern age and the worldwide spread of knowledge, written examples ...
. In ''A Survey of Modern Algebra,'' Birkhoff and Mac Lane state: "Cantor's argument for this result ot every real number is algebraicwas at first rejected by many mathematicians, since it did not exhibit any specific transcendental number." The proof that Cantor published produces transcendental numbers, and there appears to be no evidence that his argument was rejected. Even
Leopold Kronecker Leopold Kronecker (; 7 December 1823 – 29 December 1891) was a German mathematician who worked on number theory, abstract algebra and logic, and criticized Georg Cantor's work on set theory. Heinrich Weber quoted Kronecker as having said, ...
, who had strict views on what is acceptable in mathematics and who could have delayed publication of Cantor's article, did not delay it. In fact, applying Cantor's construction to the sequence of real algebraic numbers produces a limiting process that Kronecker accepted—namely, it determines a number to any required degree of accuracy.


The influence of Weierstrass and Kronecker on Cantor's article

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 Proofreading is a phase in the process of publishing where galley proofs are compared against the original manuscripts or graphic artworks, to identify transcription errors in the typesetting process. In the past, proofreaders would place corr ...
.. * 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. * The proof of Cantor's second theorem came from Dedekind. However, it omits Dedekind's explanation of why the limits ''a'' and ''b'' exist. * 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. To explain these facts, historians have pointed to the influence of Cantor's former professors,
Karl Weierstrass Karl Theodor Wilhelm Weierstrass (; ; 31 October 1815 – 19 February 1897) was a German mathematician often cited as the " father of modern analysis". Despite leaving university without a degree, he studied mathematics and trained as a school t ...
and Leopold Kronecker. Cantor discussed his results with Weierstrass on December 23, 1873.. English translation: . Weierstrass was first amazed by the concept of countability, but then found the countability of the set of real algebraic numbers useful. Cantor did not want to publish yet, but Weierstrass felt that he must publish at least his results concerning the algebraic numbers. 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 ..." Cantor biographer Joseph Dauben believes that "local circumstances" refers to Kronecker who, as a member of the editorial board of ''
Crelle's Journal ''Crelle's Journal'', or just ''Crelle'', is the common name for a mathematics journal, the ''Journal für die reine und angewandte Mathematik'' (in English: ''Journal for Pure and Applied Mathematics''). History The journal was founded by A ...
'', had delayed publication of an 1870 article by
Eduard Heine Heinrich Eduard Heine (16 March 1821 – 21 October 1881) was a German mathematician. Heine became known for results on special functions and in real analysis. In particular, he authored an important treatise on spherical harmonics and Leg ...
, one of Cantor's colleagues. Cantor would submit his article to ''Crelle's Journal''. 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. It appears in a remark at the end of the article's introduction. 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. Weierstrass changed his opinion later. Without the uncountability theorem, the article needed a title that did not refer to this theorem. Cantor chose "Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen" ("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. 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'' = lim''n'' → ∞ ''an'' and ''b'' = lim''n'' → ∞ ''bn'' exist. Dedekind had used his "principle of continuity" to prove they exist. This principle (which is equivalent to the
least upper bound property In mathematics, the least-upper-bound property (sometimes called completeness, supremum property or l.u.b. property) is a fundamental property of the real numbers. More generally, a partially ordered set has the least-upper-bound property if ever ...
of the real numbers) comes from Dedekind's construction of the real numbers, a construction Kronecker did not accept. 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. Cantor did this for expository reasons and because of "local circumstances". 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.


Dedekind's contributions to Cantor's article

Since 1856, Dedekind had developed theories involving infinitely many infinite sets—for example: ideals, which he used in
algebraic number theory Algebraic number theory is a branch of number theory that uses the techniques of abstract algebra to study the integers, rational numbers, and their generalizations. Number-theoretic questions are expressed in terms of properties of algebraic ob ...
, and
Dedekind cut In mathematics, Dedekind cuts, named after German mathematician Richard Dedekind (but previously considered by Joseph Bertrand), are а method of construction of the real numbers from the rational numbers. A Dedekind cut is a partition of a set, ...
s, which he used to construct the real numbers. This work enabled him to understand and contribute to Cantor's work. Dedekind's first contribution concerns the theorem that the set of real algebraic numbers is countable. Cantor is usually given credit for this theorem, but the mathematical historian José Ferreirós calls it "Dedekind's theorem." Their correspondence reveals what each mathematician contributed to the theorem. In his letter introducing the concept of countability, Cantor stated without proof that the set of positive rational numbers is countable, as are sets of the form (''a''''n''1, ''n''2, ..., ''n''''ν'') where ''n''1, ''n''2, ..., ''n''''ν'', and ''ν'' are positive integers. Cantor's second result uses an
indexed family In mathematics, a family, or indexed family, is informally a collection of objects, each associated with an index from some index set. For example, a family of real numbers, indexed by the set of integers, is a collection of real numbers, wher ...
of numbers: a set of the form (''a''''n''1, ''n''2, ..., ''n''''ν'') is the range of a function from the ''ν'' indices to the set of real numbers. His second result implies his first: let ''ν'' = 2 and ''a''''n''1, ''n''2 = . The function can be quite general—for example, ''a''''n''1, ''n''2, ''n''3, ''n''4, ''n''5 =  +  Dedekind replied with a proof of the theorem that the set of all algebraic numbers is countable. In his reply to Dedekind, Cantor did not claim to have proved Dedekind's result. He did indicate how he proved his theorem about indexed families of numbers: "Your proof that (''n'') he set of positive integerscan be correlated one-to-one with the field of all algebraic numbers is approximately the same as the way I prove my contention in the last letter. I take ''n''12 + ''n''22 + ··· + ''n''''ν''2 = \mathfrak and order the elements accordingly." However, Cantor's ordering is weaker than Dedekind's and cannot be extended to n-tuples of integers that include zeros. Dedekind's second contribution is his proof of Cantor's second theorem. Dedekind sent this proof in reply to Cantor's letter that contained the uncountability theorem, which Cantor proved using infinitely many sequences. Cantor next wrote that he had found a simpler proof that did not use infinitely many sequences. So Cantor had a choice of proofs and chose to publish Dedekind's. Cantor thanked Dedekind privately for his help: "... your comments (which I value highly) and your manner of putting some of the points were of great assistance to me." However, he did not mention Dedekind's help in his article. In previous articles, he had acknowledged help received from Kronecker, Weierstrass, Heine, and
Hermann Schwarz Karl Hermann Amandus Schwarz (; 25 January 1843 – 30 November 1921) was a German mathematician, known for his work in complex analysis. Life Schwarz was born in Hermsdorf, Silesia (now Sobieszów, Poland). In 1868 he married Marie Kummer ...
. Cantor's failure to mention Dedekind's contributions damaged his relationship with Dedekind. Dedekind stopped replying to his letters and did not resume the correspondence until October 1876.


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 R''n'' (where R is the set of real numbers) and the set of irrational numbers have the same cardinality as R. In 1883, Cantor extended the positive integers with his infinite ordinals. This extension was necessary for his work on the
Cantor–Bendixson theorem In the mathematical field of descriptive set theory, a subset of a Polish space has the perfect set property if it is either countable or has a nonempty perfect subset (Kechris 1995, p. 150). Note that having the perfect set property is n ...
. Cantor discovered other uses for the ordinals—for example, he used sets of ordinals to produce an infinity of sets having different infinite cardinalities. His work on infinite sets together with Dedekind's set-theoretical work created set theory. 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. In the 1890s,
Émile Borel Félix Édouard Justin Émile Borel (; 7 January 1871 – 3 February 1956) was a French people, French mathematician and politician. As a mathematician, he was known for his founding work in the areas of measure theory and probability. Biograp ...
used countable unions in his theory of measure, and René Baire used countable ordinals to define his classes of functions. Building on the work of Borel and Baire,
Henri Lebesgue Henri Léon Lebesgue (; ; June 28, 1875 – July 26, 1941) was a French mathematician known for his Lebesgue integration, theory of integration, which was a generalization of the 17th-century concept of integration—summing the area between an ...
created his theories of measure and integration, which were published from 1899 to 1901. Countable
models A model is an informative representation of an object, person, or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin , . Models can be divided int ...
are used in set theory. In 1922,
Thoralf Skolem Thoralf Albert Skolem (; 23 May 1887 – 23 March 1963) was a Norwegian mathematician who worked in mathematical logic and set theory. Life Although Skolem's father was a primary school teacher, most of his extended family were farmers. Skole ...
proved that if conventional
axioms of set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory – as a branch of mathematics – is mostly ...
are
consistent In deductive logic, a consistent theory is one that does not lead to a logical contradiction. A theory T is consistent if there is no formula \varphi such that both \varphi and its negation \lnot\varphi are elements of the set of consequences ...
, then they have a countable model. Since this model is countable, its set of real numbers is countable. This consequence is called Skolem's paradox, and Skolem explained why it does not contradict Cantor's uncountability theorem: although there is a one-to-one correspondence between this set and the set of positive integers, no such one-to-one correspondence is a member of the model. Thus the model considers its set of real numbers to be uncountable, or more precisely, the first-order sentence that says the set of real numbers is uncountable is true within the model. In 1963,
Paul Cohen Paul Joseph Cohen (April 2, 1934 – March 23, 2007) was an American mathematician, best known for his proofs that the continuum hypothesis and the axiom of choice are independent from Zermelo–Fraenkel set theory, for which he was awarded a F ...
used countable models to prove his
independence Independence is a condition of a nation, country, or state, in which residents and population, or some portion thereof, exercise self-government, and usually sovereignty, over its territory. The opposite of independence is the status of ...
theorems..


See also

*
Cantor's theorem In mathematical set theory, Cantor's theorem is a fundamental result which states that, for any Set (mathematics), set A, the set of all subsets of A, known as the power set of A, has a strictly greater cardinality than A itself. For finite s ...


Notes


Note on Cantor's 1879 proof


References


Bibliography

* . * . * . Reprinted, 1984, . * . Reprinted, Taylor & Francis, 1997, . * . * . * . * . * . * . * . * . * . * . * . * . * . * . * . * . * . * . * . * . * . * . * . * .
Reprinted by Dover Publications
2002, .) * . * . * . * . * . * . * . {{Mathematical logic Georg Cantor History of mathematics Real analysis Set theory