Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Wouldn't s model T and thus make T inconsistent? –  Ryan Thorngren Apr 19 '10 at 19:55
1  
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). –  François G. Dorais Apr 19 '10 at 21:47
    
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. –  Joel David Hamkins Apr 19 '10 at 22:44
2  
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? –  Joel David Hamkins Apr 19 '10 at 23:03
1  
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? –  Joel David Hamkins Apr 21 '10 at 1:26

1 Answer 1

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.

share|improve this answer
    
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$? –  Joel David Hamkins Apr 21 '10 at 2:02
    
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. –  Carl Mummert Apr 21 '10 at 2:28
    
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.) –  Joel David Hamkins Apr 21 '10 at 2:38
    
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. –  François G. Dorais Apr 21 '10 at 2:41
    
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. –  Joel David Hamkins Apr 21 '10 at 2:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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