FOM: How natural is RCA_0 ???

Peter Smith peter.smith at
Mon Apr 1 13:31:35 EST 2002

Apologies if the following is just dumb and/or ignorant: but here goes ...!

The background is Simpson's wonderful SOSOA, and the qn is "How 
natural is his base theory RCA_0" ? OK, mathematically it has lots of 
really nice properties (e.g. its minimum omega model is the set of 
recursive subsets of omega). So what more could one want?? Well, take 
a "second-order arithmetic" in SOSOA's sense as a two-sorted 
first-order theory, with a suitable bunch of basic axioms for 
addition, multiplication and the order relation, plus a comprehension 

(Comp K)    (EX)(An)(n is in X <--> phi(n))

for any phi of type K, where X isn't free, plus an Induction 
axiom/scheme in one of two forms, the closure of

(Ind Set)    (0 is in X & (An)(n is in X --> n+1 is in X)) --> (An)n is in X

or of each instance of

(Ind K)       (phi(0) is in X & (An)(phi(n) --> phi(n+1))) --> (An)phi(n)

for any phi of type K. Now, plausibly, the "natural" combinations here are

i)  Accepting some (Comp K) for your favourite type K, and then Ind 
Set -- induction with the sort of sets you like;
ii) Accepting some (Comp K) and the matching (Ind K);
iii) Accepting some (Comp K) plus (Ind) for unrestricted K --- the 
idea being that IF you can establish phi(0), and (An)(phi(n) --> 
phi(n+1)), for some phi, however complex, then nothing more can be 
required to establish (An)phi(n).

And to be sure, Simpson's ACA_O is of form (i), with the favoured K 
being arithmetical formulae; and another key theory for him, 
Pi_1_1-CA_0, is again of form (i), with the favouried K now being 
Pi_1_1 formula. But RCA_0 isn't, and it is not quite of form (ii) 
either, as it marries (Comp Delta_0_1) with (Ind Sigma_0_1) and -- 
maybe here comes the dumb/ignorant bit!! -- at least before finding 
that the resulting pairing has "nice" properties you might be puzzled 
about the apparent mismatch. So three questions:

a) Antecedently to doing the hard mathematical work and finding that 
the(Comp Delta_0_1) married to  (Ind Sigma_0_1) is particularly 
fruitful, are there a priori/"philosophical" reasons for supposing 
the combination is natural and well-motivated and ought to turn out 
well (a travesty: "I only really believe in recursive sets; but I'll 
use induction when a predicate would pick out any old recursively 
enumerable set, if only I believed in them all")?

b) What exciting things would happen if, more generously, we married 
(Comp Sigma_0_1) with (Ind Sigma_0_1)?

c) Or more meanly married (Comp Delta_0_1) with (Delta_0_1)?

Peter Smith
Dr Peter Smith
DoS in Philosophy and HPS
Jesus College
Cambridge CB5 8BL, UK

More information about the FOM mailing list