8
$\begingroup$

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?

$\endgroup$
9
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 29, 2012 at 18:16
  • $\begingroup$ 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. $\endgroup$
    – Goldstern
    Aug 29, 2012 at 23:27
  • $\begingroup$ @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$. $\endgroup$
    – Zhen Lin
    Aug 30, 2012 at 11:36
  • 1
    $\begingroup$ For the record, Russell's paradox doesn't depend on excluded middle; it works just as well in intuitionistic logic. And personally, I find the usual paraconsistent approach unimpressive because mere paraconsistency of a logic (i.e. ability to sustain the simultaneous truth of $P$ and $\neg P$ without deducing an arbitrary $Q$) is insufficient to avoid set-theoretic paradoxes, since Curry's paradox doesn't involve negation at all but goes directly to an arbitrary $Q$. $\endgroup$ Sep 14, 2017 at 8:31
  • 1
    $\begingroup$ 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). $\endgroup$ Sep 14, 2017 at 8:33

2 Answers 2

5
$\begingroup$

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).

$\endgroup$
8
  • $\begingroup$ 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.) $\endgroup$
    – Ed Dean
    Aug 29, 2012 at 20:11
  • 3
    $\begingroup$ 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). $\endgroup$ Aug 29, 2012 at 20:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – user26062
    Aug 29, 2012 at 21:46
  • 2
    $\begingroup$ 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.) $\endgroup$
    – user26062
    Aug 29, 2012 at 22:57
  • 1
    $\begingroup$ 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? $\endgroup$ Aug 29, 2012 at 23:36
2
$\begingroup$

Ackermann set theory seems "pretty close" to having unrestricted comprehension, specifically in the form of the class and set comprehension schemas. Reinhardt proved that it is as strong as ZF (in particular, an additional replacement schema is not necessary). It's not entirely clear whether class comprehension is necessary.

I asked a question here about the strength of an even more minimalist fragment of Ackermann's set theory, which has only 1 or 2 axioms and a single comprehension schema. The form of the comprehension schema is, again, conceptually "quite close" to unrestricted comprehension.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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