Cantor's theorem

In set theory, Cantor's theorem states that the set which contains all subsets of a set has a greater cardinality (a formal definition of "size") than the set itself. Georg Cantor showed this in an article he published in 1890. The theorem is valid both for finite and infinite sets.

Proof

Definitions

We will refer to our starting set as $U$ (short for "universe"), and the set of its subsets as $P(U)$ (another name for "set of all subsets of $U$" is "the power set of $U$").

In set theory, the informal idea of "size" is more formally defined as the cardinality of a set. Two sets have the same cardinality if and only if there is a bijection between the two sets: that is, a relation that connects one element of one set to one element of the other set, with all elements used exactly once (nothing is repeated or left out).

Cantor's theorem is a proof by contradiction: it assumes the existence of a bijection $f:U\to P(U)$, and then shows that this gives us an impossible result.

Argument

The proof of Cantor's theorem is similar to Cantor's diagonal argument.

First, we assume the two sets have the same cardinality, which means there must be a function $f:U\to P(U)$ and its inverse $f^{-1}:P(U)\to U$.

Since this function sends every element $x\in U$ to a subset $f(x)\subset U$, we can use it to define a unary relation based on a simple property: "Does the set $f(x)$ contain the value $x$?"

More formally, we want to look at all the values $x$ where this property does not hold,

$S=\{x\in U:x\not \in f(x)\}$

This can be read as "the set of all elements of $U$ whose corresponding set in $P(U)$ does not contain that element". This statement is similar to Russell's paradox, which arises from "sets that do not contain themselves" in naive set theory.

Now, we must consider our set $S$. Since $S$ contains only elements of $U$, then by definition $S\subset U$ and $S\in P(U)$. This means that there must exist some $s=f^{-1}(S)\in U$.

This gives rise to a contradiction:

• If $s\in S$, then $s\in f(s)$, which contradicts the definition of $S$.
• If $s\not \in S$, then $s\not \in f(s)$, so by definition $s\in S$ - an explicit contradiction.

From the contradiction, it follows that our premise must be flawed. Thus, no bijection exists between the set $S$ and the set of its subsets $P(S)$, so they must have different cardinality.