FOM: Some remarks on Friedman's 73 posting

[Fernando Ferreira]

THREE REMARKS ON HARVEY FRIEDMAN'S 73 POSTING
[MAINLY REMARKS ON INTERPRETABILITY IN Q]

FIRST:

Five years ago (JSL vol. 59), I introduced a Base Theory for Feasible 
Analysis (BTFA) in which some basic analysis can be stated and proved 
(this latter part is stated but not worked in the paper; at the time 
there was evidence for this, since I had studied some analysis over 
the Cantor space in my Penn State'88 dissertation). In a 
working-in-progress paper of mine and my student Marques Fernandes, 
we retake this line of work and, among other things, prove the 
intermediate value theorem in BTFA (Yamazaki has also work in this 
direction). From this it follows that the theory of real closed 
fields (RCF) is interpretable in BTFA. Now, BTFA is interpretable in 
Q. Thus, RCA is interpretable in Q, as Friedman points.

The upshot is: the interpretability result of RCF in Q - striking as 
it is - is not a *freak* phenomenon. It is the conjugation of the 
facts that many bounded theories of arithmetic (without 
exponentiation) are interpretable in Q plus the fact that some 
analysis can be done over (suitable) conservative extensions of these 
bounded theories.

Note that, by the above, the more analysis you prove in BTFA (more on 
this on the next remark) the more analysis is interpretable in Q.


SECOND:

Wilkie's 86 result on the non-interpretability of ISigma0(exp) in Q 
is the fundamental result on non-interpretability in Q. It surely 
draws a line, and surely there is the question on whether this line 
is optimal. However, I believe that *reasonable* bounded theories 
which do not prove the totality of exponentiation are interpretable 
in Q. For instance, theories whose provably total functions are the 
PSPACE computable functions. In such theories more analysis can be 
done (Riemman integration, for a start). Thus, more analysis can be 
interpreted in Q.

It has always struck me that certain analytical principles do not add 
any consistency strength over suitable base theories. Take for 
instance Weak Konig's Lemma (henceforth WKL), a compactness 
principle. Back in the seventies Friedman showed that adding WKL is 
Pi^0_2 conservative over RCA_0 [this result has been successively 
generalized: Harrington showed the Pi^1_1 conservation result, and 
recently Simpson et al. generalized this result even further.] This 
*no-consistency strength* phenomenon also holds of a Baire category 
principle (Brown/Simpson).

Now, this phenomenon is not restricted to the base theory RCA_0. It 
holds for any reasonable bounded base theory. Regarding WKL, one has 
in general a Pi^1_1 conservation result over the base theory plus 
bounded collection (some formulations of WKL indeed imply full 
bounded collection). [See Simpson/Smith APAL vol. 31 for a base 
theory with exponentiation, and my above mentioned paper for a 
feasible base theory.] Since bounded collection is Pi^0_2 
conservative over *reasonable* bounded theories (an old result of 
Buss), we have the above mentioned phenomenon. [Yamazaki and 
Fernandes independently studied the Baire category principle over a 
feasible base theory.]

I do not know if theories with WKL are still interpretable in Q. But 
I see no reason why not. Again, with WKL more analysis can be done. 
Hence (hopefully) more analysis can be interpreted in Q.

THIRD:

Every logician knows that Frege wanted to reduce arithmetic to logic, 
and that he found contradiction instead (more precisely, Russell 
pointed a contradiction to him). The blame was the infamous Axiom V. 
This is un-restricted comprehension in the set-theoretic setting, but 
one must not forget that Frege was working over second-order logic. 
Some philosophers of mathematics have in the last decade or so 
re-discovered Frege and studied the minutiae of Frege's work (e.g., 
his Grundgesetz der Arithmetik). Recently, Richard Heck (building on 
work of J. Bell and T. Parsons) proved in vol. 17 of History and 
Philosophy of Logic that a predicative fragment of Frege's 
second-order system plus Axiom V is consistent (actually, a little 
more is true: Heck asks a question in note 6 of his paper which I 
answered negatively). The interesting thing for the matter at hand is 
that Heck showed that Q is interpretable in this restricted Fregean 
system.

After all, some arithmetic (and some algebra, and some analysis) can 
be done within a consistent Fregean framework.

Fernando Ferreira
CMAF - Universidade de Lisboa
Av. Professor Gama Pinto, 2
P-1649-003 Lisboa
PORTUGAL
ferferr at ptmat.lmc.fc.ul.pt