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 concer ...

, Cantor's paradox states that there is no set of all

cardinalities 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 ...

. This is derived from the

theorem In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of t ...

that there is no greatest

cardinal number In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. The ...

. In informal terms, the paradox is that the collection of all possible "infinite sizes" is not only infinite, but so infinitely large that its own infinite size cannot be any of the infinite sizes in the collection. The difficulty is handled in

axiomatic 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 ...

by declaring that this collection is not a set but a

proper class Proper may refer to: Mathematics * Proper map, in topology, a property of continuous function between topological spaces, if inverse images of compact subsets are compact * Proper morphism, in algebraic geometry, an analogue of a proper map for ...

; in

von Neumann–Bernays–Gödel set theory In the foundations of mathematics, von Neumann–Bernays–Gödel set theory (NBG) is an axiomatic set theory that is a conservative extension of Zermelo–Fraenkel–choice set theory (ZFC). NBG introduces the notion of class, which is a colle ...

it follows from this and the

axiom of limitation of size In set theory, the axiom of limitation of size was proposed by John von Neumann in his 1925 axiom system for sets and classes.; English translation: . It formalizes the limitation of size principle, which avoids the paradoxes encountered in ea ...

that this proper class must be in

bijection 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 ...

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 A paradox is a logically self-contradictory statement or a statement that runs contrary to one's expectation. It is a statement that, despite apparently valid reasoning from true premises, leads to a seemingly self-contradictory or a logically u ...

is named for

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 ...

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

Statements and proofs

In order to state the paradox it is necessary to understand that the cardinal numbers are

totally 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 ( reflexiv ...

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

on the cardinality of the

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 post ...

of a set. Another consequence of

is that the cardinal numbers constitute a

. That is, they cannot all be collected together as elements of a single set. Here is a somewhat more general result.

Discussion and consequences

Since the cardinal numbers are well-ordered by indexing with the

ordinal numbers 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 least ...

(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 paradox In set theory, a field of mathematics, the Burali-Forti paradox demonstrates that constructing "the set of all ordinal numbers" leads to a contradiction and therefore shows an antinomy in a system that allows its construction. It is named after C ...

we obtain another proof that the cardinal numbers are a

rather than a set, and (at least in ZFC or in

) 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 notes

While Cantor is usually credited with first identifying this property of cardinal sets, some mathematicians award this distinction to

Bertrand Russell Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, ...

, who defined a similar theorem in 1899 or 1901.

References

* *

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.

article. {{Set theory Cardinal numbers

Paradox A paradox is a logically self-contradictory statement or a statement that runs contrary to one's expectation. It is a statement that, despite apparently valid reasoning from true premises, leads to a seemingly self-contradictory or a logically u ...

Mathematical logic Paradoxes of naive set theory