Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Cantor's theorem
Summary
In mathematical set theory, Cantor's theorem is a fundamental result which states that, for any set , the set of all subsets of the power set of has a strictly greater cardinality than itself.
For finite sets, Cantor's theorem can be seen to be true by simple enumeration of the number of subsets. Counting the empty set as a subset, a set with elements has a total of subsets, and the theorem holds because for all non-negative integers.
Much more significant is Cantor's discovery of an argument that is applicable to any set, and shows that the theorem holds for infinite sets also. As a consequence, the cardinality of the real numbers, which is the same as that of the power set of the integers, is strictly larger than the cardinality of the integers; see Cardinality of the continuum for details.
The theorem is named for German mathematician Georg Cantor, who first stated and proved it at the end of the 19th century. Cantor's theorem had immediate and important consequences for the philosophy of mathematics. For instance, by iteratively taking the power set of an infinite set and applying Cantor's theorem, we obtain an endless hierarchy of infinite cardinals, each strictly larger than the one before it. Consequently, the theorem implies that there is no largest cardinal number (colloquially, "there's no largest infinity").
Cantor's argument is elegant and remarkably simple. The complete proof is presented below, with detailed explanations to follow.
Consider the set . Suppose to the contrary that is surjective. Then there exists such that . But by construction, . This is a contradiction. Thus, cannot be surjective. On the other hand, defined by is an injective map. Consequently, we must have . Q.E.D.
By definition of cardinality, we have for any two sets and if and only if there is an injective function but no bijective function from to . It suffices to show that there is no surjection from to . This is the heart of Cantor's theorem: there is no surjective function from any set to its power set.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.