Philosophia Mathematica (III), Vol. 13 No. 1 © Oxford University Press, 2005, all rights reserved
Book Review |
Calixto Badesa. The Birth of Model Theory: Löwenheim's Theorem in the Frame of the Theory of Relatives Princeton: Princeton University Press, 2004. Pp. xiii + 240. ISBN 0–691–05853–9.
* Departament de Lògica, Història i Filosofia de la Ciència, Universitat de Barcelona 08028 Barcelona, Spain jane{at}ub.edu
When we encounter a theorem with a composite name, like Heine-Borel, Cantor-Bendixson, or Löwenheim-Skolem, we are curious to know what the particular contribution to it of each author actually was. The obvious guess is an alternative: either the first author provided a deficient or incomplete proof, or else the second author generalized the original theorem. As regards the Löwenheim-Skolem theorem, both things are the case. The theorem was first proved in 1915 by Leopold Löwenheim (1878–1957), and then reproved and generalized by Thoralf Skolem (1887–1963) in 1920, in 1922, and again in 1929. As stated by Löwenheim in 1915 and by Skolem in 1920, the theorem says that if a first-order sentence has a model, then it has a countable (finite or infinite) model. On the deficiencies of Löwenheim's proof something will be said later, but for now it is worth noting that in 1920 Skolem did not claim that Löwenheim's proof was defective—only that some aspects of it were ‘somewhat involved’ (van Heijenoort [1967a]
, p. 254) and he wanted to give a simpler proof. As to the generalization that Skolem provided, it consisted in extending the theorem so as to apply to a countably infinite set of sentences instead of a single one.
Calixto Badesa's monograph The Birth of Model Theory deals, as its subtitle says, with Löwenheim's theorem in the frame of the theory of relatives. It concentrates on the first two sections of Löwenheim's 1915 essay Über Möglichkeiten im Relativkalkül, 1 where first-order logic is singled out for study and Löwenheim's Theorem is proved. Löwenheim's arguments are carried out in the theory of relatives, initiated by Augustus De Morgan and extensively developed by Charles S. Peirce and Ernst Schröder. The theory of relatives is discussed in the second chapter of the book, the first being devoted to a concise account of the development of the algebra of logic from George Boole to Löwenheim's time. The rest of the book (chapters 3 to 6, and an appendix) focusses on Löwenheim's proof.
The word birth in the title should be understood in a restricted sense, namely as referring to the moment where the first model-theoretic result was established. As Badesa says in the preface, ‘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’. Accordingly, the publication of Löwenheim's essay can be taken to mark the beginning of model theory.
 |
1 |
|---|
 Top 1 23456References |
|---|
The description ‘The Löwenheim-Skolem theorem’ is not uniquely denoting, and it is not even if we restrict our consideration to the actual work of Löwenheim and Skolem and leave aside later generalizations. As Badesa makes it clear, the lack of unique reference of the term is partly responsible for the difficulties that most modern commentators encountered in Löwenheim's proof. Here, ‘modern’ means ‘from 1967 onwards’, 1967 being the year of publication of the source book From Frege to Gödel, which included an English translation of Löwenheim's paper with an introductory comment by the editor, Jean van Heijenoort. The twofold way of understanding the theorem was neatly described by Skolem in 1938. There is the submodel version of the theorem, according to which if a first-order sentence
(or a countable set of first-order sentences 
) has a model 
, then there is a countable substructure of 
which is also a model of (respectively, of ). This form of the theorem implies the other, weaker version, which says that if a first-order sentence (or a countable set of first-order sentences) has a model at all, then it has a countable model. In 1920 Skolem proved the submodel version, although he stated the theorem in the weaker form. He first sketched a proof of the weaker version in 1922, in order to avoid the axiom of choice which he had used in the 1920 proof. It should be noticed that some use of the axiom of choice is needed to prove the sumbodel version, since it implies that every infinite set has a countably infinite subset. 2 Skolem was eager to avoid the axiom of choice, and indeed any irreducibly set-theoretic principles or methods, because he wanted to use his theorem to argue that the axiomatic method cannot provide a foundation for set theory. In 1929, Skolem expanded the 1922 sketch into a fully fledged proof. Only then was he explicit about the fact that in 1920 and 1922 he had proved two inequivalent versions of a theorem, and not that he had merely given two different proofs of one and the same theorem.
Which of the two versions did Löwenheim prove—or aim to prove? Modern commentators assert, or assume, that he tried to prove the weak version. Skolem, however, is very explicit in his assertion that Löwenheim proved the submodel version:
Löwenheim starts from the hypothesis that the given first-order formula [...] represents a proposition which is true in a domain M with a particular choice of the predicates A, B, C, ... With this hypothesis he shows that if one maintains the meaning of A, B, C, ..., this proposition is true in a countable subdomain M 0 of M (Skolem [1941]
Why did modern commentators as well qualified as Jean van Heijenoort, Hao Wang, or Robert Vaught dismiss or ignore Skolem's opinion and maintain that Löwenheim proved the weaker version? One tentative reason could be the strong outer resemblance of Löwenheim's argument with Skolem's 1922 and 1929 proof of the weak version: both Löwenheim and Skolem construct a tree of formulas from which a model is determined. Moreover, at crucial points in Löwenheim's proof where one should expect the domain to be mentioned if he were proving the submodel version, he does not mention it (p. 159). 3
With Skolem (but carefully avoiding leaning on his authority), Badesa maintains that Löwenheim was after the submodel version. When reading Badesa's painstaking study of Löwenheim's proof, one has the impression that the main reason previous commentators had misunderstood Löwenheim's aim is that they did not get deeply enough into the proof itself. As a matter of fact, The Birth of Model Theory is the first in-depth study of Löwenheim's proof—a study that was long overdue in view of the historical importance of Löwenheim's result and of the manifest obscurity of Löwenheim's reasoning. As Badesa points out, ‘the fact that Löwenheim's proof allows two interpretations that diverge in an aspect of such importance indicates patently that his argument is far from clear’ (p. 146). The divergences extend beyond this point. ‘The most widely held position today is that the proof has some important gaps, although commentators differ as to precisely how important they are’ (p. 147). Indeed, ‘a highly significant illustration of the difficulty of understanding Löwenheim's argument is that [the scholars mentioned] do not appear to be confident that they have fully understood it’ (p. 148).
Badesa subjects Löwenheim's text to a careful scrutiny with the aim of presenting Löwenheim's argument as a sensible one. This he does while remaining scrupulously faithful to the text. Whenever he takes a stand on a particular issue that conflicts with the opinions of previous commentators he sustains his position on Löwenheim's words, often taking into account the particular choice of terminology employed. In fact, Badesa's strict faithfulness to apparently minor details strongly enhances the conviction his interpretation carries. This is most evident in the long Section 6.2, devoted to the analysis of Löwenheim's construction, which comes rather smoothly at a point where the reader has already acquired the technical background. In this section, which is the high point of the book, we find the justification that Löwenheim aimed to prove the submodel version of the theorem, and we can follow Löwenheim's indications for the construction of the countable substructure of some originally given model. The proof does not run as we would expect. To us, the construction seems to be unnecessarily convoluted, but as the discussion progresses we come to see why Löwenheim took the particular path he did. At the end, we feel confident that we have understood Löwenheim's argument, even though we may be unsure about the correctness of the proof. But, in Badesa's own words, ‘the answer to the question whether the proof is acceptable or not, bearing in mind the level of the research in logic at that time, seems to me to be far less important [than understanding Löwenheim's argument], because it depends above all on one's own level of tolerance’ (p. 148). 4
|
2 |
|---|
|
Top123456References |
|---|
In the construction of a countable submodel, Löwenheim confines himself to universal sentences, that is, to sentences consisting of a prefix of universal quantifiers followed by a quantifier-free matrix. In order to justify this restriction, Löwenheim had previously argued that the satisfaction of an arbitrary first-order formula can be reduced to that of a formula of this particularly simple form. The way Löwenheim argued for this is rather opaque to a modern reader and has obscure points that have been the subject of discussion by every commentator. I will deal with it presently, but before, and as an introduction to it, it may be helpful to convey Löwenheim's basic idea by turning to Skolem's own simplification ([1941], p. 456) of Löwenheim's reasoning. The essential point is the introduction of Skolem functions, whose justification rests on two facts. The first fact is the equivalence (dependent on the axiom of choice) of a first-order formula of the form:
 | (1) |
with the second-order formula:
 | (2) |
The second fact is that (2), and thus (1), is satisfiable in a domain D (i.e., it is true in some structure with domain D) if and only if the first-order formula with the extra function symbol g:
 | (3) |
is satisfiable in the same domain D. By repeated applications of this process of eliminating existential quantifiers in a formula in prenex form, one can transform any first-order formula 
into a first-order universal formula ß, with new function symbols, in such a way that is satisfiable in a given domain if and only if ß is. Accordingly, Löwenheim's restriction to universal formulas becomes unobjectionable.
Rather, it would be unobjectionable were the procedure just sketched the one Löwenheim had followed. But, as already suggested, this is not how he proceeded. In fact, Löwenheim relied on an equivalence similar to the one between (1) and (2), except that instead of the second-order function variable g in (2), Löwenheim, like Schröder before him, used what he called fleeing indices, subscripted variables whose meaning was not completely clear. We describe the corresponding equivalence in Löwenheim's notation, using the symbol 
as the universal quantifier and as the existential one. The simplest case of an equivalence between a formula of form (1) and the formula (2), namely
 | (4) |
 | (5) |
But instead of (5), Löwenheim writes 5
 | (6) |
and takes i k A ik to be satisfiable in a particular domain if and only if the universal formula i A ik i is. As the comparison of (4) and (5) suggests, the terms i and k (they are called indices) are individual variables. The terms of the form k i , the fleeing indices, are variables with a subscript which is also a variable. A ik and A ik i stand for formulas which we could more perspicuously render as A(i, k) and A(i,k i ).
As an explanation of the meaning of (6), Löwenheim says that in
 | (7) |
k i is to run through all elements of the domain of individuals (of the structure under consideration), and that ‘we have an n-fold sum if [the domain] possesses n elements (where n can also denote a transfinite cardinality)’. ‘In order to make this formula more intelligible’, Löwenheim supposes that the domain is the set of positive integers, and expands (7) as:
 | (8) |
which, apparently, stands for a string of infinitely many existential quantifiers before a matrix consisting of an infinite conjunction (represented by mere juxtaposition). 6
Some commentators (in particular Jean van Heijenoort and Gregory Moore) have inferred from Löwenheim's explanation that (7) is not really a definite formula, but rather a blueprint for building different formulas for different domains. The formula corresponding to a particular domain—the expansion of (7) for that domain—will have one existential quantifier for each element of the domain; thus it will be an infinite formula if the domain is infinite. According to these authors, (7) is meant to be replaced by its expansion when interpreted in a domain, which implies that Löwenheim's proof involves dealing with infinite formulas.
Badesa argues that this way of reading Löwenheim's words is not forced by the text, and that it is actually wrong. He maintains that Löwenheim viewed (7) as a single formula, and that the expansions do not have a place in Löwenheim's proof. As Badesa emphasizes, nowhere in the proof itself do we find a replacement of a formula by its expansion. Moreover, when Löwenheim is about to write (8) as an explanation of (7), he asserts that in so doing he is contravening his own stipulations on the use of symbols. As Badesa points out, the contravention in question has nothing to do, as (8) might suggest, with the infinity of the domain. Löwenheim is not saying that these expansions are unlawful because they yield infinite formulas when the domain is infinite. The stipulations are infringed even when the domain, and thus the expansion, is finite. Badesa discusses which stipulations are being violated, and how they are, when expanding a formula in a domain (the violations have to do with the different uses of and , on the one hand, and of + and ·, on the other), and he concludes that the reason why the expansions are introduced is simply to convey the semantics of (7). Löwenheim had no means of explaining what (7) meant in a rigorous way, but the expansion (8), although not a formula and thus unacceptable in a proof, is hopefully clear enough to suggest the meaning of (7). According to Badesa, what Löwenheim intended to express with his unofficial use of expansions is that 
is true in a given structure with domain D if and only if there is an indexed family 
k a : a 
D
of elements of D such that for all a D, the formula A is satisfied in that structure by a and k a .
|
3 |
|---|
|
Top123456References |
|---|
There is a clear similarity between equations (5) and (6), and thus between Skolem functions and fleeing indices. Indeed, it is not unusual to explain fleeing indices by likening them to Skolem functions, as I have in fact done, following van Heijenoort and Wang. Nevertheless, the fact that we can view fleeing indices as forerunners of Skolem functions does not mean that Löwenheim or Schröder viewed them thus. Actually, as Warren Goldfarb argued and Badesa sustains, ‘these authors did not connect quantification over double subscripts with (second-order) quantification over functions’ (p. 95).
Suppose that 
is a structure with domain D in which the formula 
x 
y Rxy holds (thus interprets R as R *). We may highlight the difference between the use of Skolem functions and that of Löwenheim's fleeing indices by sketching how Skolem and Löwenheim would produce a countable substructure of satisfying x y Rxy. In both cases, we begin by eliminating the existential quantifier and finding a universal formula which is satisfiable in any given domain if and only if x y Rxy is. This formula contains a new function symbol in one case, and a fleeing index in the other. In Skolem's case, the universal formula is x Rxg(x), in Löwenheim's x Rxy x .
One noticeable difference between these two formulas is that x Rxg(x) is a sentence, whereas x Rxy x is an open formula. Even if x Rxg(x) is not true in (because has no interpretation for g), it is true in any expansion of by an operation g *: D 
D such that every a D stands in the relation R * to g *(a). From any such expansion (which can be shown to exist with the help of the axiom of choice) it is easy to produce a countable substructure of which is a model of the original formula x y Rxy. It suffices to pick any a D and close the singleton {a} under g *.
The situation for x Rxy x is somewhat different. Like x Rxg(x), x Rxy x is not true in , but now not because we have to expand in order to evaluate it, but simply because open formulas are neither true nor false in a structure. To evaluate x Rxy x in we have to provide an assignment of members of D to the free variables generated from y x when x ranges over D—that is, to all the variables y a , for a D. Such an assignment is a map a 
a of D into D. The formula x Rxy x is then true in under this assignment if and only if every a D stands in the relation R * to a . 7
Admittedly, there seems to be not much of a difference between the two situations, as they can be taken to be merely different descriptions of the same phenomenon. Indeed, each interpretation g * of the function symbol g corresponds to an assignment a a (letting g *(a) = a ). However, the difference remains that the interpretation of g is given by the structure in which x Rxg(x) is evaluated (which is not , but D, R *, g *), whereas the assignment map is not fixed by , which is the structure in which x Rxy x is evaluated. If we think of the map a a as the very function g * given in a somewhat peculiar way, then we can proceed as we did for x Rxg(x): we pick a member a D and form the set {a 0, a 1, a 2, ...}, where a 0 = a and, for each n, a n+1 = a n . However, Löwenheim did not argue like this. Even though he assumed that the formula x Rxy x was satisfied in , he followed a deviant course in which he seemed to ignore the values that the requisite assignment ascribed to the y a .
As Badesa argues, one reason for Löwenheim's surprising detour (it is certainly surprising if we understand the machinery of fleeing indices as a clumsy form of Skolem functions) is that he did not seem to think of the assumption that the formula x Rxy x is satisfied in a structure with domain D as entitling him to a definite assignment of elements of D to the fleeing indices, but only as guaranteeing that there is one. It is as if Löwenheim read x Rxy x as: ‘for each object x there is some object y x such that Rx y x ’, as one often finds in mathematical texts—using y x simply to get rid of the existential quantifier, but refraining from any commitment that thereby a choice function has been summoned.
In The Birth of Model Theory, the use of fleeing indices by Löwenheim is carefully scrutinized. As we saw, Löwenheim, introduced them in equations of the form (6), whose meaning he explained with the help of expansions. This original use of fleeing indices is rather well-understood. Given a domain D, the variable k i generates the class {k a : a D} of terms, or, equivocally, of elements of D. And a formula i A i k i holds in a given structure with domain D if and only if for each a D, A holds of a and k a . Here a conflation of syntax and semantics occurs, namely the conflation of the generated indices k a with the elements they denote (as well as the conflation of each object a D with a constant canonically denoting it). This identification has no harmful effects in this context, since the discussion takes place under an implicit structure (of which only the domain is mentioned) and an implicit assignment to the generated indices.
In contrast to this basic use, in the construction of the submodel Löwenheim uses the fleeing indices in a different way, in which the lack of a distinction between semantics and syntax can be troublesome. As in the above situation, he deals with a formula of form i A ik i , but now instead of letting i range over a given domain D—thus giving rise to the terms k a for a D, and the corresponding formulas A a k a —he comes to consider terms of form k n (and formulas A n k n ), where n is a positive integer which is not a member of the domain, but only stands for one. Actually, and against the original use, he allows for the possibility that two different integers stand for the same object. In this new situation, a question arises that could not arise before, namely whether fleeing indices generate functional terms; that is to say, whether, for distint integers n and m, the two distinct terms k n and k m must have the same denotation whenever n and m stand for the same object. Unfortunately, Löwenheim did not address this question openly, but Badesa examines with meticulous detail how he dealt with this new use of fleeing indices and finds some evidence that, in this particular situation at least, Löwenheim did not view them as functional terms: it is not excluded that k n and k m stand for different objects, even though n and m have the same denotation. The evidence for this, although quite strong, is not fully conclusive, but it is worth pointing out that, if Badesa is right, the distance between fleeing indices and Skolem functions is actually very large.
|
4 |
|---|
|
Top123456References |
|---|
So far I have presented what I take to be the main points where Badesa's interpretation differs from that of modern commentators, namely that Löwenheim aimed to prove the submodel version of the theorem, that no infinite formulas occur in the proof at all, and that fleeing indices do not behave as Skolem functions. I have dwelt on fleeing indices because they are an important tool in Löwenheim's proof, and also because it is likely that the obscurities concerning them are a major obstacle to understanding Löwenheim's argument. Another obstacle is the lack of a clear distinction between syntax and semantics that pervades Löwenheim's reasoning.
Löwenheim's paper is embedded in the algebraic tradition of logic, as opposed to the line of logical research developed by Frege and Russell. It originated in Boole and came to fruition with Peirce and Schröder. It is precisely in Schröder's theory of relatives that Löwenheim's results are obtained. As van Heijenoort points out, the mere inquiring about the validity of a formula in diverse domains was ‘entirely alien to the Frege-Russell trend in logic’ ([1967b], p. 328). The main reason for this is that these authors had a universal view of logic, according to which the individual variables of the system they worked in are meant to range over absolutely all objects, and that ‘nothing can be, or has to be, said outside the system’ ([1967b], p. 326). This contrasts with the practice of the logicians in the algebraic tradition, who were concerned with restricted universes of discourse.
When we think that Löwenheim's Theorem is the first result ever proved about the relationship between a formal language and its models, a number of basic questions come to mind. Was Löwenheim's concern about models prompted by his working in the theory of relatives? How is it that, if Löwenheim did not have a clear distinction between syntax and semantics, he could state and prove a significant theorem about the existence of models of a first-order formula? Again, the restriction to a first-order language is essential for the validity of Löwenheim's theorem. So, the question naturally arises whether the interest in first-order languages was already present in the algebraic tradition, in particular in Schröder, or, on the contrary, it originated with Löwenheim. These are questions that a book like this should tackle, and Badesa certainly addresses them.
In order to deal with these questions we should go into the theory of relatives. So far, I have avoided getting into details because (except for fleeing indices) the formal language considered by Löwenheim{} could be understood as a mere variant of today's first-order languages. But if we want to see whether Löwenheim's contributions were inspired by the tradition he was part of, and to what extent his approach was original, we have to be a little more explicit.
The theory of relatives deals with a non-empty domain of individuals, the universe of discourse U, and the binary relations, or relatives, on it. Four particular relations, or modules, are distinguished, namely 1, 0, 1', and 0', which are the universal relation, the null relation, the identity relation, and the diversity relation (i.e., the relation in which every two distinct individuals stand). Besides the symbols for these four relations, the language of the theory has one identity symbol (=), variables for the individuals (the indices) and for the relatives, and the symbols and for unions and intersections ranging over all individuals, or over all relatives, depending on the variable bound by them. Moreover, the language has symbols for various operations on relations, in particular for the complement (
) and the converse (
) of a relation a, and for the intersection (a · b), the union (a + b), the relative product (a; b) and the relative sum (a 
b), of any two relations a and b. 8
As described, the symbols have a purely algebraic meaning. But, as we have seen when dealing with Löwenheim's theorem, the language of the theory (or part of it, at least) admits of a propositional reading, in which the symbols –, +, and · stand for negation, disjunction, and conjunction, and and are the existential and universal quantifiers. In this reading, the so-called relative coefficients, which are the expressions of form a ij , where a is a relative symbol and i and j are indices, play the role of atomic formulas. In the propositional interpretation, a ij can be read, roughly, as ‘the individual i stands in the relation a to the individual j’.
This sketchy description of the language of the theory of relatives will suffice for our purposes. First we deal with the question about the place of first-order logic in this language and Löwenheim's contribution to delimiting it. Löwenheim defines a first-order expression as one obtained from relative coefficients (though allowing relatives of any number of places, i.e., not necessarily binary), by successive applications of negation, conjunction, disjunction, and quantification over individuals. We refer to first-order expressions as first-order formulas, although, strictly speaking, the genuine formulas of the language are equations. Instead of asserting that a first-order expression F is true (is false) in a given structure, Löwenheim would say that the equation F = 1 (F = 0) holds in it. In this context, 0 and 1 do not stand for the null and the universal relation, respectively. They are propositional constants which we may view as denoting truth values. 9
Löwenheim's first-order formulas are the expressions of the language of the theory of relatives in which neither quantification over relatives nor use of the symbols for the relative operations of conversion (
), relative sum () and product (;) are allowed. This second restriction is inessential, since these operations are obviously first-order definable. So the important point is the ban on the quantification over relatives. Was Löwenheim the first author to single out the first-order part of the language for special study, or was he following the lead of previous scholars, of Schröder in particular?
Badesa argues that Schröder showed no interest at all in first-order logic or in metalogical issues. Nor did he, because he was after a higher goal. He wanted to show that all mathematical objects could be taken to be relatives, and all mathematics could be reformulated fully in terms of relatives, with no mention of individuals at all. He claimed that every formula of the theory of relatives involving individuals could be condensed, that is, proven to be equivalent to an equation in which only binary relations and operations among them, but neither unary predicates nor indices, occurred. Thus, by insisting on the elimination of indices, not only did Schröder fail to concentrate on first-order logic, but he wanted to do without the first-order fragment of his theory, so to speak. To avoid unary predicates, he simulated classes by means of binary relations. He defined a class, or a system, to be a relation a satisfying the identity a = a; 1. This means that a class of individuals x is simulated by the relation x × U, where U is the domain of individuals. To get rid of individuals, Schröder interpreted them as binary relations of a certain kind. He identified the individuals with those systems a satisfying the equation 0'; a = . By performing the operations, one sees that individual systems are precisely the relations of form {i} × U, for some individual i U. An appealing sketch of how to recast arithmetic and the most basic aspects of set theory in the theory of relatives can be found in Schröder's [1898] programmatic paper ‘On pasigraphy’. There Schröder presents the theory of relatives as the embodiment of Leibniz's calculus ratiocinator and lingua characteristica, and he claims that ‘almost everything may be viewed as, or considered under the aspect of, a (dual or) binary relative, and can be represented as such. Even statements submit to be looked at and treated as binary relatives’ ([1898], p. 53). 10 Indeed, in the paper, not a single individual or class (in the strict, not in the relative version) occurs.
Neither did Löwenheim inherit his interest in first-order logic from Schröder, nor has any evidence been provided that he acquired it from some other author. This notwithstanding, Badesa shies away from asserting that Löwenheim was the first author to single out first-order logic for investigation. The reason he adduces for his caution is that not enough is known about the evolution of the algebraic tradition to preclude that other logicians, especially Korselt, had anticipated Löwenheim in this.
Once first-order logic was isolated, asking for the existence of models came very naturally in the context of the algebraic tradition. A common task in an algebraic context is inquiring about the solutions of an equation in a given domain, a solution being, in the simplest case, an assignment of objects of the domain to the unknowns under which the equation holds. Models of a first-order formula can be likened to solutions. When Löwenheim evaluates a formula in a structure with domain D, he reasons as if the language had been enlarged so as to have one specific individual constant for each element of D as its canonical name. (He speaks of elements, not of constants, since he makes no distinction between an element of D and the constant denoting it.) In this setting, a solution of a formula F in a given domain D consists in the assignment of a truth value (0 or 1) to each relative coefficient a ij , where now i and j are canonical names of elements of the domain, under which the formula is true—i.e., under which the equation F = 1 holds. A solution, then, amounts to an interpretation of the relative symbols which satisfies the formula, thus to a model of the formula. Of course, Löwenheim does not speak of models. In fact, he does not use ‘solution’ or any other word for them, but his meaning is clear. In order to express that a sentence F has a model with domain D, he simply says that the equation F = 1 is satisfied in D for some values of the relative coefficients.
It is worth remarking that, by viewing models as solutions of equations in this way, semantical questions can be posed and answered—even when lacking, as Löwenheim patently did, a clear distinction between syntax and semantics.
|
5 |
|---|
|
Top123456References |
|---|
In his description of Schröder's calculus of classes, Badesa briefly discusses Schröder's distinction between consistent and inconsistent manifolds (pp. 19–20). Although this is an issue which has no bearing upon Löwenheim's work, I will comment on it in order to clarify its relation to Cantor's homonymous opposition between consistent and inconsistent multiplicities, since they have sometimes been likened. Thus, according to van Heijenoort, Cantor's ‘distinction between consistent and inconsistent multiplicities had already been introduced by Schröder ([1890]
, p. 213), a multiplicity being consistent if its elements are compatible (‘verträglich’) with each other, and inconsistent if they are not'. And he adds: ‘It is remarkable that Schröder introduced this distinction independently of the paradoxes, still unknown then in their modern form’ (van Heijenoort [1967a], p. 113). No such identification between Schröder's and Cantor's dichotomy is to be found in The Birth of Model Theory, and happily so, because, even if both Cantor's and Schröder's explanations of what they meant by ‘consistent’ are not completely clear, they are sufficient to conclude that they have incompatible properties and thus that they are different. In 1899, Cantor told Dedekind that
a multiplicity can be such that the assumption that all of its elements ‘are together’ leads to a contradiction, so that it is impossible to conceive of the multiplicity as a unity, as ‘one finished thing’. Such multiplicities I call absolutely infinite or inconsistent multiplicities.
If on the other hand the totality of the elements of a multiplicity can be thought of without contradiction as ‘being together’, so that they can be gathered into ‘one thing’, I call it a consistent multiplicity or a ‘set’. (van Heijenoort [1967a]
This has an outer resemblance to Schröder's requirement that ‘the elements of a manifold be all mutually compatible, so that we are able to conceive the manifold as a whole’ (Schröder [1890], p. 212). This requirement is Postulate ((1+)), which a manifold must fulfill in order that Schröder's calculus be applicable to its subsets. Schröder's words are even more similar to Cantor's 1895 definition of a set (in Beiträge zur Begründung der transfiniten Mengenlehre) as a collection into a whole of definite objects. This outer similarity notwithstanding, Schröder's idea of consistency is quite different from Cantor's, as can be seen from the following considerations.
First, according to Schröder [1890], for the elements of a manifold to be compatible, they must be ‘simultaneously thinkable, no two of them must exclude each other in the sense that to think of both of them would involve a contradiction’ (pp. 342–343). This implies that, for Schröder, if there are any inconsistent manifolds at all, then some two-element manifold is already inconsistent. But for Cantor all finite multiplicities are consistent.
Moreover, Schröder's notion of incompatibility applies only to objects like propositions, which can be true or false, affirmed or denied. In Schröder's words:
There are manifolds which do not satisfy Postulate ((1+)), and these are found exclusively in intellectual [geistige] fields, in the realm of theories, opinions and assertions. There are opinions and assertions, as well as requirements or conditions, which are mutually incompatible. For example, the two propositions: ‘the function f(x,y) is symmetric’ and ‘the (same) function f(x, y) is not symmetric' cannot be assembled into a [consistent] manifold,the reason for this impossibility being that one cannot consistently entertain both at the same time:
Since these two propositions—each one assumed as satisfied or fulfilled, put forward as plausible—involve a contradiction, since they, in other words, turn out to be mutually ‘incompatible’, the human mind is unable to unite them. We can accept as valid only one or the other of these two propositions. (Schröder [1890]
There is no doubt that, as Badesa suggests, Schröder is confused here. 11 In any event, Schröder's considerations are completely alien to Cantor, because for Cantor neither the nature of its elements nor their mutual relationship have anything to do with a multiplicity's being inconsistent or a set. Actually, no explication of the distinction which, like Schröder's, makes the consistency of a multiplicity depend on some compatibility relation among their members will be faithful to Cantor's. After stating his distinction, Cantor told Dedekind that two equivalent multiplicities are either both sets or are both inconsistent. Since two multiplicities are equivalent if there is a one-to-one correspondence between them, being a set or being inconsistent cannot depend on how the members of a multiplicity are mutually related. It cannot because mere one-to-one correspondences do not have to preserve any particular relation save identity.
|
6 |
|---|
|
Top123456References |
|---|
Untangling and clarifying Löwenheim's argument is not a linear process. Guesses have to be made at different junctures which can only be tested later on, when one is in a position to gauge their effects and how they fit together. As we saw, not even such a basic question as what theorem did Löwenheim actually set out to prove has an obvious answer. Moreover, despite the brevity of Löwenheim's text, its proper understanding presupposes a substantial amount of often unfamiliar, and occasionally not fully developed, material. Because of this, the proper organization of a book dealing with Löwenheim's proof is fundamental for its success. In this respect, as well as in clarity and effectiveness of exposition, The Birth of Model Theory is excellent. The attentive reader always knows what particular issue is being discussed and what the point of the discussion is—although one may have to wait until later to see how it fits in the proof. The book is self-contained (at least as regards the algebraic view of logic), but it demands sustained attention on the reader's part.
The Birth of Model Theory not only offers a sound and compelling interpretation of Löwenheim's paper, but, as already pointed out, one that corrects in several crucial points the current scholarship, in particular, regarding the theorem that Löwenheim actually proved, the use of infinite formulas in the proof, and the relation of fleeing indices to Skolem functions.
The book proper ends with chapter six, in which Badesa submits Löwenheim's construction of a countable model to detailed analysis, and shows conclusively that Löwenheim proved the submodel version of the theorem and that infinite formulas have no place in the proof. After that, we find an appendix where a first-order language with fleeing indexes is presented in which a correct proof very close to Löwenheim's is carried out. Its main purpose seems to be to convince the reader that reasoning with fleeing indices can be made sufficiently rigorous to uphold Löwenheim's reasoning.
Footnotes play an important role throughout the book, and the reader should be grateful to Princeton University Press for having printed them as footnotes, and not, as one too often finds, as endnotes. As to errata, most of the ones I found, even inside a formula, are self-correcting. I report only two: In the third displayed formula in page 54, there should be a complement sign over the product (a· 0'). In the second line of page 201, the comma after ‘domain’ should be a period, and the period before ‘Löwenheim’ should be a comma.
|
Footnotes |
|---|
1 Translated into English as ‘On possibilities in the calculus of relatives’ in van Heijenoort [1967a], pp. 228–251.
2 This is obvious in Skolem's generalization of the theorem to countably many sentences, since any infinite set A is a model of the set consisting, for each positive integer n, of a sentence asserting that there are at least n objects. But it is also true if we allow only a single sentence as in Löwenheim's case.
3 Page numbers in parentheses refer to The Birth of Model Theory.
4 It may be worth remarking that Jacques Herbrand found Löwenheim's proof not rigorous enough for metamathematics, although he thought it was ‘sufficient in mathematics’ (pp. 146–147).
5 Actually, in place of , Löwenheim uses a double sigma. Moreover, instead of 
he writes 
, although later on he simplifies the notation as we have done.
6 By adapting Löwenheim's notation to the present-day one, we could write (8) as
 |
7 Löwenheim does not distinguish between the term (the variable) y a and the object a assigned to it, which must mean that he takes the assignment to be implicitly given with the term.
8 In set theoretical notation, where U is the universe of discourse, = (U × U)–a, = {i, j : j, i a}, a · b = a 
b, a + b = a 
b, a; b = {i, j: k U (i, k a 
k, j b)}, and a b = { i, j : k U( i, k a 
k, j b)}.
9 We described the operations for building first-order expressions as negation, conjunction, disjunction, and quantification because we thought of those expressions as formulas. If we choose to see them as terms in an equation, it would be more appropriate to refer to them by their algebraic counterparts. In the algebraic tradition, the logical and the strictly algebraic reading of the symbols were conflated.
10 For i an individual, let us denote, {i} × U by i (so that i is the relation representing the individual i). Schröder codifies the statement that the individuals i and j stand in the relation a, with the relative term 
; a; j . ([1898], p. 54, formula 16). Notice that ; a; j is the relation {i, j}, if i is related to j by a, and that it equals the empty relation 0 otherwise.
11 Schröder is also confused in his requirement that a manifold be pure (as opposed to mixed) in order to be admissible as a universe of discourse—where a manifold is pure in case no element of it is a class one of whose members is also an element of the manifold (Schröder [1890], p. 248). He excluded mixed manifolds because he thought that a contradiction ensued from applying the algebraic rules to them, but the specious argument he offered for this ([1890], p. 245) was guilty of a confusion between membership and inclusion (p. 19).
|
REFERENCES |
|---|
|
Top123456References |
|---|
Schröder, E. [1890]: Vorlesungen über die Algebra der Logik I. Leipzig: Teubner.
Schröder, E. [1898]: ‘On pasigraphy’, The Monist, 9, pp. 246–262.
Skolem, Th. [1941]: ‘Sur la portée du théorème de Löwenheim-Skolem’, In Fenstad, Jens Erik (Ed.). Selected works in Logic. Oslo: Universitetsforlagert, 1970 pp. 455–482.
(Ed.). From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931. [1967a]: Cambridge, Mass.: Harvard University Press.
‘Logic as calculus and logic as language’, Synthese, [1967b]: 17, pp. 324–330.
CiteULike 
Connotea 
Del.icio.us What's this?
| ||||||||||||||||||||||||||||||||||||||||||||||||