A proof that the "set of all sets" does not exist in ZFC using Cantor's Theorem?
Solution 1:
It is correct. I posted about it a while ago in a comment somewhere here (on a question on whether there was a relation between Cantor's theorem and Russell's paradox). You can see a 140-characters-or-less summary here: https://twitter.com/andrescaicedo/status/263151880295813120
The usual proofs of both the fact that there is no set of all sets ("Russell's paradox"), and Cantor's theorem use a diagonal argument. There is actually a proof of Cantor's theorem that avoids diagonalization, due to Zermelo, see this answer on MO. This is why I find this argument interesting, as it gives us a diagonalization-free proof of Russell's paradox.
(For the answer to the question on MO mentioned at the end of the link above, see here.)
Solution 2:
Both arguments are actually the same.
Cantor's theorem is logically equivalent to (after pushing negation all the way inside the formula) $\forall S \; \forall (f \in \mathcal P(S)^S) \; \exists (Y \in \mathcal P(S)) \; \forall (x \in S) \; f(x) = Y \implies \bot$.
Cantor's proof goes by defining $Y \in P(S)$ by $Y = \{x \in S / x \notin f(x)\}$. Then for any $x \in S$, $f(x) = Y$ implies that $x \in f(x) \Leftrightarrow x \in Y \Leftrightarrow x \notin f(x)$ which is a contradiction. Notice how we never used the fact that the range of $f$ was $\mathcal P(S)$ so what Cantor actually proves is $\forall S \forall T \; \forall (f \in T^S) \; \exists (Y \in \mathcal P(S)) \; \forall (x \in S) \; f(x) = Y \implies \bot$, which means that $\mathcal P(S)$ is never a subset of the image of a function defined on $S$.
Russel's theorem is logically equivalent to (after pushing negation all the way inside the formula) $\forall S \; \exists Y \; Y \in S \implies \bot$.
Russel's proof goes by defining the set $Y$ by $ Y = \{ x \in S / x \notin x\}$ (and notice that $Y \in \mathcal P(S))$. Then if $Y \in S$ you get that $Y \in Y \Leftrightarrow Y \notin Y$, which is a contradiction.
So what Russel actually proves is this : $\forall S \; \exists (Y \in \mathcal P(S)) \; Y \in S \implies \bot$, which means that $\mathcal P(S)$ is never a subset of $S$
Now, your proof of Russel's theorem via Cantor's proof goes like this :
pick $T=S$ and $f : S \to S$ defined by $f(x)=x$. As in Cantor's proof, pick $Y = \{x \in S / x \notin f(x)\} = \{x \in S / x \notin x\}$. Then $Y \neq f(x)$ for any $x \in S$, which implies that $Y \notin S$ : if $Y \in S$, you deduce that $Y \in Y \Leftrightarrow Y \notin f(Y)=Y$, so you get a contradiction. But this is exactly Russel's proof.
So Russel's proof of Russel's theorem is a direct application and reduction of Cantor's proof of Cantor's theorem