5
$\begingroup$

We always hear about the paradox of the set of all sets that don't contain themselves and whether it contains itself or not. What about the set of all sets that do contain themselves? Is that an alligator paradox?

(Assume that you don't have the axiom of regularity, by the way.)

$\endgroup$
6
$\begingroup$

In the usual set of axioms of set theory, ZFC, this is the empty set. That is no set contains itself. It is immediate that $\varnothing\notin\varnothing$.

If we consider ZF without the axiom of regularity, it is consistent that the collection of sets of the form $x=\{x\}$ is a proper class (i.e. definable, but not a set, much like the Russell class). In which case this is not even a set.

But suppose that there is only one set which contains itself, $x=\{x\}$ then the set of all sets which contain themselves is $\{x\}=x$. It must contain itself! But if the set which contains itself is $y=\{y,\varnothing\}$ then the set of sets which contain themselves is $Y=\{y\}\neq y$ and $Y\notin Y$.

If we analyze the proof of the Russell paradox in this case we have that:

If $X=\{x\mid x\in x\}$ is a set, then either $X\in X$ in which case $X\in X$; or $X\notin X$ in which case $X\notin X$.

There is no problem with either case.

$\endgroup$
  • 3
    $\begingroup$ (Included for OP's benefit) Sets of the form $x = \{ x \}$ are called Quine atoms. $\endgroup$ – Clive Newstead Jan 6 '13 at 15:18
  • $\begingroup$ But since both are possible, isn't that a problem? Isn't the set as ill-defined as the set in Russell's paradox? $\endgroup$ – Albert Hendriks Aug 30 '18 at 19:14
  • $\begingroup$ @Albert: I don't follow, what exactly are you asking about? $\endgroup$ – Asaf Karagila Aug 30 '18 at 19:19
  • $\begingroup$ OP asks about THE set of all set that contain themselves, but apparently there are more such sets. So something like $\{x|x\in x\}$ is ill-defined, right? Does it contain itself or doesn't it? Such a definition should define only one exact set. $\endgroup$ – Albert Hendriks Aug 30 '18 at 20:03
  • $\begingroup$ @Albert: No, there is exactly one collection defined by this. But is it a set or a proper class, or is it the empty set, this depends on your axioms. Like saying $\{n\in\Bbb N\mid n=0\text{ and RH is true, or }n\leq 2\text{ and RH is false}\}$. This defines a unique set. But can you tell me, without knowing more information whether or not it has just one element or more? (RH stands for the Riemann Hypothesis.) $\endgroup$ – Asaf Karagila Aug 30 '18 at 20:19
1
$\begingroup$

In ZF(C) it is a theorem that $\forall x(x\notin x)$: no set has itself as a member. Thus, $\{x:x\in x\}=\varnothing$. And $\varnothing\notin\varnothing$, so the set of all sets that do contain themselves is not such a set.

$\endgroup$
0
$\begingroup$

I get to use the two element model again!

Depending on your axiom such sets may or may not exist.

There is a two element model of union, pairing, comprehension, and foundation such that $y \in y$. (If you like, you can ignore foundation.)

For example, let $M = \{x, y\}$ and $\in^\mathcal{M} = \{(x,y), (y,y)\}$. You can verify all the axiom stated above. In this model, there exists a set $y$ such that $y \in y$.

Also if you are familiar with Russel's paradox, the set of all $\{x : x \notin x\}$ is also a set in this model. The whole universe $V = y$ is also a set in this model $\mathcal{M}$.


Of course, if you look at any of the other answers, the full $ZF$ axions prove that such sets do not exist.

$\endgroup$
0
$\begingroup$

In Zermelo-Fraenkel set theory, you can't prove the inexistence of the set of all sets that contain themselves. Since there is no universal set, you can't prove that the complement of that set is the set of all sets that don't contain themselves. In fact, in that theory, it can be proven using the axiom of regularity that that set is the empty set. In New Foundations, there is a universal set. In that theory, you can prove that the set of all sets that contain themselves doesn't exist either. Here's an incomplete proof but I'm sure a complete formal proof exists.

The set of all sets that don't contain themselves doesn't exist. Suppose the set of all sets that contain themselves exists. Then its complement with respect to the universal set is the set of all sets that don't contain themselves, which contradicts the fact that that set doesn't exist. Therefore, the set of all sets that contain themselves doesn't exist either.

Sources:

$\endgroup$

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.