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.

Russell's paradox is about a set not in a set itself - but don't all sets are not in sets themselves? $x \in x$ is not true, as {$1,2,3$} $\in$ {$1,2,3$} is not true..

Can anyone explain this?

share|improve this question
1  
All familiar sets $x$ certainly have the property that $x\not\in x$. If the collection $V$ of all sets is a set, then the set of all $x$ such that $x\not\in x$ is a set. And then Russell's argument leads to a contradiction. One way out is to try to restrict the principles of set construction so that the collection of all sets will not be a set. But at the time of Russell's Paradox, there was the belief that any collection could be called a set, and manipulated using set-theoretic tools. –  André Nicolas Sep 18 '12 at 4:59
add comment

3 Answers 3

Russell's paradox derives a contradiction from the assumption that there exists a set containing all sets which don't contain themselves. Call such a set S. If S does not contain itself as a set, then by definition S should be an element of S. That is, S $\notin$ S implies S $\in$ S, a contradiction. If, on the other hand, S contains itself, then by our definition of S, S $\notin$ S, another contradiction. In either case, our assumption that there could be a set containing all sets which don't contain themselves leads to a contradiction, hence no such S can exist.

This paradox implies that there can be no such thing as a "set of all sets", since such a set would contain all possible sets, including the set S above.

share|improve this answer
add comment

Most current axiomatic formulations of set theory include an axiom, called Regularity, which precludes the possibility of sets containing themselves as members. Even more, this axiom even precludes the possibility of finite sequences of sets that satisfy the cyclic membership relation $$x_1 \in x_2 \in \cdots \in x_n \in x_1.$$

So why the fuss about Russell's paradox? Simply because set theory did not spring fully formed from the head of Cantor like Athena from the head of Zeus. Cantor's original definition of a set was (in English translation):

By a set we mean any collection $M$ into a whole of definite, distinct objects $m$ (which are called the elements of $M$) of our perception or of our thought.

From such a broad and vague definition one can clearly think of a set of all sets (which would contain itself). The set of all infinite sets (which also contains itself). One could even conceive of a set $x$ containing only itself as a member: $x = \{ x \}$. And from there it is not too far to consider the set of all sets which do not contain themselves. It really was in search of ways to avoid such paradoxes that early set theorists began to think of the explicit axiomatic (as opposed the naive) set theories we have today.

(As Brian mentions in his learned answer, the Axiom of Regularity does not itself rid us of Russell's paradox. In fact, this axiom came rather late, being introduced by von Neumann in 1925. I mention it because (assuming contradictions cannot be found) it does imply certain pathological collections cannot exist as sets.)

share|improve this answer
add comment

Indeed it’s a consequence of one of the axioms of ZF (the axiom of regularity, or foundation) that $\forall x(x\notin x)$. This has nothing to do with Russell’s paradox, however. Russell’s paradox is a consequence of the seemingly reasonable notion that if $\varphi$ is a property of sets, we ought to be able to form the set of all sets that have the property $\varphi$: in symbols, the collection $\{x:\varphi(x)\}$. But look what happens when we take $\varphi(x)$ to be the property $x\notin x$. We then form the collection $y=\{x:x\notin x\}$, and then ask whether $y\in y$ or not. If $y\in y$, then by the definition of $y$ it must be the case that $y$ has the property $\varphi$, i.e., that $y\notin y$. OOPS! That’s an obvious contradiction. Okay, so $y\notin y$. But then $y$ has the property $\varphi$, so we did put $y$ into $y$: that also is a contradiction. Since $y$ either is or is not a member of the set $y$, and yet each of these choices leads to a contradiction, we’re in trouble.

ZF set theory gets around this difficulty by not allowing what’s called unrestricted comprehension: it doesn’t permit us to form a ‘set’ $\{x:\varphi(x)\}$ for any old property $\varphi$. It allows us to collect into a set only those members of an existing set that have a property: $\{x\in y:\varphi(x)\}$. In particular, for any set $y$ we can form $\{x\in y:x\notin x\}$, and we can prove as a consequence of the axiom of regularity that this set is simply $y$ itself. But we can’t form $\{x:x\notin x\}$.

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.