5
$\begingroup$

In order to respond to concerns of impredicativity, Bertrand Russell developed a system of ramified second-order logic, which is like regular second-order logic except the comprehension schema is divided into levels. The comprehension schema for level $0$ sets does not allow any formulas with second-order quantifiers. For any natural number $n$, the comprehension schema for level $n+1$ sets allows quantification over sets of level $n$ and below. This ensures that no set is defined using quantification over itself. The resulting system, however, proved too weak to do much mathematics. (Although it turns out it can do more than Russell assumed; see here.) So Russell adopted his controversial axiom of reducibility, actually an axiom schema which for each natural number $n$, states that for any set $X$ of level $n$, there exists a set $Y$ of level $0$ such that $X$ and $Y$ contain the same elements.

Now, it is commonly asserted that the axiom of reducibility is equivalent to simply eliminating the ramified hierarchy and just working in standard second-order logic. But I don't see why. At first glance, it seems to me that saying that every set, period, is coextensional with a level $0$ set, is a stronger statement than saying that every set of any given level is coextensional with a level $0$ set. Aren't there sets that aren't coextensional with sets of any level?

Any help would be greatly appreciated.

Thank You in Advance.

EDIT: Here's another way to phrase my question. Consider the following two possible axiom schemata:

  1. For any formula $\phi(x)$ in the language of second-order arithmetic, there exists a set of level $0$ whose elements are the ones that satisfy $\phi(x)$
  2. For any formula $\phi(x)$ with only graded quantifiers (i.e. quantifiers of the form "for all sets of level..." or "there exists a set of level..."), there exists a set of level $0$ whose elements are the ones that satisfy $\phi(x)$.

Is the first axiom schema stronger than the second, or are they equivalent?

Improve this question
$\endgroup$
10
  • $\begingroup$ A few questions: a) Under 1, how do you say "there exists a set of level 0" in the language of second-order arithmetic? Or do you mean the language of graded second-order arithmetic? b) What is the sense of "stronger" that you have in mind -- proving more sentences in what language? c) Why have you tagged this as constructive mathematics? These systems have no constructive properties, so far as I can see. $\endgroup$
    – user44143
    Apr 25, 2014 at 14:39
  • $\begingroup$ @MattF. a) Yes, I mean the language of graded second-order arithmetic, i.e. a language that includes both graded quantifiers and ungraded quantifiers b) Yes, by stronger I mean proving more sentences, and again we're talking about in the language of second-order arithmetic with both graded and ungraded quantifiers. Basically it boils down to, if $\phi(x)$ is a formula where some of the quantifiers may be ungraded, does axiom scheme 2 suffice to prove that there exists a level $0$ set whole elements are the ones who satisfy $\phi(x)$ $\endgroup$
    – Keshav Srinivasan
    Apr 25, 2014 at 15:53
  • $\begingroup$ @MattF c) Predicative systems are constructive in the sense that we only accept the existence of a set of natural numbers if we can construct it out of previously constructed sets of natural numbers, rather than just accepting the set of all subsets of N as a completed totality as a Platonist would do. $\endgroup$
    – Keshav Srinivasan
    Apr 25, 2014 at 15:57
  • $\begingroup$ @MattF. And by the way, the predicative system we're discussing here is not fully predicative, because it adopts a Platonist attitude toward the natural numbers themselves, treating them like a completed totality. If you want to see fully predicative mathematics that doesn't even take the natural numbers for granted, you can read Edward Nelson's free online book Predicative Arithmetic. $\endgroup$
    – Keshav Srinivasan
    Apr 25, 2014 at 16:02
  • $\begingroup$ Excuse a naive question, but what would be an instance of the unrestricted comprehension schema which is not at some level? $\endgroup$
    – Andrej Bauer
    Jul 28, 2014 at 7:39

1 Answer 1

Reset to default
2
$\begingroup$

Using the language of second-order arithmetic with both graded and ungraded quantifiers, axiom schema 1 proves more theorems than axiom schema 2. The proof is that 2 does not imply 1, because we can take a non-trivial model for 2, and expand it by having all subsets of $N$ as ungraded subsets.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "The proof is that 2 does not imply 1, because we can take a non-trivial model for 2, and expand it by having all subsets of N as ungraded subsets." I'm afraid I don mt understand what you're saying. Could you elaborate on this? I'm not even sure what you mean by "ungraded subsets". $\endgroup$
    – Keshav Srinivasan
    Apr 25, 2014 at 16:56
  • $\begingroup$ It's a many-sorted language. A Henkin model for it has integers which range over $N$, grade-0 sets which range over some $S_0$, grade-1 sets which range over some $S_1$, ..., and some ungraded sets which range over $S_{-1}$, where all the $S_i$ are subsets of $P(N)$. (You can replace "ungraded subset" in the above with "element of S_{-1}".) I claim there are models for $2+\neg 1$ in which $S_0, S_1, ...$ are properly smaller than $P(N)$, but $S_{-1}=P(N)$. $\endgroup$
    – user44143
    Apr 25, 2014 at 17:05

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.