# 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
@noah: when you speak of non-classical logics, do you include systems of logic where excluded middle doesn't hold? Russell's paradox (seemingly) obtains because one assumes excluded middle. The same (possibly) implies the means for extricating ones self from Curry's paradox as well... – Thomas Benjamin Jul 30 '13 at 6:42

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
It is true that the ZFC axioms other than foundation and choice are instances of comprehension in a more straightforward way than the way in which every sentence in the language of set theory is, and I should have noticed that and pointed it out. But it is perverse to think of ZF-foundation as a weakening of naive set theory when in fact it is, as you say, an expression of the iterative conception of set, which is different conception of set. You cannot naturally arrive at ZF-foundation by removing problematic instances of comprehension. – user26062 Aug 29 '12 at 21:46
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