Let s denote the "virtual set" (x:x is an element of x). Does there exist a set theory T (based on classical logic and not so far proved inconsistent) such that: (1) T allows the existence of all the sets in ZF as well as many infinite self-membered sets. (2) T allows s to exist as an actual set and provides an answer to the question "Is s an element of s?" without engendering any paradox.
$\begingroup$
$\endgroup$
7
asked Apr 19, 2010 at 19:52
-
$\begingroup$ Wouldn't s model T and thus make T inconsistent? $\endgroup$– Ryan ThorngrenApr 19, 2010 at 19:55
-
1$\begingroup$ If your theory also allows for V = {x : x = x} then it cannot be closed under relative complements. That's a little odd but I don't see much problems if all your instances of comprehension are positive and quantifier-free (existential quantifiers might be fine too). $\endgroup$– François G. DoraisApr 19, 2010 at 21:47
-
$\begingroup$ I had posted a now-deleted answer explaining that all the classical set theories prove that your set s exists and is empty, since under the Foundation axiom no set is a member of itself, so the set of x with x in x is empty. (Gowers, in your comment you were missing a "not" in this argument). But now that I read your question more closely (as Nate Eldredge pointed out), the second clause of (1) rules out these theories. $\endgroup$– Joel David HamkinsApr 19, 2010 at 22:44
-
2$\begingroup$ Garabed, could you clarify what you mean by (1), since as I have pointed out, ZF proves that your set s is empty, which violates the second clause of (1). So what exactly do you mean? $\endgroup$– Joel David HamkinsApr 19, 2010 at 23:03
-
1$\begingroup$ To focus your question somewhat, I think you should just say that you want T to contain ZF-Foundation. I can't make precise sense of your proposal that T "should allow the existence of all the sets that are allowed to exist in ZF" in any other way. So my proposal is that you ask: Is it (relatively) consistent with ZF-Foundation that { x | x in x} is a nonempty set with infinite members? $\endgroup$– Joel David HamkinsApr 21, 2010 at 1:26
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
7
Yes, there is such a set theory. It is ZF minus foundation plus Aczel's "anti-foundation axiom".
One reference for this system is a book-length set of lecture notes by Aczel, http://standish.stanford.edu/pdf/00000056.pdf
In this theory, the collection of all sets that contain themselves is nonempty (in fact, it is a proper class) and contains elements that are themselves infinite.
If you wanted the collection of all sets that contain themselves to itself be a set, you could try to restrict the anti-foundation axiom to a some particular definable set of graphs; it is usually stated for the class of all graphs.
answered Apr 21, 2010 at 1:52
-
$\begingroup$ Can you prove that if you restrict the anti-Foundation axiom to a set of graphs G, that in ZF-Foudnation+AntiFoundation(G), that s is a set? Of course, it contains all the non-well-founded sets that must exist by G, but how do you know that this doesn't somehow lead to a proper class of x such that $x\in x$? $\endgroup$ Apr 21, 2010 at 2:02
-
$\begingroup$ No, I have not thought about a rigorous proof. Of course even if you limit the anti-foundation axiom, the old model of the full axiom is still a model of the limited axiom. So it appears that some analogue of L would be needed to guarantee there are not too many sets that contain themselves. Aczel does give a concrete class model of ZF - foundation + antifoundation, so that might be a place to start. I'll see if I can strike that part of my answer. $\endgroup$ Apr 21, 2010 at 2:28
-
$\begingroup$ My point is that under ZF-Foundation, it is conceivable that once there is a single set x with $x\in x$, then you can build from that x a proper class of such x, and in this case the answer to the question would be negative. (But I have not yet found a proof of this, and so I'm not sure.) $\endgroup$ Apr 21, 2010 at 2:38
-
$\begingroup$ Hi Carl! Welcome to MO! @Joel: I think you do get something reasonable with just extensionality + AFA(G) + positive quantifier-free comprehension (which proves that the set S exists). If you take for the class of graphs G the class of all graphs in some model of ZF, then you get a reasonable interpretation of the OP's "all the sets in ZF." Of course, the problem is that the big sets like S don't have much combinatorics in this kind of theory. I doubt that you can actually throw much combinatorics on top of sets like S without running into problems. $\endgroup$ Apr 21, 2010 at 2:41
-
$\begingroup$ François, is that theory consistent? But also, under this route, are you giving up on power set P(s) etc.? I would think that the OP wants P(s), Union(s), etc. $\endgroup$ Apr 21, 2010 at 2:47