3
$\begingroup$

I was wondering if it was possible to formally prove that the set of all sets does not exist in ZFC by using a simple argument based on Cantor's Theorem:

  • Assume for contradiction that the set of all sets exists (call it $S$).
  • This means that its power set $\wp(S)$ exists as well.
  • By Cantor's Theorem, we know $|S| < |\wp(S)|$.
  • Since $|S| < |\wp(S)|$, we know that $\wp(S) - S \ne \emptyset$
  • Since every element of $\wp(S)$ is a set, we know that $\wp(S) - S = \emptyset$.
  • However, we know that $\wp(S) - S \ne \emptyset$.
  • Therefore, we have a contradiction, so $S$ does not exist.

I have not seen this line of reasoning used before to show that the set of all sets does not exist. Is this proof correct?

$\endgroup$
  • $\begingroup$ This is of course using somewhat stronger premises than needed. For example, arguing with cardinalities requires the axiom of choice (though one could get rid of it by reformulating) $\endgroup$ – Hagen von Eitzen Jan 16 '13 at 6:19
  • 2
    $\begingroup$ No, it doesn't. $|S|<|\mathcal P(S)|$ is (by definition) a statement about maps $f:S\to\mathcal P(S)$, choice is not relevant here. $\endgroup$ – Andrés E. Caicedo Jan 16 '13 at 6:48
4
$\begingroup$

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.)

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.