The road to modern logic - an interpretation

The Bulletin of Symbolic Logic Volume 7, Number 4, Dec. 2001 THE ROAD TO MODERN LOGIC—AN INTERPRETATION JOS ´ E FERREIR ´ OS1 Abstract. This paper aims to outline an analysis and interpretation of the process that led to First-Order Logic and its consolidation as a core system of modern logic. We begin with an historical overview of landmarks along the road to modern logic, and proceed to a philosophical discussion casting doubt on the possibility of a purely rational justification of the actual delimitation of First-Order Logic. On this basis, we advance the thesis that a certain historical tradition was essential to the emergence of modern logic; this traditional context is analyzed as consisting in some guiding principles and, particularly, a set of exemplars (i.e., paradigmatic instances). Then, we proceed to interpret the historical course of development reviewed in section 1, which can broadly be described as a two-phased movement of expansion and then restriction of the scope of logical theory. We shall try to pinpoint ambivalencies in the process, and the main motives for subsequent changes. Among the latter, one may emphasize the spirit of modern axiomatics, the situation of foundational insecurity in the 1920s, the resulting desire to find systems well-behaved from a proof-theoretical point of view, and the metatheoretical results of the 1930s. Not surprisingly, the mathematical and, more specifically, the foundational context in which First-Order Logic matured will be seen to have played a primary role in its shaping. Mathematical logic is what logic, through twenty-five centuries and a few transformations, has become today. (Jean van Heijenoort) While trying to outline and interpret the process leading to modern logic, we shall focus on First-Order Logic, because its development is indiscernible from the rise of modern logicaltheory. It will be mycontention that, contrary to a frequent assumption (at least among philosophers), First-Order Logic is not a ‘natural unity’, i.e., a system the scope and limits of which could be justified solely by rational argument. There is reason to think that, like so many other conceptual systems, First-Order Logic—hereafter FOL—is the sound and satisfactory outcome of a fascinating combination of rational argument and historical contingencies. In accordance with that viewpoint, Received June 23, 2000; revised July 12, 2001. 1Preliminary versions of this paper were read at Madrid, G¨ ottingen and Mainz. I would like to thank participants in those talks for their reactions, and also Andreas Blass and an unknown referee for their suggestions and corrections. c 2001, Association for Symbolic Logic 1079-8986/01/0704-0001/$5.40 441 442 JOS ´ E FERREIR ´ OS we shall analyze the main factors in the genesis of modern logic, that is, the motives for changes that happened between roughly 1850 and 1950. We shall begin with a sketch of historical landmarks along that process, and then proceed to a more careful analysis of the traditional conception of logic and its modern transformations. It will certainly not come as a surprise that in my view the mathematical context in which FOL matured played a primary role in its shaping. By interaction with traditional views regarding logic, this broad source of motives started a two-phased movement, leading first to a great expansion in the scope of logic, and subsequently, under increasing constraints linked with research into the foundations of mathematics, to a progressive restriction. Perhaps more surprising will be my use of the Kuhnian notion of an exemplar as an extremely useful tool in understanding the historical evolution of this branch of modern mathematics.2I would go as far as saying that I consider this notion capable of shedding much light on the development of branches of mathematics in general. Obvious examples could be found in the case of modern abstract algebra, specifically in the exemplary role played by group theory. First-Order Logic itself has served as the paradigm for a modern logical system and its metatheoretical study (it can be argued that the treatment of other systems, e.g., modal logic, has mimicked that of first-order logic). In this connection, readers might consider the present paper as a case-study in the employment of that Kuhnian tool for the historiographical and philosophical analysis of mathematics. Of course, many details in the following historical narrative are not new. This is to be expected, since by now the evolution of FOL has been subjected to much scrutiny on the side of philosophers and historians. Nevertheless, I expect my overall argumentation to offer a new perspective on the process, thus stimulating both historians and philosophers to novel considerations. §1. Historisches: traces from the past. Historiographically speaking, there are many possible ways of analyzing the development of any discipline, but commonly it is unwise to embrace too exclusively one approach. In the early decades of the 20th century, it was a great improvement that historians (like Łukasiewicz) began to deploy the new technical tools of modern logic for an analysis of past approaches. But as any trained historian knows, excessive passion for the technical details, and concentration upon the emergence of the main results of a discipline (as judged from our standpoint), may easily lead to whiggism. In this way, it seems, historians of logic have tended to forget some of the complexities with which the historical road to modern logic confronts us. In particular, I aim to emphasize that the very 2Readers should keep in mind that I shall refrain completely from employing the broader and much vaguer notion of a paradigm, in the sense of what Kuhn once termed a ‘disciplinary matrix’. THE ROAD TO MODERN LOGIC—AN INTERPRETATION 443 notion of logic has gone through notable historical changes, even among the partisans of formal logic—the only trend of concern to us here. Parallel phenomena are familiar to historians of mathematics, physics, etc., but in the case of logic there is a characteristic tendency to ignore historical shifts in the delimitation of the subject. Let me give a simple example. In the early decades of the twentieth century, the paradoxes of logic and set theory grew to almost legendary proportions. It was usually emphasized that their discovery had been a great and consequential event in the development of logic. Meanwhile, the secondary literature of the second half of that century on the history of FOL hardly mentions the paradoxes at all. In the midst of a plethora of technical details concerning language, theory and metatheory, one may not even find a single mention of set theory. One can explain the discrepancy by considering that the secondary literature frequently presupposes the present notion of logic, as if it were ahistorical. While concentrating upon technical details, historians have tended to forget changes in the overall conception of the subject. To counterbalance this tendency, I shall look at the development of modern logic, so to say, from above (focusing on its relations with set theory and the foundations of mathematics) and not from below (focusing only on the elementary levels of logical theory). It will not be my purpose, in the present section, to offer a more or less complete description of the history of FOL, since this topic has been very well researched.3My aim is just to indicate what I regard to be some key historical traces that shed light on the evolution of the conception of logic, including the changing conceptions of its scope and contents. 1.1. Expanding to contradiction. The road to modern logic began, some time around 1850, with a huge thematic expansion. This expansion is intimately linked with the confluence of two traditions: the classical, philosophical tradition of logic, and the tradition of mathematics.4Philosophical conceptions of logic have been complex and varied; here we are only interested in the tradition of ‘formal logic’, and formal logic meant the theory of the syllogisms—above all the Aristotelian syllogisms but also the so-called hypothetical and disjunctive syllogisms. In the late 19th century, under pressure from interest in analyzing the logic of mathematics, the scope of logic broadened immensely, until logical theory embraced the theory of sets and the theory of relations, together with the more elementary levels of sentential and predicate logic. Compare Russell’s depiction: 3See, e.g., the writings of Goldfarb [32], Dreben & van Heijenoort [19], and Moore [45], [47]. 4Above all algebra and axiomatics, but also analysis. On this topic, see Grattan-Guinness [34], Peckhaus [52], Ferreir´ os [21], [23]. 444 JOS ´ E FERREIR ´ OS The subject of symbolic logic is formed by three parts: the calculus of propositions, the calculus of classes, and the calculus of relations.5 The same point becomes clear if one reads the work of Peano and his school, of Schr¨ oder, or of Frege. It comes out clearly, too, in the very existence of a logicistic philosophy of mathematics. As Russell wrote, also in 1903, it was one of the most important discoveries of the time that all of mathematics is just symbolic logic.6Some writers (particularly Quine) have emphasized that logicism did nothing but reduce mathematics to elementary logic and set theory. Why was this interpreted to be an extremely illuminating reduction? Precisely because set theory was regarded as a mere province of logic. The rationale for that ascription was, on the one hand, the idea that ‘is’ is a logical particle and, on the other, the principle of comprehension (see §3.3). The comprehension principle, even if frequently unstated, was a key ingredient of the logical systems of Peano, Frege, and Russell. Needless to say, the formal systems of Frege and Russell, including as they did not only higher-order logic but also set theory, are very different from modern First-Order Logic. Incidentally, it is worth reminding the reader that, while it is true that Frege’s system [24] is quite close to a modern formal one, some of his notational simplifications give rise to a deceitful appearance that the system is essentially a modern first-order one. Upon more careful reading it becomes clear that Frege’s system is higher-order throughout, and that he actually deployed higher-order logical tools (this is explicit in the theory of series contained in the last part of Begriffsschrift). Later, in his magnum opus [25], Frege introduced what he regarded as one of the most fruitful enrichments of his ideography—notation and an axiom for classes, embodying the principle of comprehension. The theory of sets or classes, as based on the principle of comprehension, was proven contradictory by the so-called logical (presently set-theoretical) contradictions, paradoxes, or antinomies. Russell’s paradox was particularly striking because of its formulation in terms of the most basic ‘logical’ notions—class or set, negation, and membership. The contradictions led to a radical revision of the foundations of set theory, its relation to logic, and the relations between logic and mathematics. In this way, they affected strongly the conception of logic. This seems to be one of the most important ways in which they constituted a consequential event for modern logic, though of course they did not lead to a single new theorem or metatheorem. It is also very important that the paradoxes (particularly what we call the semantic ones) may have been the most significant factor promoting a strict formalization of the language of mathematics, after 1900. 5Russell [60], §13. 6Russell [60], §4. THE ROAD TO MODERN LOGIC—AN INTERPRETATION 445 1.2. The age of type theory. With the paradoxes, the expansion of logic was brought to a halt, and a period of progressive restriction started. Among the systems of logic designed to cope with the paradoxes, the most influential was Russell’s Theory of Types, incorporated into the monumental Principia Mathematica, written jointly with Whitehead. The theory of types was designed to rescue logicism from the contradictions, by preserving the principle of comprehension restricted by the doctrine of types. This logical system, proposed by Russell in 1908 [61], marked the evolution of logic for the next quarter century. Offering a detailed description of type theory is not an easy task, especially if one aims to present Russell’s original system, in which the doctrine of types was supplemented by the vicious circle principle (suggested by Poincar´ eand forbidding what we call ‘impredicative definitions’). This very complex original system was labeled ramified type theory, in order to distinguish it from the system favored by logicians after 1925, the so-called simple type theory. Using simple type theory was suggested by Chwistek and Ramsey, the latter on the basis of the now-usual distinction between set-theoretic and semantic paradoxes.7Ramsey did not use those names, but called “logical” the paradoxes of set theory, and described the semantic paradoxes (Tarski’s name) as linguistic, psychological, or in some sense epistemic. But, at any rate, at this point we are not interested in a description of simple type theory. What is of relevance here is that as late as 1930 type theory was still regarded by mathematical logicians as the most important and natural system of logic. Interesting material for an evaluation of this issue can be found in the wellknown contributions to a Symposium on the foundations of mathematics held at K¨ onigsberg in 1931 (where G¨ odel announced his first incompleteness theorem). In his talk, Carnap outlined simple type theory and went on to say that “most proponents of modern logic consider [this system] legitimate and necessary”.8This suggests that type theory was acknowledged as the natural system of symbolic logic, which is actually confirmed by von Neumann’s address. Von Neumann did not enter into details concerning the axiomatization and formalization of classical mathematics because, as he said, Russell has given a “thorough and exact description of its methods—both the good and the bad”.9 Indeed, there are many indications that this was the common opinion. The first really modern treatise of formal logic is not Principia Mathematica,but Hilbert & Ackermann’s Grundz¨ uge der theoretischen Logik [37]. The book is noteworthy because here one can find, for the first time in a treatise on logic, a study of FOL as a separate system (under the name of “restricted 7Ramsey [59]. 8Carnap [7], 46. 9Von Neumann [75], 61; also 64: “Russell and his school have almost completely accomplished tasks 1–3”. 446 JOS ´ E FERREIR ´ OS functional calculus”), posing the question of its metatheoretical properties, e.g., completeness. But FOL appears only as an interesting subsystem, and the work culminates by presenting the so-called “extended functional calculus”, a peculiar version of the theory of types. Moreover, the authors show by examples that higher-order logic is necessary in order to analyze the notions of mathematics.10 The main reason for focusing on the first-order subsystem was that, for the purposes of developing Hilbert’s Beweisstheorie, it was convenient to proceed step by step from the simplest to the most complex systems. One year later, Carnap’s Abriss der Logistik [6] deals with simple type theory, the same being also the case in his most important work, Logische Syntax der Sprache,andlater. Nevertheless, the most interesting examples can be found in two of the most influential articles of 20th century logic, G¨ odel’s ‘On Formally Undecidable Propositions’ [29] and Tarski’s ‘On the Notion of Truth’ [67].11 As Quine remarked, these two papers offer “the now classical thumbnail formulation” of simple type theory.12 This is actually the system in which G¨ odel formalizes Peano arithmetic in order to prove its incompleteness, and the system for (any fragment of) which Tarski proposes his definition of truth. As a matter of fact, Tarski even goes on to offer a philosophical argument attempting to show that type-distinctions are a necessary trait of any scientific language whose sentences may have a clear intuitive meaning at all. 1.3. Constructivistic interlude. In his 1931 address, Carnap suggested that only the “intuitionists” proposed the deviant system FOL as the one to use in the foundations of mathematics: The difference between us lies in the fact that we recognize as valid not only the rules of construction which the intuitionists use (the rules of the so-called “restricted functional calculus”), but in addition, permit the use of the expression ‘for all properties’ (the operations of the so-called “extended functional calculus”).13 Carnap’s reference to the intuitionists is puzzling, since at the time Brouwer’s school avoided completely reliance on formal systems of logic and mathematics. Still, it is quite true that some authors of a constructivist tendency had proposed FOL as the adequate system for foundational work. That was the case with Hermann Weyl in his 1918 book Das Kontinuum [77], and with Skolem in his illuminating paper on axiomatic set theory of 10Hilbert & Ackermann [37], 82–92. A later and more detailed example of the same is Church’s famous [11]. 11Originally published in 1933, Tarski’s piece was written around the same time as G¨ odel’s, independently of his work. 12Quine [58], 11. 13Carnap [7], 52. Carnap follows the terminology of Hilbert & Ackermann [37], see above. THE ROAD TO MODERN LOGIC—AN INTERPRETATION 447 1923 [64].14 Both of these authors were acting as critics of set theory and abstract mathematics; it was precisely their reflections on Zermelo’s axiom system that led them to focus on FOL, and in this regard their viewpoints were essentially coincident. On the occasion of his Habilitation at G¨ ottingen and slightly later (roughly, 1909–1913), Weyl tried to perfect Zermelo’s system and came to formulate a set of logical principles that, in essence, amounts to a form of FOL.15 In the process, he started to doubt that axiomatic set theory could be formulated without having recourse to the idea of iteration (i.e., to the natural numbers), and this meant that set theory was not an absolute foundation for mathematics. Therefore he abandoned the “classical” side and went to the banks of constructivism. His new standpoint, and a new formulation of the logical principles behind FOL, was presented in Das Kontinuum.16 Meanwhile, in Skolem’s eyes it was crystal clear that axiomatic set theory cannot be a satisfactory foundation for mathematics. After discovering, to his surprise, that many authors thought differently, he presented in 1922 a series of critical remarks on Zermelo’s system. Zermelo’s axiom of Separation had to be made precise, and he proposed to do so by using FOL. But now the earliest metatheoretical result, the L¨ owenheim–Skolem theorem, applied to Zermelo’s system with paradoxical results. Both Weyl and Skolem argued that, when we work on the foundations of set theory, reliance on the usual systems of higher-order logic would involve a vicious circle, since those systems presuppose the acceptability of essential traits of abstract mathematics (we shall review their arguments in §5.1). The only valid alternative, in their eyes, was to use either predicative higher-order logic or else FOL.17 The latter system was in better agreement with the aims of axiomatization (Skolem) and it was much more convenient for actual mathematical work (Weyl). Notice that these proposals came, as a result of purely conceptual reflections, before any metatheoretical results were known that might speak in favor of FOL—quite the contrary, given that the L¨ owenheim–Skolem theorem shows a definite weakness in FOL and might be taken to argue against it. 1.4. Restriction to FOL. With simple type theory, the scope of logic had already been restricted, since set-theoretical notions were strictly regimented, and especially because the axioms of Infinity and Choice came to be regarded as properly mathematical ones, foreign to the ‘natural’ logical system, type 14For Skolem’s constructivist tendencies, see especially [66] and his paper on primitive recursive arithmetic, using bounded first-order quantifiers. Carnap presented a system of this kind in Logische Syntax der Sprache. 15Weyl [76]. 16Weyl [77], 4–10. Weyl’s presentation was intentionally informal. 17Weyl [77], 21–23; Skolem [65], 516–517. 448 JOS ´ E FERREIR ´ OS theory. Thus, unlike 1900, by this time Cantorian set theory was beyond the reaches of logic. Yet up to then the restriction had been quite mild—type theory is still a higher-order system that countenances the notion of class or set as a logical one.18 Within a few years, a much stricter restriction would be adopted, in agreement with the admonitions of Weyl and Skolem. During the 1930s some key figures in the community of logicians came to pin-point FOL as the basic system for actual research in logic and foundations. The context in which this decision was taken was that of foundational work, more precisely work on axiomatic set theory and Hilbertian metamathematics. In this way, the mathematical context underscored its primacy and effected another turn of the screw. The earliest systems formalized in an elementary way, within FOL, were actually axiom systems for set theory—the Zermelo system with the work of Skolem [64], and Von Neumann’s system in his own work [73]. During the 1930s several authors emphasized the fact that an axiomatization of set theory, and therefore the foundations of abstract mathematics, only required the FOL system. This was the case with Tarski in the appendix to [67], Quine in [54], Bernays in [2], G¨ odel in [30] and [31]. Of course, recent advances in the metatheory of logic due to G¨ odel constituted the clinching argument for a restriction of logic to FOL (we shall review the main motives in §5). After World War II, the rising community of logicians opted for FOL as the natural system of logic, formal logic par excellence. Historians of science are familiar with the fact that such profound changes rarely happen without some resistance. We have the example of Church, who in his 1956 Introduction to Mathematical Logic [11] followed the lead of Hilbert and kept speaking for higher-order logic. But introductory courses in mathematical logic concentrated more and more on FOL, presenting its study as the quintessential example of how modern logic was to be done. Also around this time we find the earliest philosophical partisans of FOL, as was notably the case of Quine.19 Presenting in a nutshell the results of our quick historical overview, we can say that around 1900 logic was conceived as a theory of sentences, sets and relations; after World War I and as late as 1930 the exemplar for modern logic was a higher-order system, simple type theory; and only around 1940–1950 did the community of logicians as a whole come to agree that the paradigm logical system is FOL. §2. Philosophisches: Is First-Order Logic a ‘natural unity’? Given those historical traces, one is naturally led to wonder whether FOL constitutes 18Novel but less influential systems established in the same spirit during the 1930s were those of Quine, NF and ML. See [22] and the literature cited therein. 19See Quine [56], chapters I and IV; and [57]. Also see [22]. THE ROAD TO MODERN LOGIC—AN INTERPRETATION 449 what might be called a natural unity. Is it a system that sooner or later had to be adopted, once an interest in logical matters had arisen, or is it perhaps a compromise between the natural and the contingent? In our discussion of this question, the names of Frege, Hilbert, von Neumann, Tarski, and Quine will be mentioned. 2.1. Purported definitions. Throughout history, philosophers have proposed many diverse definitions of logic. Here I shall just examine a couple proposed by influential writers, in order to show the implausibility of a purely rational justification of the modern delimitation of (elementary) logic. Let us begin with the young Willard Van Quine of Mathematical Logic [55]. This work has the peculiarity of offering a beautifully simple argument, that in its essence goes back to Aristotle, in order to justify Quine’s selection of logical constants. Consider the many different languages employed in the sciences—in zoology, geology, physics, mathematics. They are considerably different since they employ different vocabularies. Yet it is not difficult to notice that they share a number of elements, like ‘if ... then’, ‘and’, ‘not’, ‘all’, ‘some’, the copula ‘is’. Logical vocabulary would then be this vocabulary of universal applicability, while the rest belongs in the different sciences. To put it more clearly, logical vocabulary is defined as the intersection of the vocabularies of the special sciences.20 The argument seems promising at first sight, but upon more careful consideration it leads to peculiar results. Let us see an example. All sciences, even textbook mathematics, employ particles such as ‘but’ and ‘in spite of’, or like the conditional in its most frequent sense of expressing a contentrelation between the antecedent and the consequent. Such particles are the subject matter of relevance logic; therefore, some form of relevance logic should become a key ingredient of logic as defined by Quine. Odd result, for Quine has been an opponent of non-classical logics.21 But the most interesting example is offered by Quine himself. Given the universal use of the copula ‘is’, his 1940 book presented set theory (under the formal version of the system called ML) as an integral part of logic. Frequently the meaning of ‘is’ in natural language can be rendered in terms of membership or else inclusion, basic relations of set theory. Therefore, elementary logic ought to include some form of set theory, as was the case with Frege, Dedekind, Peano, Schr¨ oder, Russell, and Quine. However, Quine himself rejected this conclusion some years later; in 1970, while still talking about the universal character of logic, he was referring to FOL and excluding sets explicitly.22 (The conclusion that the copula is not a 20Quine [55], p. 21 of the Spanish edn. 21At an immediately lower level of universality we would find relations of cause and effect, so perhaps at the next level of logical or semi-logical theory we ought to rescue Leibniz’s principle of sufficient reason. 22Quine [57]. 456 JOS ´ E FERREIR ´ OS What is crucial for our purposes here is, simply, that the traditional core of logical theory was more consequential for the emergence of modern logic than the “newer” proposals as of 1850, excluding of course Boole and De Morgan. Therefore in our brief discussion we can ignore the more convoluted developments, for which the reader is referred to [51], [52], [53]. 3.1. Three guidelines and one set of exemplars. From Antiquity, a few guidelines, basic ideas, or guiding principles have been frequently stated, that help define or delimit the realm of logic. Making no attempt to give a complete list of all the relevant principles, I will simply point out some that seem consequential. Mention of three principles may have brought to some readers’ minds the celebrated classical principles of identity, non-contradiction, and excluded middle, but this is not what we shall be considering. Our principles are not valid logical laws (or in some renderings meta-laws), but guidelines that help define the realm of logic and its scope. The first principle is that logic deals with the conditions for an argument to be correct, attempting to establish when something is a valid deduction, and when not. In short, logic is concerned with an analysis of (valid and invalid ) deduction. This principle was absolutely clear in the mind of Aristotle, and the same applies to the Stoics. A second guideline was also clear from the start. Because it deals with the conditions for arguments to be valid in general, logic should enjoy universal applicability; therefore logical theory should not depend on reference to any particular topic or subject. This might be called the principle of universality, and it was also explicitly stated by Aristotle, who in the Topics said that logic is useful in finding the first principles of any discipline, and opens the road to all methods.35 Later it became customary to derive, from this guideline, a very useful corollary: logic does not depend on how things are, it is independent of considerations of existence.36 The third guideline was emphasized in a particularly sharp way by Kant.37 In dealing with the universal rules of reasoning or arguing, logic studies only the form of arguments and deductions, never their matter. To put it differently, in logic one abstracts some general patterns, forms, or structures of argument; one deals with inferences from a formal standpoint.38 As De Morgan wrote with characteristic wit: 35Aristotle, Topics, book A, 2, 101a36–101b3. 36This and other principles may be vague; see, e.g., Wittgenstein’s point in Tractatus logico-philosophicus 5.552. 37Kant is famous for his conservativeness regarding logical theory, but he contributed in an important way to make precise the traditional conception of logic. In this connection, see De Morgan [15], 74–76, with explicit reference to Kant. 38Tarski’s thesis [69] that there is not a single natural possibility concerning the selection of logical vocabulary, implies that logic cannot be purely formal: there is a subject matter, the constant meaning of logical particles. THE ROAD TO MODERN LOGIC—AN INTERPRETATION 457 Logic bears on its modern banner, The form of thought, the whole form, and nothing but the form.39 The basic idea behind this principle, if not the principle itself, was embodied in the use of variables A, B by Aristotle, and the use of metalinguistic names for propositions (‘the first’, ‘the second’) by the Stoics. Such names or variables mark out what is ‘material’ and what is regarded as properly logical, viz. ‘formal’, in a given argument. Nevertheless, all our considerations in §2 above tended to show that no clear-cut argument can establish that logical theory must embrace both sentential logic and quantification theory. As a matter of historical fact, both Aristotle and the Stoics seem to have been joined by the guidelines we have mentioned, and both developed a ‘classical’ two-valued logic, complying with the principles of excluded middle and non-contradiction. But, while Aristotle concentrated on his syllogisms and devoted much less attention to sentential logic, the Stoics refused to consider Aristotle’s syllogisms as a part of logic, restricting their definition of the subject to sentential logic. Once again, we are led to the conclusion that first principles are not enough. How, then, could the tradition of logic delimit a more or less precise field? In his famous Structure of Scientific Revolutions, Kuhn expressed concern with the fact that scientists may share knowledge, without sharing a set of rules that univocally determine that knowledge. His proposal was that scientists’ knowledge involves sharedparadigms, or more precisely exemplars in Kuhn’s later terminology. An exemplar is a noteworthy instance of theoryin-application, such as Newton’s treatment of the solar system, or Lavoisier’s of combustion and oxygen. I contend that exemplars have also played a key role in the development of logical and other mathematical theories. (As I remarked at the beginning, we shall avoid the broader notion of a paradigm in the sense of ‘disciplinary matrix’.) The classical period left two main, distinct sets of logical exemplars, embodied in Aristotle’s doctrine of the syllogistic figures, and the Stoic doctrine of the so-called “unprovables”, basic inference rules from which all rules of sentential logic were supposed to follow. The reception of Aristotle’s philosophy in the Middle Ages led to a logical tradition in which the Aristotelian exemplars played a dominating role, while the Stoic ones were largely forgotten. This happened in spite of the fact that the medieval logicians established independently a theory of sentential logic, the consequentiae—which seems to speak for the extreme importance of tradition and authority in this particular development. Thus it seems to have been a crucial historical contingency, decisive for the development of logic, that the same person established the theory of the syllogism and the doctrines of Physics and Metaphysics, extremely influential upon the medieval theologians, Muslim, Hebrew and Catholic. 39De Morgan [15], 78. 458 JOS ´ E FERREIR ´ OS Let us then examine some aspects of Aristotelian logic. Since we are mainly interested in the ‘traditional’ logic of the Modern period, we shall not take care to distinguish the Modern presentations from the original one of Aristotle. Therefore we will give the customary versions of the Aristotelian propositions and syllogisms.40 As for historical sources, the reader should take into account that the Aristotelian doctrines were presented in all kinds of logical works—they constituted a well-established core of knowledge, for which reason one can produce a schematic portrait. A typically Modern and widely influential treatise of the 17th century is Arnauld & Nicole’s Logique [1]; as for the 19th century, one may take as examples of formal logic the Elements of Logic by Whately [78], or the Neue Darstellung der Logik by Drobisch [20].41 Treatises on traditional logic typically divide into three parts devoted respectively to concepts, judgements, and syllogisms (there may also be a fourth part dealing with methodological matters). The Aristotelian prototypes for a proposition were: All Ais B. Some Ais B.NoAis B. Some Ais not B. It was argued that any argument can be reduced to a ‘normal’ form, employing only those prototypical propositions, structured according to the syllogistic figures. If I argue, for instance, that no oyster is a man because no oyster can talk, this can be put into the following normal form:42 All men are speakers. No oyster is a speaker. Therefore, no oyster is a man, which constitutes an example of syllogism of the second figure (Camestres). According to Kant’s principle of form & matter, what logic studies is the form of such an argument; the particular concepts are replaced by variables, as Aristotle actually did, and we obtain the formal structure: All Cis B.NoAis B. Therefore, no Ais C. This means that, according to the traditional image, the matter of the argument gets concentrated in the concepts represented by A,B,C;therestis purely formal or logical. To a large extent, logical doctrines have been forged around the mold of Aristotle’s doctrine of the figures of syllogism, his basic set of exemplars. Certainly Aristotle did not employ variable-binding quantifiers, but by dubbing the particles ‘all’ and ‘some’ as logical ones he prepared the modern introduction of the quantifiers. His modest logic was hampered by not making room for relations, but by considering the (variable or abstract) 40But see Łukasiewicz [42], §1. 41See the secondary works Boche´ nski [4] and Kneale [39]. Concerning 19th century traditions, it is very instructive to consult Ueberweg [70]; see specially pp. 47–53 on the German tradition of formal logic started by Kant and Herbart. 42I take this example in order to underscore the unnaturalness of the assumed regimentation. THE ROAD TO MODERN LOGIC—AN INTERPRETATION 459 predicates A,Bas parts of the logical form of arguments, he prepared the modern extension of logic to include a theory of relations. Let us take another exemplar, a Bocardo syllogism: Some Aare not B.AllCare B. Therefore, some Aare not C. The particles “all”, “some”, “not”, “is” constitute the core of logical vocabulary. By the use of variables, this Aristotelian exemplar presents us with a particular selection of logical constants, divergent from the Stoic selection. (Traditional logic considered also—in a secondary role, and fragmentarily— hypothetical, disjunctive and conjunctive syllogisms, where the key new particles were “if ... then”, “or”, “and”.) A basic set of exemplars should be expected to provide crucial prototypical examples to be taken care of by authors working in the field. The syllogistic exemplars can indeed be seen to play this role in the path-breaking works of Boole and Frege. The initial chapters in Boole’s Mathematical Analysis of Logic [5] are devoted to translating Aristotle’s basic propositions into his calculus, and establishing the Aristotelian doctrines of conversion and of the syllogistic figures. Frege, though much less concerned with providing a modern rendering of traditional logic, does not forget to put his formal system to the test of translating Aristotelian syllogisms in chapter one of Begriffsschrift [24]. We shall take this matter up in §4.1. 3.2. Grafting new ideas. One can find many other ideas shaping the conception of logic in the Modern period, and of course not all of them seem sound to us. The aim of this subsection is to acknowledge this fact, offer a couple of comments on it, and mention two more principles or guidelines. The last one, which I shall dub the principle of the calculus, has played a very important role in the emergence of modern logic. Throughout history, thousand and one myths have surrounded the notion of logic. One of the capital sins of the Modern tradition of logic, as practiced until around 1850, was to confuse the analysis of deduction (first guideline) with the analysis of human thought, i.e., of thinking processes. This psychologistic confusion of the theory of deduction with a theory of thought stimulated interference of epistemological conceptions; thus the long-sought ideal of an inductive logic came into being. In the 17th century, the goal was to create a new logic that would turn Aristotle’s theory obsolete—it would be an instrument of discovery, as exemplified in the inductive methods of Bacon. A different tradition endowed logic with a metaphysical, ontological, or perhaps cosmic, meaning. One might enter here into the difficult issue of the relations between Kant’s formal and transcendental logics; one might mention Hegel’s ‘logic’, identical with his metaphysics, or the dialectics of Marx. Even a key author like Frege belongs in this tradition as long as, to him, logic was something like the Language of the World in its purest form. Wittgenstein’s Tractatus is a magnificent attempt to take this image to its ultimate consequences. 460 JOS ´ E FERREIR ´ OS Another reputed principle was the idea that logic enjoys a very peculiar epistemological status, a special kind of immediacy, being somehow transparent to us.43 Its propositions or principles, its truths and rules, were supposed to be a priori, independent of experience—perhaps because they express necessary rules of reasoning given to us with the Understanding (Kant), or because they are strictly analytical, conventional, and devoid of meaning (Carnap).44 This conception was promoted by the psychologistic confusion; it was quite influential all the way up to Wittgenstein and even later, and it was consequential for some of the historical events that we shall deal with. That image explains why the reduction of other fields of knowledge to pure logic became an extremely attractive goal for many authors. The case of logicism is perhaps the clearest example of this appeal, and logicism was a driving force behind the initial phase of development of modern logic—most of those that we regard as important logicians, as of 1900, were logicists. The story of those images, how they disappeared and how they turned into or merged with other images, would also belong in the history of modern logic. But, to end this section, we shall just mention one further principle, a novelty of the Modern period that became extremely consequential for modern logic. This is the Leibnizian ideal of submitting logic to algorithmic mathematical treatment: it was regarded as possible, and of course desirable, to express all kinds of so-called ‘logical’ notions and principles by means of calculuses (similarly to the new arithmetic and algebra), so that ‘logical’ deductions could be mechanically computed. We might call this the principle of the calculus; important authors who worked along this line include Leibniz himself, Lambert and Gergonne. (Leibniz added the more or less mythical ideal of a characteristica universalis, a kind of basic vocabulary or alphabet of thought that would turn the logical calculus into a powerful instrument of discovery. Frege pursued this ideal, too, which in fact was related to his conception of logic as the cosmic language and his onto-semantics.) The first clear success in implementing the principle of the calculus came with Boole’s algebra of logic; Frege made an impressive step forward, and G¨ odel established the crucial limitations for its implementation. §4. From quantification to type theory. Starting from the traditional ideas just discussed, we shall try to make sense of the changes in the conception and scope of logic observed in §1. In the present section we shall review the developments delineated in the first three subsections of §1, leaving the fourth to §5. Even under the constraint of those traditional principles and 43For a 20th century emergence of this idea, see the Quine–Carnap correspondence in [13], 294–295. 44Naturally, there were opposite pseudo-principles, such as the strictly empiricist image advanced by Mill, which enjoyed little popularity in continental Europe, or at least in Germany. THE ROAD TO MODERN LOGIC—AN INTERPRETATION 461 exemplars, there was room for ambiguity in the historical heritage, room for divergent interpretations, and thus for biffurcations and detours in the history of logic. As is usually emphasized, the mathematical context played a primary role in the shaping of modern logic, both during the phase of expansion and later, during the restrictive phase. In the former period, the rise of abstract mathematics and the process of rigorization were crucial for the maturation of modern logic, while in the latter period the context of debates concerning the foundations of mathematics became central. 4.1. Quantification theory as the logic of analysis. In the latter part of the 19th century, it became clear that sentential logic was an essential basic frame for logical inference. We shall not deal with this development here in order to keep our discussion within limits. Leaving that aside, the most important novelties during the expansive phase were the theories of sets, relations, and the quantifiers. I shall begin with the latter. We have already mentioned that Aristotle’s “all” and “some” are still far from modern quantifiers, while at the same time they prepared the modern development by providing justification for the idea that the quantifiers are logical particles. How did this modern development come about? Everything suggests that quantification was strictly necessary for an analysis of mathematical inference as practiced in the 19th century. Indeed, it would seem that the modern use of quantifiers emerged within informal but technical mathematical language. One can find examples of this in many branches of mathematics, e.g., in number theory, when one defines: ais called a ‘divisor’ of bin case there is a number csuch that a·c=b. This existential quantifier cannot be analyzed by means of the Aristotelian propositions in such a way as to explain its inferential use in mathematics. More interesting examples are easily found within the realm of analysis. Since re-elaboration of the subject from the starting point of limits (Cauchy, Bolzano), there was steady progress towards an abstract formulation of key analytical notions by means of nested quantifiers. Bolzano’s definition of acontinuous function f(x) is based on the requirement that “the difference f(x+h)−f(x) can be made smaller than any given quantity if his taken sufficiently small”.45 In spite of the great progress that this represented, the formulation is not yet completely abstract (like Cauchy’s formulation, it might seem to appeal to some kind of process in time). The work of Weierstrass, widely acclaimed as the champion of rigor in analysis, can actually be seen as introducing a purely logical formulation of the elements of mathematical analysis. Weierstrass made it clear that one must first define continuity of f(x)at a point, and then continuity in an interval—an example of logical analysis (decomposition). Let us see the definitions given in 1872 by his friend and 45Bolzano (1817) in [3], 15. 462 JOS ´ E FERREIR ´ OS colleague Heinrich Heine, who explicitly claimed to be publishing Weierstrassian ideas: A function f(x) is called continuous at an individual value x= when, given any quantity εno matter how small, there is another positive number 0with the property that f(±)−f() cannot exceed εfor any positive smaller than 0. A function f(x) is called continuous from x=ato x=bwhen it is continuous for each individual value x=between aand b, including aand b.46 The quantificational structure of these sentences is quite explicit, thanks to the expressions “given any”, “there is”, “for any”, “for each”. No wonder that Felix Klein, himself not very sympathetic to the exertions of rigor, called the leader of the Berlin school a “logician”.47 The Weierstrassian use of universal and existential quantifiers can be called modern, and yet several years would elapse before Frege published his Begriffsschrift.Itisactually an almost mechanical task to translate Weierstrass’s definitions into Frege’s conceptual language.48 Meanwhile, in 1873, Frege was just presenting his doctoral thesis on a geometrical representation of the complex numbers. Although he studied in Jena and G¨ ottingen, not Berlin, the lectures of Weierstrass were by then famous throughout Germany (and Europe), and student lecture notes went from hand to hand. It is therefore a natural conjecture that he may have studied some version of Weierstrass’s introductory lectures; actually, Frege cites (unspecified) handwritten Collegienhefte of lectures by Weierstrass in volume 2 of the Grundgesetze [26], and one would expect these redactions to stem from the 1870s. Be that as it may have been, it is clear that Frege constructed his conceptual language by analyzing key notions of the mathematics of his time. Evidence for this statement can be found not only in Begriffschrift, but also in other documents, particularly his paper of the same year on applications of the ideography [27]. Here Frege shows by geometrical and arithmetic examples the ability of his formal language to express mathematical relations. The examples are: 1) Point Dlies in the straight line joining Band C(expressed by means of the congruence relation). 2) ais a prime number (expressed by means of the so-called ancestral relation). 46Heine (1872) in [3], 25. Heine proceeds to define uniform continuity in an interval, the difference being essentially a matter of the scope of the quantifiers (symbolically, the use of parentheses). 47Klein [38], vol. 1, 152 and 246. 48Further examples might be easily found in many other works: similar to the one of Weierstrass, e.g., in Dedekind’s paper on continuity and irrational numbers; close to Frege’s, particularly in Peano’s Formulario mathematico. THE ROAD TO MODERN LOGIC—AN INTERPRETATION 463 3) Every natural number can be represented as the sum of four squares. The third example, in particular, is rendered as follows: For every n,ifn is a natural number, then there exist natural numbers a,b,e,gsuch that n=a2+b2+e2+g2[27, 93]. One should emphasize that the combined use of two or more quantifiers within a sentence, that we have found (informally) in Weierstrass, constitutes already a very important expansion of the logical language and its capabilities. This novelty was connected with the distinction between variables and (non-logical) constants, which made it possible to introduce the variable-binding quantifiers and to distinguish a proposition like ‘Socrates is mortal’ from ‘All men are mortal’. All of this, in turn, is related with the novel Fregean analysis of the sentence, based on the notions of function and argument. With this analysis, the understanding of the Aristotelian prototypes changed substantially. From ‘All Ais B’wepassto ‘∀x(A(x)→B(x)),’ which means that, although we are still referring to the same prototype sentences, strictly speaking we are dealing with new exemplars. (The reader should recall that an exemplar is an archetypal instance of theory-in-application; the substantial change at the level of theoretical analysis involves, strictly speaking, a change of exemplars.49) Needless to say, this latter move was also inspired by mathematical ideas. There is one further important point concerning the quantifiers. While the Aristotelian set of exemplars justified the idea that they are logical constants, we have not yet found a single reason torestrict logic to the elementary level of quantification over first-order variables. On the contrary, even the syllogistic exemplars might be used to express arguments involving quantification over predicates. For instance, this might be regarded as a perfectly natural (and true) Aristotelian syllogism: All properties of animals are properties of men. Free mobility is a property of animals. Therefore, free mobility is a property of men. Actually, it is not easy (and tricky because of the characteristics of natural language) to find second-order arguments in the writings of traditional logicians.50 It was only in sophisticated contexts that the need for such sentences emerged; the first such context was the foundations of mathematics, a clear 49In a more careful analysis, it would be crucial to reflect on changes in what plays the role of an exemplar, with the emergence of modern logic. We would then find a change of level, but this topic goes beyond the scope of the present paper. 50In the Port-Royal Logique [1, 272], we read: “Every friendship is pleasing; there are dangerous friendships, therefore, some dangerous things are agreeable” (is ‘friendship’ a relation or an object?). We also find (p. 268) something close to the following: “All virtues are praiseworthy; being patient is a virtue; therefore, being patient is praiseworthy”. 464 JOS ´ E FERREIR ´ OS example being the principle of induction as formulated by Dedekind, Frege and Peano around 1880. Peano’s version might be rendered: Every property of numbers that applies to 0 and that, in case it applies to n, also applies to n+1, isapropertyofallnumbers. 51 Thus, the traditional delimitation of logic makes room for higher-order logics, which is exactly what we find in Frege, Peano, Russell and Hilbert. As we saw, the mere idea of focusing on first-order logic, even as a subsystem, did not arise until 1915 (L¨ owenheim) or 1917 (Hilbert).52 It seems that the very question, higher order or first order?, does not even arise until one begins to work on metatheoretical issues. 4.2. Set theory as logic 53 .The 19th-century expansion of logic led to the inclusion of new mathematical theories, the theory of classes and the theory of relations, in its domain. The fact that the copula “is” becomes a logical constant in Aristotle’s basic set of exemplars was the main reason why set theory came to be regarded as elementary logic. This strong tendency to regard classes or sets as a part of logic, from about 1850, can be explained briefly as follows. The copula has three different meanings, carefully analyzed by Peano and Frege.54 As Peano said, we have the meaning of identity, the meaning of membership, and the meaning of inclusion, and one should very carefully differentiate them (otherwise one gets into contradictions). The first meaning justifies considering the theory of identity as a part of elementary logic; even today we frequently employ FOL with identity as a logical framework. On the other hand, membership and inclusion are basic relations of set theory; quite naturally, then, set theory belongs in logic. This standpoint was still defended or at least represented by Quine and Tarski as late as 1940 (see §1.1). A more complex analysis may take us to the same conclusion. The logical particles, as combined in the Aristotelian propositions, establish different kinds of relationships between concepts. The Aristotelian exemplars take these relationships to be purely logical, therefore it is the business of logic to study them. How can we do it? An interestingly simple way emerged from the analysis of concepts that was characteristic of traditional logic. From Porphyry through the medieval authors to the Port-Royal logicians, a distinction between the intension and the extension of a concept consolidated. Given a concept, we can distinguish two basic aspects: the intension or comprehension of the concept, its meaning (man as rational animal), and the extension of the concept, the class of beings to which it applies (men as a group or class). Several authors (e.g., Arnauld & Nicole [1]) used the notion 51Of course, this is not a syllogism, but a single sentence with three universal quantifiers. 52See Moore [46] [47]. 53For more on this topic, see [21], and also [23]. 54See Frege [24] and [25], Peano [50]; see also Russell [60]. THE ROAD TO MODERN LOGIC—AN INTERPRETATION 465 of concept-extension or class to provide an analysis of the Aristotelian relations between concepts. This suggested that the theory of classes is essential to a study of the relationships among concepts that constitute the business of logic. In fact, some logicians employed the notion of class to create a calculus of logic in accordance with Leibniz’s principle (§3.2). It suffices to recall Euler’s diagrams in the 18th century, the doctrines of Gergonne in the early 19th, and Boole’s mathematical logic. Under this rendering, the Aristotelian propositions (see §3.1) turn out to establish relations of inclusion, membership, intersection, or disjointness, and we conclude as above. At this point, it is worth mentioning a sentence of Boole that I am fond of: That which renders logic possible, is the existence in our minds of general notions, —our ability to conceive of a class, and to designate its individual members by a common name.55 In Boole’s mind, class theory is not just one part of logic, as it would be with Russell sixty years later—the notion of class is at the very roots of logic. Yet here we find one of those instances which made wide room for divergent interpretations of the scope of logic. There were authors, especially from the late 19th century onwards (notably Cantor in the 1890s), who rejected the idea that set theory is a part of logic. The same may have been the case with Riemann earlier on,56 and we have already seen that De Morgan regarded ‘is’ as a material instance of an asymmetric and transitive relation. Other authors came to see the copula ‘is’ as a sign of predication, making it disappear from the symbolical notation—‘Ais B’ becomes B(A). 4.3. Relations. Another important novelty, during the expansive phase in the 19th century, was the theory of relations. Although we have not mentioned this is §2, one of the obscure points regarding delimitation of the scope of logic is the question, why do abstract relations like P(x), R(x, y) belong to logic? The reason seems to be, once again, because the traditional set of exemplars was the Aristotelian one. It was De Morgan who began to explore the theory of relations in the fourth issue of a series of papers entitled, not by chance, ‘On the syllogism’. To him, the theory of relations was a natural and necessary outgrowth of the extremely simple Aristotelian form ‘A is B’—it was the syllogism considered under the aspect of combination of relations. ‘A is B’ comes to be understood as A RB, where Ris an asymmetric and transitive relation. And the link with mathematics was also explicit, for, as De Morgan said, the algebraist was living in the higher atmosphere of syllogism, the unceasing composition of relations, before it was admitted that such an atmosphere existed.57 55Boole [5], 4. 56See [23], 51, 241; regarding Cantor, see pp. 266, 292–293. 57De Morgan [16], 241. 472 JOS ´ E FERREIR ´ OS the Skolem paradox, establishing the (model-)relative nature of cardinality results. Skolem’s conference, obscurely published as a paper in 1923, was a masterpiece of clarity and rigorous argument. The only point that is not clearly argued is, unfortunately, why (as he asserts) axiomatization requires a restriction of the quantifiers to the first-order level. Many commentators have assumed that Skolem was just redefining logic to mean first-order logic, but this interpretation is given the lie by his later explicit comments.65 Skolem’s point was not a general statement about logical theory, but rather the conditional thesis that, if we are interested in producing an axiomatic system, we can only use first-order logic. I interpret this to mean that, in his view, the spirit of axiomatics—in the tradition of Pasch, Dedekind, Peano, Hilbert— can only be consistent with the use of FOL as an underlying logic. Let us see how this interpretation can be justified. The main novelty in the modern axiomatic method, as practiced around 1900, was the striving to attain full deductive rigor, which implied the need to detect all of the axioms or principles relevant for rigorous derivation of a given body of theory. On the one hand, this called for closer attention to logical inferences, acting as a motive power behind the emergence of modern logic. On the other, the requirement was recognized as equivalent with a principle of independence from meaning, and ultimately with the principle of free realizability of the axiom systems—the freedom, that is, to regard completely different object-domains as models of the system. As Pasch said, Indeed, if geometry is to be really deductive, the deduction must everywhere be independent of the meaning of geometrical concepts, just as it must be independent of the diagrams. Only the relations among those geometrical concepts, specified in the propositions and definitions employed, may legitimately be taken into account. During the deduction it is legitimate and useful to think of the meaning of the terms, but not at all necessary; in fact, if it is necessary to do so, the inadequacy of the proof is made manifest. If, however, a theorem is rigorously derived from a set of propositions—the basic set—the deduction has a value which goes beyond its original purpose. For if, on replacing the geometric terms in the basic set of propositions by certain other terms, true propositions are obtained, then corresponding replacements can be made in the theorem; in this way we obtain new theorems as consequences of the altered basic propositions without having to repeat the proof.66 Instead of the “geometrical concepts”, it must be possible to consider any other concepts belonging to an arbitrary sphere; instead of geometrical 65See [65], where Skolem has no difficulty to admit predicative higher-order logic. 66Pasch [49], 91; as translated by Nagel in [48], 237–238. THE ROAD TO MODERN LOGIC—AN INTERPRETATION 473 objects such as points, lines and planes, it must be possible to consider any other sets of objects that satisfy the relevant relations (e.g., chairs, tables and beermugs, in Hilbert’s famous statement). Dedekind expressed the same principle, in an 1876 letter to Lipschitz, saying that one should use the “infallible method” of replacing “all technical expressions by newly-invented words (up to then without a meaning); the building, if well constructed, should not collapse”.67 Having the Pasch–Dedekind–Hilbert principle in mind, let us consider whether it makes sense to employ higher-order quantification in an axiom system. The simplest case is that of second-order quantifiers, which, taken at face value, refer to “all properties” or “an arbitrary property” of the objects in the domain or model of the system. But, if we are to allow models of completely diverse nature, both of these notions appear to be abstractions without any clear scope. It seems that there can be no well-defined realm of properties, unless a certain object-domain is univocally specified, and even then it is unclear whether the totality of properties may be well-defined. For, as Weyl argued [76], [77], in mathematics one usually works with just afew given properties (in the case of geometry, incidence, etc.), and in the relevant body of theory one defines more involved properties by logical means; no totality is presupposed. A possible way out is suggested by the traditional conception of the extension of a concept: we might take properties in extension, that is, classes or sets, to play the role of ‘properties’ and thus to be the referents of the second-order quantifiers. From this standpoint, given any object-domain D1 one would automatically have a unique, well-defined domain D2embracing all subclasses of the object-domain. This way out seemed quite natural so long as set theory was regarded as a part of logic, but it became obviously untenable when the need for proper axiomatization of set theory as a mathematical theory arose. Its naivet´ e has become more and more obvious with the development of metatheoretical work on axiomatic set theory, for the assumption of a single, univocally specified domain D2is equivalent to the claim that there is a unique answer to Cantor’s Continuum Problem. To put it differently, reading the second-order quantifiers as referring to “any (all) class(es)” of objects in the domain, can we assume arbitrary classes, arbitrary subsets of the domain, or not? The former would be consistent with abstract mathematics but, by taking arbitrary subsets to be validated by logic, we would be moving in circles—preempting the desired result of securing with absolute certainty the foundations of abstract mathematics. Was it not established by the paradoxes that we lack a clear notion of arbitrary set? Since authors of a constructivist tendency proposed to extirpate 67Letter of 27.07.1876 in Dedekind’s Gesammelte Werke, vol. 3; see his ‘karam tipo tatura’ in §6 of the letter to Keferstein [72] and also his work on models of the Peano axioms in §10 of [18]. 474 JOS ´ E FERREIR ´ OS arbitrary classes from the edifice of mathematics, it is natural that they were particularly aware of this problem. Set theory aims to clarify the notion of set by making explicit all of the relevant axiomatic principles. In the context of an axiom system for set theory, it is particularly clear that one cannot use second-order quantification, since this amounts to relinquishing one’s initial aim, relegating an important part of the notion of set to the underlying logic. One might still think of a different way out. We might attempt a precise delimitation of the realm of properties, once again by means of axiomatization. (An independent reason for taking this route is that one can formulate antinomies for naive ‘property theory’ like the Russell paradox or the heterological paradox. A need to axiomatize properties arises in parallel with the need to axiomatize sets.) Skolem considered this possibility of axiomatizing ‘property theory’ in [65], but only to reject it as a foundational resource. The outcome would be an axiom system similar to axiomatic set theory, whose foundations would be at least as dubious as those of Zermelo’s system. (The outcome would actually be rather obscure. Quine has repeatedly argued that properties are much more unclear than sets, since properties that apply to exactly the same objects need not be identical; as he says, we lack clear principles of identification for properties.) It would be absurd to assume such an axiom system in order to establish the foundations of axiomatic set theory. Therefore, and once again, if we are interested in axiomatizing, we cannot use higher-order logic but only a more restricted system. It might seem that, at this point, the only possibility open to us is FOL, but there still is an alternative choice. Although regular, impredicative higher-order logic is forbidden, we could resort to predicative higher-order logic, which avoids the objectionable move of introducing at the logical level the contentious notion of arbitrary set (or arbitrary property). This was actually Weyl’s argument [77], and Skolem, too, accepted this diagnosis [65]. Thus, both authors presented the dilemma: either predicative higher-order logic, or first-order logic. And both of them found it more convenient for actual mathematical work to use the simpler first-order system. Under these conditions, all of the objects that appear in an axiomatization come to play the role of individuals. Even if we were to introduce symbols that, intuitively, we understand as referring to predicates, when it comes to offering a model of the system they would become individuals. In the spirit of axiomatics, seeming higher order quantification becomes in practice elementary quantification. (It seems plausible that this was also von Neumann’s opinion in the 1920s, but there are no unequivocal statements on the topic in his work.) 5.2. Proof-theoretic motives behind FOL. As we saw above, one of the basic guiding principles of the logical tradition was that of formality. In the traditional understanding, this meant that logical theory is aimed at THE ROAD TO MODERN LOGIC—AN INTERPRETATION 475 analyzing the form of arguments, disregarding their matter. A different, modern conception of formality emerged with the notions of formal proof and formal system, first presented by Frege [24]. Modern reliance on formal systems can be regarded as an improvement on two traditions: first, it constitutes a perfected version of the older idea of subjecting logical inference to calculation (Leibniz’s principle); second, it represents a natural refinement of modern axiomatics. The latter was the motive that Frege himself emphasized when saying that the aim of his conceptual language was to provide total control of the premises and possible implicit assumptions in deduction. The conception of logic as a calculus, merged with the idea that logical theory should be embodied in formal systems, proved to be a key principle, indeed the crucial one behind restriction of the logical language to the first order. Now, the analysis of formal proof within formal systems is called proof theory, and what I have just said is that the main motives behind that final restriction were proof-theoretical. But one should keep in mind that formal proof and proof theory are quite natural, albeit profound, refinements of the 19th-century axiomatic tradition. As regards formal proof, Hilbert acknowledged this when he said in 1917 [35] that the axiomatization of logic itself constituted the “crowning achievement” of the axiomatic movement. This makes clear the existence of a natural link between the motives reviewed in §5.1 and the ones we shall consider here. It seems likely that all mathematicians who employed calculuses, from Vi` ete to Frege and Hilbert, assumed that those calculuses would prove to be ‘complete’ in the informal sense of admitting the derivation of any desired result, in the language of the calculus, by means of its formal operations. However, in the absence of a completely formalized system this notion of ‘completeness’ lacks a well-defined sense; one may well be able to realize it in practice, as long as one feels free to introduce novel symbols for new operations and functions. The question changed completely when the idea of calculus merged with that of formal system. The traditional assumption, now turned into the requirement of syntactic or semantic completeness, proved to be out of reach for most interesting mathematical systems. Anybody who has studied mathematicallogic knows this, since it is the content of G¨ odel’s first incompleteness theorem. G¨ odel [29] established that the system of simple type theory is incomplete, and made it clear that the same applies to many other “related systems”—like second-order logic and the system of first-order Peano arithmetic. In fact, as established by later work, any formal system that is consistent and contains primitive recursive arithmetic is incomplete. G¨ odel himself established in his dissertation, and published in 1930, the result that FOL is complete, thus solving a problem posed by Hilbert & Ackermann [37]. What these results, taken together, mean is that the consequence relation of FOL can be captured by means of formal proof, while the 476 JOS ´ E FERREIR ´ OS consequence relation of second-order logic cannot. If one requires logical systems to be completely formal, those results imply that the only quantificational system that merits the name of logic is FOL.68 That requirement was actually implicit in foundational work as done in the Inter-War period, as a result of foundational insecurity reinforced by the aims of Beweistheorie, but as we shall see it was far from being consciously clear. In the long run, however, FOL emerged as the only logical system available for foundational or metamathematical studies, modulo the aim of establishing with absolute certainty the security of the foundations.69 While G¨ odel was establishing his results, extensive experience with axiom systems made it clear that FOL suffices for the development of any given body of mathematical theory. This was acknowledged by Hilbert and Ackermann in an interesting statement: The restricted functional calculus was sufficient, as long as one had no other aim than the formalization of logical inference, as long as it was only a matter of developing isolated theories of themselves, in a purely formal way, from their principles. But as soon as one makes the foundations of the theories, particularly mathematical theories, the subject of investigation, as soon as one wishes to test in which connection they stand to logic, and to what extent they can be won from purely logical operations and concepts, then the expanded functional calculus is indispensable.70 The second half of this quote seems to be a reflection on logicism, which appears to have tempted Hilbert in the 1910s (see Hilbert [35]). But now we are interested in the first sentence. Work with axioms for the number system, geometry, and set theory had established that it is perfectly possible to derive all the required theorems from first-order axioms (see §1.4). The fact that axiomatic set theory can be satisfactorily formalized within FOL would be emphasized by Skolem in the 1920s [64], [65], Tarski in 1935 [67], Quine in 1936 [54], Bernays in 1937 while giving his version of the von Neumann system [2], and G¨ odel in 1939 and 1940 [30], [31]. In a word, FOL turned out to be sufficient for codifying mathematical proofs. The results that G¨ odel published in 1930 and 1931 suggested that, in principle, FOL is an ideal system of logic, being the only quantificational system that is proof-theoretically well-behaved and sound. At the same time, its sufficiency for the codification of mathematical proofs established that FOL is satisfactory in practice. The elements for decision making were 68To be careful, one might also consider a system like FOL augmented with the quantifier “for uncountably many,” but no one has proposed to take this as a basic logic. 69The proviso is essential: many other, more powerful systems have been used in the second half of the 20th century. But it is clear that, in the meantime, the aims and requirements of metamathematics changed. 70Hilbert & Ackermann [37], 86. THE ROAD TO MODERN LOGIC—AN INTERPRETATION 477 at hand, but the interplay between technical results and conceptual issues is always complex (below we shall consider Zermelo as an example of this maxim). Even logicians who openly accepted G¨ odel’s incompleteness results failed to establish the requirement that logical systems must be strictly formal and take the corresponding consequences. This is exemplified by Quine’s Mathematical Logic [55]. Faced with G¨ odel’s incompleteness theorems, most connoisseurs concluded that it is impossible to reduce mathematics to a formal system, a syntactic game within a rigid calculus. But nothing hindered them from drawing a similar conclusion regarding logic. After an interesting presentation of G¨ odel’s results in the last chapter of his book, Quine concluded: Logical truth ... is syntactically undefinable. Logical truth can be said ... to be informal.71 This is understandable, since Quine’s logical system was a substitute for type theory, and therefore a formal system for the theory of classes. However, this standpoint conflicted with the principle of the calculus, as I have called it, in its modern post-Fregean understanding. During the Inter-War period there was a clear preference for formal systems, and it was assumed that the role of logical theory was to be a tool in their formulation. In spite of Russell, Carnap, and the Vienna Circle, logicism had been abandoned by most active logicians.72 It was more coherent with these tendencies to take the route opposite to Quine’s, define logic to be a completely formal science, and leave mathematics ‘transformal,’ so to say. This was also more convenient for practical purposes, and desirable in view of further reasons to be considered shortly. Quine himself opted for this viewpoint, in a radical way, from about 1950. Finally, one may speak of an argument of simplicity speaking for FOL, judged from a foundational standpoint. In the 1930s, it was generally agreed that set-theoretical ideas afforded a natural and satisfactory foundation for all of abstract mathematics. The two main alternatives for a rigorous establishment of such a foundation were either a type-theoretical system with axioms of Infinity and Choice, or else a first-order system with the Zermelo– Fraenkel axioms. Earlier, around 1920, those had seemed to be completely different systems, but later events led to their rapprochement.73 When ramified type theory was abandoned, Russell’s system was turned into an impredicative one, close to classical mathematics. With Skolem, Fraenkel and von Neumann, the system of Zermelo was formalized, coming to be a ‘logistic’ system in the spirit of Frege and Russell. And when Zermelo adopted the axiom of Foundation, axiomatic set theory turned out to describe a universe of sets that intuitively was very similar to that of type theory. Authors like 71Quine [55], §60, p. 318. 72See [22]. 73This topic is discussed in detail in Ferreir´ os [23], ch. X and XI. 478 JOS ´ E FERREIR ´ OS Church acknowledged in the 1930s that the Zermelo system and type theory were, in their current form, “essentially similar”.74 At this point, the main differences between the two systems were the following. The full Zermelo–Fraenkel system is more powerful than type theory with Infinity and Choice, and it was preferred by working mathematicians. Secondly, and of particular interest here, to the extent that both systems described the same universe, axiomatic set theory did so in a simpler way—type theory is higher-order, while set theory, as we saw above, can be formulated within FOL. The “essential similarity” between both systems, together with the greater simplicity of axiomatic set theory, spoke for choosing the latter, based on FOL, as a foundational system. Tarski gave expression to this viewpoint in his 1935 Nachwort to the famous paper on the notion of truth: From the languages just considered it is but a step to languages of another kind [which constitute a much more convenient and actually much more frequently applied apparatus for the development of logic and mathematics]. In these new languages all the variables are of indefinite order. From the formal point of view these are languages of a very simple structure; ... all their variables belong to one and the same semantical category. Nevertheless, as is shown by the investigations of E. Zermelo and his successors (cf. Skolem, Th. [66], pp. 1–12), with a suitable choice of axioms it is possible to construct the theory of sets and the whole of classical mathematics on the basis provided by this language.75 Tarski had previously regarded as inescapable the adoption of a certain “theory of semantical categories” which, as a consequence, brought the necessity of type restrictions [67, 215]. Now he was no longer in a position to defend that viewpoint, and came to accept fully the validity of a first-order approach. §6. Schließendes.The implications of G¨ odel’s results were extremely compelling because foundational work focused on proof theory and hinged on the question of consistency for formal systems. They would not have been compelling, had most logicians been interested above all in Modelltheorie, not in Beweistheorie. (As we have seen, however, this counterfactual assumption is unlikely given the important role played by the “principle of the calculus” in the emergence of modern logic, and given the foundational situation during the 1920s—paradoxes, constructivistic criticism, naturally leading to the problem of consistency.) Witness of that alternative is the peculiar case of Zermelo, who around 1930 reacted to the results of L¨ owenheim, Skolem, and G¨ odel by abandoning the requirement of working within 74Church [9], 69–70. 75Tarski [67], 271, footnote 1. The words in brackets are not found in the 1935 German version (compare Tarski, Collected papers, vol. 2, 190 footnote). THE ROAD TO MODERN LOGIC—AN INTERPRETATION 479 formal systems. Actually, he attacked this idea directly and despised it, calling it “Skolemism”.76 Later, when metamathematical work began to pursue aims different from that of consistency, it became more and more customary to have recourse to the whole freedom of regular mathematics at the meta-level. Simultaneously the use at the system-level of infinitary logic, higher-order logic, and the like resurfaced. But one must be conscious that this implied a crucial change of route, relinquishing the notion of formal system in the strict sense (infinitary logic, e.g., can only be made sense of as a set-theoretical construct). As we have seen, the interplay between technical results and conceptual issues is always complex. The 19th-century convergence of traditional logic with mathematical traditions determined the routes taken by logical theory along the complex road leading from the Aristotelian exemplars to this paradigm of the 20th century, the first-order system. The first moves actually widened immensely the scope of logic, blurring the boundary line between logic and mathematics (logicism), but the paradoxes of set theory gave a fatal blow to that tendency. The theory of sets was eventually trimmed from logic, and a clear preference for well-behaved, strictly formal systems emerged. The needs of axiomatics, the context of Beweistheorie,andthe crucial metatheoretical results obtained about 1930 did the rest. The process was still complex and convoluted—including the emergence of type theory, initially as an attempt to preserve logicism—but the main motives seem clear now. First-order logic emerged as an analysis of the most fundamental basis for the notion of mathematical proof. To put it otherwise, it emerged as the logic that is necessary and sufficient for codifying mathematical proofs, axiomatizing mathematical theories, and studying their metatheory. Firstorder logic began to be widely proclaimed as the core of modern logic in the 1930s, reaching its zenith around 1950. It is a clear symptom of the hyperactivity that characterized mathematical logic in the 20th century, that we now view such a recent product as a classical theory. After a historico-philosophical analysis like the preceding, one is easily tempted to speculate about counterfactual history. I have defended that the history of logic would have looked quite different had the Stoic set of exemplars taken the role of the Aristotelian ones. We would have a much more trivial story, to be sure, leading rather directly to sentential logic, and later to complementary or alternative systems (modal logic, intuitionistic propositional logic). Logicism would never have been formulated, and quantification theory would perhaps have been regarded as an extremely basic mathematical system, of which the great philosopher Aristotle got a glimpse. 76Zermelo [81]. See Grattan-Guinness [33], Moore [43], Dawson [14]. 480 JOS ´ E FERREIR ´ OS Considering Zermelo and his reaction to “Skolemism”—or, as one might say, FOL-mania—one can think of other deviant historical scenarios. Imaginea worldinwhichthe 20th centurybeginswith some authorwhoofferssuch a convincing solution to the paradoxes, that everybody agrees. (This might have been a clear presentation of the iterative conception of sets, which was somehow present in the practice of 19th-century mathematicians.) Imagine, further, that this solution makes set theory appear as a consistent mathematical theory that does not belong to logic. Within such a context, the strong interest in formal systems and proof theory, that was so characteristic of the 1920s and 1930s, might not have emerged. But, without this, the key reasons for focusing on FOL would have disappeared from the scene. The main foundational theme of the era might have been, not consistency, but a semantic question—the codification of crucial mathematical notions such as that of natural number and real number, meaning the categorical characterization of such notions. Had this been the case, the recommendations of Hilbert and Church would have been heard and second-order logic would probably have taken the paradigmatic role that was played, in fact, by FOL.77 Mathematical logic is what logic, through twenty-five centuries and a few transformations, has become today. As we have seen, these transformations were not merely questions of detail—they involved fundamental changes in conception of the subject and delimitation of its scope. REFERENCES [1] Antoine Arnauld and Pierre Nicole,La logique ou l’art de penser, Flammarion, Paris, 1970 (original edition 1662). [2] Paul Bernays,A system of axiomatic set theory,The Journal of Symbolic Logic, vol. 2 (1937), pp. 65–77. [3] Garrett Birkhoff,A source book in classical analysis, Harvard University Press, 1973. [4] Joseph M. Boche ´ nski,Formale Logik, Alber, M¨ unchen, 1956. [5] George Boole,The mathematical analysis of logic, Macmillan, Cambridge, 1847, references to the reprint Basil Blackwell, Oxford, 1951. [6] Rudolf Carnap,Abriss der Logistik, mit besonderer Ber¨ ucksichtigung der Relationstheorie und ihrer Anwendungen, Springer, Wien, 1929. [7] ,Die logizistische Grundlegung der Mathematik,Erkenntnis, vol. 2 (1931), pp. 91–105, references to the English translation in P. Benacerraf and H. Putnam, Philosophy of Mathematics: selected readings, Cambridge University Press, 1983, 41–52. [8] Alonzo Church, Review of L. Chwistek,¨ Uberwindung des Begriffsrelativismus,The Journal of Symbolic Logic, vol. 2 (1937), pp. 169–170. [9] ,The present situation in the foundations of mathematics,Philosophie math´ ematique (F. Gonseth, editor), Hermann, Paris, 1939. [10] ,A formulation of the simple theory of types,The Journal of Symbolic Logic, vol. 5 (1940), pp. 56–68. 77See Shapiro [63]. THE ROAD TO MODERN LOGIC—AN INTERPRETATION 481 [11] ,Introduction to mathematical logic, Princeton University Press, 1956. [12] Leo Corry,Modern algebra and the rise of mathematical structures, Birkh¨ auser, Basel, 1996. [13] Richard Creath (editor), Dear Carnap, Dear Van: The Quine–Carnap correspondence and related work, University of California Press, 1990. [14] John W. Dawson, Jr.,Completing the G¨odel–Zermelo correspondence,Historia Mathematica, vol. 12 (1985), pp. 66–70. [15] Augustus De Morgan,On the syllogism: III and on logic in general,Transactions of the Cambridge Philosophical Society, 1858, references to (P. Heart, editor), On the Syllogism and other logical writings, pp. 74–146, Routledge & Kegan Paul, London, 1966. [16] ,On the syllogism: IV and on the logic of relations,Transactions of the Cambridge Philosophical Society (1860), references to (P. Heart, editor), On the Syllogism and other logical writings, pp. 208–246, Routledge & Kegan Paul, London, 1966. [17] Richard Dedekind,Stetigkeit und irrationale Zahlen,Gesammelte mathematische Werke, vol. 3, Chelsea, New York, 1969, reprint of original edition (1872). English translation in W. B. Ewald (editor), From Kant to Hilbert, Oxford University Press, vol. 2. [18] ,Was sind und was sollen die Zahlen?,Gesammelte mathematische Werke, vol. 3, Chelsea, New York, 1969, reprint of original edition (1888). English translation in W. B. Ewald (editor), From Kant to Hilbert, Oxford Univ. Press, vol. 2. [19] Burton Dreben and J. van Heijenoort,Introductory note,Collected works of K. G¨ odel, vol. 1, Oxford University Press, 1986, pp. 44–59. [20] Moritz W. Drobisch,Neue Darstellung der Logik nach ihren einfachen Verh¨ altnissen, Voss, Leipzig, 1836 (four editions up to 1875). [21] Jos´ e Ferreir´ os,Traditional logic and the early history of sets, 1854–1908,Archive for History of Exact Sciences, vol. 50 (1996), pp. 5–71. [22] ,Notes on types, sets and logicism, 1930–1950,Theoria, vol. 12 (1997), pp. 91– 124. [23] ,Labyrinth of thought. A history of set theory and its role in modern mathematics, Birkh¨ auser, Basel, 1999. [24] Gottlob Frege,Begriffsschrift, Nebert, Halle, 1879, reprint as Begriffsschrift und andere Aufs¨ atze (I. Angelelli, editor) in Olms, Hildesheim, 1964. [25] ,Grundgesetze der Arithmetik, vol. 1, Pohl, Jena, 1893, reprint Olms, Hildesheim, 1966. [26] ,Grundgesetze der Arithmetik, vol. 2, Pohl, Jena, 1903, reprint Olms, Hildesheim, 1966. [27] ,Anwendungen der Begriffsschrift, Jenaischer Zeitschrift f¨ ur Naturwiss,1879. References to the reprint in Begriffsschrift und andere Aufs¨ atze (I. Angelelli, editor), Olms, Hildesheim, 1964. [28] ,Der Gedanke. Eine logische Untersuchung,Beitr¨ age zur Philosophie des deutschen Idealismus, vol. 1 (1918), references to the English translation in B. McGuinness, editor. Collected Papers on Mathematics, Logic, and Philosophy, pp. 351–372, Basil Blackwell, Oxford, 1984. [29] Kurt G¨ odel,¨ Uber formal unentscheidbare S¨atze der Principia Mathematica und verwandter Systeme,Monatshefte f¨ ur Mathematik und Physik, vol. 38 (1931), pp. 173–198, references to the reprint in Collected works, vol. 1, Oxford University Press, 1986. [30] ,Consistency proof for the generalized continuum hypothesis,Proceedings of the National Academy of Sciences of the United States of America, vol. 24 (1939), pp. 220–224, references to the reprint in Collected works, vol. 2, Oxford University Press, 1990. [31] ,The consistency of the axiom of choice and of the generalized continuum hypothesis with the axioms of set theory, Princeton University Press, 1940, references to the reprint in Collected works, vol. 2, Oxford University Press, 1990.