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.

We can clearly define a set of sets. I feel intuitively like we ought to define sets which do contain themselves; the set of all sets which contain sets as elements, for instance. Does that set produce a contradiction?

I do not have a very firm grasp on what constitutes a set versus what constitutes a class. I understand that all sets are classes, but that there exist classes which are not sets, and this apparently resolves Russell's paradox, but I don't think I see exactly how it does so. Can classes not contain classes? Can a class contain itself? Can a set?

share|improve this question
2  
The short answer is the axiom of foundation: en.wikipedia.org/wiki/Axiom_of_foundation. But I suspect you will get a very good answer shortly, so I only suggest the above link as a first reading. –  M Turgeon Aug 14 '12 at 22:03
1  
@MTurgeon This question does not involve the axiom of foundation. If the OP wanted a set $x$ such that $x \in x$, then the axiom of foundation would be need to show that no such set exists. –  William Aug 14 '12 at 22:05
2  
I think he referred to Russell's paradox. Bertrand is unfortunately Russell's first name and Joseph's last name. –  Tunococ Aug 14 '12 at 22:08
1  
@William My knowledge of set theory is very poor. But it seems to me that you just proved in your comment that the axiom of foundation is relevant to the OPs question. –  M Turgeon Aug 14 '12 at 22:08
4  
Call the set containing precisely all sets that are not members of themselves $S$. Thus we have $$A\in S\iff A\not\in A$$ for every set $A$. That is, a set does not contain itself if and only if it is a member of $S$. Then it follows that $S\in S\iff S\not\in S$ (because $S$ is a set!), a clear impossibility. This does not follow if $S$ is not a set, because we cannot substitute $A:=S$ when $S$ is not a set. (Intuitively, a (proper) class is a collection too large to be a set. An actual set theorist should be able to describe the situation better.) –  anon Aug 14 '12 at 22:10

9 Answers 9

up vote 10 down vote accepted

Russell's paradox

In Zermelo set theory, the proof of the titular question is straightforward:

  • Assume there is such a set. Call it $R$.
    • Fact: $x \notin x$ if and only if $x \in R$. This is the defining property of $R$.
    • Assume $R \in R$.
      • By the fact, this means $R \notin R$.
      • Contradiction!
    • Therefore $R \notin R$.
    • By the fact, this means $R \in R$.
    • Contradiction!
  • Therefore no such set exists.

There is an immediate corollary: there is no set of all sets.

  • Assume there is a set of all sets. Call it S.
    • There is a subset $R \subseteq S$ containing exactly those sets $x$ for which that $x \notin x$
    • Contradiction!
  • Therefore, there is no set of all sets.

Rationale for Zermelo set theory

One of the most important features of a set theory is having tools to actually construct sets. Cantor's 'naive' set theory had the most powerful rule of all: if you could name any property $P$, then there was a set of all sets that have property $P$. This let you construct any set you could image! Unfortunately, it lets you construct the set of Russell's paradox, and thus Cantor's set theory is self contradictory.

Zermelo took a more modest approach*: he looked for a more conservative collection of constructions that sufficed for mathematics, but isn't so strong as to create any of the known paradoxical sets. Fraenkel added another useful construction, and gave us the axiom of foundation which simplifies technical arguments.

Among the constructions of Zermelo set theory is the restricted form of Cantor's "comprehension principle": if we have any property $P$ and a set $S$, then we can form the subset of $S$ of things satisfying property $P$.

The axiom of restricted comprehension exactly the property of a universe of sets that is needed to make the argument in the opening section.

*: I do not know if this is historically accurate. Really, I'm espousing an a postiori observation about it.

Classes

Set-builder notation is very useful notation to denote sets. Recall that each of the following notations define sets in ZFC:

$$ \{ x \in S \mid P(S) \} \qquad \qquad \{ f(x) \mid x \in S \} \qquad \qquad \{ a, b \} $$

where $a,b,S$ are all sets, $P$ is a unary predicate whose domain includes $S$, and $f$ is a function whose domain includes $S$.

The same notation turns out to be quite useful to define predicates. For example, predicate

P(x) = "x contains the empty set"

is easily notated as

$$ P = \{ x \mid \emptyset \in x \} $$

and the assertion that $x$ satisfies the predicate $P$ can be written as

$$ x \in P. $$

This notation, formally, has nothing to do with sets: it is alternative notation for logic. When we do this, we call a predicate a "class".

The way you manipulate logic in the form of classes is so strikingly similar to the way you manipulate sets that this unified notation is extremely useful.

To answer a question you had, the only objects are still sets. The only thing that can be a member of a set is a set. The only thing that can be a member of a class is a set. Classes can't be members of anything, because they aren't objects: they're logic. (at least, if we stick to first-order logic....)

It can be technically awkward when you hav0e to pay attention to what is a set and what is a class, especially if you want to reason in a 'stripped down' version of formal logic.

So, Von Neumann, Bernays, and Gödel invented (NBG) set theory*. The objects of NBG set theory are classes. It might be a little confusing to use the same word as we did for the alternative view of logic above; however in practice it's not a problem.

NBG set theory includes a class called $\mathbf{Set}$. $V$ is another commonly used name for this class. There is a theorem/axiom that says if $x \in y$, then $x \in \mathbf{Set}$.

NBG can also be presented (and usually is, I think) as a theory with two sorts: a sort of sets and a sort of classes. Only sets may be elements of things. But for any set there is a class that has the same elements, and it is reasonable to conflate the two.

*: Again, this is not meant to be a historically accurate presentation.

Universes

Another approach to dealing with classes is a Grothendieck universe. However, using them requires assuming a large cardinal axiom.

A Grothendieck universe is, briefly, a set $U$ with the property that the elements of $U$ collectively have good enough properties to be justifiably called a 'universe of sets'. We call the elements of $U$ "small sets". The things we would normally call classes are all subsets of $U$.

In this way (other than having had to assume a large cardinal axiom) we don't have to do much that is special -- everything we are talking about is a set. We just occasionally have to take note of which sets are "small" and which are not.

share|improve this answer
2  
"This notation, formally, has nothing to do with sets: it is alternative notation for logic. When we do this, we call a predicate a 'class'." Ohhhhhhhhhh. That helps a lot. Thank you! –  crf Aug 18 '12 at 1:42
    
What's the point/benefit of building the set pointed in Russell's paradox in a non-paradoxical way (considering it's possible)? What change would it make for mathematics? –  Vÿska Jun 23 '13 at 5:55

Since the other users have answered the question in the context of well-founded set theory, let me say a few words about other set theories.

Before we can really answer this question, we must first think about what a ‘set’ is in the first place. Intuitively, a set is something that has members and which is wholly determined by what its members are. This is codified in the axiom of extensionality:

Extensionality. If $X$ and $Y$ are sets, and for all $z$, $z \in X \iff z \in Y$, then $X = Y$.

Notice, however, that the quantifier “for all $z$” is unbounded – that is, there is no restriction on the type of $z$. Let us non-commitally fix a universe of discourse $\mathbf{U}$ and say that $z$ is required to be in $\mathbf{U}$. So, can a set be a member of another set? Well, that depends – are there any sets in $\mathbf{U}$? If not, then obviously a set cannot be a member of any set. This is rather unacceptable for doing modern mathematics, so we must rectify this somehow.

Russell's own solution to his paradox was to introduce the notion of a type. (What I describe here is the unramified type theory TST, not the type theory of Principia Mathematica.) We start with some basic type $\mathbf{U}_0$ – say, the natural numbers. We define sets whose members are of type $\mathbf{U}_0$ – and this is a new type $\mathbf{U}_1$. We repeat this procedure infinitely, forming at each stage the type $\mathbf{U}_{n+1}$ corresponding to sets of things of type $\mathbf{U}_n$. Thus, we get sets whose members are other sets; on the other hand, it is clear that the universal ‘set’ does not exist in this ontology: if $X$ is a set, then it is of type $\mathbf{U}_{n+1}$ for some natural number $n$, and its members must be of type $\mathbf{U}_n$ – so in particular, $X \notin X$. We could even entirely banish the formula “$X \in X$” because there is no possible assignment of types that makes it a well-formed formula!

Unfortunately, we have had to introduce infinitely many types of sets, and it seems rather complicated to keep track of all these types in practice. Modern set theory resolves this by taking $\mathbf{U}_0$ to be the empty type and collapsing all the higher types into a single type $\mathbf{U}$. Thus, everything in the universe of discourse is a set (but that does not mean all sets are in $\mathbf{U}$!), and it makes sense to ask whether $x \in y$ for any $x$ and $y$ in $\mathbf{U}$. In particular, the once-banished formula $x \in x$ is well-formed again – so again we have to find some other solution to Russell's paradox.

Digging a little bit deeper, we discover that one of the assumptions of the paradox is the naïve axiom of comprehnsion: that is, whenever $\varphi (x)$ is a well-formed formula, then there exists a set $\{ x : \varphi (x) \}$ in $\mathbf{U}$ whose members are precisely those $x$ in $\mathbf{U}$ for which $\varphi (x)$ is satisfied. As such, we must be more careful about the sets we assume are in $\mathbf{U}$. This is where the set–class distinction comes from: in the usual parlance, ‘set’ refers to sets that are in $\mathbf{U}$, and ‘class’ refers to sets whose members are in $\mathbf{U}$ but are not necessarily in $\mathbf{U}$ themselves. To avoid confusion, I will say $\mathbf{U}$-set for the former.

So what should we assume instead of the naïve axiom of comprehension? Quine's New Foundations (NF) offers one option:

Stratified comprehension. Let us say a well-formed formula $\varphi (x)$ is stratified if there is a way to assign types to all the variables appearing in $\varphi (x)$ so that whenever $y \in z$ appears in $\varphi (x)$, $y$ is of type $\mathbf{U}_n$ and $z$ is of type $\mathbf{U}_{n+1}$, and whenever $y = z$ appears in $\varphi (x)$, both $y$ and $z$ are of type $\mathbf{U}_n$. Then, whenever $\varphi (x)$ is a stratified formula, the class $\{ x : \varphi(x) \}$ is a $\mathbf{U}$-set.

Roughly speaking, any set that exists under TST also exists under NF. In particular, the class $\{ x : x = x \}$ is a $\mathbf{U}$-set under NF – so NF admits a universal set. On the other hand, the paradoxical class $\{ x : x \notin x \}$ does not exist in NF, because $x \notin x$ is not a stratified formula. Now, the relative consistency of NF is not well-understood, but the related theory NFU (obtained by allowing $\mathbf{U}_0$ to be non-empty) is known to be consistent relative to ZF set theory. Thus, if we believe ZF is consistent, then we should also believe that there is a consistent set theory in which the universal set exists – in particular, the universal set does not produce a contradiction on its own.

Having mentioned it, I suppose I should also say how comprehension is handled in ZF. We have the following axiom:

Separation. For any $\mathbf{U}$-set $X$, if $\varphi (x)$ is any well-formed formula, the class $\{ x \in X : \varphi (x) \}$ is a $\mathbf{U}$-set.

Obviously, in the presence of a universal set, the axiom of separation is equivalent to the naïve axiom of comprehension, so we had better do something about that.

Regularity. Any $\mathbf{U}$-set $X$ has a member $Y$ such that any member of $Y$ is not a member of $X$. (Equivalently, $X \cap Y = \emptyset$.)

In particular, there is no universal set. It is tempting to call say that the membership relation $\in$ is well-founded on $\mathbf{U}$, but there is a subtlety here: only $\mathbf{U}$-sets are guaranteed to have a $\in$-minimal member. There are still other problems to fix, however – so far, there are no axioms that guarantee our universe $\mathbf{U}$ is non-empty! But that is a story for another day.

Finally, we should discuss formal class–set theories such as von Neumann–Bernays–Gödel (NBG) or Morse–Kelley (MK). In these theories, the universe of discourse $\mathbf{U}$ consists of ‘classes’, and a ‘set’ is defined to be a class that is a member of some class. To avoid confusion, let us say $\mathbf{V}$-class for the former and $\mathbf{V}$-set for the latter. A proper $\mathbf{V}$-class is a $\mathbf{V}$-class that is not also a $\mathbf{V}$-set.

We have a class comprehension axiom governing the formation of $\mathbf{V}$-classes:

Bounded class comprehension. If $\varphi (x)$ is a well-formed formula that does not have any bound variables ranging over $\mathbf{V}$-classes, then the class $\{ x : x \text{ is a } \mathbf{V} \text{-set and } \varphi (x) \}$ is a $\mathbf{V}$-class.

Full class comprehension. If $\varphi (x)$ is any well-formed formula, then the class $\{ x : x \text{ is a } \mathbf{V} \text{-set and } \varphi (x) \}$ is a $\mathbf{V}$-class.

NBG uses the bounded class comprehension axiom, while MK uses the full class comprehension axiom. Either way, we are guaranteed the existence of the $\mathbf{V}$-class $$\mathbf{V} = \{ x : x \text{ is a } \mathbf{V} \text{-set and } x = x \}$$ which contains all $\mathbf{V}$-sets. But is $\mathbf{V}$ itself a $\mathbf{V}$-set? To answer that we need an axiom telling us which $\mathbf{V}$-classes are $\mathbf{V}$-sets.

Limitation of size. Let us say that a bijection is a $\mathbf{U}$-bijection if its graph exists in $\mathbf{U}$, i.e. if it can be defined by a $\mathbf{V}$-class function. A $\mathbf{V}$-class $X$ is a $\mathbf{V}$-set if and only if there does not exist a $\mathbf{U}$-bijection between $X$ and $\mathbf{V}$.

In particular, $\mathbf{V}$ must be a proper $\mathbf{V}$-class. Note that by definition a proper $\mathbf{V}$-class cannot contain itself. Unfortunately, this doesn't answer the question of whether a $\mathbf{V}$-set can be contained in itself. In NBG and MK, this question is settled by the regularity axiom applied to classes:

Class regularity. Any $\mathbf{V}$-class $X$ has a member $Y$ such that any member of $Y$ is not a member of $X$.

Thus, no $\mathbf{V}$-set can contain itself – at least in NBG or MK.

share|improve this answer

I don't entirely understand, "We can clearly define a set of sets. I feel intuitively like we ought to define sets which do contain themselves"

You can define the collection of all sets. It is defined by the formula $x = x$. $V = \{x : x = x\}$. Similarly, you can define the collection of all sets that are not members of themselves. The formula that does this is $x \notin x$. Let $A = \{x : x \notin x\}$. In any structure in the language of set theory, these would correspond to definable classes.

However, both of these are not sets. You are interested in the fact that $A$ is not a set. Suppose that $A$ is a set. You have that $A \in A$ or $A \notin A$. If $A \in A$, then $A$ does not satisfy the formula defining $A$; hence, you $A \notin A$. Contradiction. Now suppose that $A \notin A$. Then $A$ satisfies the defining formula for $A$. So $A \in A$. Contradiction. Since neither can occur, you must have that $A$ is not a set.

Russel paradox is resolved by limiting the comprehension axiom. Instead of all definable classes being sets, the axiom of specification asserts that the intersection of any definable class with a set is a set.

share|improve this answer
    
Do you mean "$x \in x$" where you have "$x = x$"? –  Austin Mohr Aug 15 '12 at 1:41
    
@AustinMohr If you referring to the second sentence of the second paragraph, it should be $x = x$ since I am trying to define the entire universe $V$ here. –  William Aug 15 '12 at 1:54
    
@AustinMohr He's just using a formula (x=x) that is trivially satisfied by every set, so the 'collection' of all that do must be the whole universe. –  Quinn Culver Aug 15 '12 at 5:10
    
I'm also interested in the set $B=\{x:x\in x\}$, and whether it leads directly to a contradiction. I suppose it does since if $A$ is a set then $x\notin B$ is a perfectly good formula and we're back to Russell. But then—what are A and B? Are they "classes"? Is there a thing that prevents us from talking about the class which contains all and only those classes which do not contain themselves? I'm sure I've got some great reading ahead in the other answers that will answer these questions though... –  crf Aug 15 '12 at 7:35

There are two intertwined issues here: first, (Bertrand) Russell's paradox of the "set" of all sets which don't contain themselves, which the question title asks about. This is resolved by the restriction of Frege's naive comprehension axiom to permit only subsets of pre-existing sets.

Second, your question body seems more concerned with the problem of sets which contain themselves. The axiom of foundation AF(or regularity,) which bans such sets, actually is not the resolution of Russell's paradox: if we keep naive comprehension and add AF, the set $S$ of all sets which don't contain themselves will simply become the set of all sets. So it's apparent that $S \in S,$ while AF requires $S \notin S$, so naive set theory with just AF is inconsistent.

So AF isn't sufficient for fixing Frege's set theory. It isn't necessary, either: if Zermelo-Fraenkel set theory in inconsistent with AF removed, then ZF itself is inconsistent. This leaves the way open for alternatives. Aczel did the canonical work on this with his anti-foundation axiom AFA. Loosely speaking, this defines sets as things which can be broken down into sets, rather than built up from sets as with AF. The upshot is that sets exist which contain themselves, while the theory maintains the same consistency strength as ZF. So, the answer to your question whether a set can contain itself is "no" in standard set theory, but "yes" in general.

share|improve this answer

There's a lot of interplay between set theory and first-order logic. A system of set theory is a list of first-order axioms (which 'live outside' the system of set theory!), so for example, naive set theory might have axioms like:

1) if two sets $x$ and $y$ have the same elements they are the same sets (the axiom of extensionality). in first-order language, this might be written as $(\forall x,y)(\forall z ((z \in x) \iff (z\in y)) \iff (x=y)$

2) for any first order formula with one free variable there is a set of objects which satisfies that formula (naive comprehension).

However, this leads to Russell's paradox, so we instead restrict the number of sets we consider to only have well-founded sets, that is, sets for which $x \neq \{x\}$ (or sets which are not members of themselves). This leads to Zermelo-Fraenkel set theory, and the important thing here is that we restrict the axiom scheme of comprehension so that we cannot ask for a set of all things which satisfy a first-order formula.

(it is interesting to note that originally Zermelo tried to code $0$ as $\emptyset$, 1 as $\{\emptyset\}$, 2 as $\{\{\emptyset\}\}$ etc etc, and $\omega$ as $\{ \dots\{\emptyset\}\dots\}$, which would have violated foundation)

We can, however, consider a class of all sets which satisfy a first-order formula. So, for instance, the formula $\varphi$ with one free variable $x$ stating $(x=x)$, and this is satisfied by all sets, so the class corresponding to $\varphi$ is the class of all sets. Note that this is not a set, as we cannot reach it by the axioms of ZFC - it lives 'outside ZFC' as it were. So, to recap, a class is an equivalence class (this is not circular!) of sets satisfying a first-order formula, not necessarily constructable inside our set theory.

share|improve this answer
    
Okay so, we do outlaw sets which contain themselves as elements? Is this justified only because it prevents us from defining a set which contains all and only sets of which it is a member? Actually, how is that even prevented by this restriction? –  crf Aug 14 '12 at 22:13
    
@crf The axiom of foundation implies that that there are no sets which contains themselves as elements. This does not prevent you from showing that $\{x : x \notin x\}$ is a set. The axiom of specification prevent you from proving that the above is a set. –  William Aug 14 '12 at 22:30
    
Yes, I should probably have added that what stops Russell's paradox in ZFC (or how ZFC tries to stop Russell's paradox) is restriction of comprehension to replacement and separation. –  Kris Aug 15 '12 at 3:09
    
@William so the axiom of foundation basically says $\{x:x\in x\}$ is not a set. You mention we need the axiom of specification in order to show that $\{x:x\notin x\}$ is not a set. Why do we need both axioms? If we outlaw $\{x:x\notin x\}$ axiomatically, doesn't that prevent contradictions arising out of $\{x:x\in x\}$? –  crf Aug 15 '12 at 7:41
    
@crf Your statement isn't quite true; the axiom of foundation says that it is not the case that $x\in x$ for any set $x$, but that's different than saying that the collection $\{x:x\in x\}$ isn't a set. What AF says is that that collection is empty - that no set satisfies the condition - but the empty collection is in fact a perfectly good set - it's the empty set $\emptyset$. –  Steven Stadnicki Aug 15 '12 at 18:07

The difference between sets and classes is subtle. It arises because in the naive approach to set theory, where you don't define what a set is nor axiomatize what you can and can't do with them (and instead just pretend everybody agrees on what a set is and just hope all is well) leads to the famous Russell's Paradox: A set $R$ that satisfies the contradictory assertion $R\in R$ and $R\notin R$.

There are many ways to deal with that problem in the world of axiomatic set theory. Since it is only certain sets that lead to such a contradiction one way out of the paradox is to exclude these pathological entities. But, that means you can no longer just form a set by the familiar construction of conjuring it by collecting all those things that satisfy some nice formula. The reason is that you don't a priori know if that entity that will be defined is one of those pathological things you cast out.

So what happens is that you must be more careful about the axioms of how sets can be manipulated and you find yourself calling 'sets' less entities then what you (at least think) that you can define. Those things that you can define but you cast away as not sets are called proper classes. The rest are sets (and classes). It is not always easy to determine if something that looks harmless is a proper class or not. For instance, the collection of all singleton sets is a proper class.

This is just one way of dealing with Russell's Paradox. There are others within classical axiomatic set theory, also ones that don't introduce a distinction between sets and classes (i.e., everything in the model is a set (but not everything you can imagine will be in the model)). Another way to address the paradox is by reconsidering our problem with the (what I will now call 'apparent') paradox: $R\in R$ and $R\notin R$. Namely, in classical logic it is well known that from the provability of a contradiction, such as Russell's Paradox, every assertion, such as "I am the Queen of England", can be proven. However, one might object that such an implication is not material leading one to consider a different kind of logic than the classical one. In the same vein, one might actually not be too worried by the apparent paradoxical nature of a statement of the form $P \wedge \neg P$, if that contradiction is not material to what interests you most. This approach will lead to paraconsistent logic.

share|improve this answer

crf wrote:

"I understand that all sets are classes, but that there exist classes which are not sets, and this apparently resolves Russell's paradox...."

You don't need classes to resolve Russell's paradox. The key is that, for any formula P, you cannot automatically assume the existence of $\{x | P(x)\}$. If $P(x)$ is $x\notin x$, we have arrive at Russsell's Paradox. If $P(x)$ is $x\in x$, however, you don't necessarily run into any problems.

So, you can ban the use of certain formulas, hoping that the ban will cover all possibilities that lead to a contradiction. My preference (see http://www.dcproof.com ) is not to assume a priori the existence of any sets, not even the empty set. In such a system, you cannot prove the existence of any sets, problematic or otherwise. You can, of course, postulate the existence of a set in such a system, and construct other sets from it, e.g. subsets, or power sets as permitted.

share|improve this answer

Disclaimer: I am very far from any level of expertisa on logic or set theory, so what I've written below should be taken as my philosophical (or metamathematical), rather than mathematical answer.


I think the fundamental source of confusion is that, mathematically, it is in fact NOT clear what sets are or why they are. Sure, there are a number of axiomatizations (which tell you how sets ought to relate to one another), but an axiomatization can come only after an intuition about what the objects in question ought to be. For example, Euclidean geometry has multiple axiomatizations as well, and it cannot be said that one is a TRUE axiomatization. Rather, they all satisfy certain basic properties which we find intuitively should hold, i.e. intuition ought to exist before axiomatization. On the other hand, intuition can be refined by an attempt to axiomatize it (e.g. we really CANNOT omit the parallel postulate, etc.)

So a good question to ask yourself is what, if any, is the intuition for what a set ought to be? An even better question is to ask yourself what questions, if any, should the notion of a set allow us to answer (it is clear that geometry allows us to ask (and often answer) intuitively geometric questions, and that algebra allows us to ask (and sometimes answer) intuitively numeric questions. What kind of questions do we want sets to answer?

What do we use sets for? We use sets, naively, as notation. In common mathematical practice, sets are just a shorthand for collecting elements that satisfy a certain property (e.g. the "set" U of all sets, the "set" NO of all sets not containing themselves). How would you use these? Well, you would roughly use these to pick out elements, e.g. if I want a set that does not contain itself, instead of writing that all the time, I would just pick an element of the "set" NO. Would I ever consider the whole set? Maybe if I wanted to do some comparisons regarding which set had more stuff in it (was of larger cardinality), maybe for something else.

EDITED: What is the problem with Russel's paradox (in ZFC)? The problem is the following: suppose that S is a set. Then let V be the set of elements of S which do not contain themselves (this relies on ability to construct subsets of sets satisfying any formula, i.e. restricted comprehension). Then if V is in V, we get the genuine contradiction that V is not in V. Hence V is not in V. Since it is not an element of itself, then it would be in V if it were in S, but it's not in V, so it's not in S.

Hence, for any set S there exists a set V that is not an element of itself, and that is also not an element of S (as a direct consequence of the restricted comprehension axiom allowing us to make a set $V=\{s\in S\colon\phi(s)\}$ where $\phi$ is any formula). END EDIT.

But notice that I can still talk about elements of S that do not contain themselves. In general I can still talk about sets that do not contains themselves (non-sets obviously don't contain themselves). I can take one of them, and prove things about it. What I cannot do is talk about ALL of them, at the same time (not that sets in ZFC have that many properties, other than cardinality, and maybe ordinality).

What about classes then? People talk about "the proper class" of the set of all sets, what is that? Kenneth Kunen wrote in The Foundations of Set Theory (I suspect with tongue firmly in cheek) that

"Formally, proper classes do not exist, and expressions involving them must be thought of as abbreviations for expressions not involving them."

What this means is that the set of all sets (or the set of all sets not containing themselves) are proper classes in the sense that there exists a formula "x contains itself" or "x does not contain itself", and that we can surely talk about elements of the proper class, i.e. sets that satisfy or do not satisfy the formula, but that proper classes by themselves are NOT mathematical objects: they are only notational convenience. (it is sometimes easier to say x in NO rather than x is a set that does not contain itself).

But wait, didn't I say that that's how we use sets (as notational convenience)? Yes, that's how we use sets naively. But notation is not a priori a mathematical object, it is an object of social convention (even if between mathematicians). What is the distinction between sets and proper classes then, if they fulfill the same function in daily practice? The difference is that sets CAN be made into mathematical objects (what is a mathematical object? It seems currently that it is an object that can be specified in a formal language which mirrors the intuitive properties we want, e.g. subsets and power sets, and which has no contradictions as far as we know) by any of the axiomatizations we have (and according to the different axiomatizations, we get seemingly different features for sets), while proper classes CANNOT be made into mathematical objects.

share|improve this answer
    
Vladimir wrote: "What is the problem with Russel's paradox (in ZFC)? The problem is the following: suppose that $S$ is a set. Then let $V$ be the set of subsets of $S$ which do not contain themselves." This is not the form that Russell's Paradox takes. RP does not talk about subsets. There is in fact no problem with this particular construction. You are correct that $V$ is neither an element of itself nor $S$. But I don't think you will be able to prove that $V$ is an element of itself or $S$ to obtain a contradiction. –  Dan Christensen Aug 17 '12 at 5:07
    
Vladimir wrote: "$V$ is not a subset of $S$." Do you mean $V$ is not an element of $S$? –  Dan Christensen Aug 17 '12 at 5:23
    
Oops, I screwed up. Thanks for pointing out my mistake, Dan. The correction is that V should be defined as the set of elements of S that do not contain themselves, not subsets (if s in S is not a set, then vacuously s is not contained in itself and hence is in V). –  Vladimir Sotirov Aug 17 '12 at 19:49

Surprisingly, Russell's paradox occurs even in the absence of any axioms! We don't even need Extensionality - so its not a quirk of modern set theory. To see this, suppose we have a two-place relation $\in$ defined on a domain of discourse whose elements will be called 'sets'. Now assume for a contradiction that for some 'paradoxical' set $R$ it holds that $$\forall x(x \in R \leftrightarrow x \notin x).$$

In words, this reads, 'For all sets $x$ it holds that $x$ is an element of $R$ if and only if $x$ is not an element of itself.' We therefore conclude:

$$R \in R \leftrightarrow R \notin R$$

Contradiction! So no such $R$ exists. But the point is, this argument works irrespective of your axioms.

share|improve this answer
2  
The point of the answers is not that $R$ cannot exist (which, as you say, is straightforward), but rather that we need a workaround, so we can still have a theory of sets rich enough to do something with it but not so unwieldy that would allow us to conclude that $R$ exists (and therefore be inconsistent). What the answers are trying to do is to explain how the standard restrictions of Zermelo's, Quine's, etc, (attempt to) achieve this balance. –  Andres Caicedo Jun 23 '13 at 5:44
    
@Andres, I guess our readings of the original question are different. My reading is: which combination of axioms rules out the existence of $R$? –  goblin Jun 23 '13 at 6:13

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.