A “reverse” diagonal argument?

Question

Cantor's diagonal argument can be used to show that a set $S$ is always smaller than its power set $\wp(S)$. The proof works by showing that no function $f : S \rightarrow \wp(S)$ can be surjective by constructing the explicit set $D = \{ x \in S | x \notin f(s) \}$ from a function $f$ and showing that no element of $S$ maps to $D$.

This proof works because all bijections are surjections, so if no surjection from $S$ to $\wp(S)$ exists, then there cannot be a bijection between $S$ and $\wp(S)$.

My question is whether it is possible to run a "reverse diagonalization" that works by instead showing that there is no injection from $\wp(S)$ to $S$. I am curious about this because I have never seen Cantor's theorem proved this way (or, more generally, any diagonal argument structured like this).

Is it possible to take Cantor's diagonal argument and "reverse" it to show that there cannot be an injection from $\wp(S)$ to $S$, rather than showing that there can be no surjection from $S$ to $\wp(S)$?

Thanks!

Answer 1

Suppose $f : \mathcal{P}(S) \to S$ were an injection. Consider the following recursive construction:

• $s_0 = f(\emptyset)$
• $s_\alpha = f(\{s_\beta\}_{\beta < \alpha})$

Because $f$ is injective, all the $s_\alpha$ are distinct. But this can't be otherwise we have an injection $\mathrm{Ord} \to S$, where $S$ is a set.

EDIT: Or, if we want to be frugal and not mention injections from $\mathrm{Ord}$, we can say that the fact that the $s_\alpha$ are all distinct contradicts Hartog's Lemma.