Cantor's first set theory article contains
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor ( , ; – January 6, 1918) was a German mathematician. He played a pivotal role in the creation of set theory, which has become a fundamental theory in mathematics. Cantor established the importance o ...
's first theorems of transfinite
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 concern ...
, which studies
infinite sets 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 distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s 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 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 called ...
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.
[. 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.
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 an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
of
degree ''n'' with integer
coefficients 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 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 below the su ...
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 (''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. 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
limit
Limit or Limits may refer to:
Arts and media
* ''Limit'' (manga), a manga by Keiko Suenobu
* ''Limit'' (film), a South Korean film
* Limit (music), a way to characterize harmony
* "Limit" (song), a 2016 single by Luna Sea
* "Limits", a 2019 ...
s ''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''
∞ ∈ (''a''
''n'', ''b''
''n'') but ''x''
''n'' ∉ (''a''
''n'', ''b''
''n'').
:
:Case 3: ''a''
∞ < ''b''
∞. Then every ''y'' in
∞, ''b''∞">'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. Computer programs are one component of software, which also includes software documentation, documentation and oth ...
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 (e.g. ). The set of all ra ...
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, 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 notion of a point set ''P'' being "everywhere
dense 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 is type of topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called poin ...
.
}
, -
, age 6br>
definitely occur ''within'' the interval �, β one of these numbers must have the ''least index,'' let it be ωκ1, and another: ωκ2 with the next larger index.
Let the smaller of the two numbers ωκ1, ωκ2 be denoted by α', the larger by β'. (Their equality is impossible because we assumed that our sequence consists of nothing but unequal numbers.)
Then according to the definition:
α < α' < β' < β,
furthermore:
κ1 < κ2;
and all numbers ωμ of our sequence,
for which μ ≤ κ2, do ''not'' lie in the interior of the interval �', β' as is immediately clear from the definition of the numbers κ1, κ2. Similarly, let ωκ3 and ωκ4 be the two numbers of our sequence with smallest indices that fall in the ''interior'' of the interval �', β'and let the smaller of the numbers ωκ3, ωκ4 be denoted by α'', the larger by β''.
Then one has:
α' < α'' < β'' < β',
κ2 < κ3 < κ4;
and one sees that all numbers ωμ of our sequence, for which μ ≤ κ4, do ''not'' fall into the ''interior'' of the interval '', β''">�'', β''
After one has followed this rule to reach an interval , the next interval is produced by selecting the first two (i. e. with lowest indices) numbers of our sequence (ω) (let them be and ωκ2ν) that fall into the ''interior'' of . Let the smaller of these two numbers be denoted by α(ν), the larger by β(ν).
The interval (ν), β(ν)">�(ν), β(ν)then lies in the ''interior'' of all preceding intervals and has the ''specific'' relation with our sequence (ω) that all numbers ωμ, for which μ ≤ κ2ν, ''definitely do not lie in its interior''. Since obviously:
and these numbers, as indices, are ''whole'' numbers, so:
κ2ν ≥ 2ν,
and hence:
ν < κ2ν;
thus, we can certainly say (and this is sufficient for the following):
''That if ν is an arbitrary whole number, the ealquantity ων lies outside the interval (ν) . . . β(ν)">�(ν) . . . β(ν)''
, german: eite 6br>
sicher Zahlen ''innerhalb'' des Intervalls (α . . . β) vorkommen, so muss eine von diesen Zahlen den ''kleinsten Index'' haben, sie sei ωκ1, und eine andere: ωκ2 mit dem nächst grösseren Index behaftet sein.
Die kleinere der beiden Zahlen ωκ1, ωκ2 werde mit α', die grössere mit β' bezeichnet. (Ihre Gleichheit ist ausgeschlossen, weil wir voraussetzten, dass unsere Reihe aus lauter ungleichen Zahlen besteht.)
Es ist alsdann der Definition nach:
α < α' < β' < β,
ferner:
κ1 < κ2;
und ausserdem ist zu bemerken, dass alle Zahlen ωμ unserer Reihe,
für welche μ ≤ κ2, ''nicht'' im Innern des Intervalls (α' . . . β') liegen, wie aus der Bestimmung der Zahlen κ1, κ2 sofort erhellt. Ganz ebenso mögen ωκ3, ωκ4 die beiden mit den kleinsten Indices versehenen Zahlen unserer Reihen ee note 1 belowsein, welche in das ''Innere'' des Intervalls (α' . . . β') fallen und die kleinere der Zahlen ωκ3, ωκ4 werde mit α'', die grössere mit β'' bezeichnet.
Man hat alsdann:
α' < α'' < β'' < β',
κ2 < κ3 < κ4;
und man erkennt, dass alle Zahlen ωμ unserer Reihe, für welche μ ≤ κ4 ''nicht'' in das ''Innere'' des Intervalls (α'' . . . β'') fallen.
Nachdem man unter Befolgung des gleichen Gesetzes zu einem Intervall gelangt ist, ergiebt sich das folgende Intervall dadurch aus demselben, dass man die beiden ersten (d. h. mit niedrigsten Indices versehenen) Zahlen unserer Reihe (ω) aufstellt (sie seien ωκ2ν – 1 und ωκ2ν), welche in das ''Innere'' von fallen; die kleinere dieser beiden Zahlen werde mit α(ν), die grössere mit β(ν) bezeichnet.
Das Intervall (α(ν) . . . β(ν)) liegt alsdann im ''Innern'' aller vorangegangenen Intervalle und hat zu unserer Reihe (ω) die ''eigenthümliche''
Beziehung, dass alle Zahlen ωμ, für welche μ ≤ κ2ν ''sicher nicht in seinem Innern'' liegen. Da offenbar:
und diese Zahlen, als Indices, ''ganze'' Zahlen sind, so ist:
κ2ν ≥ 2ν,
und daher:
ν < κ2ν;
wir können daher, und dies ist für das Folgende ausreichend, gewiss sagen:
''Dass, wenn ν eine beliebige ganze Zahl ist, die Grösse ων ausserhalb des Intervalls (α(ν) . . . β(ν)) liegt.'', label=none, italic=unset
, -
, age 7br>
Since the numbers α', α'', α, . . ., α(ν), . . . are continually increasing by value while simultaneously being enclosed in the interval �, β they have, by a well-known fundamental theorem of the theory of magnitudes ee note 2 below a limit that we denote by A, so that:
The same applies to the numbers β', β'', β, . . ., β(ν), . . ., which are continually decreasing and likewise lying in the interval �, β We call their limit B, so that:
Obviously, one has:
But it is easy to see that the case A < B can ''not'' occur here since otherwise every number ων of our sequence would lie ''outside'' of the interval , Bby lying outside the interval (ν), β(ν)">�(ν), β(ν) So our sequence (ω) would ''not'' be ''everywhere dense'' in the interval �, β contrary
to the assumption.
Thus, there only remains the case A = B and now it is demonstrated that the number:
η = A = B
does ''not'' occur in our sequence (ω).
If it were a member of our sequence, such as the νth, then one would have: η = ων.
But the latter equation is not possible for any value of ν because η is in the ''interior'' of the interval (ν), β(ν)">�(ν), β(ν) but ων lies ''outside'' of it.
, german: eite 7br>
Da die Zahlen α', α'', α, . . ., α(ν), . . . ihrer Grösse nach fortwährend wachsen, dabei jedoch im Intervalle (α . . . β) eingeschlossen sind, so haben sie, nach einem bekannten Fundamentalsatze der Grössenlehre, eine Grenze, die wir mit A bezeichnen, so dass:
Ein Gleiches gilt für die Zahlen β', β'', β, . . ., β(ν), . . . welche fortwährend abnehmen und dabei ebenfalls im Intervalle (α . . . β) liegen; wir nennen ihre Grenze B, so dass:
Man hat offenbar:
Es ist aber leicht zu sehen, dass der Fall A < B hier ''nicht'' vorkommen kann; da sonst jede Zahl ων, unserer Reihe ''ausserhalb'' des Intervalles (A . . . B) liegen würde, indem ων, ausserhalb des Intervalls (α(ν) . . . β(ν)) gelegen ist; unsere Reihe (ω) wäre im Intervall (α . . . β) ''nicht überalldicht,'' gegen die Voraussetzung.
Es bleibt daher nur der Fall A = B übrig und es zeigt sich nun, dass die Zahl:
in unserer Reihe (ω) ''nicht'' vorkommt.
Denn, würde sie ein Glied unserer Reihe sein, etwa das νte, so hätte man: η = ων.
Die letztere Gleichung ist aber für keinen Werth von v möglich, weil η im ''Innern'' des Intervalls (ν), β(ν)">�(ν), β(ν) ων aber ''ausserhalb'' desselben liegt., label=none, italic=unset
, -
, colspan="2" , Note 1: This is the only occurrence of "" ("our sequences") in the proof. There is only one sequence involved in Cantor's proof and everywhere else "" ("sequence") is used, so it is most likely a typographical error and should be "" ("our sequence"), which is how it has been translated.
Note 2: , which has been translated as "the theory of magnitudes", is a term used by 19th century German mathematicians that refers to the theory of discrete and continuous
Continuity or continuous may refer to:
Mathematics
* Continuity (mathematics), the opposing concept to discreteness; common examples include
** Continuous probability distribution or random variable in probability and statistics
** Continuous g ...
magnitudes. (.)
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 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. 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 and mathematics, 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. Proof by contradiction is also known ...
that the set of real numbers is uncountable. Cantor starts by assuming that the real numbers in