# weakening naive comprehension to avoid the paradoxes

Weakening the axiom of naive comprehension has not been a popular way of escaping from the set-theoretic paradoxes because no consistent weakenings seem to be particularly well motivated or even to lead to understandable models. At any rate, that is so of the most famous consistent (well, probably consistent) weakening, New Foundations. Nonetheless, it could be illuminating to understand the partial order of consistent subtheories of naive set theory. My question would be: what is known about it? Unfortunately, however, that question seems ill-posed in that an arbitrary axiom $\psi$ can be coded as comprehension for $(\psi \land x\neq x)\lor (\lnot\psi \land x\notin x)$. But can anything interesting be said?

Besides NF, I am aware of just one type of set theory that is (almost) naturally thought of as arrived at by admitting only a subset of all possible instances of naive comprehension. These are the so-called positive set theories. Unfortunately, I know nothing about them except that they admit a universal set (like NF), and they apparently do require some extra axioms that are not naturally expressed as instances of comprehension. In particular, according to Wikipedia, the theory known as $GPK^{+}_{\infty}$ requires the axiom of infinity, the empty set axiom (!), and an axiom scheme of "closure" giving, for each formula $\phi$ with one free variable, the intersection of all the sets that contain every $x$ such that $\phi(x)$. This seems to me arguably in the spirit of restricting naive comprehension because comprehension is still the main set construction principle, and in particular there is no need for powerset or replacement. Are there other "natural" examples of set theories that can be thought of as arrived at by weakening naive comprehension? Perhaps ones that don't admit a universal set?

Even non-effective examples (examples where the set of instances of comprehension that is admitted is not computably enumerable) might be interesting. Also, there might be interesting ways of weakening naive comprehension that are different from simply restricting the allowed instances of the schema. For instance, maybe some set of disjunctions of instances of naive comprehension is interesting, or maybe it is interesting to consider an axiom that would only guarantee the existence of a set that is in some sense "close" to the class of objects satisfying $\phi$.

The context in which this question came up is that I was trying to explain Russell's paradox to someone, and their reaction was, well you should just throw out the instance of the comprehension axiom that leads to paradox. Of course, throwing out literally that one instance won't restore consistency. But pointing out a flaw in any particular proposal someone with this attitude toward the paradoxes might propose wouldn't show that some more sophisticated proposal might succeed. I was hoping for some sort of general argument that, say, proceeding in this way inevitably leads to a system that is either like NF or like positive set theory (if it is not inconsistent or extremely weak). (What else could be wrong with $x\notin x$ except that it is unstratified or that it involves negation?) Or at least an argument that you won't get an extension of ZF by any natural weakening procedure would be nice! Both NF and positive set theory, if I understand the situation aright, could serve as a foundation for mathematics, but both are less intuitive and convenient than ZFC, and it is sort of an article of faith for set theorists that any alternative to ZFC we might ever find is either somehow worse than ZFC or not deeply different from it, yes?

• Probably not a fix you intend to consider, but you can also escape Russell's paradox by keeping full comprehension, and instead adopting a non-classical logic as your deductive framework. I tend to find this approach not very interesting, but it certainly can yield a non-trivial set theory which is very different from ZFC, NF, positive set theory, etc. – Noah Schweber Aug 29 '12 at 18:16
• When you write "This seems to me arguably in the spirit of restricting naive comprehension because comprehension is still the main set construction principle, and in particular there is no need for powerset or replacement.", you seem to imply that replacement and power set are NOT instances of naive comprehension. If so, please explain what you mean by "naive comprehension". If not, then "ZF minus Foundation and Extensionality" is a natural weakening of comprehension, guided by "limitation of size". Except that I think that any "natural" set theory needs some version of extensionality. – Goldstern Aug 29 '12 at 23:27
• @Noah: Russell's paradox still occurs with naïve comprehension even in very weak systems: we are basically given $R \notin R \leftrightarrow R \in R$, and to deduce $\bot$ we just need the deduction rules for $\land$ and $\to$. – Zhen Lin Aug 30 '12 at 11:36
• @Zhen Lin: What you wrote depends sensitively on the details of the propositional deduction rules. Specifically, the obvious deduction of $\bot$ won't work in a system like Girard's linear logic. The problem is that $\phi\to(\phi\to\psi)$ doesn't give you $\phi\to\psi$ in such systems. (I vaguely recall that an attempt was made to use linear logic to circumvent Russell's paradox, but the resulting set theory was terribly weak; there may have been better attempts since then but I don't recall seeing any.) – Andreas Blass Sep 16 '12 at 1:27
• To avoid Curry's paradox, paraconsistentists are usually forced to discard some instances of "contraction" ($P\to (P\to Q)$ yields $P\to Q$) as well -- in which case it seems to me you are more than halfway to linear logic instead, in which case (as Andreas mentioned) a naive comprehension rule can actually be consistent (as opposed to paraconsistent). – Mike Shulman Sep 14 '17 at 8:33

I'm not clear on why you don't regard ZFC as an example. You say:

Weakening the axiom of naive comprehension has not been a popular way of escaping from the set-theoretic paradoxes because no consistent weakenings seem to be particularly well motivated or even to lead to understandable models.

But it seems to me that the ZFC axioms of set theory result essentially from a weakening of naive comprehension, are highly popular, are well motivated and seem to avoid the paradoxes while having an abundance of understandable models.

In particular, the ZFC axiom of separation is the result of weakening the naive comprehension axiom to the assertion that for any property $\phi$ and any set $A$, the collection $\{ \ x\ \mid\ x\in A\text{ and }\phi(x)\ \}$ forms a set. And one can similarly view the replacement axiom as an instance or weakening of naive comprehension, asserting of any set $A$ and property $\phi$ that the collection $\{\ x\ \mid\ \exists a\in A\ x\text{ is unique such that }\phi(x,a)\ \}$ forms a set.

Furthermore, the ZFC formulation of set theory seems to be very well motivated by the iterative conception of set, where one views the class of all sets being formed in a well-founded cumulative hierarchy formed in stages, in which the elements of a set are constructed at earlier stages than the set itself, and the stages continue in an endless transfinite progression. In essence, one must construct the elements of a set before constructing the set itself. On this philosophical view of how sets are formed, there is ample support for the separation and replacement axioms, and essentially none for the naive comprehension axiom (since there seems in general no reason to suppose all the $x$ with the desired property exist by some stage).

• That was my initial reaction upon reading the question as well, but I think the point that kimtown is only after theories all of whose axioms (besides extensionality) are instances of comprehension. So ZFC in its entirety doesn't make the cut, and one would have to do without foundation, infinity and choice. (Though I suppose infinity could be recovered as part of the theory while respecting kimtown's criterion by adding as axioms the finitely many instances of stratified comprehension which Specker used in his proof that NF refutes choice.) – Ed Dean Aug 29 '12 at 20:11
• The power set, union and pairing axioms seem to be instances of naive comprehension, as well as the infinity axiom, since it asserts the existence of { n ∣ n is a finite ordinal}. So this means that ZF-Foundation is obtainable as a weakening of naive comprehension. The standard discussion of foundation shows that every model of ZF-Foundation has a model of ZF as its well-founded part and so we arrive at ZF in this way (and even at ZFC by going to the inner models). – Joel David Hamkins Aug 29 '12 at 20:24
• Just to be clear, I wasn't suggesting that ZFC is in any way lacking for motivation, or that it doesn't originate from a weakening of naive comprehension, and I agree wholeheartedly that the lines you quote from the OP are mistaken as written. I meant no more and no less in my comment than that part of ZFC (Choice and Foundation, please excuse the mention of Infinity) isn't axiomatized as it seems the OP intends, and so I thought ZF-Foundation (rather than ZFC) would speak more directly to what concerns the OP. – Ed Dean Aug 29 '12 at 21:29
• I don't mean it is perverse to adopt ZFC in the face of the paradoxes, just that the iterative conception is a <i>different</i> conception of set, one that is natural, but not <i>more</i> natural than the naive conception. That is how Boolos describes the iterative conception. The only thing wrong with the naive conception is that it's inconsistent. If we really only had the iterative conception, it wouldn't even be necessary to mention Russell's paradox. (I don't want to ague philosophy though. I was just curious about ways of avoiding the paradox by weakening comprehension.) – user26062 Aug 29 '12 at 22:57
• I would say that it is more natural; whatever pleasant thoughts we might have had about the naive conception were largely abandoned once we realized it was contradictory. Why should we cling to a mistaken conception we know is wrong? – Joel David Hamkins Aug 29 '12 at 23:36