# The set of all sets of the universe?

I can't understand Russell's paradox. What I understand is that Russell's paradox arises because the set of all sets that are members of themselves is empty. That it's impossible to find a set that's a member of itself, but one can define the set of all sets of the universe that clearly contain itself. Does it mean that there is no set of all sets of the universe?

Please, make answers as simple as possible, I'm nearly ignorant in set theory.

-
I think you are confusing something. Russell's paradox doesn't exhibit the non-existence of sets which are members of themselves. It rather says that there is no set containing all sets which aren't members of themselves. – Nils Matthes Aug 27 '12 at 14:17

Russell's paradox, as well other paradoxes (Cantor's paradox, Burali-Forti paradox) simply tell us that some collections that we can define are not sets. There are two ways to overcome these things:

1. In modern set theory such as ZFC (Zermelo-Fraenkel with Choice) the collection of all sets is not a set. This is why there is a notion of class, it simply means a collection which we can define. In the case of "all the sets" we just define it to be $\{x\mid x=x\}$.

2. There are, however, set theories in which the collection of all sets is a set. One example is NF (New Foundations). In this theory we limit the formulas which define new sets, and so Russell's collection cannot become a set. This means that we cannot prove from NF that the collection defined by Russell's paradox is a set itself, so no contradiction arises.

-
My understanding of NF is that it can express the collection of "sets that are not members of themselves" just as well as ZFC can (that is, the collection is not a set, but you can choose to abbreviate $x\not\in x$ as $x\in\mathbf B$ as long as you don't pretend $\mathbf B$ is something that can be the value of a variable). In ZFC what prevents it from being a set is that ZF comprehension requires a preexisting superset; in NF it is because the formula $x\not\in x$ is syntactically disallowed in the set comprehension axiom. But you can use the formula as much as you like outside that axiom. – Henning Makholm Aug 27 '12 at 14:32
@Henning: Yes. That is a more accurate depiction of the affairs. I was trying to be less accurate and technical, and give a readable explanation though. – Asaf Karagila Aug 27 '12 at 16:25
@AsafKaragila, is NF a single theory ("In this theory...") or a set of theories? NFU, TSTU, NF_n, .... ? – alancalvitti Aug 28 '12 at 0:37
@alancalvitti: NF is a theory, like ZF. It has variants, much like ZF. – Asaf Karagila Aug 28 '12 at 0:42
@AsafKaragila, and much like ZF, ZFC, ZFU, ZF+AD, ZF+AFA &c, the different variants can lead to distinct results. What is the use of calling something a theory if variations therein can lead, sometimes, to starkly opposed results (eg the disasters in Herrlich's Axiom of Choice). – alancalvitti Aug 28 '12 at 1:09

The fact that (in ZFC) a set cannot be a member of itself has no real connection to the Russell Paradox. It is a consequence of the Axiom of Regularity..

The Axiom of Regularity was introduced by von Neumann for purely technical reasons that had nothing to do with paradox avoidance. For one thing, it makes the development of the theory of ordinals smoother. However, set theory can be perfectly well developed without Regularity.

The axioms of ZFC are intended to be (i) powerful enough to allow all the set constructions that we need for a mathematics based on Set Theory and (ii) not so powerful as to lead to a contradiction.

One cannot know for sure that inconsistency has been avoided. But the cheap kind of inconsistency that doomed the logic of Frege is, one hopes, made impossible by putting limitations on how one is allowed to construct sets. (Very) roughly speaking, one is allowed to construct a set from the contents of an already constructed set (here the major exception is the Axiom of Infinity, along with parts of the Axiom scheme of Replacement).

-
Also, if ZFC without Regularity is consistent, then it is does not introduce any new inconsistency to explicitly postulate (instead of Regularity) that there exists a set that is a member of itself. – Henning Makholm Aug 27 '12 at 14:52
To fill in a detail on Henning's note, one axiom that broadens the statement 'there is a set that is a member of itself' is known as the Anti-Foundation Axiom (AFA), introduced by Peter Aczel; it basically states that 'any membership graph you can produce (with a designated node representing your set, and all other nodes reachable from it) corresponds to a unique well-defined set'. – Steven Stadnicki Aug 27 '12 at 16:35

In case you want a short answer that does not attempt to add too much perspective:

1. Russell's paradox does not prove or require that $\{x\mid x\in x\}$ is empty. It proves that $\{x\mid x\not\in x \}$ cannot exist as a set (which is different from being empty -- an empty set does exist), no matter whether there are sets that contain themselves or not.

2. In ordinary ZFC set theory there is indeed no "set of all sets of the universe". (But see Asaf's answer) .

3. In ordinary ZFC set theory $\{x\mid x\in x\}$ is indeed the empty set -- and therefore $\{x\mid x\in x\}$ happens to exist there. (But see André's answer).

-

I have had a problem understanding this before. Here's what I can provide.

The Russell's paradox says that it is impossible to define the set $U$ of all things if $U$ is also considered one of "all things". By impossible, I mean if you allow $U$ to exist, you will violate one of many intuitive rules. You may, as a result, convince yourself that maybe some "intuitive" rules are not supposed to hold as a way to resolve Russell's paradox.

A property $x \notin x$ is considerably nice, so intuitively it should not pose a problem if I pick a subset $V \subseteq U$ by picking elements that satisfy $x \notin x$. However, Russell's paradox says that if you define $V$ like this, you will not know whether $V \in V$ or $V \notin V$. This is considered a contradiction to our basic assumption that you must be able to tell whether $x \in y$ or $x \notin y$ if $y$ is a set.

There are several ways to resolve Russell's paradox. I will list some here.

1. Some may think that the statement like $x \in x$ is actually not so nice. In fact, a set can only contain itself if it's infinitely nested (informally speaking), so it's not hard for me to convince myself that I won't find much use of that in real life. We can choose to disallow sets that contain themselves from being defined, i.e., refuse the existence of such sets. This restriction will render the question "Is $x \in x$?" an invalid statement. This resolves Russell's paradox by making the definition of $V$ invalid. But however practically-looking this is, we know consciously that we lose the ability to define some sets that we were able to define.
2. If you drop the assumption that either $x \in y$ or $x \notin y$ must be true, then the existence of $V$ doesn't seem so problematic. This may be one of reasons people invented intuitionistic logic.
3. You can expand the universe by adding more things that are not considered "sets", then you define $U$ as a "collection" of all sets, and $V = \{x \in U\ |\ x \notin x\}$. This way, $U$ does not contain "everything", but it does contain every set. $U$ itself cannot be a set, or the definition of $V$ will cause a paradox. This solution is used quite a lot. Objects in this system are called "classes". A class that belongs to other classes is called a set. A class that is not a set is called a "proper class". Note that you still cannot have the class of all classes, or the Russell's paradox will appear again, with the word "class" replacing "set".

Anyway, the root of all evil is self-referencing. I feel that it's a common theme in all branches of mathematics.

-