- Cantor's paradox
set theory, Cantor's paradox is the theoremthat there is no greatest cardinal number, so that the collection of "infinite sizes" is itself infinite. Furthermore, it follows from this fact that this collection is not a set but a proper class; in von Neumann–Bernays–Gödel set theoryit follows from this and the axiom of limitation of sizethat 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 many mathematical "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 theoryand therefore demonstrates that a careless axiomatization of this theory is inconsistent.
Statement and proof
In order to state the paradox it is necessary to understand that the cardinal numbers admit an ordering, 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 theoremon the cardinality of the power setof 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.
However, see A. Garciadiego, Bertrand Russell and the Origins of The Set-Theoretic 'Paradoxes,' for a discussion of the idea that this is not a paradox, and that Cantor did not consider it a paradox.
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 paradoxwe also conclude that the cardinal numbers are a proper classrather than a set, and (at least in ZFCor 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".
While Cantor is usually credited with first identifying this property of cardinal sets, some mathematicians award this distinction to
Bertrand Russell, who defined a similar theorem in 1899 or 1901.
* cite book
title="The first Russell paradox," Perspectives on the History of Mathematical Logic
* cite journal
author=Moore, G.H. and Garciadiego, A.
title=Burali-Forti's paradox: a reappraisal of its origins
* [http://citeseer.ist.psu.edu/496807.html An Historical Account of Set-Theoretic Antinomies Caused by the Axiom of Abstraction] : report by Justin T. Miller, Department of Mathematics, University of Arizona.
* [http://planetmath.org/encyclopedia/CantorsParadox.html PlanetMath.org] : article.
Wikimedia Foundation. 2010.
Look at other dictionaries:
Cantor's paradox — The contradiction arising if we compare for size the set of all sets, and its own power set . By Cantor s theorem the power set must be bigger (contain more members). But it is itself a subset of the set of all sets, and so cannot be bigger. The… … Philosophy dictionary
Cantor's diagonal argument — An illustration of Cantor s diagonal argument for the existence of uncountable sets. The sequence at the bottom cannot occur anywhere in the list of sequences above. Cantor s diagonal argument, also called the diagonalisation argument, the… … Wikipedia
Paradox — For other uses, see Paradox (disambiguation). Further information: List of paradoxes A paradox is a seemingly true statement or group of statements that lead to a contradiction or a situation which seems to defy logic or intuition. Typically,… … Wikipedia
Georg Cantor — Infobox Scientist name = Georg Ferdinand Ludwig Cantor image width=225px caption = birth date = birth date|1845|3|3 birth place = Saint Petersburg, Russia death date = death date and age|1918|1|6|1845|3|3 death place = Halle, Germany residence =… … Wikipedia
Skolem's paradox — is the mathematical fact that every countable axiomatisation of set theory in first order logic, if consistent, has a model that is countable, even if it is possible to prove, from those same axioms, the existence of sets that are not countable.… … Wikipedia
Russell's paradox — Part of the foundations of mathematics, Russell s paradox (also known as Russell s antinomy), discovered by Bertrand Russell in 1901, showed that the naive set theory of Frege leads to a contradiction.It might be assumed that, for any formal… … Wikipedia
Hilbert's paradox of the Grand Hotel — is a mathematical paradox about infinite sets presented by German mathematician David Hilbert (1862–1943). The Paradox of the Grand Hotel Consider a hypothetical hotel with infinitely many rooms, all of which are occupied that is to say every… … Wikipedia
Banach–Tarski paradox — The Banach–Tarski paradox is a theorem in set theoretic geometry which states that a solid ball in 3 dimensional space can be split into several non overlapping pieces, which can then be put back together in a different way to yield two identical … Wikipedia
Olbers' paradox — in action In astrophysics and physical cosmology, Olbers paradox is the argument that the darkness of the night sky conflicts with the assumption of an infinite and eternal static universe. It is one of the pieces of evidence for a non static… … Wikipedia
Barber paradox — This article is about a paradox of self reference. For an unrelated paradox in the theory of logical conditionals with a similar name, introduced by Lewis Carroll, see the Barbershop paradox. The Barber paradox is a puzzle derived from Russell s… … Wikipedia