Cantor’s Theorem
For any set \(X\), the power set of \(X\) (i.e., the set of subsets of \(X\)), is larger (has a greater cardinality) than \(X\).
Cantor’s Theorem tells us that no matter how large a set we have, we may consider a set that is still larger. This is trivial if the set in question has finitely many members, but not at all obvious if our set is infinite.
The word larger in this usage has a precise meaning. In set theory two sets are considered to be the same ‘size’ if we can form a one-to-one match-up between the elements of the two sets with none left over on either side. (This is called a bijection in mathematics.) If the sets are finite, this means they have the same number of elements. However, if the sets are infinite then it isn’t quite clear how the ordinary concept of ‘number of elements’ should apply, and so we need this notion of one-to-one match-up to make it perfectly clear.
For example, if you have more pennies than dimes and you attempt to form a one-to-one matchup between them, you will find that you always have a penny left over:
Cantor realized that the same principle can be applied to infinite sets, and discovered that no matter what set you start with, any attempt to form a one-to-one match-up of the elements of the set to the subsets of the set must leave some subset unmatched.
The proof uses a technique that Cantor originated called diagonalization, which is a form of proof by contradiction. We begin by assuming that for some set we can form a one-to-one match-up between the elements and the subsets that leaves none out on either side. Let's call the set \(X\), and we'll denote the power set by \(\mathcal{P}(X)\):
\[X=\{a,b,c,d,e,f,\ldots\}\] and \[\begin{eqnarray*}\mathcal{P}(X) & = & \{\,\{a\},\{b\},\{a,b\},\{c\},\{a,c\}, \\ & & \,\,\,\,\{b,c\},\{a,b,c\},\{d\},\{a,d\}\ldots\} \end{eqnarray*}\]
Now the one-to-one matchup (that we are assuming exists) between the elements and the power sets might look something like this:
\[X \,\, \left\{ \,\, \begin{array}{rcl} a & \longrightarrow & \{c,d\} \\ b & \longrightarrow & \{a\} \\ c & \longrightarrow & \{a,b,c,d\} \\ d & \longrightarrow & \{b,e\} \\ e & \longrightarrow & \{a,c,e\} \\ \vdots & & \,\,\,\,\,\,\vdots \end{array} \,\, \right\} \,\, \mathcal{P}X \]
Notice that some of the elements of \(X\) are matched to subsets that contain them. For example, in the hypothetical match-up pictured above the element \(e\) is matched to the subset \(\{a,c,e\}\). Other elements might match to subsets that do not contain them. For example, above the element \(a\) is matched with the subset \(\{c,d\}\). For any given match-up we may define the subset of \(X\) consisting of just those elements that are matched to subsets that do not contain them. By the assumption that our match-up exists this is a well-defined subset. Call it \(F\).
This \(F\), being a subset of \(X\), has to appear somewhere in the match-up, with some element being matched to it. But what element could it be? Whatever element it is, it can't be an element of \(F\) since \(F\) is specifically defined as containing just those elements that don't match to subsets that contain them. On the other hand, if it isn't an element of \(F\)—why then it must be, since it would then match to a subset that doesn’t contain it, forcing it to be a member of \(F\) by definition.
The only possible conclusion is that no element can be matched to \(F\), which means that our one-to-one match-up can't be complete after all. QED
You might need to read that again. Then take a minute to ponder what it means. Cantor’s Theorem proves that given any set, even an infinite one, the set of its subsets is ‘bigger’ in a very precise sense. But this means there can be no largest infinity either. The kinds of infinity are (ahem) infinite….
