Preface
The name “Löwenheim-Skolem theorem” is commonly given to a variety of results to the effect that if a set of formulas has a model of some (infinite) cardinality, it also has models of some other infinite cardinality. The first result of this type, proved by Löwenheim in “Über Möglichkeiten im Relativkalkül” [1915], asserts (though he put it rather differently) that if a first-order sentence has a model, then it has a countable model as well.
Because of the significance of this theorem, “Über Möglichkeiten im Relativkalkül” is mentioned in every history of logic; but the extraordinary historical interest of the paper does not reside in the theoretical importance of any of the results it contains (in the same paper Löwenheim also proved that the monadic predicate calculus is decidable and that first-order logic can be reduced to binary first-order logic), but in the fact that its publication marks the beginning of what we call model theory. As far as we know, no one had asked openly about the relation between the formulas of a formal language and their interpretations or models before Löwenheim did so in this paper. From this point of view, Löwenheim's paper would still be fundamental for the history of logic, even if his theorem had not had so many mathematical and philosophical repercussions.
The algebraic study of logic was initiated by Boole in The mathematical analysis of logic [1847] and consolidated by Peirce and Schröder. Peirce established the fundamental laws of the calculus of classes and created the theory of relatives. Schröder proposed the first complete axiomatization of the calculus of classes and expanded considerably the theory of relatives. Löwenheim carried out his research within the frame of the theory of relatives developed by Schröder, and so it is inside this algebraic tradition initiated by Boole that the first results of model theory were obtained.
For many years historians of logic paid little attention to the logicians of the algebraic tradition after Boole. However surprising it may seem today, an event as important as the birth of model theory passed practically unnoticed. A look at the chapters on contemporary logic by Kneale and Kneale [1984] and by Bocheński [1956] is enough to convince us of this. To my knowledge van Heijenoort was the first to grasp the real historical interest of Löwenheim's paper. In “Logic as calculus and logic as language” [1967] van Heijenoort contrasted the semantic approach to logic characteristic of the logicians of the algebraic school with the syntactic approach represented by Frege and Russell; he noted the elements in Löwenheim's paper that made it a pioneering work, deserving of a place in the history of logic alongside Frege's Begriffsschrift and Herbrand's thesis; and he stressed that Löwenheim's theorem was inconceivable in a logic such as Frege's.
In recent years the interest of historians of logic in the algebraic school has increased appreciably, but our knowledge of it remains insufficient and there are still many questions to be answered. Among the most interesting of them are those concerning Löwenheim's theorem. Even today, its original proof raises more uncertainties than that of any other relatively recent theorem of comparable significance. On the one hand, the very result that is attributed to Löwenheim today is not the one that Skolem — a logician raised in the algebraic tradition — appears to have attributed to him. On the other hand, present-day commentators agree that the proof has gaps, but, with the exception of van Heijenoort, they avoid going into detail and cautiously leave open the possibility that the shortcomings may be put down to an insufficient understanding of the proof. Indeed, the obscurity of Löwenheim's exposition makes it difficult to understand his argument, but it is also true that the proof appears to be more obscure than it really is, due to an insufficient understanding of the semantic way of reasoning which typified the algebraic tradition.
In general terms, the object of this book is to analyze Löwenheim's proof and to give a more detailed description of the theoretical framework that made it possible.
Chapter 1 is an introduction which summarizes the contributions of Boole, Jevons, Peirce, and Schröder leading to the first complete axiomatization (by Schröder) of the theory of Boolean algebras. The aim of this brief historical sketch is to situate the reader in the algebraic tradition, rather than to expound on all the contributions of the logicians just mentioned. Although quite schematic, this chapter includes a reconstruction of the key points of the controversy between Peirce and Schröder on the axiomatization of the calculus of classes, and also highlights a difficulty in Schröder's proofs of certain theorems of propositional calculus.
The first three sections of chapter 2 are devoted to expounding the theory of relatives according to Schröder, as presented in the third volume of his Vorlesungen über die Algebra der Logik. Section 4 of this chapter takes up the issue of the emergence of model theory within the algebraic approach to logic. The most widely held view is that Löwenheim received from Schröder the theory and the kind of interests that made it possible to obtain the first results in model theory.In addition to the theory of relatives, this inheritance includes the type of semantic reasoning characteristic of the algebraic tradition, a greater concern with first-order than with second-order logic, and, perhaps, an interest in metalogical questions. Nevertheless, a close examination of Schröder's research project forces us to conclude that he was not interested in first-order logic or in metalogical questions and, in consequence, that Löwenheim could not have inherited these interests from him. In the same section I analyze the sense in which the theory of relatives includes a system of logic, and discuss whether Löwenheim was aware of the possibility of rendering mathematical theories in a formal language. The chapter ends by specifying the syntactic and semantic notions needed to analyze Löwenheim's proof of his theorem.
A significant step in Löwenheim's proof is the application of a transformation introduced by Schröder that allows us to move the existential quantifiers in front of the universal ones, preserving logical equivalence. This transformation is traditionally considered to be the origin of the notion of Skolem function. In chapter 3, I discuss Schröder's transformation in detail, explain how Löwenheim interpreted and applied it in his proof of the theorem, and finally show why the functional interpretation of it is inadequate for the reconstruction of the arguments of either logician.
Löwenheim's proof of his theorem has two separate parts. The first consists in showing, with the aid of Schröder's transformation, that every formula is logically equivalent to a formula having a normalized form. Specifically, a formula is in normal form if it is in prenex form and all the existential quantifiers precede the universal ones. In Chapter 4, I analyze this part of the proof, which, surprisingly, has been ignored in the commentaries published to date.
Chapter 5 addresses a series of points that are crucial to a full understanding of the core of Löwenheim's argument, but have not been considered in the previous chapters. Some of the difficulties in interpreting Löwenheim's proof may stem from an insufficient consideration of the details analyzed in this chapter.
The simplest versions of the Löwenheim-Skolem theorem are
(a) if a first-order formula has a model, then it has a countable model;
(b) if a first-order formula has a model M, then it has a countable model M0, which is a submodel of M.
The second part of Löwenheim's argument is the proof of one of these versions for first-order formulas in normal form. The question is, of which?
According to the traditional view, Löwenheim proved (or aimed to prove) version (a), making an essential use of formulas of infinite length, but his proof had major gaps and it was only Skolem who offered a sound proof of both versions and generalized the theorem to infinite sets of formulas. Against this, we have Skolem's opinion, which ascribed to Löwenheim the proof of version (b). Historians of logic have usually ignored Skolem's attribution (assuming, I suppose, that it was either overgenerous or sloppy), but in my view it is highly significant and deserves to be taken seriously. In chapter 6, I analyze in detail the second part of Löwenheim's proof. I conclude that infinite formulas play no substantial role in it and, in agreement with Skolem, that Löwenheim did prove the submodel version, or at least attempted to do so. Moreover, the shortcomings that prompted Skolem to offer another proof of the theorem are not the ones commonly attributed to Löwenheim's original proof.
In the appendix, I present a formal language suitable for the reconstruction of Löwenheim's proof and prove the technical assertions which in my commentary of the argument have been rigorously but informally justified. The proof of the theorem included in the appendix is not the simplest one that can be offered today, but the one that in my opinion most closely agrees with the spirit of Löwenheim's argument.
For the quotations written originally in German, whenever possible I have used the English translation included in van Heijenoort's From Frege to Gödel. When I felt that this version should be amended, I have introduced the modification in the quotation and mentioned the fact in a note. In the cases in which there is no translation of the quoted text that can be considered standard, I have included the original text in German in a note. To aid comprehension, I have occasionally inserted a footnote or a short comment in a quotation. These interpolations are enclosed in double square brackets: [[ ]]. Where the context makes it clear that a symbol or a formula is being mentioned, I have often omitted the quotation marks that are normally used in these cases. In the index, the technical terms of the theory of relatives are referred both to the pages where the term is explicated and to the pages where the original quotations including the term appear.
I am indebted to Jesús Mosterín, who directed my doctoral dissertation in which this book has its origin. Ramon Cirera, Manuel García-Carpintero, Manuela Merino, Francesc Pereña, and Daniel Quesada helped me in different forms when I was writing my dissertation; I am grateful to all of them. I owe special thanks to Ignacio Jané and Ramon Jansana for their careful and valuable criticism of an earlier Spanish version which helped me both to correct a number of errors and to improve my exposition. Ignacio Jané has been patient and kind enough to read the English version and his comments have once again been very useful. Finally, thanks are also due to Paolo Mancosu, Richard Zach, and an anonymous referee for their comments and suggestions. The mistakes that remain are, of course, my own.
This book has been partially supported by Spanish DGICYT grants PS94–0244 and PB97–0948.