
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
∞, ''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. 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