FOM: Some remarks on Friedman's 73 posting
Fernando Ferreira
ferferr at alf1.cii.fc.ul.pt
Tue Dec 21 16:15:17 EST 1999
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
More information about the FOM
mailing list