38
$\begingroup$

A more focused version of this question has now been asked at MO.

Tl;dr version: are there "reasonable" theories which prove/disprove "the set of all sets containing themselves, contains itself"?


Inspired by this question, I'd like to ask a question which has been vaguely on my mind for a while but which I've never looked into.

Working naively for a moment, let $S=\{x: x\in x\}$ be the "dual" to Russell's paradoxical set $R$. There does not seem to be an immediate argument showing that $S$ is or is not an element of itself, nicely paralleling the fact that there are of course arguments for $R$ both containing and not containing itself (that's exactly what the paradox is, of course).

However, it's a bit premature to leap to the conclusion that there actually are no such arguments. Namely, if we look at the Godel situation, we see something quite different: while the Godel sentence "I am unprovable (in $T$)" is neither provable nor disprovable (in $T$), the sentence "I am provable (in $T$)" is provable (in $T$) (as long as we express "is provable" in a reasonable way)! So a certain intuitive symmetry is broken. So this raises the possibility that the question

$$\mbox{Does $S$ contain itself?}$$

could actually be answered, at least from "reasonable" axioms.

Now ZFC does answer it, albeit in a trivial way: in ZFC we have $S=\emptyset$. So ideally we're looking for a set theory which allows sets containing themselves, so that $S$ is nontrivial. Also, to keep the parallel with Russell's paradox, a set theory more closely resembling naive comprehension is a reasonable thing to desire.

All of this suggests looking at some positive set theory - which proves that $S$ exists, since "$x\in x$" is a positive formula, but is not susceptible to Russell's paradox since "$x\not\in x$" is not a positive formula - possibly augmented by some kind of antifoundation axiom.

To be specific:

Is there a "natural" positive set theory (e.g. $GPK_\infty^+$), or extension of such by a "natural" antifoundation axiom (e.g. Boffa's), which decides whether $S\in S$?

In general, I'm interested in the status of "$S\in S$" in positive set theories. I'm especially excited by those which prove $S\in S$; note that these would have to prove the existence of sets containing themselves, since otherwise $S=\emptyset\not\in S$.

$\endgroup$
  • $\begingroup$ @egreg I'm aware. Note that positive set theory does prove that $S$ is a set, as I said in the paragraph before "to be specific." $\endgroup$ – Noah Schweber Sep 15 '17 at 23:15
  • 1
    $\begingroup$ @egreg Actually, ZFC does let us define $S$ (note that it can also define the class of sets not containing themselves) - even better it proves that $S$ is a set, since it proves that $S=\emptyset$. $\endgroup$ – Noah Schweber Sep 15 '17 at 23:16
  • $\begingroup$ Well, $x\in x$ is not stratified, so NF is not gonna prove it is a set. $\endgroup$ – Asaf Karagila Sep 15 '17 at 23:17
  • $\begingroup$ @AsafKaragila NF is not positive set theory. I didn't mention NF. $\endgroup$ – Noah Schweber Sep 15 '17 at 23:17
  • 1
    $\begingroup$ The 'standard model' of positive set theory $+\neg \mathrm{Inf}$ has a natural topology that is a compact computable metric space. In particular the set membership relation is co-c.e. between 'computable sets' (sets that are computable points in this metric) and I'm fairly certain $S$ is such a computable point. So if the answer is no for this model a(n extremely slow) computer search can tell us, but my gut tells me $S\in S$ in this structure. $\endgroup$ – James Hanson Jun 17 '19 at 7:04
1
$\begingroup$

This is not a direct answer to your specific question, but it might shed an idea on a possible solution within the arena of $\mathsf{GPK}_\infty^+$ in which your question is decidable and to the positive!

Around three months ago I've asked Olivier Esser if whether adding the following condition is consistent with $\mathsf{GPK}_\infty^+$:

$``$ if $\phi$ is purely positive without free variables other than $y,A$, and without using the false formula, then: $$\exists A \forall y (y \in A \iff \phi)"$$ By this principle we can construct Quine atoms and alike sets, which are not constructible in merely $\mathsf{GPK}_\infty^+$

However Olivier Esser see that it's unclear whether such addition is consistent or not? So this principle is itself debatable?

The idea is that everything depends on what "reasonable" is? If the above principle is considered as more or less reasonable and if found consistent, then an answer is there! However, we are not there yet!

| cite | improve this answer | |
$\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.