In

_{1}, ''x''_{2}, ''x''_{3}, ...), where each ''x_{n}'' is either ''m'' or ''w''. Each of these elements corresponds to a _{1}, ''x''_{2}, ''x''_{3}, ...) corresponds to . So Cantor's argument implies that the set of all subsets of N has greater cardinality than N. The set of all subsets of N is denoted by ''P''(N), the

Doron Zeilberger's 68th Opinion

Philosopher Hartley Slater's argument against the idea of "number" that underpins Cantor's set theory

Wolfgang Mueckenheim: Transfinity - A Source Book

Hodges "An editor recalls some hopeless papers"

{{Infinity Discovery and invention controversies History of mathematics Philosophy of mathematics Set theory Georg Cantor

mathematical logic
Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...

, the theory of 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 th ...

s was first developed by 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 of ...

. Although this work has become a thoroughly standard fixture of classical 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 conce ...

, it has been criticized in several areas by mathematicians and philosophers.
Cantor's theorem
In mathematical set theory, Cantor's theorem is a fundamental result which states that, for any set A, the set of all subsets of A, the power set of A, has a strictly greater cardinality than A itself.
For finite sets, Cantor's theorem can be ...

implies that there are sets having cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...

greater than the infinite cardinality of the set of natural numbers
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal n ...

. Cantor's argument for this theorem is presented with one small change. This argument can be improved by using a definition he gave later. The resulting argument uses only five axioms of set theory.
Cantor's set theory was controversial at the start, but later became largely accepted. Most modern mathematics textbooks implicitly use Cantor's views on mathematical infinity
Infinity is that which is boundless, endless, or larger than any natural number. It is often denoted by the infinity symbol .
Since the time of the Greek mathematics, ancient Greeks, the Infinity (philosophy), philosophical nature of infinit ...

. For example, a line is generally presented as the infinite set of its points, and it is commonly taught that there are more real numbers than rational numbers (see cardinality of the continuum
In set theory, the cardinality of the continuum is the cardinality or "size" of the set of real numbers \mathbb R, sometimes called the continuum. It is an infinite cardinal number and is denoted by \mathfrak c (lowercase fraktur "c") or , \mathb ...

).
Cantor's argument

Cantor's first proof that infinite sets can have differentcardinalities
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...

was published in 1874. This proof demonstrates that the set of natural numbers and the set of 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 real ...

s have different cardinalities. It uses the theorem that a bounded increasing 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 calle ...

of real numbers has a 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 ...

, which can be proved by using Cantor's or 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. His ...

's construction of the irrational number
In mathematics, the irrational numbers (from in- prefix assimilated to ir- (negative prefix, privative) + rational) are all the real numbers that are not rational numbers. That is, irrational numbers cannot be expressed as the ratio of two integ ...

s. Because Leopold Kronecker
Leopold Kronecker (; 7 December 1823 – 29 December 1891) was a German mathematician who worked on number theory, algebra and logic. He criticized Georg Cantor's work on set theory, and was quoted by as having said, "'" ("God made the integers, ...

did not accept these constructions, Cantor was motivated to develop a new proof.
In 1891, he published "a much simpler proof ... which does not depend on considering the irrational numbers." His new proof uses his diagonal argument A diagonal argument, in mathematics, is a technique employed in the proofs of the following theorems:
*Cantor's diagonal argument (the earliest)
*Cantor's theorem
*Russell's paradox
*Diagonal lemma
** Gödel's first incompleteness theorem
**Tarski' ...

to prove that there exists an infinite set with a larger number of elements (or greater cardinality) than the set of natural numbers N = . This larger set consists of the elements (''x''subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...

of N—namely, the element (''x''power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...

of N.
Cantor generalized his argument to an arbitrary set ''A'' and the set consisting of all functions from ''A'' to . Each of these functions corresponds to a subset of ''A'', so his generalized argument implies the theorem: The power set ''P''(''A'') has greater cardinality than ''A''. This is known as Cantor's theorem
In mathematical set theory, Cantor's theorem is a fundamental result which states that, for any set A, the set of all subsets of A, the power set of A, has a strictly greater cardinality than A itself.
For finite sets, Cantor's theorem can be ...

.
The argument below is a modern version of Cantor's argument that uses power sets (for his original argument, see Cantor's diagonal argument
In set theory, Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument, the anti-diagonal argument, the diagonal method, and Cantor's diagonalization proof, was published in 1891 by Georg Cantor as a m ...

). By presenting a modern argument, it is possible to see which assumptions of axiomatic 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 mathematics, ...

are used. The first part of the argument proves that N and ''P''(N) have different cardinalities:
* There exists at least one infinite set. This assumption (not formally specified by Cantor) is captured in formal set theory by the axiom of infinity
In axiomatic set theory and the branches of mathematics and philosophy that use it, the axiom of infinity is one of the axioms of Zermelo–Fraenkel set theory. It guarantees the existence of at least one infinite set, namely a set containing the ...

. This axiom implies that N, the set of all natural numbers, exists.
* ''P''(N), the set of all subsets of N, exists. In formal set theory, this is implied by the power set axiom
In mathematics, the axiom of power set is one of the Zermelo–Fraenkel axioms of axiomatic set theory.
In the formal language of the Zermelo–Fraenkel axioms, the axiom reads:
:\forall x \, \exists y \, \forall z \, \in y \iff \forall w ...

, which says that for every set there is a set of all of its subsets.
* The concept of "having the same number" or "having the same cardinality" can be captured by the idea of one-to-one correspondence
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...

. This (purely definitional) assumption is sometimes known as Hume's principle
Hume's principle or HP says that the number of ''F''s is equal to the number of ''G''s if and only if there is a one-to-one correspondence (a bijection) between the ''F''s and the ''G''s. HP can be stated formally in systems of second-order logic. ...

. As Frege
Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician. He was a mathematics professor at the University of Jena, and is understood by many to be the father of analytic ph ...

said, "If a waiter wishes to be certain of laying exactly as many knives on a table as plates, he has no need to count either of them; all he has to do is to lay immediately to the right of every plate a knife, taking care that every knife on the table lies immediately to the right of a plate. Plates and knives are thus correlated one to one." Sets in such a correlation are called equinumerous
In mathematics, two sets or classes ''A'' and ''B'' are equinumerous if there exists a one-to-one correspondence (or bijection) between them, that is, if there exists a function from ''A'' to ''B'' such that for every element ''y'' of ''B'', ther ...

, and the correlation is called a one-to-one correspondence.
* A set cannot be put into one-to-one correspondence with its power set. This implies that N and ''P''(N) have different cardinalities. It depends on very few assumptions 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 conce ...

, and, as John P. Mayberry puts it, is a "simple and beautiful argument" that is "pregnant with consequences". Here is the argument:
*:Let $A$ be a set and $P(A)$ be its power set. The following theorem will be proved: If $f$ is a function from $A$ to $P(A),$ then it is not onto
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of i ...

. This theorem implies that there is no one-to-one correspondence between $A$ and $P(A)$ since such a correspondence must be onto. Proof of theorem: Define the diagonal subset $D\; =\; \backslash .$ Since $D\; \backslash in\; P(A),$ proving that for all $x\; \backslash in\; A,\backslash ,\; D\; \backslash ne\; f(x)$ will imply that $f$ is not onto. Let $x\; \backslash in\; A.$ Then $x\; \backslash in\; D\; \backslash Leftrightarrow\; x\; \backslash notin\; f(x),$ which implies $x\; \backslash notin\; D\; \backslash Leftrightarrow\; x\; \backslash in\; f(x).$ So if $x\; \backslash in\; D,$ then $x\; \backslash notin\; f(x);$ and if $x\; \backslash notin\; D,$ then $x\; \backslash in\; f(x).$ Since one of these sets contains $x$ and the other does not, $D\; \backslash ne\; f(x).$ Therefore, $D$ is not in the image
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...

of $f$, so $f$ is not onto.
Next Cantor shows that $A$ is equinumerous with a subset of $P(A)$. From this and the fact that $P(A)$ and $A$ have different cardinalities, he concludes that $P(A)$ has greater cardinality than $A$. This conclusion uses his 1878 definition: If ''A'' and ''B'' have different cardinalities, then either ''B'' is equinumerous with a subset of ''A'' (in this case, ''B'' has less cardinality than ''A'') or ''A'' is equinumerous with a subset of ''B'' (in this case, ''B'' has greater cardinality than ''A''). This definition leaves out the case where ''A'' and ''B'' are equinumerous with a subset of the other set—that is, ''A'' is equinumerous with a subset of ''B'' and ''B'' is equinumerous with a subset of ''A''. Because Cantor implicitly assumed that cardinalities are linearly ordered
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...

, this case cannot occur. After using his 1878 definition, Cantor stated that in an 1883 article he proved that cardinalities are well-ordered
In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-orde ...

, which implies they are linearly ordered. This proof used his well-ordering principle "every set can be well-ordered", which he called a "law of thought". The well-ordering principle is equivalent to the axiom of choice
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...

.
Around 1895, Cantor began to regard the well-ordering principle as a theorem and attempted to prove it. In 1895, Cantor also gave a new definition of "greater than" that correctly defines this concept without the aid of his well-ordering principle.Cantor 1895, pp. 483–484; English translation: Cantor 1954, pp. 89–90. By using Cantor's new definition, the modern argument that ''P''(N) has greater cardinality than N can be completed using weaker assumptions than his original argument:
* The concept of "having greater cardinality" can be captured by Cantor's 1895 definition: ''B'' has greater cardinality than ''A'' if (1) ''A'' is equinumerous with a subset of ''B'', and (2) ''B'' is not equinumerous with a subset of ''A''. Clause (1) says ''B'' is at least as large as ''A'', which is consistent with our definition of "having the same cardinality". Clause (2) implies that the case where ''A'' and ''B'' are equinumerous with a subset of the other set is false. Since clause (2) says that ''A'' is not at least as large as ''B'', the two clauses together say that ''B'' is larger (has greater cardinality) than ''A''.
* The power set $P(A)$ has greater cardinality than $A,$ which implies that ''P''(N) has greater cardinality than N. Here is the proof:
*# Define the subset $P\_1\; =\; \backslash .$ Define $f(x)\; =\; \backslash ,$ which maps $A$ onto $P\_1.$ Since $f(x\_1)\; =\; f(x\_2)$ implies $x\_1\; =\; x\_2,\; \backslash ,\; f$ is a one-to-one correspondence from $A$ to $P\_1.$ Therefore, $A$ is equinumerous with a subset of $P(A).$
*# Using 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 as ...

, assume that $A\_1,$ a subset of $A,$ is equinumerous with $P(A).$. Then there is a one-to-one correspondence $g$ from $A\_1$ to $P(A).$ Define $h$ from $A$ to $P(A)\backslash text$ if $x\; \backslash in\; A\_1,$ then $h(x)\; =\; g(x);$ if $x\; \backslash in\; A\; \backslash setminus\; A\_1,$ then $h(x)\; =\; \backslash .$ Since $g$ maps $A\_1$ onto $P(A),\; \backslash ,\; h$ maps $A$ onto $P(A),$ contradicting the theorem above stating that a function from $A$ to $P(A)$ is not onto. Therefore, $P(A)$ is not equinumerous with a subset of $A.$
Besides the axioms of infinity and power set, the axioms of separation, extensionality
In logic, extensionality, or extensional equality, refers to principles that judge objects to be equal if they have the same external properties. It stands in contrast to the concept of intensionality, which is concerned with whether the internal ...

, and pairing
In mathematics, a pairing is an ''R''-bilinear map from the Cartesian product of two ''R''-modules, where the underlying ring ''R'' is commutative.
Definition
Let ''R'' be a commutative ring with unit, and let ''M'', ''N'' and ''L'' be ''R''-modu ...

were used in the modern argument. For example, the axiom of separation was used to define the diagonal subset $D,$ the axiom of extensionality was used to prove $D\; \backslash ne\; f(x),$ and the axiom of pairing was used in the definition of the subset $P\_1.$
Reception of the argument

Initially, Cantor's theory was controversial among mathematicians and (later) philosophers. AsLeopold Kronecker
Leopold Kronecker (; 7 December 1823 – 29 December 1891) was a German mathematician who worked on number theory, algebra and logic. He criticized Georg Cantor's work on set theory, and was quoted by as having said, "'" ("God made the integers, ...

claimed: "I don't know what predominates in Cantor's theory – philosophy or theology, but I am sure that there is no mathematics there." Many mathematicians agreed with Kronecker that the completed infinite may be part of philosophy
Philosophy (from , ) is the systematized study of general and fundamental questions, such as those about existence, reason, knowledge, values, mind, and language. Such questions are often posed as problems to be studied or resolved. Some ...

or theology
Theology is the systematic study of the nature of the divine and, more broadly, of religious belief. It is taught as an academic discipline, typically in universities and seminaries. It occupies itself with the unique content of analyzing the ...

, but that it has no proper place in mathematics. Logician has commented on the energy devoted to refuting this "harmless little argument" (i.e. Cantor's diagonal argument
In set theory, Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument, the anti-diagonal argument, the diagonal method, and Cantor's diagonalization proof, was published in 1891 by Georg Cantor as a m ...

) asking, "what had it done to anyone to make them angry with it?" Mathematician Solomon Feferman
Solomon Feferman (December 13, 1928 – July 26, 2016) was an American philosopher and mathematician who worked in mathematical logic.
Life
Solomon Feferman was born in The Bronx in New York City to working-class parents who had immigrated to th ...

has referred to Cantor's theories as “simply not relevant to everyday mathematics.”
Before Cantor, the notion of infinity was often taken as a useful abstraction which helped mathematicians reason about the finite world; for example the use of infinite limit cases in calculus
Calculus, originally called infinitesimal calculus or "the calculus of infinitesimals", is the mathematical study of continuous change, in the same way that geometry is the study of shape, and algebra is the study of generalizations of arithm ...

. The infinite was deemed to have at most a potential existence, rather than an actual existence. "Actual infinity does not exist. What we call infinite is only the endless possibility of creating new objects no matter how many exist already". Carl Friedrich Gauss
Johann Carl Friedrich Gauss (; german: Gauß ; la, Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields in mathematics and science. Sometimes refer ...

's views on the subject can be paraphrased as: "Infinity is nothing more than a figure of speech which helps us talk about limits. The notion of a completed infinity doesn't belong in mathematics." In other words, the only access we have to the infinite is through the notion of limits, and hence, we must not treat infinite sets as if they have an existence exactly comparable to the existence of finite sets.
Cantor's ideas ultimately were largely accepted, strongly supported by David Hilbert
David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician, one of the most influential mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many a ...

, amongst others. Hilbert predicted: "No one will drive us from the paradise which Cantor created for us." To which Wittgenstein
Ludwig Josef Johann Wittgenstein ( ; ; 26 April 1889 – 29 April 1951) was an Austrians, Austrian-British people, British philosopher who worked primarily in logic, the philosophy of mathematics, the philosophy of mind, and the philosophy o ...

replied "if one person can see it as a paradise of mathematicians, why should not another see it as a joke?" The rejection of Cantor's infinitary ideas influenced the development of schools of mathematics such as constructivism
Constructivism may refer to:
Art and architecture
* Constructivism (art), an early 20th-century artistic movement that extols art as a practice for social purposes
* Constructivist architecture, an architectural movement in Russia in the 1920s a ...

and intuitionism
In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of fu ...

.
Wittgenstein did not object to mathematical formalism wholesale, but had a finitist view on what Cantor's proof meant. The philosopher maintained that belief in infinities arises from confusing the intensional nature of mathematical laws with the extensional nature of sets, sequences, symbols etc. A series of symbols is finite in his view: In Wittgenstein's words: "...A curve is not composed of points, it is a law that points
obey, or again, a law according to which points can be constructed."
He also described the diagonal argument as "hocus pocus" and not proving what it purports to do.
Objection to the axiom of infinity

A common objection to Cantor's theory of infinite number involves theaxiom of infinity
In axiomatic set theory and the branches of mathematics and philosophy that use it, the axiom of infinity is one of the axioms of Zermelo–Fraenkel set theory. It guarantees the existence of at least one infinite set, namely a set containing the ...

(which is, indeed, an axiom and not a logical truth
Logical truth is one of the most fundamental concepts in logic. Broadly speaking, a logical truth is a statement which is true regardless of the truth or falsity of its constituent propositions. In other words, a logical truth is a statement whic ...

). Mayberry has noted that "... the set-theoretical axioms that sustain modern mathematics are self-evident in differing degrees. One of them—indeed, the most important of them, namely Cantor's Axiom, the so-called Axiom of Infinity—has scarcely any claim to self-evidence at all …"Mayberry 2000, p. 10.
Another objection is that the use of infinite sets is not adequately justified by analogy to finite sets. Hermann Weyl
Hermann Klaus Hugo Weyl, (; 9 November 1885 – 8 December 1955) was a German mathematician, theoretical physicist and philosopher. Although much of his working life was spent in Zürich, Switzerland, and then Princeton, New Jersey, he is assoc ...

wrote:
The difficulty with finitism is to develop foundations of mathematics using finitist assumptions, that incorporates what everyone would reasonably regard as mathematics (for example, that includes real analysis
In mathematics, the branch of real analysis studies the behavior of real numbers, sequences and series of real numbers, and real functions. Some particular properties of real-valued sequences and functions that real analysis studies include converg ...

).
See also

*Preintuitionism In the philosophy of mathematics, the pre-intuitionists were a small but influential group who informally shared similar philosophies on the nature of mathematics. The term itself was used by L. E. J. Brouwer, who in his 1951 lectures at Cambridge d ...

Notes

References

* * * * * * * * * * * : "''Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können.''" : Translated in * * * * (address to the Fourth International Congress of Mathematicians) * * * * *External links

Doron Zeilberger's 68th Opinion

Philosopher Hartley Slater's argument against the idea of "number" that underpins Cantor's set theory

Wolfgang Mueckenheim: Transfinity - A Source Book

Hodges "An editor recalls some hopeless papers"

{{Infinity Discovery and invention controversies History of mathematics Philosophy of mathematics Set theory Georg Cantor