A short proof of Cantor's theorem

31 Oct 2018 • Theory

Cantor’s theorem states that for any set \(S\) we have \(S \preceq \mathcal{P}(S)\) and \(S \nsim \mathcal{P}(S)\). In words this means that the cardinality of \(\mathcal{P}(S)\) is strictly bigger than the cardinality of \(S\).

Unlike some of my other posts, this one is strictly mathematical.

First we will have a look at the definitions and then we will prove Cantor’s theorem:

Two sets \(A\), \(B\) are equinumerous, denoted \(A \sim B\) if there exists a bijection \(A \to B\)

A set \(B\) dominates a set \(A\), denoted \(A\preceq B\), if \(A\sim C\) for some \(C \subseteq B\).

The second definition is equivalent to the existence of an injective funtion \(A \to B\), namely the bijection \(A \to C\).

Let \(S\) be any set. The power set of \(S\), denoted by \(\mathcal{P}(S)\), has a strictly greater cardinality than \(S\) itself.

The proof is split into two parts. First we will show \(S \preceq \mathcal{P}(S)\) and then in a second step we will show \(S \nsim \mathcal{P}(S)\).

Part 1 : \(S \preceq \mathcal{P}(S)\)

By definition of \(\preceq\) we need to find an injection from \(S\) to \(\mathcal{P}(S)\). We can constructively define an injection as follows: \(g: S \to \mathcal{P}(S)\) with \(g(x) = \{x\} \in \mathcal{P}(S)\).

Now we need to show that \(g\) is indeed an injection. For \(g\) to be an injection, the following must hold: \(\forall x,y \in S, x \neq y :g(x) \neq g(y)\)

It is clear that \(\{x\} \neq \{y\}\). This however implies \(g(x) = \{x\} \neq \{y\} = g(y) \implies g(x) \neq g(y)\) which is exactly what we had to show. Therefore \(g\) is injective, which shows us, by definition 2, that \(S \preceq \mathcal{P}(S)\).

This leads us to the conclusion that \(S \preceq \mathcal{P}(S)\)

Part 2 : \(S \nsim \mathcal{P}(S)\)

Assume for the sake of contradiction that \(S \sim \mathcal{P}(S)\). Then, by definition, there exists a surjection \(f : S \to \mathcal{P}(S)\). We now define the set \(T := \{x \in S\| x \not \in f(x)\}\). The set \(T\) looks very abstract, but that doesn’t really matter, we just constructed this set with this property to ensure we will get a contradiction at the end.

Since \(f\) is surjective \(\exists x \in s : f(x) = T\), for every \(T \in \mathcal{P}(S)\). Let’s now look at this \(x\) for which \(f(x) = T\). There are two options:

Case 1: if \(x \in T\), then \(x \in f(x)\) since \(T = f(x)\), but this implies \(x \not \in T\) by Definition of \(T\). This contradicts our assumption.
Case 2: if \(x \not \in T\) then since \(T = f(x)\) implies \(x \not \in f(x)\), thus \(x \in T\) by Definition of \(T\). This however is a contradiction.

Since we have found a contradiction in both cases, our assumption \(S \sim \mathcal{P}(S)\) must be wrong. This means there does not exist a surjection from \(S\) to \(\mathcal{P}(S)\) which implies that \(S \nsim \mathcal{P}(S)\)

This concludes our proof of Cantor’s Theorem.

This proof uses the definitions from ETH Zurichs Discrete Mathematics Course and is based on materials from the course.

Have any feedback?

Please feel free to send me a mail! I would love to hear from you.