FOM: How natural is RCA_0 ???
peter.smith at phil.cam.ac.uk
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)?
Dr Peter Smith
DoS in Philosophy and HPS
Cambridge CB5 8BL, UK
More information about the FOM