The Limits of Logic

Higher-Order Logic and the Löwenheim-Skolem Theorem

Stewart Shapiro

• Publisher: Routledge
• Year: 2016
• eBook ISBN: 9781351886666
• Edition: 1
• Topic: Philosophy
• Subtopic: Philosophy History & Theory

The International research Library of Philosophy collects in book form a wide range of important and influential essays in philosophy, drawn predominantly from English-language journals. Each volume in the library deals with a field of enquiry which has received significant attention in philosophy in the last 25 years and is edited by a philosopher noted in that field.

Part I

Is Second-Order Logic Logic?

[1]

History and Philosophy of Logic, 1 (1980), 95–137

Beyond First-order Logic: The Historical Interplay between Mathematical Logic and Axiomatic Set Theory

Dedicated to Kurt Gödel and Ernst Zermelo

GREGORY H. MOORE

Department of Mathematics, University of Toronto, Toronto, Ontario, Canada, M5S 1A1

Received 31 December 1979

What has been the historical relationship between set theory and logic? On the one hand, Zermelo and other mathematicians developed set theory as a Hilbert-style axiomatic system. On the other hand, set theory influenced logic by suggesting to Schröder, Löwenheim and others the use of infinitely long expressions. The question of which logic was appropriate for set theory – first-order logic, second-order logic, or an infinitary logic – culminated in a vigorous exchange between Zermelo and Gödel around 1930.

1. INTRODUCTION

How has the historical boundary developed between logic and set theory? Prior to Georg Cantor’s researches, the notion of class belonged to logic and hence constituted a part of philosophy. In particular George Boole, whose logic continued to be influenced by the Aristotelian tradition, employed the notion of class in this fashion.¹ Yet during the 1880s, when Cantor generalized his fundamental notion from that of a point-set (a set of n-tuples of real numbers) to that of a set with elements of arbitrary nature, the time was ripe for an interplay between set theory as a part of mathematics and logic as a part of philosophy.² Thus it was only natural that both mathematicians and philosophers began to inquire what relationship existed, or ought to exist, between set theory and logic.

If set theory were to form a subdivision of logic, then either one pre-empted its concepts, as both Gottlob Frege and Bertrand Russell were to do, or else one had to formulate set theory as a deductive system with explicit postulates. In 1899 David Hilbert had provided a paradigm for such a deductive system by axiomatizing geometry in a way that did not require the postulates to be supplemented by intuition. Influenced by Hilbert while at Göttingen, Ernst Zermelo axiomatized set theory – not in order to reduce it to logic but so that set theory could provide a foundation for all of mathematics. Nevertheless, the criticisms directed against his axiomatization urgently required that he specify the underlying logic as well.

At the time mathematical logic was very much in flux. As the nineteenth century ended, the distinction between syntax and semantics was not uniformly observed nor even clearly understood (with the exception of Frege and to a lesser extent Hilbert). This partial conflation of syntax and semantics occurred frequently within the Boolean tradition of logic, as developed by C. S. Peirce and Ernst Schröder. Consequently, the door was opened to an infinitary logic – one employing either infinitely long expressions or rules of inference with infinitely many premises. In particular, Peirce treated the notions of universal and existential quantifier as all but identical with infinite conjunctions and disjunctions. Thus the actual infinite entered logic not only in the semantic guise of infinite sets but also in the syntactic guise of infinitely long expressions – a fact that has long been neglected by both historians and philosophers. The situation was further complicated because first-order logic, which permitted quantification only over individuals, had not yet been separated from second-order logic, whose quantifiers could range over predicates as well as over individuals.

Indeed, the question of how to formulate set theory became entangled with the distinction between first-order and second-order logic, as well as with the related problem of categoricity. Certain mathematicians, such as Abraham Fraenkel, sought to modify Zermelo’s axiomatization in order to render it categorical. On the other hand. Thoralf Skolem insisted that no system of axiomatic set theory could be categorical since every such system had a denumerable model within first-order logic. This so-called ‘Skolem paradox’ caused Zermelo to reject first-order logic as inadequate to the needs of mathematics – a conclusion which, he believed, was corroborated by Kurt Gödel’s incompleteness theorem. In response, Zermelo proposed a very strong infinitary logic, with arbitrarily long expressions and even with infinitely long proofs, to serve as the underlying logic for mathematics.

Yet Zermelo’s proposal to strengthen logic attracted no interest at the time. In fact, Skolem’s desire to base set theory solely on first-order logic became increasingly the standard approach. This article investigates how the restrictive logic of Skolem triumphed over the rich logic of Zermelo, and how this triumph affected the development of set theory.

2. MATHEMATICAL LOGIC AROUND 1900

Historians of logic have often distinguished between two logical traditions which arose during the latter half of the nineteenth century.³ The first of these, originating with Boole, grew through the researches of his English followers as well as through those of Peirce in the United States and of Schröder in Germany. Frequently these logicians treated the analogy between the laws of algebra and the laws of logic as a guide in their logical investigations. For Schröder and often for Peirce, the same symbols represented both classes and propositions – an ambiguity important in what follows.

The second tradition, often designated the logistic method, had two sources: Frege and Peano. Yet despite his many insights into the nature of logic, Frege had little influence upon his contemporaries. Even Russell was most affected not by Frege but by Peano, whose symbolism Russell adopted.⁴ Above all, it was through Russell that the logistic method influenced the development of mathematical logic.⁵

Within these two logical traditions there arose quite different notions of quantifier. In his Begriffsschrift of 1879, Frege introduced a universal quantifier that resembles its modern counterpart, except that he placed no restriction on what may be quantified. At the same time he treated the existential quantifier, for which he did not propose any special symbol, as ‘not for every x not’. A decade later Peano introduced a universal quantifier as a subscript to equivalence and implication, and an existential quantifier as ‘not for every x, A(x) is the false’.⁶ Thus Peano understood quantifiers, in effect, similarly to Frege. Nevertheless, at the time Peano was not acquainted with Frege’s work, but cited instead an article of 1885 in which Peirce had introduced quantifiers quite differently. In fact, Peirce defined universal and existential quantifiers by analogy to infinite algebraic sums and products.

Peirce’s notion of quantifier, a term that he suggested, merits closer examination. His symbols Σ and Π, originally representing algebraic sum and product, stood respectively for set-theoretic union and intersection on the one hand and for existential and universal quantifiers on the other. Since he used this notation for relations (or classes) and for propositions, the reader might wonder at times which meaning was intended. Yet this very confusion was to prove fruitful, since it encouraged the introduction of infinitely long expressions into logic.

Crediting the invention of quantifiers to his student O. H. Mitchell, Peirce wrote:

Here, in order to render the notation as iconical as possible we may use Σ for some, suggesting a sum, and Π for all, suggesting a product. Thus Σ_ix_i means that x is true for some one of the individuals denoted by i or Σ_ix_i = x_i + x_j + x_k etc. In the same way Π_ix_i means that x is true of all these individuals, or Π_ix_i = x_ix_jx_k etc.… It is to be remarked that Σ_ix_i and Π_ix_i are only similar to a sum and product; they are not strictly of that nature, because the individuals of the universe may be innumerable.⁷

Peirce’s last sentence suggests two interpretations. On the one hand, it may be taken to assert that Σ_ix_i and Π_ix_i are not to be considered as infinitely long propositions. On the other hand, it may mean that Σ_ix_i and Π_ix_i stand for such infinitely long propositions, while infinite sums and products are not strictly permitted in algebra (where one replaces them by limits of finite sums and products). The latter interpretation is more reasonable in the given context, and was the one evidently taken by Schröder.

Thus Frege and Peano, the founders of the logistic method, introduced quantifiers in the modern sense (but without distinguishing between first-order and second-order logic), while Peirce and those who followed him in developing the algebraic tradition of logic had something rather different in mind. To identify a universal quantifier with an infinite conjunction, one must specify a particular domain. If this domain is infinite and if there is an individual constant naming each individual of the domain, it becomes possible to treat each universal quantifier as an infinite conjunction, and likewise each existential quantifier as an infinite disjunction, in the manner that Peirce did. Of course, if the given domain is finite, then finite conjunctions and disjunctions suffice to represent quantifiers.

It is intriguing to find that Hilbert, who was later much influenced by Russel’s Principia mathematica, represented quantifiers in 1904 by essentially the same means as Peirce. At the Third International Congress of Mathematicians, held at Heidelberg, Hilbert analyzed the foundations of logic and of the real numbers. To secure these foundations properly and to circumvent the set-theoretic paradoxes, he insisted that the laws of logic and some of those for arithmetic must be developed simultaneously. Above all, he considered such paradoxes to indicate that traditional logic had failed to fulfill the rigorous demands which set theory now imposed on it. In the course of outlining a logical theory for the positive integers, Hilbert employed both infinite conjunctions A(1) & A(2) & … and infinite disjunctions A(1) ⋁ A(2) ⋁…, where A(x) was a number-theoretic proposition. Moreover, he introduced A(x^(u)) and A(x^(o)) – meaning ‘for every x, A(x)’ and ‘there exists an x, A(x)’ respectively, where x was a positive integer – as abbreviations for A(1) & A(2) & … and A(1) ⋁ A(2) ⋁ ….⁸ Since he did not cite either Peirce or Schröder, it appears that Hilbert independently formulated this method of defining quantifiers with a fixed domain. Nevertheless, he did not further elaborate a syntax for his infinitely long expressions, nor did he investigate the relationship between this and any other form of logic. Two decades later he came to employ a version of the Axiom of Choice, rather than infinite expressions, in order to define quantifiers (see section 6).

Since Schröder did not always distinguish clearly between the calculus of domains and the calculus of propositions (with quantifiers), it remains uncertain whether he intended his infinite expressions to be understood as referring only to classes or also to propositions.⁹ However, his successors understood him to use quantifiers, in effect, as infinite conjunctions and disjunctions. After Schröder’s death in 1902, Eugen Müller reconstructed ...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Table of Contents
• Acknowledgements
• Series Preface
• Introduction
• PART I IS SECOND-ORDER LOGIC LOGIC?
• PART II ONTOLOGICAL REDUCTION, INTENDED INTERPRETATIONS, AND THE LOWENHEIM-SKOLEM THEOREMS
• PART III PLURAL QUANTIFICATION
• PART IV PHILOSOPHY OF SET THEORY
• Name Index