Abstract.This paper is the first in a series of three which culminates in an ordinal analysis of Π12-comprehension. On the set-theoretic side Π12-comprehension corresponds to Kripke-Platek set theory, KP, plus Σ1-separation. The strength of the latter theory is encapsulated in the fact that it proves the existence of ordinals π such that, for all β>π, π is β-stable, i.e. Lπ is a Σ1-elementary substructure of Lβ. The objective of this paper is to give an ordinal analysis of a scenario of (...) not too complicated stability relations as experience has shown that the understanding of the ordinal analysis of Π12-comprehension is greatly facilitated by explicating certain simpler cases first.This paper introduces an ordinal representation system based on ν-indescribable cardinals which is then employed for determining an upper bound for the proof–theoretic strength of the theory KPi+ ∀ρ ∃ππ is π+ρ-stable, where KPi is KP augmented by the axiom saying that every set is contained in an admissible set. (shrink)

In this paper we devise some technical tools for dealing with problems connected with the philosophical view usually called mathematical instrumentalism. These tools are interesting in their own right, independently of their philosophical consequences. For example, we show that even though the fragment of Peano's Arithmetic known as IΣ₁ is a conservative extension of the equational theory of Primitive Recursive Arithmetic (PRA). IΣ₁ has a super-exponential speed-up over PRA. On the other hand, theories studied in the Program of Reverse Mathematics (...) that formalize powerful mathematical principles have only polynomial speed-up over IΣ₁. (shrink)

Recent attention to "self-consistent" (Rosser-style) systems raises anew the question of the proper interpretation of the Gödel Second Incompleteness Theorem and its effect on Hilbert's Program. The traditional rendering and consequence is defended with new arguments justifying the intensional correctness of the derivability conditions.

In the first part of this paper we discuss some aspects of Detlefsen's attempt to save Hilbert's Program from the consequences of Godel's Second Incompleteness Theorem. His arguments are based on his interpretation of the long standing and well-known controversy on what, exactly, finitistic means are. In his paper [1] Detlefsen takes the position that there is a form of the ω-rule which is a finitistically valid means of proof, sufficient to prove the consistency of elementary number theory Z. On (...) the other hand, he claims that Z with its first-order logic is not strong enough to allow a formalization of such an ω-rule. This would explain why the unprovability of $\operatorname{Con}(Z)$ in Z does not imply that the consistency of Z cannot be proved by finitistic means. We show that Detlefsen's proposal is unacceptable as originally formulated in [1], but that a reasonable modification of the rule he suggest leads to a partial program already studied for many years. We investigate the scope of such a program in terms of proof-theoretic reducibilities. We also show that this partial program encompasses mathematically important theories studied in the "Reverse Mathematics" program. In order to investigate the provability with such a modified rule, we define new consistency and provability predicates which are weaker than the usual ones. We then investigate their properties, including a few that have no apparent philosophical significance but compare interestingly with the properties of the program based on the iteration of our ω-rule. We determine some of the limitations of such programs, pointing out that these limitations partly explain why partial programs that have been successfully carried out use quite different and substantially more radical extensions of finitistic methods with more general forms of restricted reasoning. (shrink)

The background of these remarks is that in 1967, in ‘’Constructive reasoning” [27], I sketched an argument that finitist arithmetic coincides with primitive recursive arithmetic, P RA; and in 1981, in “Finitism” [28], I expanded on the argument. But some recent discussions and some of the more recent literature on the subject lead me to think that a few further remarks would be useful.

Philosophers of language have drawn on metamathematical results in varied ways. Extensionalist philosophers have been particularly impressed with two, not unrelated, facts: the existence, due to Frege/Tarski, of a certain sort of semantics, and the seeming absence of intensional contexts from mathematical discourse. The philosophical import of these facts is at best murky. Extensionalists will emphasize the success and clarity of the model theoretic semantics; others will emphasize the relative poverty of the mathematical idiom; still others will question the aptness (...) of the standard extensional semantics for mathematics. In this paper I investigate some implications of the Gödel Second Incompleteness Theorem for these positions. I argue that the realm of mathematics, proof theory in particular, has been a breeding ground for intensionality and that satisfactory intensional semantic theories are implicit in certain rigorous technical accounts. (shrink)

Some of the most important developments of symbolic logic took place in the 1920s. Foremost among them are the distinction between syntax and semantics and the formulation of questions of completeness and decidability of logical systems. David Hilbert and his students played a very important part in these developments. Their contributions can be traced to unpublished lecture notes and other manuscripts by Hilbert and Bernays dating to the period 1917-1923. The aim of this paper is to describe these results, focussing (...) primarily on propositional logic, and to put them in their historical context. It is argued that truth-value semantics, syntactic ("Post-") and semantic completeness, decidability, and other results were first obtained by Hilbert and Bernays in 1918, and that Bernays's role in their discovery and the subsequent development of mathematical logic is much greater than has so far been acknowledged. (shrink)

In the early 1920s, the German mathematician David Hilbert (1862–1943) put forward a new proposal for the foundation of classical mathematics which has come to be known as Hilbert's Program. It calls for a formalization of all of mathematics in axiomatic form, together with a proof that this axiomatization of mathematics is consistent. The consistency proof itself was to be carried out using only what Hilbert called “finitary” methods. The special epistemological character of finitary reasoning then yields the required justification (...) of classical mathematics. Although Hilbert proposed his program in this form only in 1921, various facets of it are rooted in foundational work of his going back until around 1900, when he first pointed out the necessity of giving a direct consistency proof of analysis. Work on the program progressed significantly in the 1920s with contributions from logicians such as Paul Bernays, Wilhelm Ackermann, John von Neumann, and Jacques Herbrand. It was also a great influence on Kurt Gödel, whose work on the incompleteness theorems were motivated by Hilbert's Program. Gödel's work is generally taken to show that Hilbert's Program cannot be carried out. It has nevertheless continued to be an influential position in the philosophy of mathematics, and, starting with the work of Gerhard Gentzen in the 1930s, work on so-called Relativized Hilbert Programs have been central to the development of proof theory. (shrink)

The epsilon calculus is a logical formalism developed by David Hilbert in the service of his program in the foundations of mathematics. The epsilon operator is a term-forming operator which replaces quantifiers in ordinary predicate logic. Specifically, in the calculus, a term εx A denotes some x satisfying A(x), if there is one. In Hilbert's Program, the epsilon terms play the role of ideal elements; the aim of Hilbert's finitistic consistency proofs is to give a procedure which removes such terms (...) from a formal proof. The procedures by which this is to be carried out are based on Hilbert's epsilon substitution method. The epsilon calculus, however, has applications in other contexts as well. The first general application of the epsilon calculus was in Hilbert's epsilon theorems, which in turn provide the basis for the first correct proof of Herbrand's theorem. More recently, variants of the epsilon operator have been applied in linguistics and linguistic philosophy to deal with anaphoric pronouns. (shrink)

After sketching the main lines of Hilbert's program, certain well-known andinfluential interpretations of the program are critically evaluated, and analternative interpretation is presented. Finally, some recent developments inlogic related to Hilbert's program are reviewed.

The aim of the paper is to discuss the influence exercised by Russell's thought inGöttingen in the period leading to the formulation of Hilbert's program in theearly twenties. I show that after a period of intense foundational work, culminatingwith the departure from Göttingen of Zermelo and Grelling in 1910 we witnessa reemergence of interest in foundations of mathematics towards the end of 1914. Itis this second period of foundational work that is my specific interest. Through theuse of unpublished archival sources (...) I will describe how Hilbert, Behmann, and Bernays,among others, were influenced by and reacted to the technical and philosophical thesespresented in Principia Mathematica. I also argue that there are some elements of continuity between Russell's approach and Hilbert's program as it was presented inthe early twenties. (shrink)

Hilbert's program attempts to show that our mathematical knowledge can be certain because we are able to know for certain the truths of elementary arithmetic. I argue that, in the absence of a theory of mathematical truth, Hilbert does not have a complete theory of our arithmetical knowledge. Further, while his deployment of a Kantian notion of intuition seems to promise an answer to scepticism, there is no way to complete Hilbert's epistemology which would answer to his avowed aims.

is a fragment of first-order aritlimetic so weak that it cannot prove the totality of an iterated exponential fimction. Surprisingly, however, the theory is remarkably robust. I will discuss formal results that show that many theorems of number theory and combinatorics are derivable in elementary arithmetic, and try to place these results in a broader philosophical context.

Does science justify any part of mathematics and, if so, what part? These questions are related to the so-called indispensability arguments propounded, among others, by Quine and Putnam; moreover, both were led to accept significant portions of set theory on that basis. However, set theory rests on a strong form of Platonic realism which has been variously criticized as a foundation of mathematics and is at odds with scientific realism. Recent logical results show that it is possible to directly formalize (...) almost all, if not all, scientifically applicable mathematics in a formal system that is justified simply by Peano Arithmetic (via a proof-theoretical reduction). It is argued that this substantially vitiates the indispensability arguments. (shrink)

We discuss the development of metamathematics in the Hilbert school, and Hilbert’s proof-theoretic program in particular. We place this program in a broader historical and philosophical context, especially with respect to nineteenth century developments in mathematics and logic. Finally, we show how these considerations help frame our understanding of metamathematics and proof theory today.

We consider a seemingly popular justification (we call it the Re-flexivity Defense) for the third derivability condition of the Hilbert-Bernays-Löb generalization of Godel's Second Incompleteness Theorem (G2). We argue that (i) in certain settings (rouglily, those where the representing theory of an arithmetization is allowed to be a proper subtheory of the represented theory), use of the Reflexivity Defense to justify the tliird condition induces a fourth condition, and that (ii) the justification of this fourth condition faces serious obstacles. We (...) conclude that, in the types of settings mentioned, the Reflexivity Defense does not justify the usual ‘reading’ of G2—namely, that the consistency of the represented theory is not provable in the representing theory. (shrink)

Hilbert proposed the epsilon substitution method as a basis for consistency proofs. Hilbert's Ansatz for finding a solving substitution for any given finite set of transfinite axioms is, starting with the null substitution S0, to correct false values step by step and thereby generate the process S0,S1,… . The problem is to show that the approximating process terminates. After Gentzen's innovation, Ackermann 162) succeeded to prove termination of the process for first order arithmetic. Inspired by G. Mints as an Ariadne's (...) thread we formulate the epsilon substitution method for the theory ID1 of non-iterated inductive definitions for disjunctions of simply universal and existential operators, and give a termination proof of the H-process based on Ackermann 162). The termination proof is based on transfinite induction up to the Howard ordinal. (shrink)

Philosophy is often conceived in the Anglophone world today as a subject that focuses on questions in particular ‘‘core areas,’’ pre-eminently epistemology and metaphysics. This article argues that the contemporary conception is a new version of the scholastic ‘‘self-indulgence for the few’’ of which Dewey complained nearly a century ago. Philosophical questions evolve, and a first task for philosophers is to address issues that arise for their own times. The article suggests that a renewal of philosophy today should turn the (...) contemporary conception inside out, attending to and developing further the valuable work being done on the supposed ‘‘periphery’’ and attending to the ‘‘core areas’’ only insofar as is necessary to address genuinely significant questions. (shrink)

In the 1920s, Ackermann and von Neumann, in pursuit of Hilbert's programme, were working on consistency proofs for arithmetical systems. One proposed method of giving such proofs is Hilbert's epsilon-substitution method. There was, however, a second approach which was not reflected in the publications of the Hilbert school in the 1920s, and which is a direct precursor of Hilbert's first epsilon theorem and a certain "general consistency result" due to Bernays. An analysis of the form of this so-called "failed proof" (...) sheds further light on an interpretation of Hilbert's programme as an instrumentalist enterprise with the aim of showing that whenever a "real" proposition can be proved by ?ideal? means, it can also be proved by "real", finitary means. (shrink)

After a brief flirtation with logicism around 1917, David Hilbertproposed his own program in the foundations of mathematics in 1920 and developed it, in concert with collaborators such as Paul Bernays andWilhelm Ackermann, throughout the 1920s. The two technical pillars of the project were the development of axiomatic systems for everstronger and more comprehensive areas of mathematics, and finitisticproofs of consistency of these systems. Early advances in these areaswere made by Hilbert (and Bernays) in a series of lecture courses atthe (...) University of Göttingen between 1917 and 1923, and notably in Ackermann's dissertation of 1924. The main innovation was theinvention of the -calculus, on which Hilbert's axiom systemswere based, and the development of the -substitution methodas a basis for consistency proofs. The paper traces the developmentof the ``simultaneous development of logic and mathematics'' throughthe -notation and provides an analysis of Ackermann'sconsistency proofs for primitive recursive arithmetic and for thefirst comprehensive mathematical system, the latter using thesubstitution method. It is striking that these proofs use transfiniteinduction not dissimilar to that used in Gentzen's later consistencyproof as well as non-primitive recursive definitions, and that thesemethods were accepted as finitistic at the time. (shrink)

IN Hilbert's theory of the foundations of any given branch of mathematics the main problem is to establish the consistency (of a suitable formalisation) of this branch. Since the (intuitionist) criticisms of classical logic, which Hilbert's theory was intended to meet, never even alluded to inconsistencies (in classical arithmetic), and since the investigations of Hilbert's school have always established much more than mere consistency, it is natural to formulate another general problem in the foundations of mathematics: to translate statements of (...) theorems and proofs in the branch considered into those of some preferred system, where the translation must satisfy certain appropriate conditions (interpretation). The problem is relative to the choice of preferred system, as is Hilbert's consistency problem since he required the consistency to be established by particular methods (finitist ones). A finitist interpretation of classical number theory, which has been published in full detail elsewhere, is here described by means of typical examples. Partial results on analysis (theory of arbitrary functions whose arguments and values are the non-negative integers) are here presented for the first time. One of these results is restricted to functions whose values are bounded; its interest derives from the fact that real numbers may be represented by such functions. It is hoped that diverse general observations and comments, which would bore the specialist, may be of help to the general reader. The specialist may find some points of interest in the last two sections of the main text and in the notes following it. (shrink)

Hilbert’s unpublished 1917 lectures on logic, analyzed here, are the beginning of modern metalogic. In them he proved the consistency and Post-completeness (maximal consistency) of propositional logic -results traditionally credited to Bernays (1918) and Post (1921). These lectures contain the first formal treatment of first-order logic and form the core of Hilbert’s famous 1928 book with Ackermann. What Bernays, influenced by those lectures, did in 1918 was to change the emphasis from the consistency and Post-completeness of a logic to its (...) soundness and completeness: a sentence is provable if and only if valid. By 1917, strongly influenced by PM, Hilbert accepted the theory of types and logicism -a surprising shift. But by 1922 he abandoned the axiom of reducibility and then drew back from logicism, returning to his 1905 approach of trying to prove the consistency of number theory syntactically. (shrink)

Hilbert's plan for understanding the concept of infinity required the elimination of non‐finitist machinery from proofs of finitist assertions. The failure of the original plan leads to a hierarchy of progressively less elementary, but still constructive methods instead of finitist ones . A mathematical proof of this failure requires a definition of « finitist ».—The paper sketches the three principal methods for the syntactic analysis of non‐constructive mathematics, the resulting consistency proofs and constructive interpretations, modelled on Herbrand's theorem, and their (...) mathematical and logical consequences. A characterization of finitist proofs is sketched. A remark on the completeness of the predicate calculus concludes the paper. Throughout open problems and alternative approaches are emphasized.ZusammenfassungHilbert sah das Verstehen des Begriffs des Unendlichen in der Eliminierung nichtfiniter Methoden aus Beweisen finiter Sätze. Das Versagen dieses Unternehmens führt zu einer Hierarchic progressiv weniger elementarer, aber noch konstruktiver Methoden, statt der finiten . Ein Unmöglichkeitsbeweis des ursprünglichen Planes setzt eine Definition von « finit » voraus.—Die drei wichtigsten Methoden der syntaktischen Analyse nichtkonstruktiver mathematischer Theorien, die daraus gewonnenen Widerspruchsfreiheitsbeweise and konstruktiven Interpretationen and deren mathematische and logische Anwendungen werden besprochen. Eine Prazisierung des Begriffs « finit » wird skizziert. Eine Bemerkung zur Vollstandigkeit des engeren Funktionenkalküls beschliesst die Abhandlung.—Oflene Fragen and komplementare Fragestellungen werden betont. (shrink)

The goals of reduction andreductionism in the natural sciences are mainly explanatoryin character, while those inmathematics are primarily foundational.In contrast to global reductionistprograms which aim to reduce all ofmathematics to one supposedly ``universal'' system or foundational scheme, reductive proof theory pursues local reductions of one formal system to another which is more justified in some sense. In this direction, two specific rationales have been proposed as aims for reductive proof theory, the constructive consistency-proof rationale and the foundational reduction rationale. However, (...) recent advances in proof theory force one to consider the viability of these rationales. Despite the genuine problems of foundational significance raised by that work, the paper concludes with a defense of reductive proof theory at a minimum as one of the principal means to lay out what rests on what in mathematics. In an extensive appendix to the paper,various reduction relations betweensystems are explained and compared, and arguments against proof-theoretic reduction as a ``good'' reducibilityrelation are taken up and rebutted. (shrink)

In this paper I have considered various attempts to attribute significance to Gödel's second incompleteness theorem (G2 for short). Two of these attempts (Beth-Cohen and the position maintaining that G2 shows the failure of Hilbert's Program), I have argued, are false. Two others (an argument suggested by Beth, Cohen and ??? and Resnik's Interpretation), I argue, are groundless.

In this paper we devise some technical tools for dealing with problems connected with the philosophical view usually called mathematical instrumentalism. These tools are interesting in their own right, independently of their philosophical consequences. For example, we show that even though the fragment of Peano's Arithmetic known as IΣ₁ is a conservative extension of the equational theory of Primitive Recursive Arithmetic, IΣ₁ has a super-exponential speed-up over PRA. On the other hand, theories studied in the Program of Reverse Mathematics that (...) formalize powerful mathematical principles have only polynomial speed-up over IΣ₁. (shrink)

Hilbert’s program in the philosophy of mathematics comes in two parts. One part is a technical part. To carry out this part of the program one has to prove a certain technical result. The other part of the program is a philosophical part. It is concerned with philosophical questions that are the real aim of the program. To carry out this part one, basically, has to show why the technical part answers the philosophical questions one wanted to have answered. Hilbert (...) probably thought that he had completed the philosophical part of his program, maybe up to a few details. What was left to do was the technical part. To carry it out one, roughly, had to give a precise axiomatization of mathematics and show that it is consistent on purely finitistic grounds. This would come down to giving a relative consistency proof of mathematics in finitist mathematics, or to give a proof-theoretic reduction of mathematics on to finitist mathematics (we will look at these notions in more detail soon). It is widely believed that Gödel’s theorems showed that the technical part of Hilbert’s program could not be carried out. Gödel’s theorems show that the consistency of arithmetic can not even be proven in arithmetic, not to speak of by finitistic means alone. So, the technical part of Hilbert’s program is hopeless, and since Hilbert’s program essentially relied on both the technical and the philosophical part, Hilbert’s program as a whole is hopeless. Justified as this attitude is, it is a bit unfortunate. It is unfortunate because it takes away too much attention from the philosophical part of Hilbert’s program. And this is unfortunate for two reasons. (shrink)