2
$\begingroup$

I have been thinking about this: One can arrive at Russell's paradox from Cantor's argument, but can we go the other way round, i.e., can we prove Cantor's diagonal argument(often referred to as Cantor's paradox) from the conclusion of Russell's paradox using the Axiom Schema of Specification/Sepration-- there is no universal set.

What do other people think?

The more I think about it, the more I realize Cantor proof of the fact that the cardinality of the power set being strictly larger than the set, implying, higher levels of infinity, is much stronger than the Russell's paradox.

But I would really like to see an argument made the other way, for I have the sneaking suspicion that it can be done.

  • 0
    Sure: Clearly, if $x=\mathcal P(x)$, then the identity, the map $f(t)=t$, is a surjection from $x$ to $\mathcal P(x)$. But Cantor's theorem tells us that no $f:x\to\mathcal P(x)$ is a surjection. This is the contradiction. In fact, and this is the connection, Cantor's theorem gives us an explicit example of a set not in the range of $f$, namely, $\{t\in x\mid t\notin f(t)\}$. In the case where $f$ is the identity, this is the set $\{t\in x\mid t\notin t\}$, which is exactly the set we get in Russell's paradox.2012-10-30

2 Answers 2

4

If we assume Russell's paradox holds then we effectively assume that there is a contradiction in the system.

From a contradiction everything is provable. In particular Cantor's theorem.

(See also: http://xkcd.com/704/)

  • 1
    Yes. You should. If this is a *$r$elevant* information, you should incorporate it into the question. I am just heading to be visited by the sandman, so I will only be able to see, edit and explain tomorrow. However I promise to try and remember to do that tomorrow.2012-10-31
0

Well as Russell's paradox gives you a contradiction and we know that once we have a contradiction we can prove any statement that we want, namely Cantors theorem, however this would not be very interesting (useful) as any system that can prove Russell's paradox is inconsistent and can prove everything (also there would be no models for this systems).

It may be worth noting that although Cantors proof gives a paradox in naive set theory once we are working an a good axiom system (ZF) it no longer does as we do not allow sets of that large a size.

  • 0
    Zermelo Fraenkel, actually.2012-10-30