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

share|improve this question
    
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?) –  Andres Caicedo Oct 30 '12 at 0:35
    
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? –  Andres Caicedo Oct 30 '12 at 0:37
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. –  Andres Caicedo Oct 30 '12 at 4:11
    
@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" –  user43901 Oct 30 '12 at 15:01
    
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. –  Andres Caicedo Oct 30 '12 at 18:25
add comment

2 Answers

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

share|improve this answer
    
The axiom of separation takes out the inconsistency; hence, I really do not see how you can just prove Cantor's theorem out of the contradiction we get. –  user43901 Oct 30 '12 at 14:58
    
The axiom schema of separation implies the Russell paradox is false. The collection defined is not a set, and so there is no paradox. If you assume the paradox holds then you assume implicitly that it is a set and thus a contradiction occurs. If you mean to ask something else please clarify your question. –  Asaf Karagila Oct 30 '12 at 15:28
    
The Axiom Schema of separation, when applied, creates a subset relationship that avoids the paradox. However, this does not entail that the collection defined is not a set; it is a set, but the way we define a set has been changed from Naive Set theory, where any set is defined by a condition. Introducing the subset relationship avoids the paradox. You are right in saying that if we accept Russell's paradox then we can (almost uselessly) prove \it{anything} we want, but I was looking for something more constructive. I think Andres has addressed part of my query. –  user43901 Oct 31 '12 at 0:09
    
I think that you can, and should, using Andres' input as well as my "overly simplistic answer" (as I see it) edit and rephrase your question to reflect the things you said. –  Asaf Karagila Oct 31 '12 at 0:15
    
Sorry if I am misunderstanding it: so you want me to incorporate these and change the original post? And I do not think your answer is overly simplistic, it is just that I was naively hoping for something more--wistful thinking, at times. But I think you are correct in saying so from the way you were looking at it. –  user43901 Oct 31 '12 at 0:17
show 1 more comment

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.

share|improve this answer
    
Yes, the axiom of separation criteria allows to fix the naive set theory paradox that Russell points out. What is ZF? –  user43901 Oct 30 '12 at 0:57
    
ZF is zermelo frankelen set theory. So just a suitable axiom system that does not allow us to define sets that are "too big" –  hmmmm Oct 30 '12 at 11:20
    
Zermelo Fraenkel, actually. –  Asaf Karagila Oct 30 '12 at 15:28
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.