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
    Let's see if I understand. From the fact that there is no set of all $x$ such that $x\notin x$, you want to conclude that no $f:y\to\mathcal P(y)$ is onto. The two certainly have an air of kinship, as the usual example of a set missing the range is the collection of $x$ (in $y$) such that $x\notin f(x)$. But you'd like something more direct, right? How are you planning on leveraging the *non-existence* of a set into the existence of a specific subset? (or is the question whether such a thing is possible?)2012-10-30
  • 0
    Perhaps you need to specify what axiom system you have in mind. I assume you want an argument in as weak a subsystem of ZFC as possible?2012-10-30
  • 1
    Interesting. I hadn't thought about this before. It is not what you are asking, but: Russell's paradox is a *particular* case of Cantor's theorem: If $x$ is the set of all sets, then $x=\mathcal P(x)$. By Cantor's theorem, no $f:x\to\mathcal P(x)$ is onto. We get a contradiction by taking $f$ to be the identity.2012-10-30
  • 1
    @AndresCaicedo: your last post is very related to what I was asking. Although I did not say it explicitly, I did share the intuition that Russell's paradox is almost a subset of Cantor's proof. Would you mind elaborating the last statement: "We get a contradiction by taking f to be the identity"2012-10-30
  • 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