I thought about this question a while ago, while teaching a topics course. Since one can easily check that $${}|{\mathbb R}|=|{\mathcal P}({\mathbb N})|$$ by a direct construction that does not involve diagonalization, the question can be restated as:

Is there a proof of Cantor's theorem that ${}|X|<|{\mathcal P}(X)|$ that is not a diagonal argument?

I suspect the following works. Even if it doesn't, I believe there may be some interest in this presentation (Please let me know if you spot diagonalization somewhere).

A remark of François Dorais helped me (re)locate the argument in print. It is presented in A. Kanamori-D. Pincus. "Does GCH imply AC locally?", in **Paul Erdős and his mathematics, II (Budapest, 1999)**, 413-426, Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, 2002. I believe it actually dates back to Zermelo's 1904 well-ordering paper. (I now think I learned the argument from Kanamori-Pincus, since I certainly used the paper in the topics course.)

**a.** There is obviously an injection $g:X\to{\mathcal P}(X)$. It is enough to show there is no surjection. Suppose there is, and call it $f$. Then $f^{-1}:{\mathcal P}^2(X)\to{\mathcal P}(X)$ is 1-1.

(If $h:A\to B$, $h^{-1}:{\mathcal P}(B)\to{\mathcal P}(A)$ is the map that to $C\subseteq B$ assigns $\{a\in A\mid h(a)\in C\}$. Since $f$ is surjective, we have that $f^{-1}$ is injective.)

(Of course, we could simply use an injection $g:{\mathcal P}(X)\to X$ and invoke Schröder-Bernstein at this point, but this route seems shorter.)

**b.** There is no injection $F:{\mathcal P}(Y)\to Y$ for any set $Y$. The reason is that for any $F$ we can (definably from $F$) produce a pair $(A,B)$ with $A\ne B$ and $F(A)=F(B)$. In effect, Zermelo proved that:

For any $F:{\mathcal P}(Y)\to Y$ there is a unique well-ordering $(W, \lt)$ with $W\subseteq Y$ such that:

- $\forall x\in W (F (\{y ∈ W \mid y \lt x\}) = x)$, and
- $F (W )\in W$.

We can then take $A=W$ and $B=\{y\in W\mid y\lt F(W)\}$.

**c.** *Zermelo's theorem* can be proved as follows: Simply notice that $W=\{a_\alpha\mid \alpha\lt \beta\}$ where $$ a_\alpha= F(\{a_\gamma\mid \gamma\lt \alpha\}) $$ and $\beta$ is largest so that this sequence is injective.

That $\beta$ exists is a consequence of *Hartogs theorem* that for any set $A$ there is a least ordinal $\alpha$ does not inject into $A$.

Uniqueness of $W$ is shown by considering the ﬁrst place where two potential candidates for $(W, \lt)$ disagree.

**d.** Hartogs theorem is proved by noticing that if $\alpha$ is an ordinal and injects into $A$, then there is a subset $B$ of $A$ and a binary relation $R$ on $B$ such that $(B,R)$ is order isomorphic to $\alpha$. From this one easily sees that the collection of $\alpha$s that inject into $A$ forms a set, that is in fact an ordinal $\beta$. Then $\beta$ is least that does not inject into $A$.

Let me close with a remark, and a question: The proof above is formalizable in ZF, without choice. In fact, Zermelo's theorem is provable without using replacement, although the argument I sketched uses it.

The question is mentioned in Kanamori-Pincus: We showed that if $F:{\mathcal P}(Y)\to Y$ then $F$ is not injective by exhibiting a pair $(A,B)$ with $F(A)=F(B)$. If instead of Zermelo's argument we had used at this point the construction from the diagonal argument, we would have taken $$ A=\{y\in Y\mid \exists Z(y=F(Z)\notin Z)\}, $$ and checked that there must be a $B\ne A$ with $F(A)=F(B)$.

Can we *define* such $B$ from $F$?

(**Update:** In general, the answer to the question is no. See here.)

**Update, Sep. 6, 2017:** Let me add a few additional remarks. First, in comments, Martin Brandenburg asked why one should bother about trying to obtain a "diagonalization-free" proof. That the proof above avoids diagonalization is perhaps simply a curiosity (though one is left with the question of how to define precisely "diagonalization-free"); what matters is that the argument gives a bit more than Cantor's: As I pointed out in a comment, the proof just given shows that 1) The collection of well-orderable subsets of $X$ has strictly larger size than $X$. This is an improvement over Cantor's result in the context of $\mathsf{𝖹𝖥}$. 2) Given any $f\!:\mathcal P(X)\to X$, we can find $A\subsetneq B$ with $f(A)=f(B)$. This is also a combinatorial strengthening, and it can be pushed further. Stevo Todorcevic in particular obtained several extensions of this idea, see this answer in Math.Stackexchange.

Second, Hartogs's theorem can be used to provide a different (also "diagonalization-free") proof of Cantor's result, and actually establish a generalization in the context of quasi-ordered sets, due to Gleason and Dilworth. For the pretty argument and appropriate references, see here.

keep openwhich should be taken into account by the next person wishing to vote to close. If you wish to do so, then please let's take this to meta, where I have started this thread: tea.mathoverflow.net/discussion/789/… $\endgroup$ – José Figueroa-O'Farrill Nov 22 '10 at 17:46againstclosing. The question is: "Is there a different proof of this theorem?" which, to me, sounds very interesting and a natural question that a mathematically mature but non-expert-in-set-theory person might ask. I've asked several questions that have exposed my lamentable ignorance of the subtleties of mathematical foundations and, so far, all have received very interesting and informative answers. This one feels as though it is in the same vein as those. $\endgroup$ – Andrew Stacey Nov 22 '10 at 18:2024more comments