Cantor's paradox
Encyclopedia
In set theory
, Cantor's paradox is derivable from the theorem
that there is no greatest cardinal number
, so that the collection of "infinite sizes" is itself infinite. The difficulty is handled in axiomatic set theory by declaring that this collection is not a set but a proper class; in von Neumann–Bernays–Gödel set theory
it follows from this and the axiom of limitation of size
that this proper class must be in bijection with the class of all sets. Thus, not only are there infinitely many infinities, but this infinity is larger than any of the infinities it enumerates.
This paradox is named for Georg Cantor
, who is often credited with first identifying it in 1899 (or between 1895 and 1897). Like a number of "paradoxes" it is not actually contradictory but merely indicative of a mistaken intuition, in this case about the nature of infinity and the notion of a set. Put another way, it is paradoxical within the confines of naïve set theory
and therefore demonstrates that a careless axiomatization of this theory is inconsistent.
, so that one can speak about one being greater or less than another. Then Cantor's paradox is:
This fact is a direct consequence of Cantor's theorem
on the cardinality of the power set of a set.
Another consequence of Cantor's theorem
is that the cardinal numbers constitute a proper class. That is, they cannot all be collected together as elements of a single set. Here is a somewhat more general result.
we obtain another proof that the cardinal numbers are a proper class rather than a set, and (at least in ZFC or in von Neumann–Bernays–Gödel set theory
) it follows from this that there is a bijection between the class of cardinals and the class of all sets. Since every set is a subset of this latter class, and every cardinality is the cardinality of a set (by definition!) this intuitively means that the "cardinality" of the collection of cardinals is greater than the cardinality of any set: it is more infinite than any true infinity. This is the paradoxical nature of Cantor's "paradox".
, who defined a similar theorem in 1899 or 1901.
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, Cantor's paradox is derivable from the theorem
Theorem
In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements, such as axioms...
that there is no greatest cardinal number
Cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
, so that the collection of "infinite sizes" is itself infinite. The difficulty is handled in axiomatic set theory by declaring that this collection is not a set but a proper class; in von Neumann–Bernays–Gödel set theory
Von Neumann–Bernays–Gödel set theory
In the foundations of mathematics, von Neumann–Bernays–Gödel set theory is an axiomatic set theory that is a conservative extension of the canonical axiomatic set theory ZFC. A statement in the language of ZFC is provable in NBG if and only if it is provable in ZFC. The ontology of NBG includes...
it follows from this and the axiom of limitation of size
Axiom of limitation of size
In class theories, the axiom of limitation of size says that for any class C, C is a proper class, that is a class which is not a set , if and only if it can be mapped onto the class V of all sets....
that this proper class must be in bijection with the class of all sets. Thus, not only are there infinitely many infinities, but this infinity is larger than any of the infinities it enumerates.
This paradox is named for Georg Cantor
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...
, who is often credited with first identifying it in 1899 (or between 1895 and 1897). Like a number of "paradoxes" it is not actually contradictory but merely indicative of a mistaken intuition, in this case about the nature of infinity and the notion of a set. Put another way, it is paradoxical within the confines of naïve set theory
Naive set theory
Naive set theory is one of several theories of sets used in the discussion of the foundations of mathematics. The informal content of this naive set theory supports both the aspects of mathematical sets familiar in discrete mathematics , and the everyday usage of set theory concepts in most...
and therefore demonstrates that a careless axiomatization of this theory is inconsistent.
Statements and proofs
In order to state the paradox it is necessary to understand that the cardinal numbers admit an orderingOrdered set
In order theory in mathematics, a set with a binary relation R on its elements that is reflexive , antisymmetric and transitive is described as a partially ordered set or poset...
, so that one can speak about one being greater or less than another. Then Cantor's paradox is:
- Theorem: There is no greatest cardinal number.
This fact is a direct consequence of Cantor's theorem
Cantor's theorem
In elementary set theory, Cantor's theorem states that, for any set A, the set of all subsets of A has a strictly greater cardinality than A itself...
on the cardinality of the power set of a set.
- Proof: Assume the contrary, and let C be the largest cardinal number. Then (in the von Neumann formulation of cardinality) C is a set and therefore has a power set 2C which, by Cantor's theorem, has cardinality strictly larger than that of C. But the cardinality of C is C itself, by definition, and therefore we have exhibited a cardinality (namely that of 2C) larger than C, which was assumed to be the greatest cardinal number. This contradiction establishes that such a cardinal cannot exist.
Another consequence of Cantor's theorem
Cantor's theorem
In elementary set theory, Cantor's theorem states that, for any set A, the set of all subsets of A has a strictly greater cardinality than A itself...
is that the cardinal numbers constitute a proper class. That is, they cannot all be collected together as elements of a single set. Here is a somewhat more general result.
- Theorem: If S is any set then S cannot contain elements of all cardinalities. In fact, there is a strict upper bound on the cardinalities of the elements of S.
- Proof: Let S be a set, and let T be the union of the elements of S. Then every element of S is a subset of T, and hence is of cardinality less than or equal to the cardinality of T. Cantor's theoremCantor's theoremIn elementary set theory, Cantor's theorem states that, for any set A, the set of all subsets of A has a strictly greater cardinality than A itself...
then implies that every element of S is of cardinality strictly less than the cardinality of 2T.
Discussion and consequences
Since the cardinal numbers are well-ordered by indexing with the ordinal numbers (see Cardinal number, formal definition), this also establishes that there is no greatest ordinal number; conversely, the latter statement implies Cantor's paradox. By applying this indexing to the Burali-Forti paradoxBurali-Forti paradox
In set theory, a field of mathematics, the Burali-Forti paradox demonstrates that naively constructing "the set of all ordinal numbers" leads to a contradiction and therefore shows an antinomy in a system that allows its construction...
we obtain another proof that the cardinal numbers are a proper class rather than a set, and (at least in ZFC or in von Neumann–Bernays–Gödel set theory
Von Neumann–Bernays–Gödel set theory
In the foundations of mathematics, von Neumann–Bernays–Gödel set theory is an axiomatic set theory that is a conservative extension of the canonical axiomatic set theory ZFC. A statement in the language of ZFC is provable in NBG if and only if it is provable in ZFC. The ontology of NBG includes...
) it follows from this that there is a bijection between the class of cardinals and the class of all sets. Since every set is a subset of this latter class, and every cardinality is the cardinality of a set (by definition!) this intuitively means that the "cardinality" of the collection of cardinals is greater than the cardinality of any set: it is more infinite than any true infinity. This is the paradoxical nature of Cantor's "paradox".
Historical note
While Cantor is usually credited with first identifying this property of cardinal sets, some mathematicians award this distinction to Bertrand RussellBertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
, who defined a similar theorem in 1899 or 1901.
External links
- An Historical Account of Set-Theoretic Antinomies Caused by the Axiom of Abstraction: report by Justin T. Miller, Department of Mathematics, University of Arizona.
- PlanetMath.org: article.