1
$\begingroup$

At uni, I learned that a set can't contain* itself years ago and this still bothers me to this day. I'm posing this question because I want to understand why this is. Obviously, what we call a set and what we don't isn't a mathematical fact but one made up by humans. So it was decided that it's a good idea to call a set what we call a set today, and only that.

When googling for reasons, I basically only came across Russell's paradox where from $ R = \{ x \mid x \not \in R \} $, you can follow that $ R \in R \iff R \not \in R $. I don't see a problem with this paradox existing.

To me, the definition of $R$ just doesn't make sense. That doesn't mean it's a good idea to not call anything that contains itself a set.

No computer scientist would say that you can't call something a Turing machine if it simulates itself, just because you can construct the halting problem from that. It's just that a machine that simulates itself and then returns the opposite of what its simulation returns doesn't make sense and neither does a machine which simulates itself and then goes to an infinite loop iff its simulation halted.

Plus, I think that there are useful "sets" which contain themselves. For example, the domain or codomain of the identity function. I have no idea how that even is defined as sets can't contains themselves. It would be great for my understanding if you answered that along the main part of this question.

 * By "contain" I mean as an element, not as a subset.

Edit:

  • When I write "contains", I obviously mean as an element, not as a subset, as every set is a subset of itself. Plus, this should be really evident from the first formula.
  • The answers below the question this question has been marked as a possible duplicate of don't answer my question. I want to know why sets aren't required to be properly defined as I don't think mandating that sets must not contain themselves doesn't solve the problem but only solves a few ones and creates now ones. I'd call a set properly defined if for each object, it can be decided whether it's in the set. As far as I can see, there is no implication to or from the definition where sets cannot contain themselves.
$\endgroup$
14
  • 3
    $\begingroup$ Just to be clear, Russel's Paradox is about something else. It holds that no set can be put in bijection with its own power set. This is intuitively clear for finite sets (if a set has $n$ elements, its power set has $2^n$ elements) but somewhat surprising for infinite sets. $\endgroup$
    – lulu
    May 30, 2017 at 22:20
  • 2
    $\begingroup$ @lulu by containing OP means , as an element of set not its subset. $\endgroup$
    – Red shoes
    May 30, 2017 at 22:22
  • 1
    $\begingroup$ The problem with a paradox existing in a formal system is that if there is a single statement that can be proven both true and false, then every statement can be proven both true and false and the system is useless. $\endgroup$
    – Jair Taylor
    May 30, 2017 at 22:29
  • 1
    $\begingroup$ You can prove anything using proof by contradiction. This is the principle of explosion. Suppose you want to prove some $P$. The proof goes: Suppose $P$ is false. Note that Russell's paradox occurs. Therefore, "$P$ is false" must be false. So, $P$. $\endgroup$
    – Jair Taylor
    May 30, 2017 at 22:30
  • 1
    $\begingroup$ @lulu en.wikipedia.org/wiki/Russell's_paradox doesn't contain the word "bijection" a single time. What you describe sounds like Cantor's theorem. $\endgroup$
    – UTF-8
    May 30, 2017 at 23:31

2 Answers 2

Reset to default
2
$\begingroup$

The fact that a set can't contain itself follows from the axiom of regularity. See here: https://en.wikipedia.org/wiki/Axiom_of_regularity They give a nice brief proof of this fact. This does not have anything to do with Russell's paradox.

With regards to Russell's paradox: you are on the right path. The whole problem is that it is a bad idea to call "everything" a set. Russell's paradox arises exactly when you do this: Assume that any set-theoretic formula defines a set. A sketch would be: if all formulas allow you to define sets, then $A=\{x\notin{x}\}$ is a set. Now this leads to $A\in{A}$ if and only if $A\notin{A}$. This is a contradiction ($p$ if and only if $\neg p$ is contradictory). The modern set theory axioms get around this by not calling "everything" a set: See https://en.wikipedia.org/wiki/Axiom_schema_of_specification.

Per Eric's comments I have added some more text which hopefully lessens confusion.

$\endgroup$
9
  • $\begingroup$ @EricWofsey: I never claimed it did. The OP has asked many different questions. $\endgroup$
    – user185596
    May 30, 2017 at 22:46
  • 1
    $\begingroup$ Afaik, the axiom of regularity is the very thing that mandates sets not containing themselves. It doesn't provide a reason. $\endgroup$
    – UTF-8
    May 30, 2017 at 23:35
  • $\begingroup$ But there can still be paradoxical sets. Wouldn't it be a better idea to require all sets to be properly defined? If you can't decide for all objects whether they are an element of the set, it's not properly defined. There still are sets which aren't properly defined. That's what the axiom of regularity tries to achieve, right? (I might be misunderstanding this.) $\endgroup$
    – UTF-8
    May 30, 2017 at 23:37
  • 1
    $\begingroup$ @UTF-8: Ah, well you can study $ZFC$ without the axiom of regularity (sometimes denoted as $ZFC^-$). It is known that they are equi-consistent. It is somewhat loosely discussed in Kunen's book: amazon.com/Set-Theory-Studies-Logic-Mathematical/dp/1848900503 $\endgroup$
    – user185596
    May 31, 2017 at 20:51
  • 1
    $\begingroup$ Thank you! Now I understand why you linked to the Wikipedia article of urelements. (Because of the paragraph about quine atoms.) en.wikipedia.org/wiki/Non-well-founded_set_theory seems to be a nice (albeit short) read, too. $\endgroup$
    – UTF-8
    May 31, 2017 at 20:59
1
$\begingroup$

"To contain" is ambiguous: as subset? or as element? Of course, from every reasonable viewpoint any set contains itself as subset, but that is quite different from the (apparently paradox-generating) issue about sets that are elements of themselves (or not). Since allowing $S\in S$ leads to trouble, we try to declare it somehow illegal. If one believes that axioms are somehow enforceable, then, indeed, the axiom of regularity makes $S\in S$ "impossible". :)

$\endgroup$
2
  • $\begingroup$ But how does allowing $S\in S$ lead to trouble? $\endgroup$
    – Eric Wofsey
    May 30, 2017 at 22:41
  • $\begingroup$ @EricWofsey, from my viewpoint, the possibility (or putative sense) of $S\in S$ is what allows the Russell paradox/trouble. $\endgroup$
    – paul garrett
    May 30, 2017 at 23:02

Not the answer you're looking for? Browse other questions tagged .