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 am trying to understand Russells's paradox

How can a set contain itself? Can you show example of set which is not a set of all sets and it contains itself.

share|improve this question
1  
The set of all possible things is an element of itself since it itself is a thing...but, of course, this is precisely what Russell's paradox came to point at and since then there is no set of all sets or set of all things or weird stuff like that. Thus, within the usual ZF (with AC or without) logical system, we cannot have stuff as above. –  DonAntonio Dec 8 '12 at 15:37
1  
In mathematics, sets that are elements of themselves don't come up in practice. They are just a problematic, theoretical possibility in discussions of things like RP. Various convoluted workarounds for them have nevertheless been put forward, e.g. type theory, some axioms of ZFC. But IMHO, they are overkill. You just have to make sure you cannot prove $\exists k\forall x (x\in k\leftrightarrow\neg x\in x)$ in the set theory you adopt. There are simpler, more natural ways than TT or ZFC. –  Dan Christensen Dec 10 '12 at 14:42

4 Answers 4

up vote 12 down vote accepted

In modern set theory (read: ZFC) there is no such set. The axiom of foundation ensures that such sets do not exist, which means that the class defined by Russell in the paradox is in fact the collection of all sets.

It is possible, however, to construct a model of all the axioms except the axiom of foundation, and generate sets of the form $x=\{x\}$. Alternatively there are stronger axioms such as the Antifoundation axiom which also imply that there are sets like $x=\{x\}$. Namely, sets for which $x\in x$.

For the common mathematics one can assume the foundation is based on ZFC or not (because there is a model of ZFC within a model of ZFC-Foundation), so there is no way to point out at a particular set for which it is true.

Also interesting:

  1. Is the statement $A \in A$ true or false?
  2. Where is axiom of regularity actually used?
share|improve this answer
    
And as Russell showed, well-foundedness is also closely related to typeability in a system without recursive types. –  Jon Purdy Dec 8 '12 at 20:19

$x = \{ x \}$ ...

... but actually one of the axioms of ZFC (the "usual" axioms of set theory) has the immediate consequence that no set has itself as a member.

share|improve this answer

Aczel's anti-foundational axiom is a classic example: http://en.wikipedia.org/wiki/Aczel%27s_anti-foundation_axiom

"It states that every accessible pointed directed graph corresponds to a unique set. In particular, the graph consisting of a single vertex with a loop corresponds to a set which contains only itself as element, i.e. a Quine atom."

share|improve this answer

Example, $R=\{{R,2,4,6,8,10,...\}}$ it can just be written explicitly like this.

share|improve this answer
    
That looks just like something of the form: $$\{\{\cdots \{\{x\}\}\cdots \}\}$$ which seems to be frowned upon by set theorists. –  Pedro Tamaroff Dec 8 '12 at 15:43
1  
@PeterTamaroff: Not frowned upon as much as just violating regularity. A set containing itself as an element is by definition not well-founded. Russel's paradox is a paradox in naive set theory, so without anything like the axiom of foundation. There are axiomatizations on set theory that allow regularity to be violated. One of the most famous axioms which imply that sets like the one proposed exist is Aczel's anti-foundation axiom (and its various flavours). –  tomasz Dec 8 '12 at 17:24
1  
@Peter: To add on tomasz' comment, regardless to well-foundedness the paradox shows that there is a definable collection which is not a set. This doesn't even have to be the collection of all well-founded sets, but it is not a set. If the universe is not well-founded it is possible that the class defined is not all the sets in the universe. –  Asaf Karagila Dec 8 '12 at 17:50
    
OK. ${}{}{}{}{}{}$ –  Pedro Tamaroff Dec 8 '12 at 17:51

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.