[Date Index] [Thread Index] [FOM Postings] [FOM Home]

*To*: fom@math.psu.edu*Subject*: FOM: Some remarks on Friedman's 73 posting*From*: Fernando Ferreira <ferferr@alf1.cii.fc.ul.pt>*Date*: Tue, 21 Dec 1999 21:15:17 +0000*Sender*: owner-fom@math.psu.edu

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@ptmat.lmc.fc.ul.pt

**Follow-Ups**:**Harvey Friedman**- FOM: Interpretability in Q

[Date Prev] [Date Next] [Thread Prev] [Thread Next]

[Date Index] [Thread Index] [FOM Postings] [FOM Home]