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

, Cantor's paradox states that there is no

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 cardinalities. This is derived from the

theorem In mathematics and formal logic, a theorem is a statement (logic), statement that has been Mathematical proof, proven, or can be proven. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to esta ...

that there is no greatest

cardinal number In mathematics, a cardinal number, or cardinal for short, is what is commonly called the number of elements of a set. In the case of a finite set, its cardinal number, or cardinality is therefore a natural number. For dealing with the cas ...

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

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

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

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

that this proper class must be in

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

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 or apparently true premises, leads to a seemingly self-contradictor ...

is named for

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

, 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 order 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 ( r ...

, 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 (mathematics), set A, the set of all subsets of A, known as the power set of A, has a strictly greater cardinality than A itself. For finite s ...

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

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

(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 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 philosopher, logician, mathematician, and public intellectual. He had influence on mathematics, logic, set theory, and various areas of analytic ...

, 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 or apparently true premises, leads to a seemingly self-contradictor ...

Mathematical logic Paradoxes of naive set theory