Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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) –  Hagen von Eitzen Jan 16 '13 at 6:19
2  
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. –  Andres Caicedo Jan 16 '13 at 6:48
add comment

2 Answers

up vote 4 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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