What does Cantor's theorem state?
Cantor's theorem states that for any set, the power set, meaning the set of all its subsets, has a strictly greater cardinality than the set itself. This holds for both finite and infinite sets.
Questions about Cantor's theorem
Short answers, pulled from the story.
Who proved Cantor's theorem and when was it published?
Georg Cantor proved the theorem and published it in 1891 in a paper titled "Uber eine elementare Frage der Mannigfaltigkeitslehre." The same paper also contains the diagonal argument for the uncountability of the real numbers.
What is the Cantor diagonal set and how is it used in the proof?
The Cantor diagonal set collects all elements of a set that are not members of the subset they are paired with under a given function. Any function from a set to its power set must leave this diagonal set uncovered, which proves no such function can be surjective.
What does Cantor's theorem imply about the sizes of infinite sets?
Cantor's theorem implies that infinite sets come in an endless hierarchy of sizes. By repeatedly taking the power set of an infinite set, you generate infinitely many distinct infinite cardinalities, each strictly larger than the previous. There is no largest cardinal number.
How is Cantor's theorem related to Russell's paradox?
Substituting the identity function into the proof of Cantor's theorem produces the Russell set. Ernst Zermelo showed that assuming a universal set exists leads to a contradiction via this construction, a result known as Russell's paradox. Alonzo Church noted that Russell's paradox is independent of cardinality, despite the surface similarity to the diagonal argument.
How did automated theorem provers fare with Cantor's theorem?
Lawrence Paulson noted in 1992 that the theorem prover Otter could not independently discover the Cantor diagonal set construction, while Isabelle could, but only with enough directional guidance that it might be considered a form of cheating.