The Emergence of First-Order Logic

First published Sat Nov 17, 2018

For anybody schooled in modern logic, first-order logic can seem anentirely natural object of study, and its discovery inevitable. It issemantically complete; it is adequate to the axiomatization of allordinary mathematics; and Lindström’s theorem shows that itis the maximal logic satisfying the compactness andLöwenheim-Skolem properties. So it is not surprising thatfirst-order logic has long been regarded as the “right”logic for investigations into the foundations of mathematics. Itoccupies the central place in modern textbooks of mathematical logic,with other systems relegated to the sidelines. The history, however,is anything but straightforward, and is certainly not a matter of asudden discovery by a single researcher. The emergence is bound upwith technical discoveries, with differing conceptions of whatconstitutes logic, with different programs of mathematical research,and with philosophical and conceptual reflection. So if first-orderlogic is “natural”, it is natural only in retrospect. Thestory is intricate, and at points contested; the following entry canonly provide an overview. Discussions of various aspects of thedevelopment are provided by Goldfarb 1979, Moore 1988, Eklund 1996,Brady 2000, Ferreirós 2001, Sieg 2009, Mancosu, Zach &Badesa 2010, Schiemer & Reck 2013, the notes to Hilbert [LFL], andthe encyclopedic handbook Gabbay & Woods 2009.

1. George Boole

The modern study of logic is commonly dated to 1847, with theappearance of Boole’sMathematical Analysis of Logic.This work established that Aristotle’s syllogistic logic can betranslated into an algebraic calculus, whose symbols Boole interpretedas referring either to classes or to propositions. His systemencompasses what is today called sentential (or Boolean) logic, but itis also capable of expressing rudimentary quantifications. Forinstance, the proposition “AllXs areYs” isrepresented in his system by the equation \(xy = x\), with themultiplication being thought of either as an intersection of sets, oras logical conjunction. “SomeXs areYs” ismore difficult, and its expression more artificial. Boole introduces a(tacitly: non-empty) setV containing the items common toX andY; the proposition is then written \(xy =V\) (1847: 21). Boole’s system, in modern terms, can be viewedas a fragment of monadic first-order logic. It is first-order becauseits notational resources cannot express a quantification that rangesover predicates. It is monadic because it has no notation forn-ary relations. And it is a fragment because it cannot expressnested quantifications (“for every girl, there exists a boy wholoves her”). But these are our categories: not Boole’s.His logical system has no symbols corresponding to the quantifiers; soeven to call it a restricted system of quantificational logic isanachronistic.

The two principal augmentations to Boole’s system that produceda recognizably modern logic were (a) the introduction, in addition toone-placed predicates (“x is mortal”), ofmany-placed relations (“x is the brother ofy”; “x lies betweeny andz”); and (b) the introduction of a notation for universaland existential quantification.

Two logicians working in the Boolean tradition carried out thesesteps. The first step was partially carried out by Augustus De Morgan(in De Morgan 1864). The second was carried out by C. S. Peirce (inPeirce 1885). Working entirely independently, Gottlob Frege carriedout both steps simultaneously in hisBegriffsschrift of 1879.The subsequent history for several decades is a branching structure,with numerous researchers working in different traditions and onlypartially aware of one another’s accomplishments.

2. Charles S. Peirce

Peirce worked in the algebraic tradition of Boole. His first logicpapers appeared in 1867;they simplify Boole’s system, re-interpret union or logicaladdition \(A+B\) so that it applies also whenA andBare not disjoint, correct several mistakes, and explore connectionsbetween logic, arithmetic, and algebra.

Three years later, in his “Description of a Notation for theLogic of Relatives” (1870) Peirce produced a major expansion ofBoole’s system. De Morgan had pointed out (De Morgan 1864) thatthe Aristotelian syllogistic was incapable of handling such inferencesas, “If every man is an animal, then every head of a man is ahead of an animal”. De Morgan had introduced a logic ofrelations, defined the converse and the contrary of a relation, and,for relations such as “X is a lover ofY”and “Z is a servant ofW”, had explored suchcompositions of relations as “x is the lover of a servantofy”. This work successfully expanded the Aristoteliansyllogistic logic, but was also limited in several ways. First, DeMorgan only operated with binary relations. Secondly, his notation wasclumsy. (For example: if \(X\pdot\pdot LY\) designates thatXis a lover ofY, then \(X\pdot LY\) designates thatX isnot a lover ofY. De Morgan has no separate sign for negation,nor for the Boolean propositional connectives.)

Peirce noticed these shortcomings, and in 1870 showed how to extendBoole’s logic to cover

the whole realm of formal logic, instead of being restricted to thatsimplest and least useful part of the subject, the logic of absoluteterms, which, when [Boole] wrote, was the only formal logic known.

He studied the composition of relations with each other and withclass-terms, and worked out the principal laws for the resultingabstract algebraic system, ultimately showing that the linearassociative algebras studied by his father (Benjamin Peirce, theHarvard mathematician) could all be defined in terms of what he called“elementary relatives”. His 1870 system, although a largeadvance both on Boole and on De Morgan, remains notationally awkward,and in retrospect it is clear that it needed the theory ofquantification. But it was the first successful attempt to extendBoole’s system into the logic of relations.

In 1880 Peirce described the procedure for reducing formulae of thesentential calculus to conjunctive and disjunctive normal form, andalso in unpublished work demonstrated that the sentential calculus canbe obtained from the single connective of joint denial (“neitherp norq”). His 1881, “On the Logic ofNumber”, examined the foundations of arithmetic, and analyzedthe natural numbers in terms of discrete, linearly ordered setswithout a maximum element. He gave informal recursive definitions ofaddition and multiplication, and proved that both operations wereassociative and commutative.

In two remarkable papers, the short note 1883 and the longer “Onthe Algebra of Logic” of 1885, he introduced a modern notationfor what he was the first to call the “quantifier”. Heviewed his quantifiers (for which he used the symbols \(\Pi\) and\(\Sigma)\) as a generalization of the Boolean connectives, with theuniversal quantifier \(\Pi\) being interpreted as a (possiblyinfinite) conjunction, so that \(\Pi_x P(x)\) is understood as“a isP andb isP andc isP and …”. Similarly the existential quantifier\(\Sigma\) is understood as a (possibly infinite) sum: “aisP orb isP orc isP or…”. This flexible \(\Pi\) and \(\Sigma\) notation allowedhim easily to express nested quantifications to any desired depth.Thus, in his notation, if \(l_{ij}\) represents “i is alover ofj”, \(\Sigma_i \Sigma_j\) \(l_{ij}\) tells usthat somebody loves somebody, whereas \(\Pi_i \Sigma_j\) \(l_{ij}\)tells us that everybody loves somebody. (The \(\Sigma\) and \(\Pi\)notation is of course intended, in a Boolean spirit, to emphasize theanalogy to arithmetical sums and products.)

“On the Algebra of Logic” is remarkable for other reasonsas well. It begins with an important passage (§2) on thepropositional calculus, containing the first explicit use of two truthvalues. Peirce then describes a decision procedure for the calculus:

[T]o find whether a formula is necessarily true substitute\(\mathbf{f}\) and \(\mathbf{v}\) for the letters and see whether itcan be supposed false by any such assignment of values. (1885: 191)

He gives a defense of material implication, and shows how to definenegation in terms of implication and a special symbol for absurdity.In the next section (§3) he treats what he calls, following theSchoolmen, the “first-intentional logic of relations”. Itis here that he coins the term “quantifier”; thepropositional matrix of a quantified formula he calls its“Boolian”. In this section the quantifiers range only overthe individuals of the universe; the “first-intentionallogic” is thus first-order. Here, too, he was the first todiscuss the rules for transforming a quantified formula into prenexnormal form. The following section (§4) is headed“second-intentional logic”. There is a clear demarcationfrom the first-intentional logic of §3. Here the quantifiers arepermitted to range over predicates; and he uses his new notation tostate the modern second-order definition of identity: two objects areidentical just in case they satisfy the same predicates.

Peirce’s paper was in many respects far ahead of its time. Hissharp distinction between propositional, first-intentional, andsecond-intentional logical systems was not to be equaled in clarityuntil Hilbert in his lectures of 1917/18. Peirce was also prescient inviewing the quantifiers as (possibly infinite) sums and products, anotation which Löwenheim was to credit with making possible thediscovery of the Löwenheim-Skolem theorem, and which was to playa significant role in the formulation of Hilbert’sproof-theoretic program in the 1920s. (Peirce’s logical ideaswere well-known in continental Europe, having been taken up by ErnstSchröder and given wide circulation in the three volumes of hisAlgebra der Logik (1890–95).)

Peirce drew these various distinctions—and, in particular, thedistinction between first-order and second-order logic—withgreater clarity than any logician until Hilbert’s lectures in1917. And, unlike Hilbert, Peirce was steeped in the writings of themedieval logicians. He fully appreciated the philosophicalsignificance of the arguments about the reality of universals: this isclearly why he drew such a sharp differentiation between the logic of§2 and that of §3. It was thus open to him to make (or, atleast, to consider) a nominalist argument on behalf of first-orderlogic, and against second-order logic. But apart from a few incidentalremarks, he himself did not further develop his observations onsecond-intentional logic, and it seems likely that the moderndistinction between first-order and higher-order logic was are-discovery made independently in 1917/18 by Hilbert, rather thanbeing directly inspired by Peirce.

3. Gottlob Frege

Frege’s logical contributions grew out of a different soil, andwere made (as far as can be determined) entirely independently of theAnglo-American algebraic tradition of Boole, De Morgan, and Peirce.Instead they have their root in the work on the foundations of realanalysis by such German mathematicians as Dirichlet, Riemann,Weierstrass, and Heine. From this tradition Frege took, first, theidea of providing a rigorous foundation for mathematics (a projectthat, in his hands, became the project of showing that arithmetic canbe grounded in the laws of logic); and, secondly, the centralmathematical concepts offunction andvariable,which he employed in place of the Aristotelian concepts ofpredicate andsubject. This latter step led himnaturally to a logic of relations (since the functions considered inmathematics were multivariate); and his analysis of mathematicalinference also led him to introduce a notation for quantificationallogic. (Mathematicians such as Weierstrass, in his analysis of thelimit concept, was already sensitive to the “nesting” ofquantifiers, and the importance of their ordering: to the difference,for example, between saying “for every \(\varepsilon\) thereexists a \(\delta\)”, and “there exists a \(\delta\) suchthat for every \(\varepsilon\)”. What was required now, and whatFrege supplied, was a formal language to express and make explicit thequantificational inferences already present in the work of the Germananalysts.) So, at a single stroke, in theBegriffsschrift of1879, Frege took the two major steps beyond traditionallogic—relations and quantifiers—that the algebraictradition had taken separately and decades apart.

Frege’s logical system had several advantages over Peirce. Hisaxiomatic presentation of a purely syntactic calculus was considerablymore precise, and his analysis of the number concept went deeper. Hissystem permitted both variables and functions to be quantified. Thiswas a central component of his program for providing a logicalfoundation for arithmetic, since, in his logical system, identity,cardinal number, and mathematical induction were all definedvia higher-order quantifications. In hisGrundlagen(1884) he distinguishes between concepts of different order, so thatif conceptA falls under conceptB, thenB is of“second-order” (§53). In the more technical treatmentin hisGrundgesetze (1893) he considered third-orderquantifications, though his actual derivation of arithmetic proceededentirely within second-order logic.

Frege was thus one of the first logicians to recognize the importanceof a hierarchy of logical levels. His discovery was virtuallysimultaneous with Peirce’s, and arrived at entirelyindependently, in pursuit of different goals. Frege’s discoverywas to have the greater impact. It formed the basis forRussell’s theory of types (and also, decades later, influencedCarnap, who studied logic with Frege).

But although Frege distinguished between logical levels, he did notisolate the portion of his quantificational system that ranges onlyover variables of the first order as a distinct system of logic: norwould it have been natural for him to have done so. In this respect,there is a significant contrast with Peirce. Frege’s project wasto show that arithmetic could be grounded in the laws of logic: forhim, there was only one logic, and logic necessarily included thelogic of higher-order concepts. Peirce, in contrast, rejected thenotion of a single, over-arching logic, instead thinking in terms oflogics that vary according to the “universe of discourse”.Largely for this reason he came closer in his 1885 paper to isolatingthe propositional calculus, the “logic of firstintention”, and the “logic of second intention” asdistinct systems, each worthy of study in its own right: in thatregard, he was closer to modern conceptions than was Frege. There is afurther and subtler difference. Peirce’s \(\Sigma\) and \(\Pi\)notation for the quantifiers was explicitly conceived of in terms of(possibly infinite) conjunctions and disjunctions of propositionsabout individuals. This is a highly suggestive conception that is hardto represent in Frege’s system of notation. Löwenheim wasto exploit it in his early work in model theory, leading to technicaldiscoveries that were ultimately to call attention to first-orderlogic. But all this work lay decades in the future, and neither Fregenor Peirce can be credited with a modern understanding of thedifference between first-order and higher-order logics.

4. Ernst Schröder

Frege’s contributions were not immediately understood orappreciated, and in the closing decade of the century logic wasdominated by the three volumes of Ernst Schröder’sVorlesungen über die Algebra der Logik (1890–95).Schröder provided an encyclopedic treatment of the logical workof Boole and Peirce, systematizing and extending their results.Peirce’s quantifiers make their appearance in volume two, butthe distinction between first-and second-order quantification is notdrawn with comparable clarity. As Frege pointed out in his review(1895), Schröder’s notation did not distinguish setmembership from the subset relation, and as a result it can bedifficult to tell whether he intends a given quantification to rangeover the subsets of a domain (i.e., to be second-order) or over itselements (i.e., to be first-order). Schröder employs bothsecond-order and first-order quantifications; and in his third volumehe used the technique of expanding a second-order quantification intoan infinite product of first-order quantifications—a techniquethat was a development of the Peircian product notation, and that wasto furnish the starting point for the investigations ofLöwenheim. But Schröder does not extract from his widersystem a sub-system of first-order logic, and does not treat thedistinction of orders as itself being of any great significance,either mathematically or philosophically. In this sense, he is lessclear than Peirce’s paper of 1885. (A helpful analysis ofSchröder’s logical work is contained in Brady 2000.)

5. Giuseppe Peano

In his 1889, Giuseppe Peano, independently of Peirce and Frege,introduced a notation for universal quantification. Ifa andb are propositions with the free variables \(x, y, \ldots\),then \(a \mathbin{\revc_{x, y,\ldots}} b\) symbolized: Whatever \(x,y, \ldots\), may be, from the propositiona one deducesb. One hesitates to call this a notation for the universalquantifier, since the quantification is not severable from the signfor material implication: notationally, this is a considerable stepbackwards from Peirce. Peano moreover does not distinguish first-orderfrom second-order quantification. The point of his essay was topresent the principles of arithmetic in logical symbolism, and hisformulation of the principle of mathematical induction can be seen, byour lights, to be second-order: but only tacitly. This was adistinction to which (again unlike Peirce) he seems to have attachedno importance. He did, however, add a range of new symbols tomathematical logic which were to be influential on the work ofWhitehead and Russell inPrincipia Mathematica; and one ofthe symbols was the notation \(\exists\) for the existentialquantifier. (Oddly, Peano did not introduce a parallel symbol for theuniversal quantifier. It seems to have been Whitehead who introducedthe \((x)\) notation inPrincipia, and Hilbert who introducedthe symbol \(\forall\).)

6. Alfred North Whitehead and Bertrand Russell

Russell’s discovery in 1901 of the Russell Paradox led himwithin a few months, in a letter to Frege (Frege [PMC]: 144) to proposea tentative version of the theory of types. The central idea he tookfrom Frege’s theory of functions of the first, second, andhigher orders. Russell presented a version of his theory in anappendix to thePrinciples of Mathematics (1903), and then ina mature form in his “Mathematical Logic as Based on the Theoryof Types” (1908), which provided the conceptual underpinningsforPrincipia Mathematica. Russell views the universe asstriated into levels or types. The first type comprises theindividuals; the second type comprises the “first-order”propositions whose quantifiers range over the individuals of the firsttype; in general, the quantifiers in propositions of then+1sttype range over propositions of thenth type. Russell’ssystem in fact comprises two distinct hierarchies: one to deal withthe paradoxes of set theory (specifically, to prohibit sets from beingelements of themselves); the other to deal with the semanticalparadoxes (such as the paradox of the liar). This dual structure,branching in two directions, gives his theory the name “ramifiedtheory of types”. In order to be able to establish classicalanalysis, he was forced to adopt the axiom of reducibility, whichprovides that any function of level \(n+1\) is coextensive with apredicate of function of lower level. The system was immenselycomplicated; in time, at the hands of Chwistek, Ramsey, Carnap,Tarski, and Church, it was recognized that the hierarchy dealing withthe semantical paradoxes could be pruned away, leaving the“simple theory of types”. (A survey of this evolution canbe found in Church 1974, and detailed examinations of Russell’stheory in Landini 1998 and Linsky 2011.)

Russell and Whitehead thus possessed a notation for the twoquantifiers, as well as a distinction between quantifications of thefirst and highertypes. But this is not the same aspossessing a conception offirst-order logic, conceived as afree-standing logical system, worthy of study in its own right. Therewere essentially two things blocking the way. First (and in contrastto Peirce), their object of study was not multiple logical systems,but logictout court: they show no interest in splitting offa fragment for separate study, let alone in arguing that thefirst-order fragment enjoys a privileged status. On the contrary: aswith Frege, the ambition ofPrincipia was to demonstrate thatmathematics can be reduced to logic, and for Whitehead and Russelllogic encompassed the full apparatus of ramified type theory (togetherwith the axioms of infinity, choice, and reducibility). Secondly,althoughPrincipia provided an axiomatization of type theory(and thus can be viewed as specifying a conception of deductiveconsequence), Whitehead and Russell thought of their system as aninterpreted system, stating the truths of logic, rather thanas a formal calculus in the sense of Hilbert. Hilbert was to use theiraxiomatization as the starting-point for his own axiomatizations ofvarious systems of logic; but until the distinction between logic andmetalogic had been formulated, it did not naturally occur to anybodyto pose the metalogical questions of completeness, consistency, anddecidability, or to investigate such matters as the relationshipbetween deductive and semantic completeness, or failures ofcategoricity; and it was only once such notions became the focus ofattention that the significance of first-order logic becameapparent.

7. Leopold Löwenheim

In 1915, Löwenheim published his landmark “ÜberMöglichkeiten im Relativkalkül”. This paper, writtenin the tradition of the Peirce-Schroeder calculus of relatives,established the first significant metalogical theorem; from certainpoints of view, it marks the beginning of model theory. Löwenheimconsidered a class of what he called “countingexpressions” (Zählausdrücke) whosequantifiers range only over the domain of objects in the universe, butnot over relatives; he then proved that, for any such countingexpression, if it is satisfiable, it is satisfiable in somedenumerable domain. In modern terminology, his “countingexpressions” are formulas of first-order logic; but histerminology shows no influence either from Peirce’s logic of“first intention”, or from Russell’s theory oftypes. Löwenheim, like all logicians of this era, did not possessthe distinction between an object language and a metalanguage. Hisproof is difficult to follow, and the precise details of histheorem—of what he believed he had proved, and what he had, infact, proved—have been the subject of extensive scholarlydiscussion. (A survey of the differing interpretations is provided byMancosu, Zach, & Badesa 2009, and a detailed reconstruction of the proof itself byBadesa 2004.) The paper appears to have had no influence until Skolemsharpened and extended its results in his 1920. Löwenheim, likePeirce and Russell, did not isolate an axiomatic system encompassingfirst-order logic, nor did he draw a distinction between syntax andsemantics. Still less does he argue that his class of “countingexpressions” is in some way logically privileged, and provides afavored foundation for mathematics. The Löwenheim theorem was intime to be recognized as isolating a fundamental property offirst-order logic. But the full implications of his result were not tobecome clear until later, after Hilbert had introduced themetamathematical study of logical systems. (Incidentally,Löwenheim credited the elegant \(\Sigma\) and \(\Pi\) symbolismof Peirce for suggesting the infinitary expansions that were necessaryto his proof; and it is difficult to see how he could have obtainedhis theorem with any of the other quantificational notations then onoffer. He was still vigorously defending the advantages of thePeirce-Schroeder notation against the notation ofPrincipiaas late as Löwenheim 1940.)

8. David Hilbert and Paul Bernays

Let us briefly take stock of the situation as it existed in 1915.Peirce had differentiated between first-order and second-order logic,but had put the distinction to no mathematical use, and it droppedfrom sight. Both Frege and Russell had formulated versions ofmulti-level type theory, but neither had singled out the first-orderfragment as an object worthy of study. The American postulatetheorists, Edward Huntington and Oswald Veblen, had formulated variousnotions of completeness and categoricity, and Veblen had remarked thataxiomatic deducibility might diverge from semantic implication (Awodey& Reck 2002: 15–19). But Veblen did not possess a precisecharacterization of formal deduction, and his observation remainedinert. Löwenheim had proved a deep theorem about what inretrospect could be characterized as first-orderformulas,but had not isolated a system of first orderlogic. A similarpoint holds for Hermann Weyl, who in 1910 proposed (in effect) to usefirst-order logic to make precise the concept of “definiteproperty” in Zermelo’s axiom of separation. But this, too,is a retrospective characterization, and Weyl’s interest was inset theory, not in the study of a system of first-order logic.

The next large step was taken by David Hilbert in his lecture coursePrinzipien der Mathematik, delivered in Göttingen in thewinter semester of 1917/18. Hilbert had lectured and published onfoundational topics in the years 1899–1905; in the interveningtime, as he concentrated on other matters, the publications hadceased, though the extensive classroom lecturing continued. He kept upwith current developments, and in particular was informed about thelogical work of Whitehead and Russell, largely through his studentHeinrich Behmann. In September, 1917, he delivered his programmaticlecture “Axiomatisches Denken” in Zürich calling foran axiomatic treatment of logic along the lines he had earlierexplored in his axiomatization of geometry, and explicitly proposingmetalogical investigations:

When we consider the matter more closely, we soon recognize that thequestion of the consistency for integers and for sets is not one thatstands alone, but that it belongs to a vast domain of difficultepistemological questions which have a specifically mathematical tint:for example (to characterize this domain of questions briefly), theproblem of the solvability in principle of every mathematicalquestion, the problem of the subsequent checkability of the results ofa mathematical investigation, the question of a criterion ofsimplicity for mathematical proofs, the question of the relationshipbetween content and formalism in mathematics and logic, and finallythe problem of the decidability of a mathematical question in a finitenumber of operations. (Hilbert 1917: 412–413)

It was on this trip to Zürich that he invited Paul Bernays toreturn to Göttingen as his assistant in foundational matters.Although Bernays had little previous experience in foundations, thisturned out to be a shrewd choice, and the beginning of a close andfruitful research partnership.

The Göttingen lectures that shortly followed the Zürichaddress (and that were recorded in an official protocol by Bernays)are a remarkable document, and mark the birth of modern mathematicallogic. They are substantially the same as the published monographknown as “Hilbert and Ackermann” (1928), and even today,with modest supplementation, could serve as an introductory textbookfor logic. Hilbert for the first time clearly distinguishesmetalanguage from object language, and step-by-step presents asequence of formal logical calculi of gradually increasing strength.Each calculus is carefully studied in its turn; its strengths and itsweaknesses are identified and balanced, and the analysis of theweaknesses is used to prepare the transition to the next calculus. Hebegins with the propositional calculus, then moves to monadicquantificational logic (with an extended discussion of the calculus ofclasses, and of the Aristotelian syllogism), and then to the“function calculus”.

The function calculus is a system of (many-sorted) first-order logic,with variables for sentences as well as for relations. It is here, forthe first time, that we encounter a precise, modern formulation offirst-order logic, clearly differentiated from the other calculi,given an axiomatic foundation, and with metalogical questionsexplicitly formulated. Hilbert concludes his discussion of first-orderlogic with the remark:

The basic discussion of the logical calculus could cease here if wehad no other end in view for this calculus than the formalization oflogical inference. But we cannot be satisfied with this application ofsymbolic logic. Not only do we want to be able to develop individualtheories from their principles in a purely formal way, but we alsowant to investigate the foundations of the mathematical theoriesthemselves and examine how they are related to logic and how far theycan be built up from purely logical operations and concept formations;and for this purpose the logical calculus is to serve us as a tool.(1917/18: 188)

This leads him next to introduce higher-order logic, and thence to aconsideration of logical paradoxes and their resolution throughRussell’s ramified theory of types; the axiom of reducibility isbriefly discussed and adopted as a foundation for mathematics. Thelecture protocol ends with the sentence:

Thus it is clear that the introduction of the Axiom of Reducibility isthe appropriate means to turn the calculus of levels into a system outof which the foundations for higher mathematics can be developed.

This sentence appeared essentially unchanged when the 1917 lectureswere re-worked as the monograph (Hilbert & Ackermann 1928).

In the course of his lectures, Hilbert addresses the metalogicalquestions he had stated in “Axiomatisches Denken”, and (atleast tacitly) shows how the questions of completeness, consistency,and decidability are to be answered for the propositional case. Thecompleteness question for first-order logic is not explicitly raisedin Bernays’s record of the lectures, though an attentive readerwould easily have recognized it as an open problem. The followingsummer, Bernays produced aHabilitation thesis in which hedeveloped, with full rigor, a Hilbert-style, axiomatic analysis ofpropositional logic. He presents the axiomatic system as anuninterpreted formal calculus; provides it with a semantics; and thenproves the completeness theorem linking the syntax to the semantics inthe form, “Every provable formula is universally valid, and viceversa”. He then proceeds to investigate questions ofdecidability, consistency, and the mutual independence of variouscombinations of axioms.

The Hilbert 1917 lectures and the 1918 BernaysHabilitation are a milestone in thedevelopment of first-order logic. In the lectures, for the first time,first-order logic is presented in its own right as an axiomaticlogical system, suitable for study using the new metalogicaltechniques. It was those metalogical techniques that represented thecrucial advance over Peirce and Frege and Russell, and that were intime to bring first-order logic into focus. But that did not happen atonce, and a great deal of work still lay ahead. In the 1917/18lectures Hilbert’s sequence of logical calculi were presented asstepping-stones on the way to full higher-order ramified type theory,which he continued to regard as the “right” logicalframework for investigating the foundations of mathematics. It wascharacteristic of Hilbert to break complex mathematical phenomena intotheir elements: the sequence of calculi can be viewed as adecomposition of higher-order logic into its simpler component parts,revealing to his students precisely the steps that went into thebuilding of the full system. Although he discusses the functionalcalculus, he does not single it out for special attention. In otherwords (and as with Peirce three decades earlier) first-order logic isintroduced primarily as an expository device: its importance was notyet clear.

Moreover, Hilbert’s own treatment of the metalogical issues issomewhat hasty and informal. He experiments with several versions ofthe concept of “completeness”: one has the sense that hewas rapidly breaking new ground, and was not yet certain whichconcepts would prove the most fruitful. His proof of the completenessof propositional calculus is a mere sketch, and relegated to afootnote; the parallel problem for first-order logic is not evenraised as a conjecture. Even more strikingly, when Bernays eventuallyin 1926 published hisHabilitation, he omitted his proof of thecompleteness theorem because (as he later ruefully said) the resultseemed at the time straightforward and unimportant. (For discussion ofthis point, see Hilbert [LFL]: 229. For readily available generaldiscussions, see Sieg 1999, Zach 1999, and the essays collected in Sieg 2013; for the originaldocuments and detailed analysis, see Hilbert [LFL.)

In other words, even in Göttingen in the 1920s a fullunderstanding of the significance of the ideas Hilbert had introducedin 1917 was missing. The Hilbert school throughout the 1920s regardedfirst-order logic as a fragment of type theory, and made no argumentfor it as a uniquely favored system. It was not until the monographHilbert & Ackermann 1928 (and the contemporaneous “BolognaLecture”, Hilbert 1928) that Hilbert explicitly called attentionto the completeness of first-order logic as an open question. That setthe stage for the work of Gödel: but before coming to that, weneed to take a chronological step backwards.

9. Thoralf Skolem

Skolem in the winter of 1915–16 visited Göttingen, where hediscussed set theory with Felix Bernstein; there is no sign that hemet Hilbert. He was already at this time familiar withLöwenheim’s theorem, and knew of its paradoxicalimplications for Zermelo’s axiomatization of set theory:specifically, that a first-order axiomatization of the theory ofnon-denumerable sets would have a denumerable model. He did not at thetime publish on these topics because, as he later said:

I believed that it was so clear that the axiomatization of set theorywould not be satisfactory as an ultimate foundation for mathematicsthat, by and large, mathematicians would not bother themselves with itvery much. To my astonishment I have seen recently that manymathematicians regard these axioms for set theory as the idealfoundation for mathematics. For this reason it seemed to me that thetime had come to publish a critique. (Skolem 1922: appendix.)

Skolem’s first major papers were his 1920 and especially his1922. In the first he proved (or re-proved) in a more perspicuous formthe downward Löwenheim-Skolem theorem. In the second he provideda new proof of that result. He also criticized Zermelo’s axiomof separation, which had taken the form: Given a setS and adefinite proposition \(\phi(x)\), there exists a setS’ of all elementss ofS suchthat \(\phi(s)\). Here the concept of “definiteproposition” was left somewhat imprecise. Skolem’sproposal was to identify “definite propositions” with theformulas of first-order logic (with identity). Although Skolemdeclared this identification to be “natural” and“completely clear”, he did not explicitly argue for therestriction of quantifiers to the first level. He then gave theearliest satisfactory first-order formulation of Zermelo’s settheory, and then applied the Löwenheim-Skolem result to obtainthe Skolem paradox.

These technical results were of great importance for the subsequentdebate over first-order logic. But it is important not to read intoSkolem 1922 a later understanding of the issues. Skolem at this pointdid not possess a distinction between the object language and themetalanguage. And although in retrospect his axiomatization of settheory can be interpreted to be first-order, he nowhere emphasizesthat fact. (Indeed, Eklund (1996) presents a compelling argument thatSkolem did not yet clearly appreciate the significance of thedistinction between first-order and second-order logic, and that thereformulation of the axiom of separation is not in fact asunambiguously first-order as it is often taken to be.)

Skolem’s remarks about first-order logic require carefulinterpretation (see, e.g., Ferreirós 2001: 470–74), butclearly must be viewed against the backdrop of theGrundlagenkrise of the 1920s, and of the debates betweenHilbert, Brouwer, and Weyl. There are two broad tendencies withinlogic during these years, and they pull in opposite directions. Onetendency is towardspruning down logical and mathematicalsystems so as to accommodate the criticisms of Brouwer and hisfollowers. The aim was to avoid the paradoxes, to delimit theterritory of “legitimate” mathematics, and to place it onsecure foundations. Set theory was in dispute, and Skolem explicitlypresented his 1922 results as a critique of set theoreticalfoundations. Weyl already in 1910 had been led by his examination ofZermelo’s system to formulate a set of logical principles thatin retrospect (and despite the idiosyncratic notation) can be seen tobe a form of first-order logic. In general, both Weyl and Skoleminclined, on methodological grounds, towards some sort ofconstructivism as a means of avoiding the paradoxes; and this meantthat they viewed quantification over, say, the totality of subsets ofan infinite set as something to be avoided: whatever one’s graspon the notion of “all integers”, the notion of “allproperties of integers” was far less firm. To put the matterslightly differently: the very point of axiomatizing set theory was tostate its philosophically problematic assumptions in such a way thatone could clearly see what they came to. But this aim would becompromised if one already presupposed in the background logic theproblematical notion of “all subsets” that one wasattempting to elucidate. One possibility was to restrict oneself tofirst-order logic; another, to adopt some sort of predicativehigher-order system.

Similar broadly constructivist tendencies were also very much inevidence in the proof theoretical work of Hilbert and Bernays andtheir followers in the 1920s. Already by the time of Hilbert’s1921/22 lectures Hilbert had identified the introduction of the(classical) quantifiers as the crucial step where the transfiniteentered logic. Hilbert, like C. S. Peirce long before, thought of thequantifiers as infinite conjunctions and disjunctions, and from theearly 1920s onwards it was well understood in Göttingen that, forthe programmatic goals of the Hilbert consistency program to becarried out, a finitary analysis of the quantifiers was necessary. Theepsilon-substitution method was the principal device Hilbertintroduced in order to attempt to attain this result. (A survey ofthis research is provided by Sieg 2009 and in the introductory notesto Hilbert [LFL].)

But despite these constructive tendencies, many logicians of the 1920s(including Hilbert) continued to regard higher-order type theory, andnot its first-order fragment, as the appropriate logic forinvestigations in the foundations of mathematics. The ultimate hopewas to provide a consistency proof for the whole of classicalmathematics (including set theory). But, in the meanwhile, researchersstill were somewhat unclear about certain basic distinctions. Hilbertat times fails to observe the distinction between a first-orderaxiom-schema and a second-order axiom; Brouwer’s intuitionism issometimes identified with “finitism”; the relationshipsbetween completeness (in several senses), categoricity (also inseveral senses), and first-order and higher-order logic were not yetunderstood. Indeed, Gregory Moore points out that even Gödel, inhis 1929 proof of the completeness of first-order logic, did not fullyunderstand the notion of categoricity and its relationship tosecond-order logic (Moore 1988: 125).

10. Kurt Gödel

So matters remained unclear throughout the 1920s. But theconstructivist ambitions of the Hilbert school, the focus on theanalysis of the quantifiers, and the explicit posing of metalogicalquestions had made the emergence of first-order logic as a systemworthy of study in its own right all but inevitable. The crucialtechnical breakthroughs came in 1929 and 1931 with the publication, byGödel, first, of the completeness theorem for first-order logic,and then of the incompleteness theorems. With these results (andothers that soon followed) it finally became clear that there wereimportant metalogical differences between first-order logic andhigher-order logics. Perhaps most significantly, first-order logic iscomplete, and can be fully formalized (in the sense that a sentence isderivable from the axioms just in case it holds in all models).First-order logic moreover satisfies both compactness and the downwardLöwenheim-Skolem property; so it has a tractable model theory.Second-order logic does not. By the middle of the 1930s thesedistinctions were beginning to be widely understood, as was the factthat categoricity can in general only be obtained in higher-ordersystems. Lindström was later to show (1969) that no logicalsystem satisfying both compactness and the Löwenheim-Skolemproperty can possess greater expressive power than first-order logic:so in that sense, first-order logic is indeed a “natural”entity.

But the technical results alone did not settle the matter in favor offirst-order logic. As Schiemer & Reck point out (2013), well intothe 1930s, even after the principal metalogical results had beenachieved, logicians such as Gödel, Carnap, Tarski, Church, andHilbert & Bernays continued to use higher-order systems (generallyin some version of the simple theory of types). In other words, evenafter the metalogical results there was a choice to be made,and the choice in favor of first-order logic was not inevitable. Afterall, the metalogical results can be taken to show a severelimitation of first-order logic: that it is not capable ofspecifying a unique model even for the natural numbers. Hilbert in1917/18 had treated first-order logic as a mere stepping-stone, andthe metalogical results can be taken to confirm the wisdom of hisapproach: If you want categoricity, then you are forced to move to ahigher-order system.

At this point in the 1930s, however, several other strands of thinkingabout logic now coalesced. The intellectual situation was highlycomplex. The famous papers by Carnap, von Neumann, and Heyting at the1931 Königsberg congress had identified the logicist, formalist,and intuitionist schools: their debates were to shape thinking aboutthe foundations of mathematics for the next several decades. A searchfor secure foundations, and in particular for an avoidance of theset-theoretical paradoxes, was something they shared, and that helpedto tip the balance in favor of first-order logic. In the first place(as Weyl and Skolem had already pointed out, and as was at leastimplicit in the Hilbert program) there were good constructivist andphilosophical reasons for avoiding higher-order quantificationwherever possible, and for restricting one’s logic to the firstorder. Secondly, several unambiguously first-order formulations werenow given of Zermelo-Fraenkel set theory, and also ofvon-Neumann-Bernays-Gödel set theory (which permits a finiteaxiomatization). The first-order nature of these theories was stressedin a number of publications from the 1930s: by Tarski (1935), Quine(1936), Bernays (1937), and Gödel (1940). As a practical matter,these first-order set theories sufficed to formulate all existingmathematical practice; so for the codification of mathematical proofs,there was no need to resort to higher-order logic. (This confirmed anobservation that Hilbert had already made as early as 1917, thoughwithout himself fully developing the point.) Thirdly, there was anincreased tendency to distinguish between logic and set theory, and toview set theory as a branch of mathematics. The fact that higher-orderlogic could be construed as (in Quine’s later phrase) “settheory in sheep’s clothing” reinforced the othertendencies: “true” logic was first-order; higher-orderlogic was “really” set theory. By the end of the decade, aconsensus had been reached that, for purposes of research in thefoundations of mathematics, mathematical theories ought to beformulated in first-order terms. Classical first-order logic hadbecome “standard”.

11. Conclusions

Let us now try to draw some lessons, and in particular ask whether theemergence of first-order logic was inevitable. I begin with anobservation. Each stage of this complex history is conditioned by twosorts of shifting background consideration. One is broadlymathematical: the theorems that had been established. The other isbroadly philosophical: the assumptions that were made (explicitly ortacitly) about logic and about the foundations of mathematics. Thesetwo things interacted. Each thinker in the sequence starts with somemore or less intuitive ideas about logic. Those ideas promptmathematical questions: distinctions are drawn: theorems are proved:consequences are noted, and the philosophical understanding issharpened. At each stage, the question, “What is logic?”(or: “What is thecorrect logic?”) needs to beassessed against both the mathematical and the philosophicalbackground: it makes little sense to ask the question in theabstract.

Let us now consider the question:When was first-order logicdiscovered? That question is too general. It needs to be brokendown into three subsidiary questions:

\((\alpha)\)Whenwas first-order logic first explicitly identified as a distinctlogical system? This question has a relatively straightforwardanswer. First-order logic was explicitly identified by Peirce in 1885,but then forgotten. It was independently re-discovered inHilbert’s 1917/18 lectures, and given wide currency in the 1928monograph, Hilbert & Ackermann. Peirce was the first to identifyit: but it was Hilbert who put the system on the map.
\((\beta)\)Whenwas first-order logic recognized as being importantly different fromhigher-order systems? This is a more complicated question.Although Hilbert isolated first-order logic, he did not treat it asespecially significant, and he himself continued to work in typetheory. An awareness of the fundamental metalogical differencesbetween first-order and higher-order logic only began to emerge in theearly 1930s, mostly, though not exclusively, at the hands ofGödel.
\((\gamma)\)Howdid first-order logic come to be regarded as a privileged logicalsystem—that is, as (in some sense) the “correct”logic for investigations in foundations of mathematics? Thatquestion, too, is highly complicated. Even after the Gödelresults were widely understood, logicians continued to work in typetheory, and it took years before first-order logic attained canonicalstatus. The transition was gradual, and cannot be given a specificdate.

Equipped with these distinctions, let us now ask:Why wasfirst-order logic not discovered earlier?

It is striking that Peirce, already in 1885, had clearlydifferentiated between propositional logic, first-order logic, andsecond-order logic. He was aware that propositional logic issignificantly weaker than quantificational logic, and, in particular,is inadequate to an analysis of the foundations of arithmetic. Hecould then have gone on to observe that second-order logic is incertain respects philosophically problematic, and that, in general,our grasp on quantification overobjects is firmer than ourgrasp on quantification overproperties. The problem ariseseven if the universe of discourse is finite. We have, for example, areasonable grasp on what it means to speak (in first-order terms) ofall the planets, or to say thatthere exists aplanet with a particular property. But what does it mean to talk(in second-order terms) ofall properties of the planets?What is the criterion of individuation for such properties? Is theproperty of being the outermost planet the same as the property ofbeing the smallest planet? What are we to say about negativeproperties? Is it a property of the planet Saturn that it is not equalto the integer 17? In that case, although there are only a finitenumber of planets, our second-order quantifiers must range overinfinitely many properties. And so on. The Quinean objections arefamiliar.

Arguments of this sort had been made in the scholastic disputesbetween realists and nominalists: and Peirce was steeped in themedieval literature on these topics. He need not have gone so far asto make point \((\gamma)\), i.e., to argue that first-order logic isspecially privileged. That would in any case have run contrary to hislogical pluralism. But he did have the tools to make point\((\beta)\), and to emphasize that there is an important gulfseparating second-order logic from first-order, just as there is animportant gulf separating first-order logic from the Booleanpropositional calculus. Why did he not make these points already in1885?

Any answer can only be speculative. One factor, a minor one, is thatPeirce was not himself a nominalist. Another is that he operatedwithin a variety of logical systems: he was temperamentally eclectic,and not disposed to search for the “one true logic”. Thereare also technical considerations. Peirce, unlike Hilbert, does notpresent first-intentional logic as an axiomatized system, nor does heurge it as a vehicle for studying the foundations of mathematics. Hedoes not possess the distinction between an uninterpreted, formal,axiomatic calculus and its metalanguage. As a result, he does not askabout questions of decidability, or completeness, or categoricity; andwithout the metamathematical results a full understanding of thedifferences in expressive power between first-order and second-orderlogic was not available to him. One of the strongest arguments againstsecond-order logic—that quantification over all subsets of adenumerable collection entails quantification over a non-denumerabletotality—could not even have been formulated untilCantor’s Theorem was known. The logical and set-theoreticalparadoxes were not yet discovered, and Zermelo had not yet axiomatizedthe theory of sets: so Peirce lacked the acute sense of motivation todiscover a “secure foundation for mathematics”. And ofcourse Peirce had no inkling of the Löwenheim-Skolem theorems, orthe Skolem paradox, or the sequence of metalogical theorems that wereto bring first-order logic into sharp focus. He provided a flexibleand suggestive notation that was to prove enormously fertile, and hewas the first to distinguish clearly between first-order andsecond-order logic: but the tools for understanding themathematical significance of the distinction did not yetexist. (As Henri Pirenne once remarked, the Vikings discoveredAmerica, but they forgot about it, because they did not yet needit.)

A related point holds for Frege and Russell. They possessed theconception of a hierarchy of logical levels, and in principle they,too, could have isolated first-order logic, and thus have accomplishedstep \((\alpha)\). But they never considered isolating the lowestlevel of the hierarchy as a free-standing system. There are bothphilosophical and mathematical reasons for this. As a philosophicalmatter, the logicist project aimed to show that “mathematics canbe reduced to logic”: and they conceived of the entire hierarchyof types as constituting logic. And then, as a mathematical matter,second-order logic was necessary to their construction of theintegers. So they had no compelling reason, either philosophical ormathematical, that would have led them to focus on the first-orderfragment.

There is here an instructive contrast with Peirce. Peirce, in thespirit of the 19^th-century algebraists, was happy toexplore a lush abundance of logical structures: his attitude wasfundamentally pluralist. The logicists, working in the analyticaltradition, were more concerned to discover what the integers actuallyare: their attitude was fundamentally monistic andreductionist. But in order to single out first-order logic as was donein the 1930s, two things were needed: an awareness that there weredistinct logical systems, and an argument for preferring one to theother. Peirce had the pluralism: the logicists had the urge to find a“correct” system: but neither had both.

Let us now turn to the question,Was the emergence of first-orderlogic inevitable? It is impossible to avoid counterfactualconsiderations, and the answer must be more speculative. And here,too, it is necessary to distinguish between the inevitability of thetechnical results \((\beta)\), and the inevitability of point\((\gamma)\).

Let us start with point \((\beta)\). By 1928, the metalogical resultscan fairly be said to have been inevitable. Hilbert & Ackermannhad isolated and described first-order logic; the distinction betweenmathematics and meta-mathematics was by then well understood; they hadshown how to prove the completeness of the propositional calculus; andthey explicitly raised the completeness of first-order logic as animportant open problem. It was certain that, within the next fewyears, some enterprising logician would provide an answer: as ithappened, Gödel got there first. It would then have been anobvious next step to inquire about the completeness of higher-ordersystems. So within a few years of Hilbert & Ackermann the basicmetalogical theorems would have been established.

If that is correct, then Hilbert’s decisive step in the 1917/18lectures was not the isolation of first-order logic—i.e., notstep \((\alpha)\). That was a comparatively insignificant matter. Thatstep had already been taken explicitly by Peirce, and tacitly by Weyland Löwenheim. Hilbert did not treat it as important, and appearsto have viewed it primarily as an expository device, a means ofsimplifying the presentation of the logic ofPrincipiaMathematica. The important step in 1917 was rather theintroduction of techniques of metamathematics, and the explicit posingof questions of completeness and consistency and decidability. To posethese questions for systems of logic was an enormous conceptual leap,and Hilbert understood it as such. His own first attempts, made in his1905 Heidelberg address, hadcollapsed under the criticisms of Poincaré, and he hadstruggled to find a satisfactory formulation. And evenafterhe had introduced his metalogical distinctions in his papers of the1920s, logicians of the caliber of Russell and Brouwer and Ramsey haddifficulty in understanding what he was attempting to do.This development was in 1917 anything but inevitable: andwithout the introduction of the metalogical techniques the history oflogic and proof theory in the 1920s and 1930s would have looked verydifferent. Would the Gödel theorems ever have been conceived?Would the work of Löwenheim or Skolem or Zermelo independentlyhave led to an investigation of the metalogical properties offirst-order logic? One can in retrospect imagine an alternative pathto the technical results \((\beta)\), but there is no reason tosuppose that they were fated to emerge either when they did, or asthey did.

A subtler issue arises if we turn now to point \((\gamma)\) and ask:Was it inevitable that first-order logic would come to be regardedas a “privileged” logical system? As we saw, themetalogical results of the 1930s do not settle the primacy offirst-order logic. The “privileging” came later, and seemsrather to have depended on philosophical considerations: the need toavoid the set-theoretical paradoxes, a search for secure foundationsfor mathematics, a desire to accommodate the objections of Brouwer andWeyl, a sense that higher-order logics were both methodologicallysuspect and avoidable. All these things show the continuing influenceof theGrundlagenkrise of the 1920s, which did so much to setthe terms of the subsequent philosophical understanding of thefoundations of mathematics.

It is therefore important to stress that an alternative history waspossible, and that theGrundlagenkrise was entirely absentfrom Hilbert’s logical writings in 1917/18. The names of Brouwerand Weyl are nowhere mentioned. Hilbert is of course aware of theparadoxes (which he had known about since 1897), but had long believedthat Zermelo’s axiomatization had shown how to avoid them. Nordo we find in his writings any quest for the “one truelogic”. On the contrary. Both in 1917/18 and in the unpublishedlecture notes from the early 1920s the emphasis is on using the newmetalogical techniques to explore the strengths and weaknesses of adiversity of logical systems. The work is explicitly undertaken in thespirit of his studies of the axioms of geometry. He will take up asystem, explore it for a while, then drop it to examine somethingelse. In his pluralism and in his pragmatic, experimental attitude heis closer to Peirce than to the logicists.

TheGrundlagenkrise and his public, polemical exchanges withBrouwer came later, and they gave a distorted picture of themotivations behind his logical investigations. What was the impact ofthese philosophical debates on thetechnical aspects of hisprogram? For the formulation of first-order logic, and for the posingof metalogical questions, the answer is easy: there was no impactwhatsoever. The contents of Hilbert & Ackermann 1928 were alreadypresent in the 1917/18 lectures. As for Hilbert’sproof-theoretic research of the 1920s, the main lines of developmentemerged quite independently of Brouwer and Weyl. The polemics mighthave added a sense of urgency, but it is hard to detect any influenceon the actual mathematics.

So even if we imagine the philosophicalGrundlagenkriseentirely removed from the picture, the technical results of theHilbert school would not have been significantly affected. Thecompleteness and incompleteness results would, in all likelihood, havearrived more or less on schedule. (It is worthwhile to note thatBernays and Hilbert had contemplated the possibility of various sortsof incompleteness as early as 1928: see the discussion by WilfriedSieg in Hilbert [LFL]: 792–796.) But those results would haveemerged in a very different philosophical climate. The incompletenesstheorems would likely have been greeted as an important technicalcontribution within the broader Hilbert program, rather than as itsdramatic refutation. Perhaps (as Angus Macintyre 2011 has suggested)they would have been viewed more like the independence results in settheory, with less talk about the limits of mathematicalcreativity.

In other words, far from being inevitable, the emergence, towards theend of the 1930s, of first-order logic as aprivileged systemof logic depended on two things, each independent of the other. On themathematical side, it depended on Hilbert’s introduction ofmetalogical techniques; on the philosophical side, it depended on thearguments of theGrundlagenkrise. Neither of these things wasinevitable: nor was the fact that they occurred at roughly the sametime. With a different history, Hilbert’s flexible attitudemight have prevailed, and there might have been more emphasis onhigher-order systems, or on the exploration of algebraic logics,infinitary logics, category-theoretic systems, and the like: in short,on logical pluralism.

It is worthwhile to observe that, as the philosophical concerns of theGrundlagenkrise have receded, and as new approaches from thedirection of computer science and homotopy theory have entered thefield, the primacy of first-order logic is open toreconsideration.

Bibliography

Awodey, Steve & Erich H. Reck, 2002, “Completeness andCategoricity, Part I: Nineteenth-century Axiomatics toTwentieth-century Metalogic”,History and Philosophy ofLogic, 23(1): 1–30. doi:10.1080/01445340210146889
Badesa, Calixto, 2004,The Birth of Model Theory:Löwenheim’s Theorem in the Frame of the Theory ofRelatives, Princeton: Princeton University Press.
Bernays, Paul, 1918, “Beiträge zur axiomatischenBehandlung des Aussagen-Kalküls”, Habilitation Thesis,University of Göttingen; first published in Hilbert [LFL],pp. 231-268.
–––, 1926, “Axiomatische Untersuchung desAussagen-Kalküls der Principia Mathematica”,Mathematische Zeitschrift, 25: 305–320.
–––, 1937, “A System of Axiomatic SetTheory”,Journal of Symbolic Logic, 2(1): 65–77.doi:10.2307/2268862
Boole, George, 1847,The Mathematical Analysis of Logic: BeingAn Essay Towards a Calculus of Deductive Reasoning, Cambridge:Macmillan. Reprinted in Ewald 1996: vol. 1, pp. 451–509. [Boole 1847 available online]
Brady, Geraldine, 2000,From Peirce to Skolem: A NeglectedChapter in the History of Logic, (Studies in the History andPhilosophy of Mathematics, 4), Amsterdam: Elsevier.
Carnap, Rudolf, “Die logizistische Grundlegung derMathematik”,Erkenntnis, 2(1): 91–105.(References to the translation in Paul Benacerraf and Hilary Putnam,Philosophy of Mathematics: Selected Readings, Cambridge:Cambridge University Press, 1983, 41–52.) doi:10.1007/BF02028142(de) doi:10.1017/CBO9781139171519.003 (en)
Church, Alonzo, 1956,Introduction to Mathematical Logic,Princeton: Princeton University Press.
–––, 1974, “Russellian Simple TypeTheory”,Proceedings and Addresses of the AmericanPhilosophical Association, 47: 21–33. doi:10.2307/3129899
De Morgan, Augustus, 1864, “On the Syllogism, No. IV, and onthe Logic of Relations”,Transactions of the CambridgePhilosophical Society, 10: 173–230. (Read 8 Feb. 1858.) [De Morgan 1864 available online]
Dutilh Novaes, Catarina, forthcoming, “Axiomatizations ofArithmetic and the First-order/Second-order Divide”,Synthese, first online: 30 December 2014.doi:10.1007/s11229-014-0636-6
Eklund, Matti, 1996, “On How Logic BecameFirst-Order”,Nordic Journal of Philosophical Logic,1(2): 147–167. [Eklund 1996 available online]
Ewald, William Bragg (ed.), 1996,From Kant to Hilbert: ASource Book in the Foundations of Mathematics, 2 vols., Oxford:Clarendon Press.
Ferreirós, José, 2001, “The Road to ModernLogic—An Interpretation”,Bulletin of SymbolicLogic, 7(4): 441–484. doi:10.2307/2687794
Fraenkel, Abraham A., 1927, “Review of Skolem 1922”,Jahrbuch über die Fortschritte der Mathematik, 49:138–139.
Frege, Gottlob, 1879,Begriffsschrift, eine der arithmetischennachgebildete Formelsprache des reinen Denkens, Halle: Nebert.Translated by Stefan Bauer-Mengelberg in van Heijenoort 1967:1–82.
–––, 1884,Die Grundlagen der Arithmetik,eine logisch-mathematische Untersuchung über den Begriff derZahl, Breslau: Koebner. Translated by J. L. Austin asTheFoundations of Arithmetic, A Logico-Mathematical Inquiry into theConcept of Number, Oxford: Blackwell, 1950.
–––, 1893,Grundgesetze der Arithmetik,begriffsschriftlich abgeleitet, vol. 1, Jena: Pohl.
–––, 1895, “Kritische Beleuchtung einigerPunkte in E. Schröders Vorlesungen über die Algebra derLogik”,Archiv für systematische Philosophie, 1:433–456. [Frege 1895 available online]
–––, [PMC],Philosophical andMathematical Correspondence, Gottfried Gabriel, Hans Hermes,Friedrich Kambartel, Christian Thiel, Albert Veraart, BrianMcGuinness, and Hans Kaal (eds.), Chicago: University of ChicagoPress, 1980.
Gabbay, Dov M. & John Woods (eds.), 2009,Handbook of theHistory of Logic, Vol. 5: Logic from Russell to Church,Amsterdam: Elsevier-North Holland.
Gödel, Kurt, 1929,Über die Vollständigkeit desLogikkalküls, Doctoral Dissertation, University of Vienna.Printed with translation in Sol Feferman et al. (eds),KurtGödel: Collected Works, Vol. 1: Publications1929–1936, Oxford: Clarendon Press, pp. 60–101.
–––, 1931, “Über formalunentscheidbare Sätze der Principia Mathematica und verwandterSysteme I”,Monatshefte für Mathematik und Physik,38: 173–198; translated by S. Bauer-Mengelberg in van Heijenoort1967: 596–616.
–––, 1940,The Consistency of the Axiom ofChoice and of the Generalized Continuum Hypothesis with the Axioms ofSet Theory, Princeton: Princeton University Press.
Goldfarb, Warren D., 1979, “Logic in the Twenties: TheNature of the Quantifier”,Journal of Symbolic Logic,44(3): 351–368. doi:10.2307/2273128
Hilbert, David, 1905, “Über die Grundlagen der Logikund der Arithmetik”, inVerhandlungen des DrittenInternationalen Mathematiker-Kongresses in Heidelberg vom 8. bis13. August 1904, Leipzig: Teubner, pp. 174–185; translatedby S. Bauer-Mengelberg in van Heijenoort 1967: 130–138.
–––, 1917, “Axiomatisches Denken”,Mathematische Annalen 78(1–4): 405–415;translated by W. Ewald in Ewald 1996 (Volume 2),pp. 1105–1115. doi:10.1007/BF01457115 (de)
–––, 1917/18,Prinzipien derMathematik, unpublished lectures held in Göttingen, WinterSemester, 1917/18 (lecture notes recorded by Paul Bernays). Reprintedin Hilbert 2013: 31–221.)
–––, 1928, “Probleme der Grundlegung derMathematik”, (the “Bologna Lecture”), reprinted inHilbert 2013: 954–966.
–––, [LFL],David Hilbert, Lectureson the Foundations of Logic, Mathematics and the Natural Sciences(Volume III: Foundations of Logic and Arithmetic, 1917–1933),William Ewald and Wilfried Sieg (eds.), Berlin: Springer Verlag, 2013.doi:10.1007/978-3-540-69444-1
Hilbert, David & Wilhelm Ackermann, 1928,Grundzügeder theoretischen Logik, Berlin: Springer Verlag.
Hilbert, David & Paul Bernays, 1939, Prinzipien derMathematik II, Berlin: Springer Verlag.
Landini, Gregory, 1998,Russell’s Hidden SubstitutionalTheory, Oxford: Oxford University Press.
Lindström, Per, 1969, “On Extensions of ElementaryLogic”,Theoria, 35(1): 1–11.doi:10.1111/j.1755-2567.1969.tb00356.x
Linsky, Bernard, 2011,The Evolution of ‘PrincipiaMathematica’: Bertrand Russell’s Manuscripts and Notes forthe Second Edition, Cambridge: Cambridge University Press.doi:10.1017/CBO9780511760181
Löwenheim, Leopold, 1915, “Über Möglichkeitenim Relativkalkül”,Mathematische Annalen, 76(4):447–470. Translation in van Heijenoort 1967: 228–251.doi:10.1007/BF01458217 (de)
–––, 1940, “Einkleidung der Mathematik imSchröderschen Relativkalkül”,Journal of SymbolicLogic, 5(1): 1–15. doi:10.2307/2269177
Macintyre, Angus, 2011, “The Impact of Gödel’sIncompleteness Theorems on Mathematics”, inKurt Gödeland the Foundations of Mathematics: Horizons of Truth, MatthiasBaaz, Christos H. Papadimitriou, Dana S. Scott, Hilary Putnam, andCharles L. Harper (eds.), Cambridge: Cambridge University Press, pp.3–26. doi:10.1017/CBO9780511974236.004
Mancosu, Paolo (ed.), 1998,From Brouwer to Hilbert: TheDebate on the Foundations of Mathematics in the 1920s, Oxford:Oxford University Press.
Mancosu, Paolo, Richard Zach, & Calixto Badesa, 2009,“The Development of Mathematical Logic from Russell to Tarski,1900–1935”, in L. Haaparanta (ed.),The Development ofModern Logic, Oxford: Oxford University Press, pp.318–470; reprinted in Paolo Mancosu (ed.),The Adventure ofReason: Interplay Between Philosophy of Mathematics and MathematicalLogic, 1900–1940, Oxford: Oxford University Press, pp.5–120.
Moore, Gregory S., 1988, “The Emergence of First-OrderLogic”, in William Aspray and Philip Kitcher (eds),Historyand Philosophy of Modern Mathematics, (Minnesota Studies in thePhilosophy of Science, 11), pp. 95–135, Minneapolis: Universityof Minnesota Press.
Peano, Giuseppe, 1889,Arithmetices Principia, nova methodoexposita, Turin: Bocca. Translated in van Heijenoort 1967:20–55. [Peano 1889 (it) available online]
Peirce, Charles S., 1867, Five Papers on Logic Presented to theAmerican Academy; reprinted inWritings of Charles S. Peirce: AChronological Edition (Volume 2), Edward C. Moore (ed.),Bloomington: Indiana University Press, 1984, pp. 12-86.
–––, 1870 [1873], “Description of a Notationfor the Logic of Relatives, Resulting from an Amplification of theConceptions of Boole’s Calculus of Logic”,Memoirs ofthe American Academy of Arts and Sciences, 9(2): 317–378,communicated 26 January 1870, published 1873. doi:10.2307/25058006
–––, 1881, “On the Logic of Number”,American Journal of Mathematics, 4(1): 85–95. Reprintedin Ewald 1996: vol. 1, pp. 598–608. doi:10.2307/2369151
–––, 1883, “A Theory of ProbableInference”, in C. S. Peirce (ed.),Studies in Logic byMembers of the Johns Hopkins University, Boston: Little Brown,pp. 126–181. [Peirce 1883 available online]
–––, 1885, “On the Algebra of Logic: AContribution to the Philosophy of Notation”,AmericanJournal of Mathematics, 7(2): 180–202. Reprinted in Ewald1996: vol. 1, pp. 608–632. doi:10.2307/2369451
Quine, Willard V., 1936, “Set-theoretic Foundations forLogic”,Journal of Symbolic Logic, 1(2): 45–57.doi:10.2307/2268548
Reck, Erich H., 2013, “Developments in Logic: Carnap,Gödel, and Tarski”, inOxford Handbook of the Historyof Analytical Philosophy, Michael Beaney (ed.), Oxford: OxfordUniversity Press, pp 546–571.
Russell, Bertrand, 1903,The Principles of Mathematics,Cambridge: Cambridge University Press. [Russell 1903 available online]
–––, 1908, “Mathematical Logic as Based onthe Theory of Types”,American Journal of Mathematics,30(3): 222–262. Reprinted in van Heijenoort 1967: 150–182.doi:10.2307/2369948
Schiemer, Georg & Erich H. Reck, 2013, “Logic in the1930s: Type Theory and Model Theory”,Bulletin of SymbolicLogic, 19(4): 433–472. doi:10.1017/S1079898600010568
Schröder, Ernst, 1890–95,Vorlesungen über dieAlgebra der Logik (exakte Logik), 3 volumes, Leipzig:Teubner.
Sieg, Wilfried, 1999, “Hilbert’s Programs:1917–1922”,Bulletin of Symbolic Logic, 5(1):1–44. doi:10.2307/421139
–––, 2009, “Hilbert’s ProofTheory”, in Gabbay & Woods 2009: 321–384.doi:10.1016/S1874-5857(09)70012-3
–––, 2013,Hilbert’s Programs andBeyond, Oxford: Oxford University Press.
Skolem, Thoralf, 1920, “Logisch-kombinatorischeUntersuchungen über die Erfüllbarkeit oder Beweisbarkeitmathematischer Sätze nebst einem theoreme über dichteMengen”, Kristiania. Partially translated by S. Bauer Mengelbergin van Heijenoort 1967: 252–263.
–––, 1922, “Einige Bemerkungen zuraxiomatischen Begründung der Mengenlehre”, translated by S.Bauer Mengelberg in van Heijenoort 1967: 217–232.
–––, 1923, “Begründung derelementaren Arithmetik durch die rekurrierende Denkweise ohneAnwendung scheinbarer Veränderlichen mit unendlichemAusdehnungsbereich”, Kristiania. Translated by S. BauerMengelberg in van Heijenoort 1967: 302–333. [Skolem 1923 (de) available online]
Tarski, Alfred, 1935, “Der Wahrheitsbegriff in denformalisierten Sprachen”,Studia Philosophica, 1:261–405. Translated inLogic, Semantics, Metamathematics:Papers from 1923 to 1938, Oxford: Oxford University Press,1956.
van Heijenoort, Jean, (ed.), 1967,From Frege to Gödel: ASource Book in Mathematical Logic, 1879–1931, Cambridge,MA: Harvard University Press
von Neumann, John, 1927, “Zur HilbertschenBeweistheorie”,Mathematische Zeitschrift, 26:1–46.
Weyl, Hermann, 1910, “Über die Definitionen dermathematischen Grundbegriffe”,Mathematisch-Wissenschaftliche Blätter, 7: 93–95,109–113.
–––, 1918,Das Kontinuum, Berlin: deGruyter.
Whitehead, Alfred N. & Bertrand Russell, 1910–1913,Principia Mathematica, 3 volumes, Cambridge: CambridgeUniversity Press.
Zach, Richard, 1999, “Completeness Before Post: Bernays,Hilbert, and the Development of Propositional Logic”,Bulletin of Symbolic Logic, 5: 331–366.
Zermelo, Ernst, 1908, “Untersuchungen über dieGrundlagen der Mengenlehre, I”,Mathematische Annalen,65(2): 261–281. Translated by S. Bauer Mengelberg in vanHeijenoort 1967: 199–215. doi:10.1007/BF01449999 (de)
–––, 1929, “Über den Begriff derDefinitheit in der Axiomatik”,Fundamenta Mathematicae,14: 339–344. doi:10.4064/fm-14-1-339-344

Academic Tools

How to cite this entry.
Preview the PDF version of this entry at theFriends of the SEP Society.
Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO).
Enhanced bibliography for this entryatPhilPapers, with links to its database.

Other Internet Resources

[Please contact the author with suggestions.]

Acknowledgments

I am grateful to Erich Reck for comments.

Open access to the SEP is made possible by a world-wide funding initiative.
The Encyclopedia Now Needs Your Support
Please Read How You Can Help Keep the Encyclopedia Free

Browse

About

Support SEP

Mirror Sites

View this site from another server:

USA (Main Site)Philosophy, Stanford University

Info about mirror sites

Library of Congress Catalog Data: ISSN 1095-5054

Movatterモバイル変換