# Cantor's Theorem (Strong Version)

## Theorem

Let $S$ be a set.

Let $\map {\PP^n} S$ be defined recursively by:

$\map {\PP^n} S = \begin{cases} S & : n = 0 \\ \powerset {\map {\PP^{n - 1} } S} & : n > 0 \end{cases}$

where $\powerset S$ denotes the power set of $S$.

Then $S$ is not equivalent to $\map {\PP^n} S$ for any $n > 0$.

## Proof 1

We temporarily introduce the notation:

$a^n = \begin{cases} a : & n = 0 \\ \set {a^{n - 1} } : & n > 0 \end{cases}$

where $a \in S$.

Thus $a^n$ consists of a single element $a^{n - 1} \in \map {\PP^{n - 1} } S$.

Let there be a bijection $f: S \to \QQ^n$ where $\QQ^n \subseteq \map {\PP^n} S$.

Then define:

$\AA^{n - 1} = \set {s^{n - 1} \in \map {\PP^{n - 1} } S: s^{n - 1} \ne \map f s}$

Each $\QQ^{n - 1} \in \QQ^n$ is the image of some element of $S$ under $f$.

Let $\QQ^{n - 1} = \map f x$ for some $x \in S$.

Let $x^{n - 1} \in \QQ^{n - 1} = \map f x$.

Then $x^{n - 1} \notin \AA^{n - 1}$, and so $\AA^{n - 1} \notin \QQ^{n - 1}$.

On the other hand, let $x^{n - 1} \notin \QQ^{n - 1} = \map f x$.

Then $x^{n - 1} \in \AA^{n - 1}$, and so again $A^{n - 1} \notin \QQ^{n - 1}$.

Thus $\AA^{n - 1} \notin Q^n$.

Therefore $Q^n$ is a proper subset of $\map {\PP^n} S$.

Hence the result.

$\blacksquare$

## Proof 2

The proof proceeds by induction.

For all $n \in \N_{> 0}$, let $\map P n$ be the proposition:

There is no surjection from $S$ onto $\map {\PP^n} S$.

### Basis for the Induction

$\map P 1$ is Cantor's Theorem.

This is our basis for the induction.

### Induction Hypothesis

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

So this is our induction hypothesis:

There is no surjection from $S$ onto $\map {\PP^k} S$.

Then we need to show:

There is no surjection from $S$ onto $\map {\PP^{k + 1} } S$.

### Induction Step

This is our induction step:

Suppose that $\map P k$ is true.

Aiming for a contradiction, suppose that $f: S \to \map {\PP^{k + 1} } S$ is a surjection.

Define the mapping $g: S \to \map {\PP^k} S$ as:

$\ds \map g x = \bigcup \map f x$

This is actually a mapping into $\map {\PP^k} S$, as follows:

$\map f x \in \map {\PP^{k + 1} } S = \powerset {\map {\mathcal P^k} S}$

By the definition of power set:

$\map f x \subseteq \map {\PP^k} S$

Thus each element of $\map f x$ is a subset of $\map {\PP^{k - 1} } S$.

Thus by Union of Subsets is Subset:

$\ds \bigcup \map f x \subseteq \map {\PP^{k - 1} } S$

Therefore:

$\ds \bigcup \map f x \in \map {\PP^k} S$

That is, $\map g x$ is a mapping into $\map {\PP^k} S$.

Next we have that:

$\forall y \in \map {\PP^k} S: \set y \in \map {\PP^{n + 1} } S$

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

$\exists x \in S: \map f x = \set y$

Then:

$\ds \map g x = \bigcup \set y = 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$

## Source of Name

This entry was named for Georg Cantor.