The period from 1900 to 1935 was particularly fruitful and important for the development of logic and logical metatheory. This survey is organized along eight "itineraries" concentrating on historically and conceptually linked strands in this development. Itinerary I deals with the evolution of conceptions of axiomatics. Itinerary II centers on the logical work of Bertrand Russell. Itinerary III presents the development of set theory from Zermelo onward. Itinerary IV discusses the contributions of the algebra of logic tradition, in particular, Löwenheim (...) and Skolem. Itinerary V surveys the work in logic connected to the Hilbert school, and itinerary V deals specifically with consistency proofs and metamathematics, including the incompleteness theorems. Itinerary VII traces the development of intuitionistic and many-valued logics. Itinerary VIII surveys the development of semantical notions from the early work on axiomatics up to Tarski's work on truth. (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)

Hilbert’s program was an ambitious and wide-ranging project in the philosophy and foundations of mathematics. In order to “dispose of the foundational questions in mathematics once and for all,” Hilbert proposed a two-pronged approach in 1921: first, classical mathematics should be formalized in axiomatic systems; second, using only restricted, “finitary” means, one should give proofs of the consistency of these axiomatic systems. Although Gödel’s incompleteness theorems show that the program as originally conceived cannot be carried out, it had many partial (...) successes, and generated important advances in logical theory and metatheory, both at the time and since. The article discusses the historical background and development of Hilbert’s program, its philosophical underpinnings and consequences, and its subsequent development and influences since the 1930s. (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)

Heinrich Behmann (1891-1970) obtained his Habilitation under David Hilbert in Göttingen in 1921 with a thesis on the decision problem. In his thesis, he solved - independently of Löwenheim and Skolem's earlier work - the decision problem for monadic second-order logic in a framework that combined elements of the algebra of logic and the newer axiomatic approach to logic then being developed in Göttingen. In a talk given in 1921, he outlined this solution, but also presented important programmatic remarks on (...) the significance of the decision problem and of decision procedures more generally. The text of this talk as well as a partial English translation are included. (shrink)

In the 1920s, David Hilbert proposed a research program with the aim of providing mathematics with a secure foundation. This was to be accomplished by first formalizing logic and mathematics in their entirety, and then showing---using only so-called finitistic principles---that these formalizations are free of contradictions. ;In the area of logic, the Hilbert school accomplished major advances both in introducing new systems of logic, and in developing central metalogical notions, such as completeness and decidability. The analysis of unpublished material presented (...) in Chapter 2 shows that a completeness proof for propositional logic was found by Hilbert and his assistant Paul Bernays already in 1917--18, and that Bernays's contribution was much greater than is commonly acknowledged. Aside from logic, the main technical contribution of Hilbert's Program are the development of formal mathematical theories and proof-theoretical investigations thereof, in particular, consistency proofs. In this respect Wilhelm Ackermann's 1924 dissertation is a milestone both in the development of the Program and in proof theory in general. Ackermann gives a consistency proof for a second-order version of primitive recursive arithmetic which, surprisingly, explicitly uses a finitistic version of transfinite induction up to www . He also gave a faulty consistency proof for a system of second-order arithmetic based on Hilbert's &egr;-substitution method. Detailed analyses of both proofs in Chapter 3 shed light on the development of finitism and proof theory in the 1920s as practiced in Hilbert's school. ;In a series of papers, Charles Parsons has attempted to map out a notion of mathematical intuition which he also brings to bear on Hilbert's finitism. According to him, mathematical intuition fails to be able to underwrite the kind of intuitive knowledge Hilbert thought was attainable by the finitist. It is argued in Chapter 4 that the extent of finitistic knowledge which intuition can provide is broader than Parsons supposes. According to another influential analysis of finitism due to W. W. Tait, finitist reasoning coincides with primitive recursive reasoning. The acceptance of non-primitive recursive methods in Ackermann's dissertation presented in Chapter 3, together with additional textual evidence presented in Chapter 4, shows that this identification is untenable as far as Hilbert's conception of finitism is concerned. Tait's conception, however, differs from Hilbert's in important respects, yet it is also open to criticisms leading to the conclusion that finitism encompasses more than just primitive recursive reasoning. (shrink)

This paper is the first in a two-part series in which we discuss several notions of completeness for systems of mathematical axioms, with special focus on their interrelations and historical origins in the development of the axiomatic method. We argue that, both from historical and logical points of view, higher-order logic is an appropriate framework for considering such notions, and we consider some open questions in higher-order axiomatics. In addition, we indicate how one can fruitfully extend the usual set-theoretic semantics (...) so as to shed new light on the relevant strengths and limits of higher-order logic. (shrink)

While claiming that diagrams can only be admitted as a method of strict proof if the underlying axioms are precisely known and explicitly spelled out, Hilbert praised Minkowski’s Geometry of Numbers and his diagram-based reasoning as a specimen of an arithmetical theory operating “rigorously” with geometrical concepts and signs. In this connection, in the first phase of his foundational views on the axiomatic method, Hilbert also held that diagrams are to be thought of as “drawn formulas”, and formulas as “written (...) diagrams”, thus suggesting that the former encapsulate propositional information which can be extracted and translated into formulas. In the case of Minkowski diagrams, local geometrical axioms were actually being produced, starting with the diagrams, by a process that was both constrained and fostered by the requirement, brought about by the axiomatic method itself, that geometry ought to be made independent of analysis. This paper aims at making a twofold point. On the one hand, it shows that Minkowski’s diagrammatic methods in number theory prompted Hilbert’s axiomatic investigations into the notion of a straight line as the shortest distance between two points, which start from his earlier work focused on the role of the triangle inequality property in the foundations of geometry, and lead up to his formulation of the 1900 Fourth Problem. On the other hand, it purports to make clear how Hilbert’s assessment of Minkowski’s diagram-based reasoning in number theory both raises and illuminates conceptual compatibility concerns that were crucial to his philosophy of mathematics. (shrink)

Bertrand Russell’s 1906 article ‘The Theory of Implication’ contains an algebraic weak completeness proof for classical propositional logic. Russell did not present it as such. We give an exposition of the proof and investigate Russell’s view of what he was about, whether he could have appreciated the proof for what it is, and why there is no parallel of the proof in Principia Mathematica.

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)

After giving a brief overview of the renewal of interest in logic and the foundations of mathematics in Göttingen in the period 1914-1921, I give a detailed presentation of the approach to the foundations of mathematics found in Behmann's doctoral dissertation of 1918, Die Antinomie der transfiniten Zahl und ihre Auflösung durch die Theorie von Russell und Whitehead. The dissertation was written under the guidance of David Hilbert and was primarily intended to give a clear exposition of the solution to (...) the antinomies as found in Principia Mathematica. In the process of explaining the theory of Principia, Behmann also presented an original approach to the foundations of mathematics which saw in sense perception of concrete individuals the Archimedean point for a secure foundation of mathematical knowledge. The last part of the paper points out an important numbers of connections between Behmann's work and Hilbert's foundational thought. (shrink)

This paper collects and presents unpublished notes of Kurt Gödel concerning the field of many-valued logic. In order to get a picture as complete as possible, both formal and philosophical notes, transcribed from the Gabelsberger shorthand system, are included.

Husserl’s notion of definiteness, i.e., completeness is crucial to understanding Husserl’s view of logic, and consequently several related philosophical views, such as his argument against psychologism, his notion of ideality, and his view of formal ontology. Initially Husserl developed the notion of definiteness to clarify Hermann Hankel’s ‘principle of permanence’. One of the first attempts at formulating definiteness can be found in the Philosophy of Arithmetic, where definiteness serves the purpose of the modern notion of ‘soundness’ and leads Husserl to (...) a ‘computational’ view of logic. Inspired by Gauss and Grassmann Husserl then undertakes a further investigation of theories of manifolds. When Husserl subsequently renounces psychologism and changes his view of logic, his idea of definiteness also develops. The notion of definiteness is discussed most extensively in the pair of lectures Husserl gave in front of the mathematical society in Göttingen (1901). A detailed analysis of the lectures, together with an elaboration of Husserl’s lectures on logic beginning in 1895, shows that Husserl meant by definiteness what is today called ‘categoricity’. In so doing Husserl was not doing anything particularly original; since Dedekind’s ‘Was sind und sollen die Zahlen’ (1888) the notion was ‘in the air’. It also characterizes Hilbert’s (1900) notion of completeness. In the end, Husserl’s view of definiteness is discussed in light of Gödel’s (1931) incompleteness results. (shrink)

Hilbert’s methodological reflection has certainly shaped a new image of the axiomatic method. However, the discussion on the procedural character of the method is still open, with commentators subs...

The use of the symbol ∨for disjunction in formal logic is ubiquitous. Where did it come from? The paper details the evolution of the symbol ∨ in its historical and logical context. Some sources say that disjunction in its use as connecting propositions or formulas was introduced by Peano; others suggest that it originated as an abbreviation of the Latin word for “or,” vel. We show that the origin of the symbol ∨ for disjunction can be traced to Whitehead and (...) Russell’s pre-Principia work in formal logic. Because of Principia’s influence, its notation was widely adopted by philosophers working in logic (the logical empiricists in the 1920s and 1930s, especially Carnap and early Quine). Hilbert’s adoption of ∨ in his Grundzüge der theoretischen Logik guaranteed its widespread use by mathematical logicians. The origins of other logical symbols are also discussed. (shrink)

Some thirty years ago, two proposals were made concerning criteria for identity of proofs. Prawitz proposed to analyze identity of proofs in terms of the equivalence relation based on reduction to normal form in natural deduction. Lambek worked on a normalization proposal analogous to Prawitz's, based on reduction to cut-free form in sequent systems, but he also suggested understanding identity of proofs in terms of an equivalence relation based on generality, two derivations having the same generality if after generalizing maximally (...) the rules involved in them they yield the same premises and conclusions up to a renaming of variables. These two proposals proved to be extensionally equivalent only for limited fragments of logic. The normalization proposal stands behind very successful applications of the typed lambda calculus and of category theory in the proof theory of intuitionistic logic. In classical logic, however, it did not fare well. The generality proposal was rather neglected in logic, though related matters were much studied in pure category theory in connection with coherence problems, and there are also links to low-dimensional topology and linear algebra. This proposal seems more promising than the other one for the general proof theory of classical logic. (shrink)

Coherence is demonstrated for categories with binary products and sums, but without the terminal and the initial object, and without distribution. This coherence amounts to the existence of a faithful functor from a free category with binary products and sums to the category of relations on finite ordinals. This result is obtained with the help of proof-theoretic normalizing techniques. When the terminal object is present, coherence may still be proved if of binary sums we keep just their bifunctorial properties. It (...) is found that with the simplest understanding of coherence this is the best one can hope for in bicartesian categories. The coherence for categories with binary products and sums provides an easy decision procedure for equality of arrows. It is also used to demonstrate that the categories in question are maximal, in the sense that in any such category that is not a preorder all the equations between arrows involving only binary products and sums are the same. This shows that the usual notion of equivalence of proofs in nondistributive conjunctive-disjunctive logic is optimally defined: further assumptions would make this notion collapse into triviality. (shrink)

Church's Thesis asserts that the only numeric functions that can be calculated by effective means are the recursive ones, which are the same, extensionally, as the Turing-computable numeric functions. The Abstract State Machine Theorem states that every classical algorithm is behaviorally equivalent to an abstract state machine. This theorem presupposes three natural postulates about algorithmic computation. Here, we show that augmenting those postulates with an additional requirement regarding basic operations gives a natural axiomatization of computability and a proof of Church's (...) Thesis, as Gödel and others suggested may be possible. In a similar way, but with a different set of basic operations, one can prove Turing's Thesis, characterizing the effective string functions, and--in particular--the effectively-computable functions on string representations of numbers. (shrink)

This paper explores the relationship borne by the traditional paradoxes of set theory and semantics to formal incompleteness phenomena. A central tool is the application of the Arithmetized Completeness Theorem to systems of second-order arithmetic and set theory in which various “paradoxical notions” for first-order languages can be formalized. I will first discuss the setting in which this result was originally presented by Hilbert & Bernays (1939) and also how it was later adapted by Kreisel (1950) and Wang (1955) in (...) order to obtain formal undecidability results. A generalization of this method will then be presented whereby Russell’s paradox, a variant of Mirimanoff’s paradox, the Liar, and the Grelling–Nelson paradox may be uniformly transformed into incompleteness theorems. Some additional observations are then framed relating these results to the unification of the set theoretic and semantic paradoxes, the intensionality of arithmetization (in the sense of Feferman, 1960), and axiomatic theories of truth. (shrink)

Steve Awodey and Erich H. Reck. Completeness and Categoricity: 19th Century Axiomatics to 21st Century Senatics.

This paper is the second in a two-part series in which we discuss several notions of completeness for systems of mathematical axioms, with special focus on their interrelations and historical origins in the development of the axiomatic method. We argue that, both from historical and logical points of view, higher-order logic is an appropriate framework for considering such notions, and we consider some open questions in higher-order axiomatics. In addition, we indicate how one can fruitfully extend the usual set-theoretic semantics (...) so as to shed new light on the relevant strengths and limits of higher-order logic. (shrink)

In 1929 Carnap gave a paper in Prague on Investigations in General Axiomatics; a briefsummary was published soon after. Its subject lookssomething like early model theory, and the mainresult, called the Gabelbarkeitssatz, appears toclaim that a consistent set of axioms is complete justif it is categorical. This of course casts doubt onthe entire project. Though there is no furthermention of this theorem in Carnap''s publishedwritings, his Nachlass includes a largetypescript on the subject, Investigations inGeneral Axiomatics. We examine this work here,showing (...) that it provides important insights intoCarnap''s development during this critical period, thetransition from Aufbau to Syntax,especially regarding the nature and motivation ofCarnap''s logicism. Moreover, we show how theAxiomatics influenced Carnap''s student Gödel inreaching the fundamental logical results that soonafterwards undermined Carnap''s project. (shrink)

The aim of this paper is to clarify why propositional logic is Post complete and its weak completeness was almost unnoticed by Hilbert and Bernays, while first-order logic is Post incomplete and its weak completeness was seen as an open problem by Hilbert and Ackermman. Thus, I will compare propositional and first-order logic in the Prinzipien der Mathematik, Bernays’s second Habilitationsschrift and the Grundzüge der Theoretischen Logik. The so called “arithmetical interpretation”, the conjunctive and disjunctive normal forms and the soundness (...) of the propositional rules of inference deserve special emphasis. (shrink)

In his Doppelvortrag, Edmund Husserl introduced two concepts of “definiteness” which have been interpreted as a vindication of his role in the history of completeness. Some commentators defended that the meaning of these notions should be understood as categoricity, while other scholars believed that it is closer to syntactic completeness. A detailed study of the early twentieth-century axiomatics and Husserl’s Doppelvortrag shows, however, that many concepts of completeness were conflated as equivalent. Although “absolute definiteness” was principally an attempt to characterize (...) non-extendible manifolds and axiom systems, an absolutely definite theory has a unique model and, thus, it is non-forkable and semantically complete. Non-forkability and decidability were formally delimited by Fraenkel and Carnap almost three decades later and, in fact, they mentioned Husserl as precursor of the latter. Therefore, this paper contributes to a reassessment of Husserl’s place in the history of logic. (shrink)

Hilbert’s choice operators τ and ε, when added to intuitionistic logic, strengthen it. In the presence of certain extensionality axioms they produce classical logic, while in the presence of weaker decidability conditions for terms they produce various superintuitionistic intermediate logics. In this thesis, I argue that there are important philosophical lessons to be learned from these results. To make the case, I begin with a historical discussion situating the development of Hilbert’s operators in relation to his evolving program in the (...) foundations of mathematics and in relation to philosophical motivations leading to the development of intuitionistic logic. This sets the stage for a brief description of the relevant part of Dummett’s program to recast debates in metaphysics, and in particular disputes about realism and anti-realism, as closely intertwined with issues in philosophical logic, with the acceptance of classical logic for a domain reflecting a commitment to realism for that domain. Then I review extant results about what is provable and what is not when one adds epsilon to intuitionistic logic, largely due to Bell and DeVidi, and I give several new proofs of intermediate logics from intuitionistic logic+ε without identity. With all this in hand, I turn to a discussion of the philosophical significance of choice operators. Among the conclusions I defend are that these results provide a finer-grained basis for Dummett’s contention that commitment to classically valid but intuitionistically invalid principles reflect metaphysical commitments by showing those principles to be derivable from certain existence assumptions; that Dummett’s framework is improved by these results as they show that questions of realism and anti-realism are not an “all or nothing” matter, but that there are plausibly metaphysical stances between the poles of anti-realism and realism, because different sorts of ontological assumptions yield intermediate rather than classical logic; and that these intermediate positions between classical and intuitionistic logic link up in interesting ways with our intuitions about issues of objectivity and reality, and do so usefully by linking to questions around intriguing everyday concepts such as “is smart,” which I suggest involve a number of distinct dimensions which might themselves be objective, but because of their multivalent structure are themselves intermediate between being objective and not. Finally, I discuss the implications of these results for ongoing debates about the status of arbitrary and ideal objects in the foundations of logic, showing among other things that much of the discussion is flawed because it does not recognize the degree to which the claims being made depend on the presumption that one is working with a very strong logic. (shrink)

The topic of this article is Hilbert’s axiom of solvability, that is, his conviction of the solvability of every mathematical problem by means of a finite number of operations. The question of solvability is commonly identified with the decision problem. Given this identification, there is not the slightest doubt that Hilbert’s conviction was falsified by Gödel’s proof and by the negative results for the decision problem. On the other hand, Gödel’s theorems do offer a solution, albeit a negative one, in (...) the form of an impossibility proof. In this sense, Hilbert’s optimism may still be justified. Here I argue that Gödel’s theorems opened the door to proof theory and to the remarkably successful development of generalized as well as relativized realizations of Hilbert’s program. Thus, the fall of absolute certainty came hand in hand with the rise of partially secure and reliable foundations of mathematical knowledge. Not all was lost and much was gained. (shrink)