REHMT PARTIAL REALIZATIONS OF HILBERT'S PROGRAM Stephen G. Simpson #0. Introduction. "____________ What follows is a write-up of my contribution to the symposium "Hilbert'sProgram Sixty Years Later" which was sponsored jointly by the AmericanPhilosophical Association and the Association for Symbolic Logic. Thesymposium was held on December 29, 1985 in Washington, D. C. The panelistswere Solomon Feferman, Dag Prawitz and myself. The moderator was WilfriedSieg. The research which I discuss here was partially supported by NSF GrantDMS-8317874. I am grateful to the organizers of this timely symposium on an importanttopic. As a mathematician I particularly value the opportunity to address anaudience consisting largely of philosophers. It is true that I was asked toconcentrate on the mathematical aspects of Hilbert's Program. But sinceHilbert's Program is concerned solely with the foundations of mathematics,the restriction to mathematical aspects is really no restriction at all. Hilbert assigned a special role to a certain restricted kind ofmathematical reasoning known as finitistic. The essence of Hilbert's Programwas to justify all of set-theoretical mathematics by means of a reduction tofinitism. It is now well known that this task cannot be carried out. Any ~such possibility is refuted by Godel's Theorem. Nevertheless, recent researchhas revealed the feasibility of a significant partial realization of Hilbert's ~Program. Despite Godel's Theorem, one can give a finitistic reduction for asubstantial portion of infinitistic mathematics including many of thebest-known nonconstructive theorems. My purpose here is to call attention tothese modern developments. I shall begin by reviewing Hilbert's original statement of his program.After that I shall explicate the program in precise terms which, although moreformal than Hilbert's, remain completely faithful to his original intention. ?~This formal version of the program is definitively refuted by Godel's Theorem.But the formal version also provides a context in which partial realizationscan be studied in a precise and fruitful way. I shall use this context todiscuss the modern developments which were alluded to above. In addition Ishall explain how these developments are related to so-called "reversemathematics." Finally I shall rebut some possible objections to thisresearch and to the claims which I make for it. #l. Hilbert's Statement of His Program. _________ _________ __ ___ _______ We must remember that in Hilbert's time all mathematicians were excitedabout the foundations of mathematics. Intense controversy centered around theproblem of the legitimacy of abstract objects. Weierstrass had greatlyclarified the role of the infinite in calculus. Cantor's set theory promisedto raise mathematics to new heights of generality, clarity and rigor. ButFrege's attempt to base mathematics on a general theory of properties led toan embarrassing contradiction. Great mathematicians such as Kronecker, 'Poincare and Brouwer challenged the validity of all infinitistic reasoning.Hilbert vowed to defend the Cantorian paradise. The fires of controversy werefueled by revolutionary developments in mathematical physics. There was astormy climate of debate and criticism. The contrast with today's foggyatmosphere of intellectual exhaustion and compartmentalization could not bemore striking. As the leading mathematician of his time, Hilbert considered it hispersonal duty to defend mathematics against all attackers and skeptics. Thistask was especially urgent in view of contemporary scientific developments.According to Hilbert, the most vulnerable point in the fortress of mathematicswas the infinite. In order to defend the foundations of mathematics, it wasabove all necessary to clarify and justify the mathematician's use of theinfinite [13]. Actually Hilbert saw the issue as having supramathematical significance.Mathematics is not only the most logical and rigorous of the sciences but alsothe most spectacular example of the power of "unaided" human reason. Ifmathematics fails, then so does the human spirit. I was deeply moved by thefollowing passage [13, pp. 370-371]. "The definitive clarification of thenature of the infinite has become necessary, not merely for the specialinterests of the individual sciences but for the honor of human understandingitself." Hilbert begins with the following question. To what if anything inreality does the mathematician's use of the infinite correspond? (In myopinion Hilbert's discussion of this point would have profited from anexamination of Aristotle's distinction between actual and potential infinity.According to Aristotle, there is no actual infinity, but potential infinityexists and first manifests itself to us in the continuous, via infinitedivisibility. See also Lear [18].) Hilbert accepts the picture of the world which is presented bycontemporary physics. The atomic theory tells us that matter is notinfinitely divisible. The quantum theory tells us that energy is likewise notinfinitely divisible. And relativity theory tells us that space and time areunbounded but probably not infinite. Hilbert concludes that themathematician's infinity does not correspond to anything in the physicalworld. (Consequently, the problem of justifying the mathematician's use ofthe infinite is even more urgent and difficult for Hilbert than it would havebeen for Aristotle.) Despite this uncomfortable conclusion, Hilbert boldly asserts thatinfinitistic mathematics can be fully validated. This is to be accomplishedby means of a three step program. 1.1. The first step is to isolate the unproblematic, "finitistic"portion of mathematics. This part of mathematics is indispensable for allscientific reasoning and therefore needs no special validation. Hilbert doesnot spell out a precise definition of finitism, but he does give some hints.Finitistic mathematics must dispense completely with infinite totalities.This means that even ordinary logical operations such as negation are suspectwhen applied to formulas which contain a quantifier ranging over an infinitedomain. In particular, the nesting of such quantifiers is illegal.Nevertheless, finitistic mathematics is to be adequate for elementary numbertheoretic reasoning and for elementary reasoning about the manipulation offinite strings of symbols. 1.2. The second step is to reconstitute infinitistic mathematics as abig, elaborate formal system. This big system (more fully described in Hilbert[14]) contains unrestricted classical logic, infinite sets galore, and specialvariables ranging over natural numbers, functions from natural numbers tonatural numbers, countable ordinals, etc. The formulas of the big system arestrings of symbols which, according to Hilbert, are meaningless in themselvesbut can be manipulated finitistically. 1.3. The last step of Hilbert's Program is to give a finitisticallycorrect consistency proof for the big system. It would then follow that any 0P sentence provable in the big system is finitistically true. (For an 1 0explanation of the role of P sentences in Hilbert's Program, see Kitcher [16] land Tait [25].) Thus the big system as a whole would be finitisticallyjustified. The infinite objects of the big system would find meaning as validauxiliary devices used to prove theorems about physically meaningful,finitistic objects. Hilbert viewed this as a new manifestation of the methodof ideal elements. That method had already served mathematics well in manyother contexts. Such was Hilbert's inspiring vision and program for the foundations ofmathematics. I have only one negative comment. With hindsight, we can see thatHilbert's proposal in step 1.2 to view infinitistic formulas as meaninglessled to an unnecessary intellectual disaster. Namely, it left Hilbert wideopen to Brouwer's accusation of "empty formalism." Brouwer's accusation wasclearly without merit. A balanced reading shows that Hilbert's overallintention was not to divest infinitistic formulas of meaning, but rather toinvest them with meaning by reference to finitistic mathematics, the meaningof which is unproblematic. Nevertheless, this part of Hilbert's formulationwas confusing and made it easy for Brouwer to step in and pin Hilbert with afalse label. The whole drama had the bad effect of lending undeservedrespectability to empty formalism. We are still paying the price of Hilbert'srhetorical flourish. #2. A Precise Explication of Hilbert's Program. _ _______ ___________ __ _________ _______ Hilbert's Program was only that: a program or proposed course of action.Let us now ask: To what extent can the program be carried out? In order tostudy this question fruitfully, one must reformulate the program in moreprecise terms. I shall now do this. Hilbert's description of the "big system," corresponding to infinitisticmathematics, is already sufficiently precise. For my purposes here I shallidentify the big system as Z , i.e. second order arithmetic. Supplement IV of 2Hilbert and Bernays [15] shows that Z is more than adequate for the formal %2development of classical analysis, etc. It would not matter if we replaced Z M2by Z , Z , or even ZFC. 3 4 The unacceptable imprecision occurs in Hilbert's discussion of finitism.There is room for disagreement over exactly which methods Hilbert would haveallowed as finitistic. This is not a defect in Hilbert's presentation.Hilbert's plan was to carry out a consistency proof which would be obviouslyfinitistic. Had the plan been completely successful, there would have been noneed for a precise specification of the outer limits of finitism. At this point I invoke the work of Tait [25]. Tait argues convincinglythat Hilbert's finitism is captured by the formal system PRA of primitiverecursive arithmetic (also known as Skolem arithmetic). This conclusion isbased on a careful study of what Hilbert said about finitism in [13,14] andelsewhere. There seems to be a certain naturalness about PRA which supportsTait's conclusion. PRA is certainly finitistic and "logic-free" yetsufficiently powerful to accommodate all elementary reasoning about naturalnumbers and manipulations of finite strings of symbols. PRA seems to embodyjust that part of mathematics which remains if we excise all infinitisticconcepts and modes of reasoning. For my purposes here I am going to acceptTait's identification of finitism with PRA. I have now specified the precise version of steps 1.1 and 1.2 ofHilbert's Program. Step 1.3 is then to show that the consistency of theformal system Z can be proved within the formal system PRA. If this could be 2 "0done, it would follow that every P sentence which is provable in Z would "1 2also be provable in PRA. We would describe this state of affairs by saying 20that Z is conservative over PRA with respect to P sentences. This would 2 +1constitute a precise and definitive realization of Hilbert's Program. ~ Unfortunately, Godel's Theorem [9] shows that any such realization of .0step 1.3 is impossible. There are plenty of P sentences which are provable .1in Z but not in PRA. (An example of such a sentence is the one which asserts 2the consistency of the formal system Z of first order arithmetic. Other &1examples, with a more combinatorial flavor, have been given by Friedman.) ~ Note that Godel's Theorem does not challenge the correctness of Hilbert'sformalization of infinitistic mathematics, nor does it undercut Tait's 5~identification of finitistic mathematics with PRA. Godel's accomplishment ismerely to show that the wholesale reduction of infinitistic mathematics tofinitistic mathematics, which Hilbert envisioned, cannot be pushed through. $* * * At this point I insert a digression concerning the relationship ofHilbert's Program to other reductionist programs. In the philosophy of mathematics, a reductionist is anybody who wants toreduce all or part of mathematics to some restricted set of "acceptable"principles. Hilbert's plan to reduce all of mathematics to finitism is only A~one of many possible reductionist schemes. In the aftermath of Godel'sTheorem, several authors have proposed reductionist programs which are quitedifferent from Hilbert's. For instance, Feferman [5] has developed an elaborate program ofpredicative reductionism. (See also Simpson [22, pp. 152-154].) CertainlyFeferman's predicative standpoint is very far away from finitism. It acceptsfull classical logic and allows the set of all natural numbers as a completedinfinite totality. But it severely restricts the use of quantification overthe domain of all subsets of the natural numbers. At this APA-ASL symposium,Feferman referred to predicative reductionism as a "relativized" form ofHilbert's Program. ~ Similarly Godel [10] has proposed an "extension" of the finitisticstandpoint, by way of primitive recursive functionals of higher type. AlsoBernays [1, p. 502] has discussed a program of intuitionistic reductionismwhich he regards as a "broadening" or "enlarging" of proof theory. In hisintroductory remarks to this symposium, Sieg interpreted Bernays as callingfor a "generalized Hilbert program." I would like to stress that these relativizations, extensions andgeneralizations are very different from the original Program of Hilbert.Above all, Hilbert's purpose was to validate infinitistic mathematics by meansof a reduction to finitistic reasoning. Finitism was of the essence becauseof its clear physical meaning and its indispensability for all scientificthought. By no stretch of the imagination can Feferman's predicativism, ~Godel's higher type functionals, Myhill's intuitionistic set theory orGentzen's transfinite ordinals be viewed as finitistic. These proof-theoreticdevelopments are ingenious and have great scientific value, but they are notcontributions to Hilbert's Program. #3. Partial Realizations of Hilbert's Program. _______ ____________ __ _________ _______ ~ Godel's Theorem shows that it is impossible to reduce all of infinitisticmathematics to finitistic mathematics. There remains the problem ofvalidating as much of infinitistic mathematics as possible. In particular,what part of infinitistic mathematics can be reduced to finitistic reasoning?Using the precise explications in #2, we may reformulate this question asfollows. How much of infinitistic mathematics can be developed within B0subsystems of Z which are conservative over PRA with respect to P sentences? 2 21 Recent investigations have revealed that the answer to the above questionis: quite a large part. The purpose of this section is to explain theserecent discoveries. I shall now do so. First, Friedman [6] has defined a certain interesting subsystem of Z I2known as WKL . The language of WKL is the same as that of Z . The logic of 0 0 2WKL is full classical logic including the unrestricted law of the excluded 0 (0middle. Induction is assumed only for S formulas of the language of Z . The (1 2mathematical axioms of WKL imply that one can obtain new functions from 0arbitrary given ones by means of substitution, primitive recursion, andminimization. In particular WKL includes PRA and hence all of finitistic 0mathematics. In addition WKL includes a highly nonconstructive axiom which 0asserts that any infinite tree of finite sequences of 0's and 1's has an :~infinite path. This powerful principle is known as weak Konig's Lemma. ~Topologically, weak Konig's Lemma amounts to the assertion that the Cantor Nspace 2 is compact, i.e. enjoys the Heine-Borel covering property for INsequences of basic open sets. Friedman pointed out that compactness of 2implies, for instance, compactness of the closed unit interval [0,1] withinWKL . 0 Second, it has been shown that WKL is conservative over PRA with respect '0 0to P sentences. This result is originally due to Friedman [7] who in fact 1 K0obtained a stronger result: WKL is conservative over PRA with respect to P 0 +2 !0sentences. This means that any P sentence which is provable in WKL is !2 "0already provable in PRA and hence is witnessed by a primitive recursive Skolemfunction. Friedman's proof of this result is model-theoretic and will bepublished by Simpson [24]. Subsequently Sieg [20] used a Gentzen-style methodto give an alternative proof of Friedman's result. Actually Sieg exhibited aprimitive recursive proof transformation. Thus the reducibility of WKL to G0PRA is itself provable in PRA. (These conclusions due to Sieg [20] could alsohave been derived from work of Parsons [19] and Harrington [12].) The above results of Friedman and Sieg may be summarized as follows. Anymathematical theorem which can be proved in WKL is finitistically reducible /0 80in the sense of Hilbert's Program. In particular, any P consequence of such 82a theorem is finitistically true. Of course all of this would be pointless if WKL were as weak as PRA with 40respect to infinitistic mathematics. But fortunately such is not the case.The ongoing efforts of Simpson and others have shown that WKL is =0mathematically rather strong. For example, the following mathematicaltheorems are provable in WKL . 0 3.1. The Heine-Borel covering theorem for closed bounded subsets ofEuclidean n-space (Simpson [21,24]) or for closed subsets of a totallybounded complete separable metric space (Brown-Simpson [3], Brown [2]). 3.2. Basic properties of continuous functions of several real variables.For instance, any continuous real-valued function on a closed bounded nrectangle in R is uniformly continuous and Riemann integrable and attains amaximum value (Simpson [21,24]). 3.3. The local existence theorem for solutions of systems of ordinarydifferential equations (Simpson [21]). 3.4. The Hahn-Banach Theorem and Alaoglu's Theorem for separable Banachspaces (Brown-Simpson [3], Brown [2]). 3.5. The existence of prime ideals in countable commutative rings(Friedman-Simpson-Smith [8]). 3.6. Existence and uniqueness of the algebraic closure of a countablefield (Friedman-Simpson-Smith [8]). 3.7. Existence and uniqueness of the real closure of a countableformally real field (Friedman-Simpson-Smith [8]). These examples show that WKL is strong enough to prove a great many !0theorems of clasical infinitistic mathematics, including some of thebest-known nonconstructive theorems. Combining this with the results ofFriedman and Sieg, we see that a large and significant part of mathematicalpractice is finitistically reducible. Thus we have in hand a ratherfar-reaching partial realization of Hilbert's Program. This partial realization of Hilbert's Program has an interestingapplication to the problem of "elementary" proofs of theorems from analyticnumber theory. Using 3.2 we can formalize the technique of contourintegration within WKL . Using conservativity of WKL over PRA, we can then 0 0 90"eliminate" this technique. Our conclusion is that any P number-theoretic 92theorem which is provable using contour integration can also be proved"elementarily," i.e. within PRA. $* * * I shall now announce some new results which extend the ones that werediscussed above. Very recently, Brown and I defined a new subsystem of Z . I2The new system properly includes WKL and is properly included in ACA . For $0 0 D+lack of a better name, we are temporarily calling the new system WKL . The D0 + 4<Naxioms of WKL are those of WKL plus an additional scheme. Let 2 denote 0 0the set of finite sequences of 0's and 1's. The new scheme says that, given a %<Nsequence of dense subcollections of 2 which is arithmetically definable froma given set, there exists an infinite sequence of 0's and 1's which meets eachof the given dense subcollections. This amounts to a strong formal version of 1Nthe Baire Category Theorem for the Cantor space 2 . Brown and I have used + 1forcing to show that WKL is conservative over RCA for P sentences. 0 0 1(Earlier Harrington [12] had used forcing to show that WKL is conservative :0 1over RCA for P sentences. Harrington's proof will appear in Simpson [24].) 0 1 =+Combining this with a result of Parsons [19], we see that WKL is conservative =0 0over PRA for P sentences and that this conservation result is itself 2demonstrable within PRA. Thus we have finitistic reducibility of any -+mathematical theorem which is provable in WKL . The point of all this is that -0 +WKL includes several highly nonconstructive theorems of functional analysis 0which are apparently not provable in WKL . Prominent among these are the Open (0Mapping Theorem and the Closed Graph Theorem for separable Banach spaces.Thus we have a finitistic reduction of these theorems as well. Thisrepresents further progress in our partial realization of Hilbert's Program.There seems to be a possibility of defining even stronger subsystems of Z I2which would contain even more theorems of infinitistic mathematics yet remainfinitistically reducible to PRA. This would represent still further progress. The results announced in the previous paragraph are not yet in finalform. A version of them will appear in Brown's forthcoming Ph. D. thesiswhich is now being written under my supervision [2]. #4. The Role of Reverse Mathematics. ___ ____ __ _______ ___________ The purpose of this section is to discuss Reverse Mathematics and itsrelationship to our previously described partial realization of Hilbert'sProgram. Reverse Mathematics is a highly developed research program whose purposeis to investigate the role of strong set existence axioms in ordinarymathematics. The Main Question is as follows. Given a specific theorem t ofordinary mathematics, which set existence axioms are needed in order to provet? Reverse Mathematics is a technique which frequently yields precise answersto special cases of this question. A fairly detailed survey of Reverse Mathematics will be found in myappendix to the forthcoming second edition of Takeuti's proof theory book[23]. Here I must confine myself to a very brief summary. Most of the work on Reverse Mathematics has been carried out in thecontext of subsystems of Z . There are a great many different subsystems of 2Z which are distinguished from one another by their stronger or weaker set 2existence axioms. It turns out that almost every theorem t of ordinarymathematics can be stated in the language of Z and proved in some subsystem .2of Z . For many specific theorems t, it turns out that there is a weakest 2natural subsystem S(t) of Z in which t is provable. Moreover S(t) is often 2one of a relatively small number of specific systems. The specific systems G1which most often arise in this context are RCA , WKL , ACA , ATR and P -CA . .0 0 0 0 1 0Of these RCA is the weakest and the others are listed in order of increasing 0strength. The system WKL has already been discussed in #3 above. For 0definitions of the other systems and an explanation of their role in ReverseMathematics, see Simpson [23,24]. Given a mathematical theorem t, the general procedure for identifyingS(t) is to show that the principal set existence axiom of S(t) is equivalentto t, the equivalence being provable in some weaker system in which t itselfis not provable. For instance, the way to show that S(t) = WKL is to show ?0 ~that t is equivalent to weak Konig's Lemma, the equivalence being provable inthe weaker system RCA . Our slogan "reverse mathematics" arises in the 0following way. The usual pattern of mathematical reasoning is to deduce atheorem from some axioms. This might be called "forward mathematics." But inorder to establish that the axioms are needed for a proof of the theorem, onemust reverse the process and deduce the axioms from the theorem. Hence"reverse mathematics." As an example, consider the local existence theorem for solutions ofordinary differential equations. Given an initial value problem y' = f(x,y),y(0) = 0 where f(x,y) is defined and continuous in some neighborhood of (0,0),there exists a continuously differentiable solution y = o(x) which is definedin some neighborhood of 0. This theorem can be formulated as a sentence t in JPthe language of Z . We may then consider the following special case of the 2Main Question. Which set existence axioms are needed for a proof of t ? FP The standard textbook proof of t proceeds by way of the Ascoli Lemma. %PWith some effort we can show that the Ascoli Lemma is provable in ACA . We E0then see fairly easily that t is provable in ACA . But, in order to prove P 0t , were the set existence axioms of ACA really needed? Motivated by this P &0question we try to "reverse" both the Ascoli Lemma and t by showing that each 8Pof them is equivalent to ACA over the weaker system RCA . This attempt 0 0succeeds for the Ascoli Lemma but fails in the case of t . We therefore try 8Pto prove t in the next system weaker than ACA , namely WKL . This attempt is P #0 0ultimately successful, but the resulting proof of t in WKL turns out to be 3P 0much more difficult than the textbook proof. This was to be expected since wealready knew that the Ascoli Lemma is not provable in WKL . Finally we tie up 90the remaining loose ends by showing that t is equivalent to WKL over RCA . *P 0 0We are thus left with a precise answer to the above-mentioned special case ofthe Main Question. (For details see Simpson [21].) This is a solidcontribution to Reverse Mathematics. As a byproduct of this work in Reverse Mathematics, we see that t is FPprovable in WKL . Combining this with the results of ## 2 and 3, we have a 0solid contribution to Hilbert's Program. Namely we see that t is in a >Pcertain precise sense finitistically reducible. The above example illustrates the general relationship between ReverseMathematics and Hilbert's Program. Our method for Hilbert's Program is toprove specific mathematical theorems within certain subsystems of Z such as C2 +WKL or WKL . Reverse Mathematics helps us to find the theorems for which 0 0this is possible. In many cases, the failure of an attempt to "reverse" a `theorem vis-a-vis ACA leads to the discovery that the theorem is in fact 0 1+provable in one of the weaker systems WKL or WKL . Thus Reverse Mathematics )0 0plays a negative yet valuable heuristic role. More fundamentally, Reverse Mathematics helps us to uncover thesubsystems of Z which are relevant to partial realizations of Hilbert's 2 (+Program. It is a fact that WKL and WKL were first discovered in the context 0 0of Reverse Mathematics. They arose naturally as candidates for the weakestsubsystems of Z in which to prove certain mathematical theorems. 2 I do not mean to imply that Reverse Mathematics is coextensive withpartial realizations of Hilbert's Program. It certainly is not. I onlyassert the existence of a certain mutually reinforcing relationship betweenthese two lines of research. I hope that I have adequately addressed Takeuti's concerns [26] about theconnection between Hilbert's Program and Reverse Mathematics. #5. Answers to Some Possible Objections. _______ __ ____ ________ __________ In this section I shall rebut some possible objections which might beraised against the research which was reported in the previous sections. 5.1. The purpose of Hilbert's Program is to defend mathematics againstskeptics. But why is mathematics in need of any defense? Doesn't everyoneagree that mathematics is both valid and useful? As to the usefulness of mathematics, opinion is divided. Some seemathematics as both a supreme achievement of human reason and, via science andindustry, the benefactor of all mankind. (This is my own view.) Othersbelieve that mathematics causes only alienation and war. Still others seemathematics as a useless but harmless pastime. The utility of mathematics canbe argued only as part of a broad defense of reason, science, technology andWestern civilization. What chiefly concerns us here is not utility but scientific truth. Ofcourse the two issues are related. Pragmatists might argue that mathematicsis useful and therefore valid. But such an inference can cover only appliedmathematics and is anyhow a non sequitur. It makes much more sense to arguethat mathematics is true and therefore useful. In the last analysis, theonly way to demonstrate that mathematics is valid is to show that it refers toreality. And make no mistake about it -- the validity of mathematics is underseige. In a widely cited article [28], Wigner declares that there is norational explanation for the usefulness of mathematics in the physicalsciences. He goes on to assert that all but the most elementary parts ofmathematics are nothing but a miraculous formal game. Kline, in hisinfluential book Mathematics: The Loss of Certainty [17], deploys a wideassortment of mathematical arguments and historical references to show that"there is no truth in mathematics." Kline's book was published by the OxfordUniversity Press and reviewed favorably in the New York Times. (For a muchmore insightful review, see Corcoran [4].) Neither Wigner nor Kline is viewedas an enemy of mathematics. But with friends like these, who needs enemies?Arguments like those of Kline and Wigner turn up with alarming frequency incoffee-room discussions and in the popular press. Russell's famouscharacterization of mathematics, as "the science in which we never know whatwe are talking about, nor whether what we say is true," is gleefully cited byevery wisecracking sophist. In the face of the attack on mathematics, what defense is offered by theexisting schools of the philosophy of mathematics? Consider first thelogicists. They say that mathematics is logic, logic consists of analytictruths, and analytic truths are those which are independent of subject matter.In short, mathematics is a science with no subject matter. What about theformalists? According to them, mathematics is a process of manipulatingsymbols which need not symbolize anything. Then there are the intuitionists,who say that mathematics consists of mental constructions which have nonecessary relation to external reality, if indeed there is any such thing asexternal reality. Finally we come to the Platonists. They are better thanthe others because at least they allow mathematics to have some subjectmatter. But the subject matter which they postulate is a separate universe ofobjects and structures which bear no necessary relation to the real world ofentities and processes. (They use the term "real world" referring not to thereal real world but to their ideal universe of mathematical objects. The realreal world is absent from their theory.) I submit that none of these schoolsis in a position to defend mathematics against the Russells and the Klines. The four schools discussed in the previous paragraph are not very farapart. Each of them is based on some variant of Kantianism. Frequently theymerge and blend. Most mathematicians and mathematical logicians lean towardan uneasy mixture of formalism and Platonism. Uneasiness flows from theimplicit realization that neither formalism nor Platonism nor the mixturesupports a comprehensive view of mathematics and its applications. There isurgent need for a philosophy of mathematics which would supply what Wignerlacks, viz. a rational explanation of the usefulness of mathematics in thephysical sciences. Some form of finitistic reductionism may be relevant here. I have argued elsewhere that the attack on mathematics is part of ageneral assault against reason. But this is not the burden of my remarkstoday. What is clear is that mathematicians and philosophers of mathematicsought to get on with the task of defending their discipline. 5.2. Hilbert's Program is exclusively concerned with the problem ofvalidating infinitistic mathematics. But what's the big problem about theinfinite? Isn't finitistic mathematics in equal need of validation? There is a long history of doubts about the role of the infinite inmathematics. Aristotle's discussion of the infinite is more acute than modernones but still inconclusive. Euclid achieved rigor in part by avoiding allreference to the infinite. Archimedes used infinite limit processes but neverrigorously justified them. Later, infinitesimals in calculus were theoccasion of intense philosophic controversy. Doubts about infinitesimals wereexploited by Bishop Berkeley in his mystical assault on science andEnlightenment values. Weierstrass' arithmetization of calculus restoredclarity and rigor, but the respite was only temporary. Controversy about theinfinite was never more intense than in our own century. The problem is that the infinite does not obviously correspond toanything in reality. The real world is made up of finite entities andprocesses. Everything that exists has a definite nature and is therefore insome sense limited. Aristotle argues for the real-world existence of theinfinite, but only by recourse to a distinction between potential and actualinfinity. Hilbert uses physical arguments to deny the existence of theinfinite anywhere except in thought. Certainly any convincing account of therelationship between the infinite and the real world would have to be fairlysubtle. By contrast, the formulas of finitistic mathematics refer in a relativelyunproblematic, common-sense way to various discrete or cyclical real-worldprocesses. For this reason, finitistic mathematics has always been much lesscontroversial than infinitistic mathematics. Only in our own time has therearisen an ultrafinitist school which posits bounds on the length of thenatural number sequence. And the ultrafinitists have neither refutedfinitistic mathematics nor shown us what an ultrafinitist textbook would looklike. Finitistic mathematics is as firmly grounded as a science can be. 5.3. The essence of Hilbert's Program is to reduce infinitisticmathematics to finitistic mathematics. But what is the point of such areduction? Does it really increase the reliability of infinitisticmathematics? I grant that the reduction of infinitistic proofs to finitistic ones doesnot increase confidence in the formal correctness of infinitistic proofs.What such a reduction does accomplish is to show that finitisticallymeaningful end-formulas of infinitistic proofs are true in the real world.Hence formulas which occur in infinitistic proofs become more reliable in thatthey are seen to correspond with reality. 5.4. Why should we concern ourselves exclusively with finitisticreductionism? What about predicativistic or intuitionistic reductionism? This objection has been partially answered in the digression at the endof #2. Finitism is much more restricted than either predicativism orintuitionism. Finitistic reasoning is unique because of its clear real-worldmeaning and its indispensability for all scientific thought. Nonfinitisticreasoning can be accused of referring not to anything in reality but only toarbitrary mental constructions. Hence nonfinitistic mathematics can beaccused of being not science but merely a mental game played for the amusementof mathematicians. Proponents of predicativism and intuitionism have nevertried to defend their respective doctrines against such accusations.Finitistic reductionism is an attempt to defend infinitistic mathematics byshowing that at least some of it is more than a mental game and doescorrespond to something in reality. It is difficult to imagine how any suchgoal could be advanced by predicativistic or intuitionistic reductionism. 5.5. Are the possibilities of finitism really exhausted by PRA? Didn'tHilbert himself allow for an extended notion of finitism which would transcendthe primitive recursive functions? One might try to insist that certain multiply recursive functions such asthe Ackermann function ought to be allowed as finitistic. However, ReverseMathematics seems to indicate that such relatively minor changes would notsignificantly enlarge the class of finitistically reducible theorems. Hencethe conclusions of #3 would remain essentially unaffected. It is also true that Hilbert [13, p. 389] discussed a certain rather wideclass of recursions of higher type. But Hilbert did not assert that suchrecursions are prima facie finitistic. Rather he presented them as part ofhis alleged proof of the Continuum Hypothesis, based on his incorrect beliefthat all of infinitistic mathematics is finitistically reducible. Certainlythe recursions in question do not satisfy Hilbert's own criteria for finitism.(See also Tait [25, pp. 544-545].) There are other possible objections to the identification of finitismwith PRA. All such objections have been dealt with adequately by Tait [25]. 5.6. The development of mathematics within Z or subsystems of Z 22 2involves a fairly heavy coding machinery. Doesn't this vitiate the claim ofsuch subsystems to reflect mathematical practice? It is true that the language of Z requires mathematical objects such as &2real numbers, continuous functons, complete separable metric spaces, etc. tobe encoded as subsets of N in a somewhat arbitrary way. (See [3,8,21,24].)However, this coding in subsystems of Z is not more arbitrary or burdensome '2than the coding which takes place when we develop mathematics within, say,ZFC. Besides, the coding machinery could be eliminated by passing toappropriate conservative extensions with special variables ranging over realnumbers, etc. If this were done, the codes would appear only in the proofs ofthe conservation results. I do not believe that the coding issue has anyimportant effect on the program of finitistic reductionism. #+ 5.7. The systems WKL and WKL do not capture the full range of 0 0standard, infinitistic mathematics. Many well-known standard theorems cannotbe proved at all in these systems. And even when a standard theorem is +provable in WKL or WKL , the proof there is sometimes much more complicated 0 0 I+than the standard proof. Doesn't this undercut the claim of WKL and WKL to @0 0embody a partial realization of Hilbert's Program? ~ Godel's Theorem and Reverse Mathematics imply that many well-knownstandard mathematical theorems are not finitistically reducible at all. G+Therefore, the fact that these theorems are not provable in WKL or WKL does ?0 0not disturb us in the least. It merely prevents our partial realization ofHilbert's Program from being a total one. Somewhat more worrisome is the gap between standard proofs and proofs in +WKL or WKL . However, this gap is certainly not wider than the one between 0 0Eulerian infinitisimal analysis and Weierstrassian e-d arguments. MoreoverHilbert explicitly embraced Weierstrass' reconstruction of analysis as a modelfor his own Program if not an integral part of it. "Just as operations withthe infinitely small were replaced by processes in the finite that have quitethe same results and lead to quite the same elegant formal relations, so themodes of inference employing the infinite must be replaced generally by finiteprocesses that have precisely the same results, that is, that permit us tocarry out proofs along the same lines and to use the same methods of obtainingformulas and theorems." These words of Hilbert [13, p. 370] make me doubtthat he would have been troubled by the above-mentioned gap. #+ 5.8. The systems WKL and WKL do not seem to correspond to any 0 0coherent, sharply defined philosophical or mathematical doctrine. Aren't WKL M0 +and WKL mere ad hoc creations? 0 H+ No, they are not mere ad hoc creations. The axioms of WKL and WKL ?0 0embody compactness and Baire category respectively. These two principles arewell known to be pervasive in infinitistic mathematics. (They are twodifferent ways of affirming the existence of "enough points" in continuousmedia.) Moreover, the principal axiom of WKL is known to be equivalent over -0RCA to a number of key mathematical theorems. For instance, each of the 0Theorems 3.1 through 3.7, which were listed in #3 as being provable in WKL , J0is in fact equivalent to WKL over RCA . These equivalences come from Reverse 0 0Mathematics and provide further evidence of the naturalness of WKL . B0 + Perhaps WKL and WKL do not correspond to any set of a priori ontological 0 0commitments such as might be proposed by philosophers unacquainted with thehistory and current state of mathematics. However, mathematics is entitled todefine its own principles in accordance with its own needs, so long as theseprinciples are compatible with the needs of the other sciences and with sound F+philosophy. This seems to leave room for systems such as WKL and WKL . =0 0 5.9. The claimed partial realization of Hilbert's Program is onlypatchwork. Infinitistic theorems are validated one at a time by laboriously &+reestablishing them within WKL or WKL or similar systems. Doesn't such a 0 0piecemeal procedure lack the "once and for all" grandeur of Hilbert'svisionary proposal? Let me say first that the work reported in #3 is much more systematicthan it may appear from the outside. Many branches of infinitisticmathematics depend on a few key nonconstructive existence theorems. If thesetheorems or a reasonable substitute can be proved within WKL , the rest <0follows routinely. Thus WKL includes whole branches of mathematics and not 0only the theorems which were mentioned in #3 for illustrative purposes. Itseems that most of the "applicable" or "concrete" branches of mathematics fallinto this category. For example, the Artin-Schreier solution of Hilbert's17th Problem can be carried out within WKL . (See Friedman-Simpson-Smith *0[8].) I would estimate that at least 85% of existing mathematics can be +formalized within WKL or WKL or stronger systems which are conservative over 0 0 0PRA with respect to P sentences. Of course highly set-theoretical topics are 2excluded, but it is remarkable how many topics which at first may seem highlyset-theoretical turn out not to be so. For instance, the Hahn-Banach Theoremfor separable Banach spaces turns out to be provable in WKL . (See ;0Brown-Simpson [3].) Having said this, I must admit that my plodding procedure lacks the grandsweep of Hilbert's plan. But to some extent this is inevitable in view of ~Godel's Theorem. In any case, if there is a better procedure, I challenge thequestioner to find it. Granted, it would be desirable to have a wholesalefinitistic reduction of a large and easily identifiable part of infinitisticmathematics. But we do not know whether this is possible. In the meantime itseems desirable to establish finitistic reducibility for as much ofinfinitistic mathematics as we can. Moreover, the experience so gained mayturn out to be useful in the larger task of validating infinitisticmathematics by methods not restricted to finitistic reductionism. It seemsreasonable to hope that patience will pay off here. 5.10. The deduction of axioms from theorems seems like a very strangeactivity. Certainly such a wrong-headed enterprise would never have beentolerated by Hilbert. Can't we dismiss as mere propaganda the attempt toassociate Reverse Mathematics with Hilbert's Program? No, we cannot. It is true that the deduction of axioms from theorems isabsent from Hilbert's formulation of his program. It is likewise absent fromthe final form of our results, discussed in #3 above, which constitute partialrealizations of Hilbert's Program. However, Reverse Mathematics has playedand will continue to play an important behind-the-scenes heuristic role in thediscovery of such results. As explained and illustrated in #4, the interplaybetween "forward mathematics" and Reverse Mathematics leads to the discovery &+of formal systems such as WKL and WKL . That same interplay is essential to 0 0the ongoing process whereby we delimit the parts of mathematics that can bedeveloped in such systems. The fact that Hilbert's vision did not encompass Reverse Mathematics isof no consequence. Hilbert mistakenly thought that it would be possible toreduce all of infinitistic mathematics to finitism. Had he been right, therewould have been no need to delimit the finitistically reducible parts ofmathematics. Reverse Mathematics is instrumental in exploring the extent towhich Hilbert's own Program can be carried out. For this reason I thinkthat Hilbert would have recognized something of his own intention in theresearch which I have reported here. G~ 5.11. What is the point of going on with Hilbert's Program once Godelshowed it to be impossible? Why not give up on finitistic reductionism andturn to some other method of validating infinitistic mathematics? Forinstance, why not appeal to Platonic intuition about the cumulative hierarchy?(This objection or one very much like it was raised at the symposium by NickGoodman.) The obituary for Hilbert's Program is premature to say the least. ~Godel's Theorem rules out only the most thoroughgoing total realizations ofHilbert's Program. It does not rule out significant partial realizations.The results of #3 show that a substantial portion of the Program can in factbe carried out. (See also my answer to 5.9, above.) This is a remarkablevindication of Hilbert. It is also an embarrassing defeat for those who ~gleefully trumpeted Godel's Theorem as the death knell of finitisticreductionism. The need to defend the integrity of mathematics has not abated. On the ~ 6~contrary, Godel's Theorem made this need more urgent than ever. Godelsupplied heavy artillery for all would-be assailants of mathematics. Authors ~such as Kline [17] cite Godel with monotonous repetition and devastatingeffect. The assault rages as never before. Platonic intuition is unsuitable as a weapon with which to defend thevalidity of mathematics. Only the first few levels of the cumulativehierarchy bear any resemblance to external reality. The rest are a huge F~extrapolation based on a crude model of abstract thought processes. Godelhimself comes close to admitting as much [11, pp. 483-484]. Arguing in favor ~of the cumulative hierarchy, Godel [11, pp. 477 and 485] proposes a validationin terms of testable number-theoretic consequences. Unfortunately such testsseem hard to carry out. Finitistic reductionism is not the only plausible method by which tovalidate infinitistic mathematics. One might try to show that a substantialpart of infinitistic mathematics is directly interpretable in the real world.Continuous real-world processes have not been sufficiently exploited.Aristotle's notion of potential infinity could be of value. Nevertheless, ofall the possible approaches, the indirect one via finitism seems to be themost convincing. !References !__________ [1] P. Bernays, "Hilbert, David," in: Encyclopedia of Philosophy, vol. 3,edited by P. Edwards, New York, 1967, pp. 496-504. [2] D. K. Brown, Ph. D. Thesis, Pennsylvania State University, 1986, inpreparation. [3] D. K. Brown and S. G. Simpson, Which set existence axioms are needed toprove the separable Hahn-Banach theorem?, Annals of Pure and Applied Logic, toappear. [4] J. Corcoran, Review of [17], Math. Reviews 1982c, #03013. [5] S. Feferman, Systems of predicative analysis I, II, J. Symbolic Logic29, 1964, pp. 1-30; 33, 1968, pp. 193-220. [6] H. Friedman, Systems of second order arithmetic with restrictedinduction I, II (abstracts), J. Symbolic Logic 41, 1976, pp. 557-559. [7] H. Friedman, personal communication to L. Harrington, 1977. [8] H. Friedman, S. G. Simpson and R. L. Smith, Countable algebra and setexistence axioms, Annals of Pure and Applied Logic 25, 1983, pp. 141-181. ~ [9] K. Godel, On formally undecidable propositions of Principia Mathematicaand related systems I, translated by J. van Heijenoort, in: [27], pp.596-616. ~ ~ ~ [10] K. Godel, Uber eine bisher noch nicht benutzte Erweiterung des finitenStandpunktes, Dialectica 12, 1958, pp. 280-287. ~ [11] K. Godel, What is Cantor's Continuum Problem?, in: Philosophy ofMathematics: Selected Readings, 2nd edition, edited by P. Benacerraf and H.Putnam, Cambridge University Press, 1983, pp. 470-485. [12] L. Harrington, personal communication to H. Friedman, l977. [13] D. Hilbert, On the infinite, translated by S. Bauer-Mengelberg, in:[27], pp. 367-392. [14] D. Hilbert, The foundations of mathematics, translated by S.Bauer-Mengelberg and D. Follesdal, in: [27], pp. 464-479. [15] D. Hilbert and P. Bernays, Grundlagen der Mathematik, vols. I and II,2nd edition, Springer-Verlag, 1968 and 1970, 473 + 571 pages. [16] P. Kitcher, Hilbert's epistemology, Phil. of Science 43, 1976, pp.99-115. [17] M. Kline, Mathematics: The Loss of Certainty, Oxford University Press,New York, 1980, vi + 366 pages. [18] J. Lear, Aristotelian infinity, Proceedings of the Aristotelian Society(n.s.) 80, 1980, pp. 187-210. [19] C. Parsons, On a number-theoretic choice schema and its relation toinduction, in: Intuitionism and Proof Theory, edited by J. Myhill, A. Kino,and R. E. Vesley, North-Holland, l970, pp. 459-473. [20] W. Sieg, Fragments of arithmetic, Annals of Pure and Applied Logic 28,1985, pp. 33-71. [21] S. G. Simpson, Which set existence axioms are needed to prove theCauchy/Peano theorem for ordinary differential equations?, J. Symbolic Logic49, 1984, pp. 783-802. [22] S. G. Simpson, Friedman's research on subsystems of second orderarithmetic, in: Harvey Friedman's Research in the Foundations of Mathematics,edited by L. Harrington, M. Morley, A. Scedrov and S. G. Simpson,North-Holland, 1985, pp. 137-159. [23] S. G. Simpson, Subsystems of Z and Reverse Mathematics, appendix to: %2G. Takeuti, Proof Theory, 2nd edition, North-Holland, 1986, to appear. [24] S. G. Simpson, Subsystems of Second Order Arithmetic, in preparation. [25] W. W. Tait, Finitism, J. of Philosophy, 1981, pp. 524-546. [26] G. Takeuti, Recent topics on proof theory (in Japanese), J. of theJapan Assoc. for Phil. of Science 17, 1984, pp. 1-5. 2~ [27] J. van Heijenoort (editor), From Frege to Godel: A Source Book inMathematical Logic, 1879-1931, Harvard University Press, 1967, xii + 660pages. [28] E. P. Wigner, The unreasonable effectiveness of mathematics in thenatural sciences, Comm. on Pure and Applied Math. 13, 1960, pp. 1-14. *Department of Mathematics *Pennsylvania State University *University Park, PA 16802 *February 4, 1986