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've heard of some other paradoxes involving sets (ie, "the set of all sets that do not contain themselves") and I understand how paradoxes arise from them. But this one I do not understand.

Why is "the set of all sets" a paradox? It seems like it would be fine, to me. There is nothing paradoxical about a set containing itself.

Is it something that arises from the "rules of sets" that are involved in more rigorous set theory?

EDIT: I don't really have much of a background with Set Theory, so an answer that deals with common english would be much appreciated =)

share|improve this question
    
Try a finite example, and try to answer, "What is the sum of its elements cardinality?" –  Jonathan Fischoff Jul 20 '10 at 23:17
add comment

8 Answers

up vote 35 down vote accepted

Let $|S|$ be the cardinality of $S$

$|S| < |2^S|$ can be proven with generalized Cantor's diagonal argument

Proof of the set of all sets doesn't exist:

Let $S$ be the set of all sets,

$|S| < |2^S|$

but $2^S$ is a subset of $S$, because every set in $2^S$ is in $S$. Therefore

$|2^S| \leq |S|$

A contradiction. Therefore the set of all sets doesn't exist.

share|improve this answer
7  
This is also a manifestation of godel's incompleteness theorem :) –  workmad3 Jul 20 '10 at 23:02
5  
What does 2^S mean? –  Casebash Jul 21 '10 at 0:51
9  
@Casebash: 2^S is standard notation for the power set of S: That is, the set of all subsets of S. If S were {1, 2}, 2^S would be {{}, {1}, {2}, {1, 2}}. –  Larry Wang Jul 21 '10 at 0:58
4  
@Seamus Here S is defined as the set of all sets. Every element of 2^S is a set, implies they are also elements of S. –  Chao Xu Jul 21 '10 at 12:22
5  
How is that incorrect. We always consider the standard framework when we are not presented other ones. –  Chao Xu Mar 6 '11 at 7:55
show 6 more comments

An informal explanation is Russel's Paradox. The wiki page is informative, here's the relevant quote:

Let us call a set "abnormal" if it is a member of itself, and "normal" otherwise. For example, take the set of all squares. That set is not itself a square, and therefore is not a member of the set of all squares. So it is "normal". On the other hand, if we take the complementary set that contains all non-squares, that set is itself not a square and so should be one of its own members. It is "abnormal".

Now we consider the set of all normal sets, R. Attempting to determine whether R is normal or abnormal is impossible: If R were a normal set, it would be contained in the set of normal sets (itself), and therefore be abnormal; and if it were abnormal, it would not be contained in the set of normal sets (itself), and therefore be normal. This leads to the conclusion that R is both normal and abnormal: Russell's paradox.

share|improve this answer
    
I mentioned this paradox in my question; it however is not the same one that I am asking about. –  Justin L. Jul 20 '10 at 23:17
2  
You're right, sorry. Probably you can say that, since "the set of all sets" is not so well-defined, it must necessarily contain the set from Russel's paradox. Since the set from Russel's Paradox can't exist, neither can any set that contains it. But I feel this is cheating somehow. –  Edan Maor Jul 20 '10 at 23:37
    
That's not cheating, that's exactly correct. I always use Russel's Paradox for the "set of all sets" question. The main point in both cases anyway is remembering that Cantor's definition of a set is a little to vague if you dig deep enough. –  balpha Jul 21 '10 at 5:10
add comment

The "set of all sets" is not so much a paradox in itself as something that inevitably leads to a contradiction, namely the well-known (and referenced in the question) Russell's paradox.

Given any set and a predicate applying to sets, the set of all things satisfying the predicate should be a subset of the original set. If the "set of all sets" were to exist, because self-containment and non-self-containment are valid predicates, the set of all sets not containing themselves would have to exist as a set in order for our set theory to be consistent. But this "set of all sets" cannot exist in a consistent set theory because of the Russel paradox.

So the non-existence of the "set of all sets" is a consequence of the fact that presuming it's existence would lead to the contradiction described by Russel's paradox.

This is in fact the origin of Russel's paradox.

In his work "The Basic Laws of Arithmetic", Gottlob Frege had taken as a postulate the existence of this "set of all sets". In a letter to Frege, Bertrand Russell essentially blew away the basis of Frege's entire work by describing the paradox and proving that this postulate could not be a part of a consistent set theory.

share|improve this answer
    
This is how I had understood it before and I always found it to be the simplest answer, which is quite neat. –  Justin L. Jul 21 '10 at 5:35
3  
If the "set of all sets" were to exist, because self-containment and non-self-containment are valid predicates, the set of all sets not containing themselves would have to exist as a set in order for our set theory to be consistent - Not true, as Quine's New Foundations, cited by François, shows. It has a universal set, but not the Russell set. –  Charles Stewart Jul 21 '10 at 11:05
    
I guess this depends on what one considers a "set theory". The usual image of the universe of sets, given by the cumulative hierarchy, doesn't allow for the set of all sets. –  Michael Greinecker Mar 8 '12 at 9:13
    
I don't see how you could not consider Quine's New Foundations a set theory; it has the usual universe of sets in it. It may in fact have a superset (superclass?) of ZF's sets, though it's possible stratified comprehension excludes some sets ZF includes. It is akin to NBG set theory; some definite weirdness if you're used to ZFC, but basically the same thing for practical purposes. –  prosfilaes Oct 17 '12 at 6:48
add comment

As others have explained, the existence of universal set is incompatible with the Zermelo–Fraenkel axioms of set theory. However, there are alternative set theories which admit a universal set. One such theory is Quine's New Foundations.

share|improve this answer
1  
Possibly also useful: Elementary Set Theory With a Universal Set, by M. Randall Holmes. –  MJD Mar 18 '12 at 18:12
add comment

How about a set that contains everything with the exception of itself?

share|improve this answer
    
You can still make the cardinality argument that the set cannot contain all its subsets. –  Michael Greinecker Mar 8 '12 at 9:11
add comment

"Why is "the set of all sets" a paradox? It seems like it would be fine, to me."

The lesson of this and other set theory paradoxes is that when you define a set in a proof, you are obliged to demonstrate that the set exists and is well-defined. To me, a paradox of Russell's Paradox is that he fell into this trap since he pretty much wore himself out trying to generate a rigorous foundation for Mathematics.

share|improve this answer
    
The set of all sets is well-defined in the set theory Cantor used: to any logical predicate there is a set of all objects satisfying it. The problem is that Cantor's set theory is inconsistent. –  Hurkyl Mar 8 '12 at 9:36
add comment

Russel's paradox arises if you consider the set $U=\left\{x:x\not\in x\right\}$. Ask yourself if $U\in U$. If you suppose so, then by the definition of unrestricted set comprehension $U\not\in U$. You have a contradiction, so it must be the opposite of what you supposed, that is, $U\not\in U$. But this is the same as saying $U$ belongs to the complement of itself, that is, $U\in U$. You now have another contradiction, but this is far worse, since you have no hypotheses. The whole theory is logically inconsistent.

In set theory there are two ways for getting rid of the Russel's paradox: either you disallow the set of all sets and other similar sets (see for example the Zermelo-Fraenkel set theory), or you allow them, but you also restrict the way they are used (see for example the Morse-Kelley set theory).

In the first case, set comprehension says if you have a set $A$ you can have $\left\{x\in A:\phi\left(x\right)\right\}$ (notice: writing $\left\{x:\phi\left(x\right)\right\}$ is just wrong in this case, because you have to have an initial set). If you now define $U=\left\{x\in A:x\not\in x\right\}$ and you repeat the same passages as before, it only follows that $U\not\in A$. There's no contradiction and the theory is consistent.

In the second case, you consider classes, not just sets. Sets are classes that belong to some other class, while proper classes are classes that belong to no class. Set comprehension, in this case, says you can have $\left\{x:\phi\left(x\right)\right\}$, but all its members are sets by definition. If try to reproduce Russel's paradox, you get that $U\not\in U$. If you then suppose that $U$ is a set, then you have a contradiction, so $U$ must be a proper class. This is all you get. No contradictions. The theory is consistent.

share|improve this answer
    
There are other ways to avoid Russell's paradox, too. For example, the axiom schema of comprehension in NF doesn't allow you to construct $\{x: x \notin x\}$ (or, AIUI, even $\{x \in A: x \notin x\}$ in general) because $x \notin x$ is not a stratified formula. It does let you construct the universal set $\{x: x=x\}$, though. –  Ilmari Karonen Mar 8 '12 at 8:57
add comment

Perhaps the following image will help take from here:

enter image description here

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.