12
$\begingroup$

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!

$\endgroup$
  • 5
    $\begingroup$ I suppose you don't want to use the following argument: If $f : \mathcal{P} ( S ) \to S$ is injective then, $f^{-1} : \mathrm{im} ( f ) \to \mathcal{P} (S)$ is surjective and you can then apply Cantor's argument to this function. $\endgroup$ – user642796 Jan 23 '13 at 6:06
  • $\begingroup$ @ArthurFischer- I was hoping to avoid something like that if possible. I'm aware that this argument absolutely works, but I was curious if there was a fundamentally different line of reasoning we could use here. $\endgroup$ – templatetypedef Jan 23 '13 at 6:16
15
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That's a beautiful construction, thanks! Could you eliminate the explicit dependence on $Ord$ by just picking an arbitrary ordinal larger than $|S|$, or would that be circular reasoning? $\endgroup$ – templatetypedef Jan 23 '13 at 7:02
  • $\begingroup$ This holds without choice, so it may not make sense to talk about "an ordinal larger than $|S|$". Of course the reference to $\mathrm{Ord}$ is overkill, this is just the way I like to think about things instead of thinking about Hartog's Lemma. $\endgroup$ – Amit Kumar Gupta Jan 23 '13 at 7:06
  • $\begingroup$ To supplement Amit's answer: This proof is due to Zermelo, and it has the additional advantage of not being a diagonal argument, and explicitly producing a pair of sets witnessing the failure of injectivity. One can also give a diagonal argument, but then (surprisingly?), it is in general not possible to exhibit the witnesses, even though we know they exist. See mathoverflow.net/questions/46970/… for the reverse diagonal argument, and mathoverflow.net/questions/47458/cantors-argument-revisited for the definability issue. $\endgroup$ – Andrés E. Caicedo Jan 23 '13 at 22:00
  • $\begingroup$ (Oh, and Zermelo argues explicitly in terms of well-orderings of subsets of $S$ rather than ordinals, so the issue mentioned on the first two comments is not essential -- and the proof is formalizable in Zermelo's set theory $\mathsf Z$, without needing replacement.) $\endgroup$ – Andrés E. Caicedo Jan 23 '13 at 22:54
1
$\begingroup$

A more 'diagonal' method of proof might be as follows:

Suppose, for contradiction, that $f: \mathcal{P}(S) \rightarrow S$ were injective and define the set $X = \{f(A) | f(A) \not\in A\}$. We then ask: is $f(X) \in X$?

  • If $f(X) \not\in X$ then X is one of those sets such that $f(A) \not\in A$. Thus $f(X) \in \{f(A) | f(A) \not\in A\} = X$: a contradiction.

  • If $f(X) \in X = \{f(A) | f(A) \not\in A\}$ then it has some preimage $A$ with $ f(X)=f(A) \notin A$. However, since $f$ is injective, the only preimage of $f(X)$ is $X$. Thus $f(X) \notin X$: a contradiction.

Since both options lead to a contradiction, no such $f: \mathcal{P}(S) \rightarrow S$ can exist.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ See the comments below the question itself... $\endgroup$ – Asaf Karagila Feb 20 '17 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.