Partial Realizations of Hilbert’s Program

Stephen G. Simpson Department of Mathematics Pennsylvania State University

                simpson@math.psu.edu

February 4, 1986

This article was originally written in MathText in January 1986. It was published in 1988 in the Journal of Symbolic Logic, volume 53, pages 349– 363. The conversion to LaTeX was performed on December 7, 1996.

1 Introduction

What follows is a write-up of my contribution to the symposium “Hilbert’s Program Sixty Years Later” which was sponsored jointly by the American Philosophical Association and the Association for Symbolic Logic. The symposium was held on December 29, 1985 in Washington, D. C. The panelists were Solomon Feferman, Dag Prawitz and myself. The moderator was Wilfried Sieg. The research which I discuss here was partially supported by NSF Grant DMS-8317874.

I am grateful to the organizers of this timely symposium on an important topic. As a mathematician I particularly value the opportunity to address an audience consisting largely of philosophers. It is true that I was asked to concentrate on the mathematical aspects of Hilbert’s Program. But since Hilbert’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 of mathematical reasoning known as finitistic. The essence of Hilbert’s Program was to justify all of set-theoretical mathematics by means of a reduction to finitism. It is now well known that this task cannot be carried out. Any such possibility is refuted by Gödel’s Theorem. Nevertheless, recent research has revealed the feasibility of a significant partial realization of Hilbert’s Program. Despite Gödel’s Theorem, one can give a finitistic reduction for a substantial portion of infinitistic mathematics including many of the best-known nonconstructive theorems. My purpose here is to call attention to these 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 more formal than Hilbert’s, remain completely faithful to his original intention. This formal version of the program is definitively refuted by Gödel’s Theorem. But the formal version also provides a context in which partial realizations can be studied in a precise and fruitful way. I shall use this context to discuss the modern developments which were alluded to above. In addition I shall explain how these developments are related to so-called “reverse mathematics.” Finally I shall rebut some possible objections to this research and to the claims which I make for it.

2 Hilbert’s Statement of His Program

We must remember that in Hilbert’s time all mathematicians were excited about the foundations of mathematics. Intense controversy centered around the problem of the legitimacy of abstract objects. Weierstrass had greatly clarified the role of the infinite in calculus. Cantor’s set theory promised to raise mathematics to new heights of generality, clarity and rigor. But Frege’s attempt to base mathematics on a general theory of properties led to an embarrassing contradiction. Great mathematicians such as Kronecker, Poincaré and Brouwer challenged the validity of all infinitistic reasoning. Hilbert vowed to defend the Cantorian paradise. The fires of controversy were fueled by revolutionary developments in mathematical physics. There was a stormy climate of debate and criticism. The contrast with today’s foggy atmosphere of intellectual exhaustion and compartmentalization could not be more striking.

As the leading mathematician of his time, Hilbert considered it his personal duty to defend mathematics against all attackers and skeptics. This task was especially urgent in view of contemporary scientific developments. According to Hilbert, the most vulnerable point in the fortress of mathematics was the infinite. In order to defend the foundations of mathematics, it was above all necessary to clarify and justify the mathematician’s use of the infinite [13].

Actually Hilbert saw the issue as having supramathematical significance. Mathematics is not only the most logical and rigorous of the sciences but also the most spectacular example of the power of “unaided” human reason. If mathematics fails, then so does the human spirit. I was deeply moved by the following passage [13], pp. 370–371. “The definitive clarification of the nature of the infinite has become necessary, not merely for the special interests of the individual sciences but for the honor of human understanding itself.”

Hilbert begins with the following question. To what if anything in reality does the mathematician’s use of the infinite correspond? (In my opinion Hilbert’s discussion of this point would have profited from an examination of Aristotle’s distinction between actual and potential infinity. According to Aristotle, there is no actual infinity, but potential infinity exists and first manifests itself to us in the continuous, via infinite divisibility. See also Lear [18].)

Hilbert accepts the picture of the world which is presented by contemporary physics. The atomic theory tells us that matter is not infinitely divisible. The quantum theory tells us that energy is likewise not infinitely divisible. And relativity theory tells us that space and time are unbounded but probably not infinite. Hilbert concludes that the mathematician’s infinity does not correspond to anything in the physical world. (Consequently, the problem of justifying the mathematician’s use of the infinite is even more urgent and difficult for Hilbert than it would have been for Aristotle.)

Despite this uncomfortable conclusion, Hilbert boldly asserts that infinitistic mathematics can be fully validated. This is to be accomplished by means of a three step program.

2.1. The first step is to isolate the unproblematic, “finitistic” portion of mathematics. This part of mathematics is indispensable for all scientific reasoning and therefore needs no special validation. Hilbert does not 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 suspect when applied to formulas which contain a quantifier ranging over an infinite domain. In particular, the nesting of such quantifiers is illegal. Nevertheless, finitistic mathematics is to be adequate for elementary number theoretic reasoning and for elementary reasoning about the manipulation of finite strings of symbols.

2.2. The second step is to reconstitute infinitistic mathematics as a big, elaborate formal system. This big system (more fully described in Hilbert [14]) contains unrestricted classical logic, infinite sets galore, and special variables ranging over natural numbers, functions from natural numbers to natural numbers, countable ordinals, etc. The formulas of the big system are strings of symbols which, according to Hilbert, are meaningless in themselves but can be manipulated finitistically.

2.3. The last step of Hilbert’s Program is to give a finitistically correct consistency proof for the big system. It would then follow that any Π_{1}^{0} sentence provable in the big system is finitistically true. (For an explanation of the role of Π_{1}^{0} sentences in Hilbert’s Program, see Kitcher [16] and Tait [25].) Thus the big system as a whole would be finitistically justified. The infinite objects of the big system would find meaning as valid auxiliary devices used to prove theorems about physically meaningful, finitistic objects. Hilbert viewed this as a new manifestation of the method of ideal elements. That method had already served mathematics well in many other contexts.

Such was Hilbert’s inspiring vision and program for the foundations of mathematics.

I have only one negative comment. With hindsight, we can see that Hilbert’s proposal in step 2.2 to view infinitistic formulas as meaningless led to an unnecessary intellectual disaster. Namely, it left Hilbert wide open to Brouwer’s accusation of “empty formalism.” Brouwer’s accusation was clearly without merit. A balanced reading shows that Hilbert’s overall intention was not to divest infinitistic formulas of meaning, but rather to invest them with meaning by reference to finitistic mathematics, the meaning of which is unproblematic. Nevertheless, this part of Hilbert’s formulation was confusing and made it easy for Brouwer to step in and pin Hilbert with a false label. The whole drama had the bad effect of lending undeserved respectability to empty formalism. We are still paying the price of Hilbert’s rhetorical flourish.

3 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 to study this question fruitfully, one must reformulate the program in more precise terms. I shall now do this.

Hilbert’s description of the “big system,” corresponding to infinitistic mathematics, is already sufficiently precise. For my purposes here I shall identify the big system as Z_{2}, i.e. second order arithmetic. Supplement IV of Hilbert and Bernays [15] shows that Z_{2} is more than adequate for the formal development of classical analysis, etc. It would not matter if we replaced Z_{2} by Z_{3}, Z_{4}, or even ZFC.

The unacceptable imprecision occurs in Hilbert’s discussion of finitism. There is room for disagreement over exactly which methods Hilbert would have allowed as finitistic. This is not a defect in Hilbert’s presentation. Hilbert’s plan was to carry out a consistency proof which would be obviously finitistic. Had the plan been completely successful, there would have been no need for a precise specification of the outer limits of finitism.

At this point I invoke the work of Tait [25]. Tait argues convincingly that Hilbert’s finitism is captured by the formal system PRA of primitive recursive arithmetic (also known as Skolem arithmetic). This conclusion is based on a careful study of what Hilbert said about finitism in [13, 14] and elsewhere. There seems to be a certain naturalness about PRA which supports Tait’s conclusion. PRA is certainly finitistic and “logic-free” yet sufficiently powerful to accommodate all elementary reasoning about natural numbers and manipulations of finite strings of symbols. PRA seems to embody just that part of mathematics which remains if we excise all infinitistic concepts and modes of reasoning. For my purposes here I am going to accept Tait’s identification of finitism with PRA.

I have now specified the precise version of steps 2.1 and 2.2 of Hilbert’s Program. Step 2.3 is then to show that the consistency of the formal system Z_{2} can be proved within the formal system PRA. If this could be done, it would follow that every Π_{1}^{0} sentence which is provable in Z_{2} would also be provable in PRA. We would describe this state of affairs by saying that Z_{2} is conservative over PRA with respect to Π_{1}^{0} sentences. This would constitute a precise and definitive realization of Hilbert’s Program.

Unfortunately, Gödel’s Theorem [9] shows that any such realization of step 2.3 is impossible. There are plenty of Π_{1}^{0} sentences which are provable in Z_{2} but not in PRA. (An example of such a sentence is the one which asserts the consistency of the formal system Z_{1} of first order arithmetic. Other examples, with a more combinatorial flavor, have been given by Friedman.)

Note that Gödel’s Theorem does not challenge the correctness of Hilbert’s formalization of infinitistic mathematics, nor does it undercut Tait’s identification of finitistic mathematics with PRA. Gödel’s accomplishment is merely to show that the wholesale reduction of infinitistic mathematics to finitistic mathematics, which Hilbert envisioned, cannot be pushed through.

∗ ∗ ∗

At this point I insert a digression concerning the relationship of Hilbert’s Program to other reductionist programs.

In the philosophy of mathematics, a reductionist is anybody who wants to reduce all or part of mathematics to some restricted set of “acceptable” principles. Hilbert’s plan to reduce all of mathematics to finitism is only one of many possible reductionist schemes. In the aftermath of Gödel’s Theorem, several authors have proposed reductionist programs which are quite different from Hilbert’s.

For instance, Feferman [5] has developed an elaborate program of predicative reductionism. (See also Simpson [22], pp. 152–154.) Certainly Feferman’s predicative standpoint is very far away from finitism. It accepts full classical logic and allows the set of all natural numbers as a completed infinite totality. But it severely restricts the use of quantification over the domain of all subsets of the natural numbers. At this APA-ASL symposium, Feferman referred to predicative reductionism as a “relativized” form of Hilbert’s Program.

Similarly Gödel [10] has proposed an “extension” of the finitistic standpoint, by way of primitive recursive functionals of higher type. Also Bernays [1], p. 502, has discussed a program of intuitionistic reductionism which he regards as a “broadening” or “enlarging” of proof theory. In his introductory remarks to this symposium, Sieg interpreted Bernays as calling for a “generalized Hilbert program.”

I would like to stress that these relativizations, extensions and generalizations are very different from the original Program of Hilbert. Above all, Hilbert’s purpose was to validate infinitistic mathematics by means of a reduction to finitistic reasoning. Finitism was of the essence because of its clear physical meaning and its indispensability for all scientific thought. By no stretch of the imagination can Feferman’s predicativism, Gödel’s higher type functionals, Myhill’s intuitionistic set theory or Gentzen’s transfinite ordinals be viewed as finitistic. These proof-theoretic developments are ingenious and have great scientific value, but they are not contributions to Hilbert’s Program.

4 Partial Realizations of Hilbert’s Program

Gödel’s Theorem shows that it is impossible to reduce all of infinitistic mathematics to finitistic mathematics. There remains the problem of validating 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 §3, we may reformulate this question as follows. How much of infinitistic mathematics can be developed within subsystems of Z_{2} which are conservative over PRA with respect to Π_{1}^{0} sentences?

Recent investigations have revealed that the answer to the above question is: quite a large part. The purpose of this section is to explain these recent discoveries. I shall now do so.

First, Friedman [6] has defined a certain interesting subsystem of Z_{2} known as WKL_{0}. The language of WKL_{0} is the same as that of Z_{2}. The logic of WKL_{0} is full classical logic including the unrestricted law of the excluded middle. Induction is assumed only for Σ_{1}^{0} formulas of the language of Z_{2}. The mathematical axioms of WKL_{0} imply that one can obtain new functions from arbitrary given ones by means of substitution, primitive recursion, and minimization. In particular WKL_{0} includes PRA and hence all of finitistic mathematics. In addition WKL_{0} includes a highly nonconstructive axiom which asserts that any infinite tree of finite sequences of 0’s and 1’s has an infinite path. This powerful principle is known as Weak König’s Lemma. Topologically, Weak König’s Lemma amounts to the assertion that the Cantor space 2^{ℕ} is compact, i.e. enjoys the Heine–Borel covering property for sequences of basic open sets. Friedman pointed out that compactness of 2^{ℕ} implies, for instance, compactness of the closed unit interval [0, 1] within WKL_{0}.

Second, it has been shown that WKL_{0} is conservative over PRA with respect to Π_{1}^{0} sentences. This result is originally due to Friedman [7] who in fact obtained a stronger result: WKL_{0} is conservative over PRA with respect to Π_{2}^{0} sentences. This means that any Π_{2}^{0} sentence which is provable in WKL_{0} is already provable in PRA and hence is witnessed by a primitive recursive Skolem function. Friedman’s proof of this result is model-theoretic and will be published by Simpson [24]. Subsequently Sieg [20] used a Gentzen-style method to give an alternative proof of Friedman’s result. Actually Sieg exhibited a primitive recursive proof transformation. Thus the reducibility of WKL_{0} to PRA is itself provable in PRA. (These conclusions due to Sieg [20] could also have been derived from work of Parsons [19] and Harrington [12].)

The above results of Friedman and Sieg may be summarized as follows. Any mathematical theorem which can be proved in WKL_{0} is finitistically reducible in the sense of Hilbert’s Program. In particular, any Π_{2}^{0} consequence of such a theorem is finitistically true.

Of course all of this would be pointless if WKL_{0} were as weak as PRA with respect to infinitistic mathematics. But fortunately such is not the case. The ongoing efforts of Simpson and others have shown that WKL_{0} is mathematically rather strong. For example, the following mathematical theorems are provable in WKL_{0}.

4.1. The Heine–Borel covering theorem for closed bounded subsets of Euclidean n-space (Simpson [21, 24]) or for closed subsets of a totally bounded complete separable metric space (Brown–Simpson [3], Brown [2]).

4.2. Basic properties of continuous functions of several real variables. For instance, any continuous real-valued function on a closed bounded rectangle in ℝ^{n} is uniformly continuous and Riemann integrable and attains a maximum value (Simpson [21, 24]).

4.3. The local existence theorem for solutions of systems of ordinary differential equations (Simpson [21]).

4.4. The Hahn–Banach Theorem and Alaoglu’s Theorem for separable Banach spaces (Brown–Simpson [3], Brown [2]).

4.5. The existence of prime ideals in countable commutative rings (Friedman– Simpson–Smith [8]).

4.6. Existence and uniqueness of the algebraic closure of a countable field (Friedman–Simpson–Smith [8]).

4.7. Existence and uniqueness of the real closure of a countable formally real field (Friedman–Simpson–Smith [8]).

These examples show that WKL_{0} is strong enough to prove a great many theorems of classical infinitistic mathematics, including some of the bestknown nonconstructive theorems. Combining this with the results of Friedman and Sieg, we see that a large and significant part of mathematical practice is finitistically reducible. Thus we have in hand a rather far-reaching partial realization of Hilbert’s Program.

This partial realization of Hilbert’s Program has an interesting application to the problem of “elementary” proofs of theorems from analytic number theory. Using 4.2 we can formalize the technique of contour integration within WKL_{0}. Using conservativity of WKL_{0} over PRA, we can then “eliminate” this technique. Our conclusion is that any Π_{2}^{0} number-theoretic theorem 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 were discussed above. Very recently, Brown and I defined a new subsystem of Z_{2}. The new system properly includes WKL_{0} and is properly included in ACA_{0}. For lack of a better name, we are temporarily calling the new system WKL_{0}^{+}. The axioms of WKL_{0}^{+} are those of WKL_{0} plus an additional scheme. Let 2^{<ℕ} denote the set of finite sequences of 0’s and 1’s. The new scheme says that, given a sequence of dense subcollections of 2^{<ℕ} which is arithmetically definable from a given set, there exists an infinite sequence of 0’s and 1’s which meets each of the given dense subcollections. This amounts to a strong formal version of the Baire Category Theorem for the Cantor space 2^{ℕ}. Brown and I have used forcing to show that WKL_{0}^{+} is conservative over RCA_{0} for Π_{1}^{1} sentences. (Earlier Harrington [12] had used forcing to show that WKL_{0} is conservative over RCA_{0} for Π_{1}^{1} sentences. Harrington’s proof will appear in Simpson [24].) Combining this with a result of Parsons [19], we see that WKL_{0}^{+} is conservative over PRA for Π_{2}^{0} sentences and that this conservation result is itself demonstrable within PRA. Thus we have finitistic reducibility of any mathematical theorem which is provable in WKL_{0}^{+}. The point of all this is that WKL_{0}^{+} includes several highly nonconstructive theorems of functional analysis which are apparently not provable in WKL_{0}. Prominent among these are the Open Mapping Theorem and the Closed Graph Theorem for separable Banach spaces. Thus we have a finitistic reduction of these theorems as well. This represents further progress in our partial realization of Hilbert’s Program. There seems to be a possibility of defining even stronger subsystems of Z_{2} which would contain even more theorems of infinitistic mathematics yet remain finitistically reducible to PRA. This would represent still further progress.

The results announced in the previous paragraph are not yet in final form. A version of them will appear in Brown’s forthcoming Ph. D. thesis which is now being written under my supervision [2].

5 The Role of Reverse Mathematics

The purpose of this section is to discuss Reverse Mathematics and its relationship to our previously described partial realization of Hilbert’s Program.

Reverse Mathematics is a highly developed research program whose purpose is to investigate the role of strong set existence axioms in ordinary mathematics. The Main Question is as follows. Given a specific theorem τ of ordinary mathematics, which set existence axioms are needed in order to prove τ? Reverse Mathematics is a technique which frequently yields precise answers to special cases of this question.

A fairly detailed survey of Reverse Mathematics will be found in my appendix 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 the context of subsystems of Z_{2}. There are a great many different subsystems of Z_{2} which are distinguished from one another by their stronger or weaker set existence axioms. It turns out that almost every theorem τ of ordinary mathematics can be stated in the language of Z_{2} and proved in some subsystem of Z_{2}. For many specific theorems τ, it turns out that there is a weakest natural subsystem S(τ) of Z_{2} in which τ is provable. Moreover S(τ) is often one of a relatively small number of specific systems. The specific systems which most often arise in this context are RCA_{0}, WKL_{0}, ACA_{0}, ATR_{0} and Π_{1}^{1}-CA_{0}. Of these RCA_{0} is the weakest and the others are listed in order of increasing strength. The system WKL_{0} has already been discussed in §4 above. For definitions of the other systems and an explanation of their role in Reverse Mathematics, see Simpson [23, 24].

Given a mathematical theorem τ, the general procedure for identifying S(τ) is to show that the principal set existence axiom of S(τ) is equivalent to τ, the equivalence being provable in some weaker system in which τ itself is not provable. For instance, the way to show that S(τ) = WKL_{0} is to show that τ is equivalent to Weak König’s Lemma, the equivalence being provable in the weaker system RCA_{0}. Our slogan “reverse mathematics” arises in the following way. The usual pattern of mathematical reasoning is to deduce a theorem from some axioms. This might be called “forward mathematics.” But in order to establish that the axioms are needed for a proof of the theorem, one must reverse the process and deduce the axioms from the theorem. Hence “reverse mathematics.”

As an example, consider the local existence theorem for solutions of ordinary 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 = ϕ(x) which is defined in some neighborhood of 0. This theorem can be formulated as a sentence τ in the language of Z_{2}. We may then consider the following special case of the Main Question. Which set existence axioms are needed for a proof of τ?

The standard textbook proof of τ proceeds by way of the Ascoli Lemma. With some effort we can show that the Ascoli Lemma is provable in ACA_{0}. We then see fairly easily that τ is provable in ACA_{0}. But, in order to prove τ, were the set existence axioms of ACA_{0} really needed? Motivated by this question we try to “reverse” both the Ascoli Lemma and τ by showing that each of them is equivalent to ACA_{0} over the weaker system RCA_{0}. This attempt succeeds for the Ascoli Lemma but fails in the case of τ. We therefore try to prove τ in the next system weaker than ACA_{0}, namely WKL_{0}. This attempt is ultimately successful, but the resulting proof of τ in WKL_{0} turns out to be much more difficult than the textbook proof. This was to be expected since we already knew that the Ascoli Lemma is not provable in WKL_{0}. Finally we tie up the remaining loose ends by showing that τ is equivalent to WKL_{0} over RCA_{0}. We are thus left with a precise answer to the above-mentioned special case of the Main Question. (For details see Simpson [21].) This is a solid contribution to Reverse Mathematics.

As a byproduct of this work in Reverse Mathematics, we see that τ is provable in WKL_{0}. Combining this with the results of §§3 and 4, we have a solid contribution to Hilbert’s Program. Namely we see that τ is in a certain precise sense finitistically reducible.

The above example illustrates the general relationship between Reverse Mathematics and Hilbert’s Program. Our method for Hilbert’s Program is to prove specific mathematical theorems within certain subsystems of Z_{2} such as WKL_{0} or WKL_{0}^{+}. Reverse Mathematics helps us to find the theorems for which this is possible. In many cases, the failure of an attempt to “reverse” a theorem vis-á-vis ACA_{0} leads to the discovery that the theorem is in fact provable in one of the weaker systems WKL_{0} or WKL_{0}^{+}. Thus Reverse Mathematics plays a negative yet valuable heuristic role.

More fundamentally, Reverse Mathematics helps us to uncover the subsystems of Z_{2} which are relevant to partial realizations of Hilbert’s Program. It is a fact that WKL_{0} and WKL_{0}^{+} were first discovered in the context of Reverse Mathematics. They arose naturally as candidates for the weakest subsystems of Z_{2} in which to prove certain mathematical theorems.

I do not mean to imply that Reverse Mathematics is coextensive with partial realizations of Hilbert’s Program. It certainly is not. I only assert the existence of a certain mutually reinforcing relationship between these two lines of research.

I hope that I have adequately addressed Takeuti’s concerns [26] about the connection between Hilbert’s Program and Reverse Mathematics.

6 Answers to Some Possible Objections

In this section I shall rebut some possible objections which might be raised against the research which was reported in the previous sections.

6.1. The purpose of Hilbert’s Program is to defend mathematics against skeptics. But why is mathematics in need of any defense? Doesn’t everyone agree that mathematics is both valid and useful?

As to the usefulness of mathematics, opinion is divided. Some see mathematics as both a supreme achievement of human reason and, via science and industry, the benefactor of all mankind. (This is my own view.) Others believe that mathematics causes only alienation and war. Still others see mathematics as a useless but harmless pastime. The utility of mathematics can be argued only as part of a broad defense of reason, science, technology and Western civilization.

What chiefly concerns us here is not utility but scientific truth. Of course the two issues are related. Pragmatists might argue that mathematics is useful and therefore valid. But such an inference can cover only applied mathematics and is anyhow a non sequitur. It makes much more sense to argue that mathematics is true and therefore useful. In the last analysis, the only way to demonstrate that mathematics is valid is to show that it refers to reality.

And make no mistake about it — the validity of mathematics is under siege. In a widely cited article [28], Wigner declares that there is no rational explanation for the usefulness of mathematics in the physical sciences. He goes on to assert that all but the most elementary parts of mathematics are nothing but a miraculous formal game. Kline, in his influential book Mathematics: The Loss of Certainty [17], deploys a wide assortment of mathematical arguments and historical references to show that “there is no truth in mathematics.” Kline’s book was published by the Oxford University Press and reviewed favorably in the New York Times. (For a much more insightful review, see Corcoran [4].) Neither Wigner nor Kline is viewed as an enemy of mathematics. But with friends like these, who needs enemies? Arguments like those of Kline and Wigner turn up with alarming frequency in coffee-room discussions and in the popular press. Russell’s famous characterization of mathematics, as “the science in which we never know what we are talking about, nor whether what we say is true,” is gleefully cited by every wisecracking sophist.

In the face of the attack on mathematics, what defense is offered by the existing schools of the philosophy of mathematics? Consider first the logicists. They say that mathematics is logic, logic consists of analytic truths, and analytic truths are those which are independent of subject matter. In short, mathematics is a science with no subject matter. What about the formalists? According to them, mathematics is a process of manipulating symbols which need not symbolize anything. Then there are the intuitionists, who say that mathematics consists of mental constructions which have no necessary relation to external reality, if indeed there is any such thing as external reality. Finally we come to the Platonists. They are better than the others because at least they allow mathematics to have some subject matter. But the subject matter which they postulate is a separate universe of objects and structures which bear no necessary relation to the real world of entities and processes. (They use the term “real world” referring not to the real real world but to their ideal universe of mathematical objects. The real real world is absent from their theory.) I submit that none of these schools is in a position to defend mathematics against the Russells and the Klines.

The four schools discussed in the previous paragraph are not very far apart. Each of them is based on some variant of Kantianism. Frequently they merge and blend. Most mathematicians and mathematical logicians lean toward an uneasy mixture of formalism and Platonism. Uneasiness flows from the implicit realization that neither formalism nor Platonism nor the mixture supports a comprehensive view of mathematics and its applications. There is urgent need for a philosophy of mathematics which would supply what Wigner lacks, viz. a rational explanation of the usefulness of mathematics in the physical sciences. Some form of finitistic reductionism may be relevant here.

I have argued elsewhere that the attack on mathematics is part of a general assault against reason. But this is not the burden of my remarks today. What is clear is that mathematicians and philosophers of mathematics ought to get on with the task of defending their discipline.

6.2. Hilbert’s Program is exclusively concerned with the problem of validating infinitistic mathematics. But what’s the big problem about the infinite? Isn’t finitistic mathematics in equal need of validation?

There is a long history of doubts about the role of the infinite in mathematics. Aristotle’s discussion of the infinite is more acute than modern ones but still inconclusive. Euclid achieved rigor in part by avoiding all reference to the infinite. Archimedes used infinite limit processes but never rigorously justified them. Later, infinitesimals in calculus were the occasion of intense philosophic controversy. Doubts about infinitesimals were exploited by Bishop Berkeley in his mystical assault on science and Enlightenment values. Weierstrass’ arithmetization of calculus restored clarity and rigor, but the respite was only temporary. Controversy about the infinite was never more intense than in our own century.

The problem is that the infinite does not obviously correspond to anything in reality. The real world is made up of finite entities and processes. Everything that exists has a definite nature and is therefore in some sense limited. Aristotle argues for the real-world existence of the infinite, but only by recourse to a distinction between potential and actual infinity. Hilbert uses physical arguments to deny the existence of the infinite anywhere except in thought. Certainly any convincing account of the relationship between the infinite and the real world would have to be fairly subtle.

By contrast, the formulas of finitistic mathematics refer in a relatively unproblematic, common-sense way to various discrete or cyclical real-world processes. For this reason, finitistic mathematics has always been much less controversial than infinitistic mathematics. Only in our own time has there arisen an ultrafinitist school which posits bounds on the length of the natural number sequence. And the ultrafinitists have neither refuted finitistic mathematics nor shown us what an ultrafinitist textbook would look like. Finitistic mathematics is as firmly grounded as a science can be.

6.3. The essence of Hilbert’s Program is to reduce infinitistic mathematics to finitistic mathematics. But what is the point of such a reduction? Does it really increase the reliability of infinitistic mathematics?

I grant that the reduction of infinitistic proofs to finitistic ones does not increase confidence in the formal correctness of infinitistic proofs. What such a reduction does accomplish is to show that finitistically meaningful end-formulas of infinitistic proofs are true in the real world. Hence formulas which occur in infinitistic proofs become more reliable in that they are seen to correspond with reality.

6.4. Why should we concern ourselves exclusively with finitistic reductionism? What about predicativistic or intuitionistic reductionism?

This objection has been partially answered in the digression at the end of §3. Finitism is much more restricted than either predicativism or intuitionism. Finitistic reasoning is unique because of its clear real-world meaning and its indispensability for all scientific thought. Nonfinitistic reasoning can be accused of referring not to anything in reality but only to arbitrary mental constructions. Hence nonfinitistic mathematics can be accused of being not science but merely a mental game played for the amusement of mathematicians. Proponents of predicativism and intuitionism have never tried to defend their respective doctrines against such accusations. Finitistic reductionism is an attempt to defend infinitistic mathematics by showing that at least some of it is more than a mental game and does correspond to something in reality. It is difficult to imagine how any such goal could be advanced by predicativistic or intuitionistic reductionism.

6.5. Are the possibilities of finitism really exhausted by PRA? Didn’t Hilbert himself allow for an extended notion of finitism which would transcend the primitive recursive functions?

One might try to insist that certain multiply recursive functions such as the Ackermann function ought to be allowed as finitistic. However, Reverse Mathematics seems to indicate that such relatively minor changes would not significantly enlarge the class of finitistically reducible theorems. Hence the conclusions of §4 would remain essentially unaffected.

It is also true that Hilbert [13], p. 389, discussed a certain rather wide class of recursions of higher type. But Hilbert did not assert that such recursions are prima facie finitistic. Rather he presented them as part of his alleged proof of the Continuum Hypothesis, based on his incorrect belief that all of infinitistic mathematics is finitistically reducible. Certainly the 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 finitism with PRA. All such objections have been dealt with adequately by Tait [25].

6.6. The development of mathematics within Z_{2} or subsystems of Z_{2} involves a fairly heavy coding machinery. Doesn’t this vitiate the claim of such subsystems to reflect mathematical practice?

It is true that the language of Z_{2} requires mathematical objects such as real numbers, continuous functions, complete separable metric spaces, etc. to be encoded as subsets of ℕ in a somewhat arbitrary way. (See [3, 8, 21, 24].) However, this coding in subsystems of Z_{2} is not more arbitrary or burdensome than the coding which takes place when we develop mathematics within, say, ZFC. Besides, the coding machinery could be eliminated by passing to appropriate conservative extensions with special variables ranging over real numbers, etc. If this were done, the codes would appear only in the proofs of the conservation results. I do not believe that the coding issue has any important effect on the program of finitistic reductionism.

6.7. The systems WKL_{0} and WKL_{0}^{+} do not capture the full range of standard, infinitistic mathematics. Many well-known standard theorems cannot be proved at all in these systems. And even when a standard theorem is provable in WKL_{0} or WKL_{0}^{+}, the proof there is sometimes much more complicated than the standard proof. Doesn’t this undercut the claim of WKL_{0} and WKL_{0}^{+} to embody a partial realization of Hilbert’s Program?

Gödel’s Theorem and Reverse Mathematics imply that many well-known standard mathematical theorems are not finitistically reducible at all. Therefore, the fact that these theorems are not provable in WKL_{0} or WKL_{0}^{+} does not disturb us in the least. It merely prevents our partial realization of Hilbert’s Program from being a total one.

Somewhat more worrisome is the gap between standard proofs and proofs in WKL_{0} or WKL_{0}^{+}. However, this gap is certainly not wider than the one between Eulerian infinitesimal analysis and Weierstrassian ϵ-δ arguments. Moreover Hilbert explicitly embraced Weierstrass’ reconstruction of analysis as a model for his own Program if not an integral part of it. “Just as operations with the infinitely small were replaced by processes in the finite that have quite the same results and lead to quite the same elegant formal relations, so the modes of inference employing the infinite must be replaced generally by finite processes that have precisely the same results, that is, that permit us to carry out proofs along the same lines and to use the same methods of obtaining formulas and theorems.” These words of Hilbert [13], p. 370, make me doubt that he would have been troubled by the above-mentioned gap.

6.8. The systems WKL_{0} and WKL_{0}^{+} do not seem to correspond to any coherent, sharply defined philosophical or mathematical doctrine. Aren’t WKL_{0} and WKL_{0}^{+} mere ad hoc creations?

No, they are not mere ad hoc creations. The axioms of WKL_{0} and WKL_{0}^{+} embody compactness and Baire category respectively. These two principles are well known to be pervasive in infinitistic mathematics. (They are two different ways of affirming the existence of “enough points” in continuous media.) Moreover, the principal axiom of WKL_{0} is known to be equivalent over RCA_{0} to a number of key mathematical theorems. For instance, each of the Theorems 4.1 through 4.7, which were listed in §4 as being provable in WKL_{0}, is in fact equivalent to WKL_{0} over RCA_{0}. These equivalences come from Reverse Mathematics and provide further evidence of the naturalness of WKL_{0}.

Perhaps WKL_{0} and WKL_{0}^{+} do not correspond to any set of a priori ontological commitments such as might be proposed by philosophers unacquainted with the history and current state of mathematics. However, mathematics is entitled to define its own principles in accordance with its own needs, so long as these principles are compatible with the needs of the other sciences and with sound philosophy. This seems to leave room for systems such as WKL_{0} and WKL_{0}^{+}.

6.9. The claimed partial realization of Hilbert’s Program is only patchwork. Infinitistic theorems are validated one at a time by laboriously reestablishing them within WKL_{0} or WKL_{0}^{+} or similar systems. Doesn’t such a piecemeal procedure lack the “once and for all” grandeur of Hilbert’s visionary proposal?

Let me say first that the work reported in §4 is much more systematic than it may appear from the outside. Many branches of infinitistic mathematics depend on a few key nonconstructive existence theorems. If these theorems or a reasonable substitute can be proved within WKL_{0}, the rest follows routinely. Thus WKL_{0} includes whole branches of mathematics and not only the theorems which were mentioned in §4 for illustrative purposes. It seems that most of the “applicable” or “concrete” branches of mathematics fall into this category. For example, the Artin–Schreier solution of Hilbert’s 17th Problem can be carried out within WKL_{0}. (See Friedman–Simpson– Smith [8].) I would estimate that at least 85% of existing mathematics can be formalized within WKL_{0} or WKL_{0}^{+} or stronger systems which are conservative over PRA with respect to Π_{2}^{0} sentences. Of course highly set-theoretical topics are excluded, but it is remarkable how many topics which at first may seem highly set-theoretical turn out not to be so. For instance, the Hahn– Banach Theorem for separable Banach spaces turns out to be provable in WKL_{0}. (See Brown–Simpson [3].)

Having said this, I must admit that my plodding procedure lacks the grand sweep of Hilbert’s plan. But to some extent this is inevitable in view of Gödel’s Theorem. In any case, if there is a better procedure, I challenge the questioner to find it. Granted, it would be desirable to have a wholesale finitistic reduction of a large and easily identifiable part of infinitistic mathematics. But we do not know whether this is possible. In the meantime it seems desirable to establish finitistic reducibility for as much of infinitistic mathematics as we can. Moreover, the experience so gained may turn out to be useful in the larger task of validating infinitistic mathematics by methods not restricted to finitistic reductionism. It seems reasonable to hope that patience will pay off here.

6.10. The deduction of axioms from theorems seems like a very strange activity. Certainly such a wrong-headed enterprise would never have been tolerated by Hilbert. Can’t we dismiss as mere propaganda the attempt to associate Reverse Mathematics with Hilbert’s Program?

No, we cannot. It is true that the deduction of axioms from theorems is absent from Hilbert’s formulation of his program. It is likewise absent from the final form of our results, discussed in §4 above, which constitute partial realizations of Hilbert’s Program. However, Reverse Mathematics has played and will continue to play an important behind-the-scenes heuristic rôle in the discovery of such results. As explained and illustrated in §4, the interplay between “forward mathematics” and Reverse Mathematics leads to the discovery of formal systems such as WKL_{0} and WKL_{0}^{+}. That same interplay is essential to the ongoing process whereby we delimit the parts of mathematics that can be developed in such systems.

The fact that Hilbert’s vision did not encompass Reverse Mathematics is of no consequence. Hilbert mistakenly thought that it would be possible to reduce all of infinitistic mathematics to finitism. Had he been right, there would have been no need to delimit the finitistically reducible parts of mathematics. Reverse Mathematics is instrumental in exploring the extent to which Hilbert’s own Program can be carried out. For this reason I think that Hilbert would have recognized something of his own intention in the research which I have reported here.

6.11. What is the point of going on with Hilbert’s Program once Gödel showed it to be impossible? Why not give up on finitistic reductionism and turn to some other method of validating infinitistic mathematics? For instance, why not appeal to Platonic intuition about the cumulative hierarchy? (This objection or one very much like it was raised at the symposium by Nick Goodman.)

The obituary for Hilbert’s Program is premature to say the least. Gödel’s Theorem rules out only the most thoroughgoing total realizations of Hilbert’s Program. It does not rule out significant partial realizations. The results of §4 show that a substantial portion of the Program can in fact be carried out. (See also my answer to 6.9, above.) This is a remarkable vindication of Hilbert. It is also an embarrassing defeat for those who gleefully trumpeted Gödel’s Theorem as the death knell of finitistic reductionism.

The need to defend the integrity of mathematics has not abated. On the contrary, Gödel’s Theorem made this need more urgent than ever. Gödel supplied heavy artillery for all would-be assailants of mathematics. Authors such as Kline [17] cite Gödel with monotonous repetition and devastating effect. The assault rages as never before.

Platonic intuition is unsuitable as a weapon with which to defend the validity of mathematics. Only the first few levels of the cumulative hierarchy bear any resemblance to external reality. The rest are a huge extrapolation based on a crude model of abstract thought processes. Gödel himself comes close to admitting as much ([11], pp. 483–484). Arguing in favor of the cumulative hierarchy, Gödel ([11], pp. 477 and 485) proposes a validation in terms of testable number-theoretic consequences. Unfortunately such tests seem hard to carry out.

Finitistic reductionism is not the only plausible method by which to validate infinitistic mathematics. One might try to show that a substantial part 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, of all the possible approaches, the indirect one via finitism seems to be the most 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, Functional Analysis in Weak Subsystems of Second Order Arithmetic, Ph. D. Thesis, Pennsylvania State University, 1987, vii + 150 pages.

[3] D. K. Brown and S. G. Simpson, Which set existence axioms are needed to prove the separable Hahn–Banach theorem?, Annals of Pure and Applied Logic, 31, 1986, pp. 123–144.

[4] J. Corcoran, Review of [17], Math. Reviews 1982c, #03013.

[5] S. Feferman, Systems of predicative analysis I, II, Journal of Symbolic Logic, 29, 1964, pp. 1–30; 33, 1968, pp. 193–220.

[6] H. Friedman, Systems of second order arithmetic with restricted induction I, II (abstracts), Journal of 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 set existence axioms, Annals of Pure and Applied Logic, 25, 1983, pp. 141–181.

[9] K. Gödel, On formally undecidable propositions of Principia Mathematica and related systems I, translated by J. van Heijenoort, in: [27], pp. 596–616.

[10] K. Gödel, Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes, Dialectica, 12, 1958, pp. 280–287.

[11] K. Gödel, What is Cantor’s Continuum Problem?, in: Philosophy of Mathematics: 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, 1977.

[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. Føllesdal, 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, Philosophy 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 to induction, in: Intuitionism and Proof Theory, edited by J. Myhill, A. Kino, and R. E. Vesley, North-Holland, 1970, 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 the Cauchy/Peano theorem for ordinary differential equations?, Journal of Symbolic Logic, 49, 1984, pp. 783–802.

[22] S. G. Simpson, Friedman’s research on subsystems of second order arithmetic, in: Harvey Friedman’s Research in the Foundations of Mathematics, edited by L. Harrington, M. Morley, A. Ščedrov and S. G. Simpson, North-Holland, 1985, pp. 137–159.

[23] S. G. Simpson, Subsystems of Z_{2} and Reverse Mathematics, appendix to: G. Takeuti, Proof Theory, 2nd edition, North-Holland, 1986, pp. 434–448.

[24] S. G. Simpson, Subsystems of Second Order Arithmetic, in preparation

[25] W. W. Tait, Finitism, Journal of Philosophy, 1981, pp. 524–546.

[26] G. Takeuti, Recent topics on proof theory (in Japanese), Journal of the Japan Association for Philosophy of Science, 17, 1984, pp. 1–5.

[27] J. van Heijenoort (editor), From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931, Harvard University Press, 1967, xii + 660 pages.

[28] E. P. Wigner, The unreasonable effectiveness of mathematics in the natural sciences, Communications on Pure and Applied Mathematics, 13, 1960, pp. 1–14.