A short proof of Cantor's theorem

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.

Writing a Sudoku Solver in Python

Pretty much every free newspaper you find comes with a sudoku puzzle. Depending on the difficulty it might take you a considerable amount of time to solve them. As a result I wanted to write an algorithm which could do that for me within seconds.

More ...

Building an API based temperature sensor

The goal of this short summary is to explain how you can build a small API based temperature sensor that costs less than 10$ and can be used anywhere. I use this sensor at my office to log the temperature and then display it on a smart dashboard.

More ...

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
© 2020