HOME

TheInfoList




In
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, i ...
, Cantor's paradox states that there is no set of all
cardinalities In mathematics, the cardinality of a set (mathematics), set is a measure of the "number of Element (mathematics), elements" of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 1 ...
. This is derived from the
theorem In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
that there is no greatest
cardinal number 150px, Aleph null, the smallest infinite cardinal In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and ca ...
. 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 mathematics, i ...
by declaring that this collection is not a set but a
proper class Proper may refer to: Mathematics * Proper map In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and qu ...
; in
von Neumann–Bernays–Gödel set theory In the foundations of mathematics Foundations of mathematics is the study of the philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philosophical theorie ...
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 Set (mathematics), sets and Class (set theory), classes.; English translation: . It formalizes the limitation of size principle, which avoi ...
that this proper class must be in
bijection In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

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

paradox
is named for
Georg Cantor Georg Ferdinand Ludwig Philipp Cantor ( , ;  – January 6, 1918) was a German mathematician. He created set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence be ...
, 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 admit an
ordering Order or ORDER or Orders may refer to: * Orderliness, a desire for organization * Categorization, the process in which ideas and objects are recognized, differentiated, and understood * Heterarchy, a system of organization wherein the elements hav ...
, 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 In elementary set theory illustrating the intersection (set theory), intersection of two set (mathematics), sets. Set theory is a branch of mathematical logic that studies Set (mathematics), sets, which informally are collections of objects. ...
on the cardinality of the
power set In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities an ...
of a set. :Proof: Assume the contrary, and let ''C'' be the largest cardinal number. Then (in the
von Neumann Von Neumann may refer to: * John von Neumann (1903–1957), a Hungarian American mathematician * Von Neumann family * Von Neumann (surname), a German surname * Von Neumann (crater), a lunar impact crater See also

* Von Neumann algebra * Von Ne ...

von Neumann
formulation of cardinality) ''C'' is a set and therefore has a power set 2''C'' which, by Cantor's theorem, has cardinality strictly larger than ''C''. Demonstrating a cardinality (namely that of 2''C'') larger than ''C'', which was assumed to be the greatest cardinal number, falsifies the definition of C. This contradiction establishes that such a cardinal cannot exist. Another consequence of
Cantor's theorem In elementary set theory illustrating the intersection (set theory), intersection of two set (mathematics), sets. Set theory is a branch of mathematical logic that studies Set (mathematics), sets, which informally are collections of objects. ...
is that the cardinal numbers constitute a
proper class Proper may refer to: Mathematics * Proper map In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and qu ...
. 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 theorem In elementary set theory illustrating the intersection (set theory), intersection of two set (mathematics), sets. Set theory is a branch of mathematical logic that studies Set (mathematics), sets, which informally are collections of objects. ...
then implies that every element of ''S'' is of cardinality strictly less than the cardinality of 2''T''.


Discussion and consequences

Since the cardinal numbers are well-ordered by indexing with the
ordinal numbers In set theory Set theory is the branch of that studies , 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 , is mostly concerned with those that ...
(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 illustrating the intersection (set theory), intersection of two set (mathematics), sets. Set theory is a branch of mathematical logic that studies Set (mathematics), sets, which informally are collections of objects. Although any ty ...
we obtain another proof that the cardinal numbers are a
proper class Proper may refer to: Mathematics * Proper map In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and qu ...
rather than a set, and (at least in
ZFC
ZFC
or in
von Neumann–Bernays–Gödel set theory In the foundations of mathematics Foundations of mathematics is the study of the philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philosophical theorie ...
) 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 polymath A polymath ( el, πολυμαθής, , "having learned much"; la, homo universalis, "universal human") is an individual whose know ...
, who defined a similar theorem in 1899 or 1901.


References

* * {{cite journal , author1=Moore, G.H. , author2=Garciadiego, A. , title=Burali-Forti's paradox: a reappraisal of its origins , journal=Historia Math , volume=8 , pages=319–350 , doi=10.1016/0315-0860(81)90070-7 , year=1981 , issue=3, doi-access=free


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. Paradoxes of naive 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 ...