Welcome to MathOverflow

Question

2

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.

flag	asked Apr 19 2010 at 19:52 Garabed Gulbenkian 3,003●6●13

Wouldn't s model T and thus make T inconsistent? – Ryan Thorngren Apr 19 2010 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 2010 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 2010 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 2010 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 2010 at 1:26

show 2 more comments

Carl Mummert · Answer 1 · 2010-04-21 02:31:05Z UTC

2

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.

edited Apr 21 2010 at 2:31

answered Apr 21 2010 at 1:52

Carl Mummert
4,838●1●15●27

	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 2010 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 2010 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 2010 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 2010 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 2010 at 2:47

show 2 more comments

Can one escape from the “mirror-image” of Russell’s Paradox?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.