The Birth of Model Theory: Löwenheim's Theorem in the Frame of the Theory of Relatives
256
The Birth of Model Theory: Löwenheim's Theorem in the Frame of the Theory of Relatives
256eBookCourse Book (Course Book)
Available on Compatible NOOK devices, the free NOOK App and in My Digital Library.
Related collections and offers
Overview
Löwenheim's theorem reflects a critical point in the history of mathematical logic, for it marks the birth of model theory--that is, the part of logic that concerns the relationship between formal theories and their models. However, while the original proofs of other, comparably significant theorems are well understood, this is not the case with Löwenheim's theorem. For example, the very result that scholars attribute to Löwenheim today is not the one that Skolem--a logician raised in the algebraic tradition, like Löwenheim--appears to have attributed to him. In The Birth of Model Theory, Calixto Badesa provides both the first sustained, book-length analysis of Löwenheim's proof and a detailed description of the theoretical framework--and, in particular, of the algebraic tradition--that made the theorem possible.
Badesa's three main conclusions amount to a completely new interpretation of the proof, one that sharply contradicts the core of modern scholarship on the topic. First, Löwenheim did not use an infinitary language to prove his theorem; second, the functional interpretation of Löwenheim's normal form is anachronistic, and inappropriate for reconstructing the proof; and third, Löwenheim did not aim to prove the theorem's weakest version but the stronger version Skolem attributed to him. This book will be of considerable interest to historians of logic, logicians, philosophers of logic, and philosophers of mathematics.
Product Details
| ISBN-13: | 9781400826186 |
|---|---|
| Publisher: | Princeton University Press |
| Publication date: | 01/10/2009 |
| Sold by: | Barnes & Noble |
| Format: | eBook |
| Pages: | 256 |
| File size: | 4 MB |
About the Author
Read an Excerpt
The Birth of Model Theory
Löwenheim's Theorem in the Frame of the Theory of RelativesBy Calixto Badesa
Princeton University Press
Copyright © 2004 Princeton University PressAll right reserved.
ISBN: 978-0-691-05853-5
Chapter One
Algebra of Classes and Propositional Calculus
1.1 BOOLE
1.1.1 George Boole (1815-1864) is justly considered the founder of mathematical logic in the sense that he was the first to develop logic using mathematical techniques. Leibniz (1646-1716) had been aware of this possibility, and De Morgan (1806-1878) worked in the same direction, but Boole was the first to present logic as a mathematical theory, which he developed following the algebraic model. His most important contributions are found in The mathematical analysis of logic [1847], his first work on logic, and An investigation of the laws of thought [1854], which contains the fullest presentation of his ideas on the subject. In what follows I will focus solely on the latter work, to which I will refer as Laws.
Boole's aim is to examine the fundamental laws (i.e., the most basic truths from which all the other laws are deduced) of the mental processes that underlie reasoning. Boole does not challenge the validity of the basic laws of traditional logic, but he is convinced that they are reducible to other more basic laws of a mathematical nature; it is these basic laws that hesets out to find.
In Boole's opinion, the mental processes that underlie reasoning are made manifest in the way in which we use signs. Algebra and natural language are systems of signs, and so the study of the laws that the signs of these systems meet should allow us to arrive at the laws of reasoning. The question of whether or not two different systems of signs obey the same laws can only be answered a posteriori. Applied to natural language-the commonest system of signs-Boole's idea implies that the laws by means of which certain terms combine to form statements or other more complex terms are the same as those observed by the mental processes that these combinations reveal. Thus, Boole believes that it is possible to establish a theory of reasoning by examining the laws by means of which the terms and statements of language are combined.
Boole classifies the propositions of interest to logic into primary and secondary (Laws, pp. 53 and 160). Primary propositions are the ones that express a relation between things. Secondary propositions express relations between propositions, or judgments on the truth or falsity of a proposition. For example, "men are mortal" is a primary proposition (because it expresses a relation between men and mortal beings), but "it is true that men are mortal" is secondary. Propositions that result from combining propositions with the aid of connectives are also secondary. Boole begins his study of the laws of reasoning with the analysis of primary propositions and of the reasonings in which they alone intervene.
1.1.2 According to Boole (Laws, p. 27), in order to formulate the laws of reasoning, the following signs or symbols are sufficient:
(a) literal signs: x, y, z, ...;
(b) signs of operations of the mind: x, +; and -;
(c) the sign of identity: =.
This claim, however, does not have the meaning it would have today. As we will see, Boole uses other signs and operations as well to present and develop his theory.
A literal symbol represents "the class of individuals to which a particular name or description is applicable." Strictly speaking, literal signs stand for classes, but Boole frequently speaks (the definition of product that I will quote later on is an example of this) as if they denoted expressions of the natural language that determine classes (nouns, adjectives, descriptions or even proper names). The reason for this ambiguity is that both literal signs and expressions determining classes are signs of the same conceptions of the mind. For example, the use of the word "tree" indicates that we have performed a mental operation that consists of selecting a class (the class of all trees) that we represent by that word. Now, since the same class can also be represented by a literal sign, Boole sees no substantial difference between saying that x stands for the class of trees and saying that it stands for the word "tree."
Boole defines the product in the following way: "by the combination xy shall be represented that class of things to which the names or descriptions represented by x and y are simultaneously applicable." For example, if x stands for "white" and y for "horse," xy stands for "white horse" or for the class of white horses.
If x and y represent classes that do not have elements in common, x + y represents the class resulting from adding the elements of x to those of y (Laws, pp. 32-33). The sum corresponds to the mental operation of aggregating two disjoint classes into a whole. This operation is performed when we combine two terms by means of "and" as in "men and women," or by "or" as in "rational or irrational." Boole argues for the restriction of the sum to disjoint classes by stating that the rigorous use of these particles presupposes that the terms are mutually exclusive, but, as Jevons observed, Boole himself on occasion analyzes examples with disjunctions whose terms do not exclude each other.
It has been said on occasion that Boole interprets the sum x + y as an excluding disjunction, but, as Corcoran notes, this assertion is incorrect. It is important to distinguish between the definition of sum that Boole adopts and the following one: x + y is the class of objects that belong either to x or to y (but not to x and to y). If Boole had adopted this definition (i.e., if he really had defined the sum as an excluding disjunction), then the sum x + y would be meaningful both if x and y have elements in common and if they do not. However, with Boole's definition, x + y lacks logical significance when x and y have elements in common. In short, Boole's sum is the usual union, but defined only for disjoint classes.
The difference is the inverse operation of the sum, and it consists of separating a part from a totality. Thus, Boole says, if class y is a part of class x, x - y is the class of things that are elements of x and not of y. This mental operation is the one that is expressed by the word "except" when it occurs in expressions such as, for example, "politicians except for conservatives."
The only sign that allows us to form statements is the sign of identity. The equality x = y means that the classes x and y have the same elements; this identification is expressed in language using the verb "to be."
Boole also introduces the symbols 0 and 1, which represent, respectively, the empty class and the class of all the things to which the discourse is limited. As is well known, the idea of limiting the universe to things that are talked about was introduced by De Morgan in [1846]. Boole adopted this idea in Laws, but did not mention its origin.
To be able to refer to a nondetermined part of a class, Boole introduces the symbol v which, he says, represents an indefinite class (Laws, p. 61). The linguistic term that corresponds to this symbol is "some." Now, the expression "some men" is symbolized by vx (where x represents the class of all men). Boole claims that v meets the same laws that the literal symbols meet, but in fact this is not so. Indeed, the interpretation of the symbol v presents numerous problems, whose analysis is beyond the scope of this introduction.
The restrictions on the sum and the difference place limits not on the use of the operation symbols, but on the logical interpretability of the expressions where the symbols occur. An expression is logically interpretable if all the sums and differences that occur in it meet their respective restrictions no matter what classes the literal symbols denote. Thus, both v and literal symbols are logically interpretable, but the sum x + y is not, because it only denotes a class when x and y are disjoint classes. The union of any two classes can be symbolized by the sum
x + (1 - x)y,
which is logically interpretable, since both the difference and the sum obey their respective restrictions whatever classes x and y denote.
Boole symbolizes the four basic types of categorical propositions as follows (Laws, p. 228):
every X is Y : x = vy, no X is Y : x = v(1 - y), some X is Y : vx = vy, some X is not Y : vx = v(1 - y).
These are the symbolizations he prefers, but he thinks that "every X is Y" can be symbolized in an equivalent way by x(1 - y) = 0 (and accordingly, "no X is Y" by xy = 0) (Laws, pp. 123 and 230).
When Boole comments on the symbolization of "every X is Y" he warns that in x = vy it should be supposed that v and y have elements in common, and when he comments on the symbolization of "some X is not Y" he notes that this can only be considered acceptable if we suppose that vx [not equal to] 0 (Laws, pp. 61 and 63). As we will see later, Boole does not always interpret the products of the form vx in this way, but it seems that at least in this context it is necessary to suppose that v is a nonempty set that has elements in common with the class x. Now, if this supposition holds, the two symbolizations of "every X is Y" cannot be equivalent, in spite of what Boole thinks, because if x = 0, then x(1 - y) = 0 is true and x = vy is false. The same can be said of two symbolizations of "no X is Y:" Boole accepts all the traditional laws of syllogism and, specifically, he accepts that the universal propositions imply the corresponding particular propositions, but these two implications can only be proved if the universal propositions are symbolized with the aid of the sign of indefinite class (Laws, p. 229).
1.1.3 Boole obtains the basic laws of his system by reflecting on the meaning of the signs. The following list of the main basic laws allows us to compare Boole's system with what today we know as Boolean algebra:
x + y = y + x, xy = yx, x + (y + z) = (x + y) + z, x(yz) = (xy)z, 0 + x = x, 1x = x, x + (1 - x) = 1, [x.sup.2] = x, z(x + y) = zx + xy.
As can be seen, 0+x is the only sum logically interpretable in these laws, but I have already pointed out that the restrictions of the sum and the difference only affect the logical interpretability of the expressions. The law [x.sup.2] = x is only applicable to logically meaningful terms; the remaining laws hold in general, that is, the literal symbols that occur in them can be replaced by any term, be it logically interpretable or not. In Boole's system the sum is not distributive over the product. Nor are
x + x = x, x + 1 = 1
laws of the system; indeed, neither of these sums is logically interpretable.
Boole attributes special importance to the law [x.sup.2] = x (that is, xx = x) because from it the principle of noncontradiction (x(1 - x) = 0) is deduced, but above all because he considers it to be characteristic of the operations of the mind, as it is the only one of the basic laws that does not hold in the algebra of numbers. Boole observes that from the arithmetical point of view the only roots of [x.sup.2] = x are 0 and 1; this fact is enough for him to conclude that the axioms and processes of the algebra of logic are the same as those of the arithmetic of numbers 0 and 1; and that it is only the interpretation that differentiates one from the other (Laws, p. 37). This identification ignores the existence of laws that hold in the arithmetic of numbers 0 and 1, but not in the algebra of logic.
The consequence that Boole extracts from the identification of the algebra of logic with the arithmetic of the numbers 0 and 1 can be read in the following quotation:
It has been seen, that any system of propositions may be expressed by equations involving symbols x, y, z, which, whenever interpretation is possible, are subject to laws identical in form with the laws of a system of quantitative symbols, susceptible only of the values 0 and 1 (II. 15). But as the formal processes of reasoning depend only upon the laws of symbols, and not upon the nature of their interpretation, we are permitted to treat the above symbols x, y, z, as if they were quantitative symbols of the kind above described. We may in fact lay aside the logical interpretation of the symbols in the given equation; convert them into quantitative symbols, susceptible only of the values 0 and 1; perform upon them as such all the requisite processes of solution; and finally restore to them their logical interpretation. (Laws, pp. 69-70; Boole's italics)
The conclusion that Boole reaches is, as we see, that logical problems can be solved by applying techniques of an algebraic nature. Since the result of symbolizing a set of statements is always a system of equations, the problem of extracting consequences from a set of premises (which is the type of logical problem that Boole considers) is merely an algebraic problem which consists essentially of solving a system of equations. When Boole says that we can lay aside the logical interpretation, he means not merely that we can ignore the restrictions on the sum and the difference, but also that we are allowed to use any algebraic procedure (including those that contain operations such as, for example, the quotient, that do not belong to logic). This is what Boole means by "all the requisite processes of solution."
The usual algebraic techniques lead, or can lead, to results that are impossible to interpret logically. To solve this difficulty, Boole introduced a highly complex algebraic procedure of reduction of systems of equations which supposedly makes it possible to obtain logically interpretable results. The transformations required to obtain these results only rarely have a logical interpretation; Boole sees nothing wrong in this. In his opinion, the essential issue in the resolution of a problem of a logical nature is that both the initial equations and the conclusion should be logically interpretable, but it is not necessary that either the intermediate expressions or the transformations required to obtain the result should be so (as, he says, in trigonometry, when [square root of (-1)] intervenes in a proof) (Laws, p. 69). Nor is Boole concerned that, on occasion, in order to interpret logically the results that he obtains using his technique it is necessary to interpret ad hoc quotients that are not even interpretable algebraically.
(Continues...)
Excerpted from The Birth of Model Theory by Calixto Badesa Copyright © 2004 by Princeton University Press. Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Table of Contents
Preface ixChapter 1. Algebra of Classes and Propositional Calculus 1
1.1 Boole 1
1.2 Jevons 10
1.3 Peirce 12
1.4 Schröder 17
Chapter 2. The Theory of Relatives 31
2.1 Introduction 31
2.2 Basic concepts of the theory of relatives 33
2.3 Basic postulates of the theory of relatives 40
2.4 Theory of relatives and model theory 51
2.5 First-order logic of relatives 66
Chapter 3. Changing the Order of Quantifiers 73
3.1 Schröder's proposal 73
3.2 Löwenheim's approach 81
3.3 The problem of expansions 87
3.4 Skolem functions 94
Chapter 4. The Löwenheim Normal Form 107
4.1 The Löwenheim normal form of an equation 107
4.2 Comments on Löwenheim's method 113
4.3 Conclusions 122
Chapter 5. Preliminaries to Löwenheim's Theorem 129
5.1 Indices and elements 129
5.2 Types of indices 132
5.3 Assignments 135
5.4 Types of equations 138
Chapter 6. Löwenheim's Theorem 143
6.1 The problem 143
6.2 An analysis of Löwenheim's proof 148
6.3 Reconstructing the proof 191
Appendix. First-Order Logic with Fleeing Indices 207
A.1 Introduction 207
A.2 Syntax 207
A.3 Semantics 211
A.4 The Löwenheim normal form 217
A.5 Löwenheim's theorem 220
References 227
Index 237
What People are Saying About This
The Birth of Model Theory represents a long overdue, in-depth analysis and exposition of one of the most important results in mathematical logic. There are hardly any informed, sustained treatments of Löwenheim's work to be found in the literature. This well-written book should fill this gap.
— Richard Zach, University of Calgary
A first-rate contribution to the history and philosophy of logic, this is scholarship at its best. It is, to my knowledge, the first book in the history of logic that focuses completely on a single result. Very original in approach and conception, it goes against the grain of much recent scholarship. Given the complexity of the subject, Badesa could not have done a better job of being clear and making the presentation accessible.
— Paolo Mancosu, University of California, Berkeley
"A first-rate contribution to the history and philosophy of logic, this is scholarship at its best. It is, to my knowledge, the first book in the history of logic that focuses completely on a single result. Very original in approach and conception, it goes against the grain of much recent scholarship. Given the complexity of the subject, Badesa could not have done a better job of being clear and making the presentation accessible."—Paolo Mancosu, University of California, Berkeley"The Birth of Model Theory represents a long overdue, in-depth analysis and exposition of one of the most important results in mathematical logic. There are hardly any informed, sustained treatments of Löwenheim's work to be found in the literature. This well-written book should fill this gap."—Richard Zach, University of Calgary"This book will be extremely useful to those seeking to make sense of Löwenheim's work and those seeking to put it into its historical context. Calixto Badesa draws well-supported conclusions that contradict the entire modern body of scholarship on the topic."—Shaughan Lavine, University of Arizona
This book will be extremely useful to those seeking to make sense of Löwenheim's work and those seeking to put it into its historical context. Calixto Badesa draws well-supported conclusions that contradict the entire modern body of scholarship on the topic.
— Shaughan Lavine, University of Arizona
Recipe
"A first-rate contribution to the history and philosophy of logic, this is scholarship at its best. It is, to my knowledge, the first book in the history of logic that focuses completely on a single result. Very original in approach and conception, it goes against the grain of much recent scholarship. Given the complexity of the subject, Badesa could not have done a better job of being clear and making the presentation accessible."—Paolo Mancosu, University of California, Berkeley
"The Birth of Model Theory represents a long overdue, in-depth analysis and exposition of one of the most important results in mathematical logic. There are hardly any informed, sustained treatments of Löwenheim's work to be found in the literature. This well-written book should fill this gap."—Richard Zach, University of Calgary
"This book will be extremely useful to those seeking to make sense of Löwenheim's work and those seeking to put it into its historical context. Calixto Badesa draws well-supported conclusions that contradict the entire modern body of scholarship on the topic."—Shaughan Lavine, University of Arizona