36
$\begingroup$

In Russell's famous paradox ("Does the set of all sets which do not contain themselves contain itself?") he obviously makes the assumption that a set can contain itself. I do not understand how this should be possible and therefore my answer to Russell's question would simply be "No, because a set cannot contain itself in the first place."

How can a set be exactly the same set as the one that contains it? To me it seems unavoidable that the containing set will always have one more additional level of depth compared to all the sets which it contains, just like those russian matryoshka-dolls where every doll contains at least one more doll than all the dolls inside it.

Of course one can define something like "the set of all sets with at least one element" which of course would include a lot of sets and therefore by definition should also include itself, but does it necessarily need to include itself just because its definition demands so? To me this only seems to prove that it's possible to define something that cannot exist beyond its pure definition.

$\endgroup$
  • 15
    $\begingroup$ The first sentence in the question "... obviously makes the assumption ..." is wrong. Russell's question makes sense whether or not there are sets that contain themselves. In fact, in some set theories (like Quine's "New Foundations") there are such sets (like the set of all sets), while in other set theories (like ZF) there are no such sets. $\endgroup$ – Andreas Blass Dec 1 '14 at 18:03
  • 6
    $\begingroup$ Is this a little bit like asking, “How can the word ‘dictionary’ be listed in the dictionary?”? $\endgroup$ – Scott Dec 1 '14 at 19:42
  • 7
    $\begingroup$ Well, there's an obvious response to your simple answer: If the set of all sets that do not contain themselves does not contain itself, as you claim, then it must contain itself since that's its criteria for inclusion. So your answer is self-contradictory. In fact, your claim that a set cannot contain itself is self-contradictory precisely because it leads to the contradiction above. $\endgroup$ – David Schwartz Dec 1 '14 at 20:55
  • $\begingroup$ In your example of all sets with at least one element (i.e. all sets except the empty set), what the Russell paradox suggests is that the collection of such sets is not a set. One way of thinking about such a big collection (proper class in the jargon) and avoiding the paradox is that it is too big to be an element of anything else. $\endgroup$ – Henry Dec 1 '14 at 22:11
  • 7
    $\begingroup$ @Scott I don't think so. Because the word "dictionary" is not the same as the dictionary whereas the set containing (or not containing) itself is supposed to be nothing else but the set itself. $\endgroup$ – jimmyorpheus Dec 2 '14 at 2:26
39
$\begingroup$

Yes, this is an issue.

Naively, this issue cannot be dealt with, and we'll get to that in a moment. But in 1917 mathematicians already noticed that "normal sets" do not contain themselves, and in fact have an even stronger property. Namely, there are no infinite decreasing chains in $\in$, so not only that $a\notin a$ it is also true that $a\notin b$ whenever $b\in a$, and that $a\notin c$ whenever for some $b\in a$ we have $c\in b$; and more generally there is no sequence $x_n$ such that $x_{n+1}\in x_n$ for all $n$.

This is exactly what the axiom of regularity came to formalize. It says that the membership relation is well-founded, which assuming the axiom of choice, is equivalent to saying that there are no decreasing chains. In particular $A\notin A$, for any set $A$.

But we know, nowadays, that it is consistent relative to the other axioms of modern set theory (read: $\sf ZFC$) that there are sets which include themselves, namely $x\in x$. We can even go as far as having $x=\{x\}$. You can even arrange for infinitely many sets of the form $x=\{x\}$.

This shows that naively we cannot prove nor disprove that sets which contain themselves exist. Because naive set theory has no formal axioms, and is usually taken as a subset of axioms which include very little from $\sf ZFC$ in terms of axioms, and certainly it does not include the axiom of regularity.

But it also tells us that we cannot point out at a set which includes itself, if we do not assume the axiom of regularity. Since these sets cannot be defined in a nontrivial way. They may exist and may not exist, depending on the universe of sets we are in. But we do know that in order to do naive set theory and even more, we can safely assume that this situation never occurs.

$\endgroup$
  • 12
    $\begingroup$ An answer with class. $\endgroup$ – copper.hat Dec 1 '14 at 18:07
  • 9
    $\begingroup$ @copper.hat: Like the class of all sets which do not contain themselves? $\endgroup$ – Asaf Karagila Dec 1 '14 at 18:10
  • $\begingroup$ :-) ${}{}{}{}{}{}$ $\endgroup$ – copper.hat Dec 1 '14 at 18:15
  • $\begingroup$ @AsafKaragila: Does the same result holds with NBG?? $\endgroup$ – Bumblebee Jun 11 '17 at 20:40
  • $\begingroup$ Typo in the 5th line? "...and that $a \notin c$ whenever for some $b \in a$ we have $a \in b$." Should it be "...$a \notin c$ whenever for some $b \in a$ we have $c \in b$"? Thanks for a wonderful answer. $\endgroup$ – Error 404 Jul 8 '17 at 13:53
10
$\begingroup$

I guess you are asking what makes a great man trouble himself with such a trivial problem. The following excerpt is Russell's own explanation of his mental journey:

I was led to this contradiction by considering Cantor's proof that there is no greatest cardinal number. I thought, in my innocence, that the number of all the things there are in the world must be the greatest possible number, and I applied his proof to this number to see what would happen. This process led me to the consideration of a very peculiar class. Thinking along the lines which had hitherto seemed adequate, it seemed to me that a class sometimes is, and sometimes is not, a member of itself. The class of teaspoons, for example, is not another teaspoon, but the class of things that are not teaspoons, is one of the things that are not teaspoons. There seemed to be instances that are not negative: for example, the class of all classes is a class. The application of Cantor's argument led me to consider the classes that are not members of themselves; and these, it seemed, must form a class. I asked myself whether this class is a member of itself or not. If it is a member of itself, it must possess the defining property of the class, which is to be not a member of itself. If it is not a member of itself, it must not possess the defining property of the class, and therefore must be a member of itself. Thus each alternative leads to its opposite and there is a contradiction.

At first I thought there must be some trivial error in my reasoning. I inspected each step under logical microscope, but I could not discover anything wrong. I wrote to Frege about it, who replied that arithmetic was tottering and that he saw that his Law V was false. Frege was so disturbed by this contradiction that he gave up the attempt to deduce arithmetic from logic, to which, until then, his life had been mainly devoted. Like the Pythagoreans when confronted with incommensurables, he took refuge in geometry and apparently considered that his life's work up to that moment had been misguided.

Source:Russell, Bertrand. My Philosophical development. Chapter VII Principia Mathematica: Philosophical Aspects. New York: Simon and Schuster, 1959

$\endgroup$
9
$\begingroup$

The reason we've learned how to develop logic and set-theroy with the "depth" thing is precisely to avoid the paradoxes of naive set theory.

One of the key ideas that naive set theory runs with is the idea of equating a logical predicate with the set of all things satisfying the predicate.

This is, I believe, actually an ancient philosophical idea: "What is blue?" "The collection of all things that we would call blue."

With the idea that sets can be used to translate logical notions into actual mathematical objects (sets) that we can then reason with, Cantor gave us (unrestricted) comprehension: for any logical predicate $\varphi$, there is a set of all things satisfying $\varphi$. In class-builder notation, Cantor said the following is a set:

$$ \{ x \mid \varphi(x) \} $$

There is nothing here to prevent a set from containing itself. In fact, we can prove there are sets containing themselves: if you select $\varphi$ to be the predicate "___ is a set", then unrestricted comprehension tells us that there is a set of all sets. And since it is a set, it must be a member of itself.


Zermelo's axioms for set theory are based on constructions; e.g. the axiom of pairing says that if $x$ and $y$ are sets, then $\{ x,y \}$ is a set. All sets we can explicitly construct using these constructions do have 'depth', but Zermelo's axioms are lacking any sort of induction principle that would allow us to prove that all sets are 'constructible', or even that they have a 'depth'.

And, in fact, Z set theory is consistent with the existence of sets that contain themselves. In fact, if you remove the axiom of foundation from ZFC, then that too is consistent with the existence of sets that contain themselves.

$\endgroup$
  • 3
    $\begingroup$ Cantor? Not Frege? $\endgroup$ – Asaf Karagila Dec 1 '14 at 18:20
  • $\begingroup$ @Asaf: Huh, I thought Cantor was mostly responsible for naive set theory. I stand corrected. $\endgroup$ – Hurkyl Dec 2 '14 at 6:35
  • $\begingroup$ Hurkyl, that might be, but as far as I understood it was Frege who first suggested comprehension. I'm a bit fuzzy on that part in the history of set theory, so I might be wrong. It's worth checking out somewhere. $\endgroup$ – Asaf Karagila Dec 2 '14 at 7:03
1
$\begingroup$

This answer is not entirely my own ideas and I got some of my ideas from Asaf Karagila's answer. I see a problem with their answer so I wrote my own answer that's similar to that answer that avoids that problem.

Naive set theory is contradictory. In Naive set theory, you can prove that there is a set of all sets that don't contain themselves and if it contains itself, it doesn't and if it doesn't, it does. There is no contradiction. Rather, Naive set theory is incorrect. It can be proven that there is no set of all sets that don't contain themselves. There's no reason to assume that in order to define the set of all sets that don't contain themselves, you don't first have to define the set of all sets that don't contain themselves. There's no reason to assume any set contains itself either. Although it is not provable that there is a set that contains itself, it is not provable that no set contains itself either. Zermelo-Fraenkel set theory has been proven to not be contradictory but it can't be proven that everything provable in that theory is true. If you accept that theory, you can prove in that theory using the axiom of regularity that no set contains itself.

$\endgroup$
  • $\begingroup$ While technically correct, yes, naive set theory is inconsistent, it misses the actual point of the question. I am guessing you have no experience teaching set theory in a naive context. There are pedagogical qualities beyond the technical ones. $\endgroup$ – Asaf Karagila Aug 30 '17 at 19:20
  • $\begingroup$ I learned a bit about Zermelo-Fraenkel set theory and New Foundations but I am not a teacher. If you restrict which statements describable in Naive set theory you use and can only deduce a statement from the restricted set of statements you're using when it follows from other statements from the restricted set of statements you already deduced, then you can't derive a contradiction. $\endgroup$ – Timothy Aug 30 '17 at 19:39
  • $\begingroup$ There is a good amount of pedagogical benefits in sometimes ignoring the inconsistency of naive set theory. $\endgroup$ – Asaf Karagila Aug 30 '17 at 19:48
0
$\begingroup$

For me, it is not possible to have "a set of all sets" (include itself), but it is possible to have "a set of all other sets" (other than itself). It is necessary to restrict conceptualization only in term of non-self-contradictory. Because, is it meaningful to make a concept such as "even odd-numbers"?

Since, there's no possible for self-contradictory concepts to exist, then, it shouldn't be conceptualize in the first place. And, in my opinion, "a set of all sets" (include itself) is one of self-contradictory concept, which shouldn't be conceptualize in the first place, rather than presuppose its existence and try to figure out the consequences of it.

About what Russell says, "The class of teaspoons, for example, is not another teaspoon, but the class of things that are not teaspoons, is one of the things that are not teaspoons." My answer is, although "the class of things that are not teaspoons" is also not teaspoons, but it is in different level than "the things that are not teaspoons", in this case we should differentiate between "things" and "class of things".

Further more, Russel says, "There seemed to be instances that are not negative: for example, the class of all classes is a class." Again, here we should differentiate between "The class of things" and "The class of classes". Because it is in different level, so that shouldn't be put in the same class.

And if we could maintain this principle, then the next point that Russel says won't be confusing either. Russel says, "The application of Cantor's argument led me to consider the classes that are not members of themselves; and these, it seemed, must form a class." Now, since we still differentiate the differentiation of different levels, then "The classes that are not members of themselves" is different than "these, it seemed, must form a class", so that the question that arise after that is not necessarily arisen, which is "whether this class is a member of itself or not." Because, the answer is clear: "this class" that contain "the class that are not members of themselves" is contain "the class that are not members of themselves", and not contain itself.

$\endgroup$
  • $\begingroup$ A very honest answer - which happens to be seemingly logical on the surface, but I'm afraid you can't stop people thinking abstractly. In fact that's all mathematics is about, so when you say we should differentiate between "The class of things" and "The class of classes" I'd say that's wrong, or at least it's limiting. Take a look at the ZFC and Category Theory and you'll find some answers to this (then you would enjoy the accepted answer here as much as I did). $\endgroup$ – Nader Ghanbari Mar 5 '17 at 4:44
  • $\begingroup$ This answer is useless. It doesn't answer the question. A good answer might answer why a set can contain itself or why one can't. Your first sentence explains why a set could contain all sets but itself. That claim turns out to be incorrect in Zermelo-Fraenkel set theory because by the axiom of union, if that set exists, so does the universal set. Also, the whole answer is gibberish. $\endgroup$ – Timothy Oct 17 '17 at 18:42
-1
$\begingroup$

A non expert reflection.

Russell did not make the assumption that a set could contain itself. Of technically reasons he elaborated with a construction "of all sets that not is a member of itself". Because with this technique he could prove that something was wrong in the previous notations of sets, especially with some ideas of Frege.

There is no canonical or categorical set theory and it's certainly possible to define a set theory where certain sets contain themselves as elements, even though axiomatic set theories use to pay attention to find out axioms to prohibit this. In no set theory it's wrong to claim that 'x do not belong to x'. And you can claim that without having to claim that there are sets that belongs to themselves.

There are no sets i nature other than groupings in human mind, so there are no real objects to model. In my mind a set is some objects with identity, thought of as surrounded by a fence. The objects could be inside or outside the fence. But this is a very naive picture that at most works for finite sets. And of course, in my definition a set could not contain itself.

But mathematicians are free to define whatever they manage to define and there are persons interested in set-like objects that isn't prohibited to contain them self.

In my opinion the problems in set theory emanates from unrestricted use of the word "all" and not from modelling of sets as such.

$\endgroup$
  • $\begingroup$ Excellent point. "All" is very tricky. $\endgroup$ – George Chen Dec 2 '14 at 23:06
  • $\begingroup$ This answer doesn't properly explain why you for some properties, there might not necessarily exist a set of all things satisfying that property and can't be improved into a good answer without being so different than its current form. $\endgroup$ – Timothy Oct 17 '17 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.