Cantor's Theorem (Strong Version)/Proof 2

Theorem

Let $S$ be a set.

Let $\mathcal P^n \left({S}\right)$ be defined recursively by:

$\mathcal P^n \left({S}\right) = \begin{cases} S & : n = 0 \\ \mathcal P \left({\mathcal P^{n-1} \left({S}\right)}\right) & : n > 0 \end{cases}$

where $\mathcal P \left({S}\right)$ denotes the power set of $S$.

Then $S$ is not equivalent to $\mathcal P^n \left({S}\right)$ for any $n > 0$.

Proof

The proof proceeds by induction.

For all $n \in \N_{> 0}$, let $P \left({n}\right)$ be the proposition:

There is no surjection from $S$ onto $\mathcal P^n \left({S}\right)$.

Basis for the Induction

$P \left({1}\right)$ is Cantor's Theorem.

This is our basis for the induction.

Induction Hypothesis

Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 1$, then it logically follows that $P \left({k+1}\right)$ is true.

So this is our induction hypothesis:

There is no surjection from $S$ onto $\mathcal P^k \left({S}\right)$.

Then we need to show:

There is no surjection from $S$ onto $\mathcal P^{k+1} \left({S}\right)$.

Induction Step

This is our induction step:

Suppose that $P \left({k}\right)$ is true.

Aiming for a contradiction, suppose that $f: S \to \mathcal P^{k+1} \left({S}\right)$ is a surjection.

Define the mapping $g: S \to \mathcal P^k \left({S}\right)$ as:

$\displaystyle g \left({x}\right) = \bigcup f \left({x}\right)$

This is actually a mapping into $\mathcal P^k \left({S}\right)$, as follows:

$f \left({x}\right) \in \mathcal P^{k+1} \left({S}\right) = \mathcal P \left({\mathcal P^k \left({S}\right)}\right)$

By the definition of power set:

$f \left({x}\right) \subseteq \mathcal P^k \left({S}\right)$

Thus each element of $f \left({x}\right)$ is a subset of $P^{k - 1} \left({S}\right)$.

Thus by Union of Subsets is Subset:

$\displaystyle \bigcup f \left({x}\right) \subseteq \mathcal P^{k-1} \left({S}\right)$

Therefore:

$\displaystyle \bigcup f \left({x}\right) \in \mathcal P^k \left({S}\right)$

That is, $\displaystyle g \left({x}\right)$ is a mapping into $\mathcal P^k \left({S}\right)$.

Next we have that:

$\forall y \in \mathcal P^k \left({S}\right): \left\{{y}\right\} \in \mathcal P^{n+1} \left({S}\right)$

But by hypothesis $f$ is surjective, and so:

$\exists x \in S: f \left({x}\right) = \left\{{y}\right\}$

Then:

$\displaystyle g \left({x}\right) = \bigcup \left\{{y}\right\} = y$

As this holds for all such $y$, $g$ is surjective.

But this contradicts the induction hypothesis.

Thus we conclude that the theorem holds for all $n$.

$\blacksquare$