Non WellFounded Set theories and Russell's Paradox

I am very puzzled by set theories which reject the axiom of regularity. If we reject the axiom of regularity, and allow a distinction to be drawn between wellfounded and non-wellfounded sets/classes, then what prevents the following Russell-like set/class definition:

Let S = the class of all wellfounded classes.

Surely something in non-wellfounded set theory must prevent it, for it leads to paradox: Is S wellfounded? If it is, then it is a member of itself, and hence, it isn't (contradiction). And if it isn't, then it must have an element which is not wellfounded, contradicting our definition of S.

So, my question is this: in a non-wellfounded set theory, what is it that blocks this Russell-like paradox?

Thanks.

• Why does it seem like the usual method of preventing that won't still work? $\;$ – user57159 Jun 6 '15 at 0:05
• What do you mean by "set theories which reject the axiom of regularity"? – Rob Arthan Jun 6 '15 at 0:14
• Because without the axiom of regularity 'the set of well-founded sets' seems like a proper-subset of the class of all sets. So it seems to be made legitimate. But, honestly, I don't know all that much about the existing solutions to Russell's paradox except for Type theory and the iterative conception of set. If it requires too much typing to explain it to me yourself, perhaps you could point me to a thread here which clearly describes how the other ZF axioms save the day from that villainous Russell? Thanks. – DavesNotHereMan Jun 6 '15 at 0:19
• Rob, I'm talking about non-wellfounded set theories: those that replace the axiom of regularity (aka. foundation) with something that implies its negation. – DavesNotHereMan Jun 6 '15 at 0:21
• Since it's easy to get confused by the mix of philosophical concepts and technical ideas, let me ask: have you actually looked, in detail, at the precise axioms of ZFC? If not, that's what you should do (and if you have, you should look at them again, and try to write some formal proofs using them to get a feel for what they really say). – Noah Schweber Jun 6 '15 at 0:43

How about the fact that you can't form a "class of classes" at all?

Work in ZFC without foundation. You want to form the set of all wellfounded sets. But how are you guaranteed that such a thing exists? By separation, given any set $X$ we can form the set $S$ of well-founded sets $Y$ which are elements of $X$. This $S$ will be well-founded and not an element of itself, but that's fine, since it's not an element of $X$.

Also, note that regularity never came into it: your argument shows that in any "reasonable" theory, we can't have a set of all well-founded sets, full stop. In particular, assuming regularity this is just saying that the set-of-all-sets doesn't exist. So this is just a restriction on comprehension. There are, as always, two broad ways of dealing with this: via a cumulative hierarchy approach (e.g., separation), or via some syntactic restriction on the kinds of formulas we have comprehension for (as is done in NF - "stratified" formulas). But this doesn't have anything to do with regularity.

EDIT: having thought about this some more, I might see where the OP is coming from: the paradoxical properties the Russell object "has" are related to well-foundedness. Indeed, half of Russell's paradox - the proof that the Russell object must contain itself - implies that the Russell object is ill-founded. So at this point it might be tempting to hope that an axiom saying "There are no ill-founded sets" would block Russell's paradox.

Unfortunately, this doesn't work. The high-level reason is that you can't make a theory consistent by adding more axioms, if it was already inconsistent: as you add axioms, theories only get "more inconsistent" (this can be made precise in a number of ways - the simplest being, "larger theories have fewer models"). So if Russell's paradox were to go through in ZF$^-$, it would also go through in ZF.

(One concrete way of seeing this is to rephrase Russell's paradox over naive set theory + regularity as follows. Let $X$ be the set of all well-founded sets. Note that by regularity this is equal to the set of all sets not containing themselves. Then $X\in X$ by regularity, so $X$ is ill-founded, contradicting regularity. So regularity won't save you.)

There's a really interesting methodological point hiding here, though: if well-foundedness has nothing to do with the paradox, then why is the Russell object so ill-founded? (You know what I mean.) The snappiest answer I can come up with is that Russell's paradox, along with basically every other paradox (there are arguably exceptions), is fundamentally about self-referential objects, and self-reference can be thought of as a kind of ill-foundedness.

This isn't super satisfying, though, so a new question arises:

is there a paradox in naive set theory, which works by producing some object $O$ and then showing that $O$ has contradictory properties, where we never specifically assert anything immediately implying that the paradoxical object $O$ is ill- or well-founded?

So Russell's paradox itself doesn't count, because part of the argument is showing that the Russell object contains itself, which means it's ill-founded. This is of course an informal question (what does "immediately imply" mean? etc.), but I think it's a good one. Note, for instance, that Burali-Forti doesn't count: you have to show that the ordinals are well-ordered, which immediately implies that the Burali-Forti object is an element of itself.

Here's a possible candidate, shamelessly stolen from Cantor. Let $V$ be the set of all sets. Let $\prec$ be a well-ordering of $V$, so we can write $V=\{x_\alpha: \alpha\in I\}$ for a well-ordered index set $I$. Now consider the set $D=\{\alpha: \alpha\not\in x_\alpha\}$. Clearly $D\not\in V$, so $D$ is not a set, contradiction.

This example is potentially unsatisfying for two reasons: it relies on the axiom of choice, and even though we never say anything about the ?-foundedness of the paradoxical object $D$, we do have to talk about the set of all sets, which is of course obviously ill-founded.

So can we do better? Not off the top of my head, but I'll think some more about this; and maybe someone else has ideas . . .

• I think the OP was talking broadly about "strong" axioms which refute regularity, such as Aczel's Anti-Foundation Axiom (en.wikipedia.org/wiki/Aczel%27s_anti-foundation_axiom). In principle such an axiom could add a contradiction; however, the OP's reasoning is incorrect, and in fact we can prove that ZF$^-$+Antifoundation is inconsistent iff ZF is. – Noah Schweber Jun 6 '15 at 0:24
• Yes! So, what's the solution to Russell's paradox in ZF-? Could you post a link? – DavesNotHereMan Jun 6 '15 at 0:31
• Well, it just doesn't work: the axioms don't imply that "the set of all sets" (say) is a set! Look at the axioms to see why - full comprehension (roughly: "given any property $P$ there is a set of all sets with property $P$") is not present, and instead we have much weaker axioms like separation (roughly: "given a property $P$ and a set $A$, there is a set of all sets in $A$ with property $P$"). So Russell's paradox just doesn't get off the ground. – Noah Schweber Jun 6 '15 at 0:36
• Basically, the way you avoid Russell's Paradox is by having axioms which only give you a limited amount of set-forming ability. There are lots of ways to do this - for instance, the axiom of separation is a "from-above" kind of comprehension, while stratified comprehension (an axiom in the theory NF, not part of ZFC) is a comprehension axiom for properties of a certain syntactic form - but the point is that Russell's paradox can be thought of as a meta-theorem about set theories: In any non-broken set theory, the collection of sets which don't contain themselves can't be a set. – Noah Schweber Jun 6 '15 at 0:39
• @DavesNotHereMan: To add on Noah's last comment, see this question and the answers given to it. – Asaf Karagila Jun 6 '15 at 7:38