Cantor's theorem

• 1. Introduction

  ›

  Cantor's theorem sits at the heart of mathematical set theory, and it carries a conclusion that stops most people cold: there is no largest infinity. Georg Cantor first stated and proved this result at the end of the 19th century, and the mathematical world has never quite looked the same since. The theorem says that for any set, the collection of all its subsets, called the power set, is strictly larger than the set itself. That sounds reasonable for small collections of objects. But the theorem holds for infinite sets too, and that is where things get strange. How can one infinite collection be provably larger than another? And what does it mean for mathematics when a single proof implies that infinities come in an endless, climbing hierarchy with no ceiling? Those are the questions this documentary sets out to answer.

• 2. A Deceptively Simple Proof

  ›

  Cantor's argument is elegant and remarkably simple, as the source text itself notes. The proof does not rely on heavy machinery. It rests on one clean idea: suppose you had a function that tried to pair every element of a set with a distinct subset of that set. Cantor shows such a function can never cover all subsets, no matter how cleverly it is built. The key construction is what is sometimes called the Cantor diagonal set. You look at every element in the original set and ask whether it appears inside the subset it was paired with. The diagonal set collects exactly those elements that do not appear inside their paired subset. That set is always left out of the pairing. No element can be assigned to map to it without producing a direct contradiction. If some element is in the diagonal set, then by definition it should not map to it. If it is not in the diagonal set, then by definition it should. Either way, a contradiction follows. The proof concludes by also demonstrating an injective function going the other direction, mapping each element to the singleton set containing only itself. That establishes the strict inequality: the power set is always larger.

• 3. Infinite Cardinals and the Hierarchy

  ›

  For finite sets, the result is easy to check. A set with a given number of elements has a power set whose size is two raised to that number of elements, and two to the power of any non-negative integer is always greater than the integer itself. The striking step is that the theorem carries over to infinite sets without modification. One immediate consequence concerns the real numbers. The cardinality of the real numbers equals the cardinality of the power set of the integers, and Cantor's theorem guarantees that this is strictly larger than the cardinality of the integers themselves. That gap between the integers and the reals is only the beginning. By repeatedly taking the power set of an infinite set and applying the theorem again each time, you generate an endless hierarchy of infinite cardinals, each strictly larger than the one before. The theorem thus implies that there is no largest cardinal number, which the source describes colloquially as meaning there is no largest infinity.

• 4. Selfish and Non-Selfish Numbers

  ›

  The proof becomes vivid when you focus on the natural numbers specifically. Suppose you tried to pair every natural number with a unique subset of the natural numbers, aiming to use every subset exactly once. Some natural numbers end up paired with subsets that contain the very same number. The number 2, for instance, might be paired with the subset containing 1, 2, and 3, which includes 2 itself. Those are what the source calls selfish numbers. Other natural numbers get paired with subsets that do not include them. The number 1, in one sample pairing, is matched with the subset containing 4 and 5, which leaves 1 out. Those are non-selfish numbers, and so are 3 and 4 in that same example. Now build a new set from all the non-selfish natural numbers. That set must appear somewhere in the power set, since the power set contains every set of natural numbers. If the original pairing is truly complete, this new set must be matched with some natural number. But any candidate for that match runs into the same contradiction the diagonal argument always produces. It is worth noting too that the set of non-selfish numbers might be empty, in which case every natural number maps to a subset containing itself and no number maps to the empty set. But the empty set belongs to the power set regardless, so the pairing still falls short.

• 5. Paradoxes at the Edge

  ›

  Cantor's theorem brushes against two of the most famous paradoxes in the history of set theory. The first is Cantor's paradox, which arises if you assume there is a universal set containing every set that exists. The theorem would then require that set's power set to be strictly larger than it. But the power set only contains sets, all of which are already elements of the supposed universal set, so the universal set would also have to be at least as large as its own power set. Those two conclusions cannot both be true. The second paradox emerges when you substitute the identity function into the proof of Cantor's theorem. The resulting object is called the Russell set. Ernst Zermelo showed that the assumption of a set containing all sets, combined with the Russell set construction, leads to a direct contradiction. That version of Russell's paradox is technically a theorem of Zermelo's, not an independent discovery. The version using unrestricted comprehension, as in Gottlob Frege's system, requires no additional hypothesis at all to reach the contradiction: the axiom system itself yields it. Alonzo Church took care to emphasize that Russell's paradox, for all its surface similarity to the diagonal argument, does not actually depend on cardinality or one-to-one correspondence.

• 6. History and Legacy

  ›

  Cantor published the proof in 1891, in a paper titled "Uber eine elementare Frage der Mannigfaltigkeitslehre." That same paper is where his diagonal argument for the uncountability of the reals first appeared in print; he had established the uncountability of the reals earlier by different methods. In that 1891 paper, Cantor framed the argument not in terms of subsets directly but in terms of indicator functions, showing that if a function maps elements of a set to two-valued functions on that set, a specific two-valued function always falls outside the range. Bertrand Russell offered a closely related proof in Principles of Mathematics, published in 1903, in section 348, where he showed that propositional functions outnumber objects by a similar diagonal move. Russell credited the idea to Cantor. Ernst Zermelo then included an identical result, calling it Cantor's Theorem, in the 1908 paper that became the foundation of modern set theory. In 1992, Lawrence Paulson noted that the automated theorem prover Otter could not independently rediscover Cantor's diagonal set construction, while the prover Isabelle could manage it, though only with enough directional guidance that it might be considered cheating. William Lawvere later placed the theorem inside a far broader context: his fixed-point theorem generalizes the core idea to any category with finite products, revealing that the impossibility of a surjection onto a power set is a special case of a much deeper pattern.