Model Theory: Third Edition

by C.C. Chang, H. Jerome Keisler

Overview

Model theory deals with a branch of mathematical logic showing connections between a formal language and its interpretations or models. This is the first and most successful textbook in logical model theory. Extensively updated and corrected in 1990 to accommodate developments in model theoretic methods — including classification theory and nonstandard analysis — the third edition added entirely new sections, exercises, and references.
Each chapter introduces an individual method and discusses specific applications. Basic methods of constructing models include constants, elementary chains, Skolem functions, indiscernibles, ultraproducts, and special models. The final chapters present more advanced topics that feature a combination of several methods. This classic treatment covers most aspects of first-order model theory and many of its applications to algebra and set theory.

Product Details

ISBN-13:	9780486310954
Publisher:	Dover Publications
Publication date:	10/03/2013
Series:	Dover Books on Mathematics
Sold by:	Barnes & Noble
Format:	eBook
Pages:	672
File size:	44 MB
Note:	This product may take a few minutes to download.
Age Range:	18 Years

About the Author

H. Jerome Keisler was a longtime professor at the University of Wisconsin, Madison, whose research included model theory and nonstandard analysis. He is known for extending the Henkin construction to what are now called Henkin-Keisler models.
C. C. Chang, Professor Emeritus of Mathematics at UCLA, also focused on model theory and proved the ordinal partition theorem. Chang's conjecture is named after him, as is ccc forcing.

Read an Excerpt

Model Theory

---

By C. C. Chang, H. Jerome Keisler

Dover Publications, Inc.

Copyright © 2012 C. C. Chang and H. Jerome Keisler
All rights reserved.
ISBN: 978-0-486-31095-4

---

CHAPTER 1

INTRODUCTION

1.1 What is model theory?

Model theory is the branch of mathematical logic which deals with the relation between a formal language and its interpretations, or models. We shall concentrate on the model theory of first-order predicate logic, which may be called 'classical model theory'.

Let us now take a short introductory tour of model theory. We begin with the models which are structures of the kind which arise in mathematics. For example, the cyclic group of order 5, the field of rational numbers, and the partially-ordered structure consisting of all sets of integers ordered by inclusion, are models of the kind we consider. At this point we could, if we wish, study our models at once without bringing the formal language into the picture. We then would be in the area known as universal algebra, which deals with homomorphisms, substructures, free structures, direct products, and the like. The line between universal algebra and model theory is sometimes fuzzy; our own usage is explained by the equation

universal algebra+logic = model theory.

To arrive at model theory, we set up our formal language, the first-order logic with identity. We specify a list of symbols and then give precise rules by which sentences can be built up from the symbols. The reason for setting up a formal language is that we wish to use the sentences to say things about the models. This is accomplished by giving a basic truth definition, which specifies for each pair consisting of a sentence and a model one of the truth values true or false. The truth definition is the bridge connecting the formal language with its interpretation by means of models. If the truth value 'true' goes with the sentence φ and model U, we say that φ is true in U and also that U is a model of φ. Otherwise we say that φ is false in U and that U is not a model of φ. Moreover, we say that U is a model of a set Σ of sentences iff U is a model of each sentence in the set Σ.

What kinds of theorems are proved in model theory? We can already give a few examples. Perhaps the earliest theorem in model theory is Löwenheim's theorem (Löwenheim, 1915): If a sentence has an infinite model, then it has a countable model. Another classical result is the compactness theorem, due to Gödel (1930) and Malcev (1936): if each finite subset of a set Σ of sentences has a model, then the whole set Σ has a model. As a third example, we may state a more recent result, due to Morley (1965). Let us say that a set Σ of sentences is categorical in power α iff there is, up to isomorphism, exactly one model of Σ of power a. Morley's theorem states that, if Σ is categorical in one uncountable power, then Σ is categorical in every uncountable power.

These theorems are typical results of model theory. They say something negative about the 'power of expression' of first-order predicate logic. Thus Löwenheim's theorem shows that no consistent sentence can imply that a model is uncountable. Morley's theorem shows that first-order predicate logic cannot, as far as categoricity is concerned, tell the difference between one uncountable power and another. And the compactness theorem has been used to show that many interesting properties of models cannot be expressed by a set of first-order sentences – for instance, there is no set of sentences whose models are precisely all the finite models.

The three theorems we have stated also say something positive about the existence of models having certain properties. Indeed, in almost all of the deeper theorems in model theory the key to the proof is to construct the right kind of a model. For instance, look again at Löwenheim's theorem. To prove that theorem, we must begin with an uncountable model of a given sentence and construct from it a countable model of the sentence. Likewise, to prove the compactness theorem we must construct a single model in which each sentence of Σ is true. Even Morley's theorem depends vitally on the construction of a model. To prove it we begin with the assumption that Σ has two different models of one uncountable power and construct two different models of every other uncountable power.

There are a small number of extremely important ways in which models have been constructed. For example, for various purposes they can be constructed from individual constants, from functions, from Skolem terms, or from unions of chains. These constructions give the subject of model theory unity. To a large extent, we have organized this book according to these ways of constructing models.

Another point which gives model theory unity is the distinction between syntax and semantics. Syntax refers to the purely formal structure of the language – for instance, the length of a sentence and the collection of symbols occurring in a sentence, are syntactical properties. Semantics refers to the interpretation, or meaning, of the formal language – the truth or falsity of a sentence in a model is a semantical property. As we shall soon see, much of model theory deals with the interplay of syntactical and semantical ideas.

We now turn to a brief historical sketch. The mathematical world was forced to observe that a theory may have more than one model in the 19th century, when Bolyai and Lobachevsky developed non-Euclidean geometry, and Riemann constructed a model in which the parallel postulate was false but all the other axioms were true. Later in the 19th century, Frege formally developed the predicate logic, and Cantor developed the intuitive set theory in which our models live.

Model theory is a young subject. It was not clearly visible as a separate area of research in mathematics until the early 1950's. However, its historical roots go back to the older subjects of logic, universal algebra, and set theory – and some of the early work, such as Löwenheim's theorem, is now classified as model theory. Other important early developments which contributed to the theory are: the extension of Löwenheim's theorem by Skolem (1920) and Tarski; the completeness theorem of Gödel (1930) and its generalization by Malcev (1936); the characterization of definable sets of real numbers, the rigorous definition of the truth of a sentence in a model, and the study of relational systems by Tarski (1931, 1933, 1935a); the construction of a nonstandard model of number theory by Skolem (1934); and the study of equational classes initiated by Birkhoff (1935). Model theory owes a great deal to general methods which were originally developed for special purposes in older branches of mathematics. We shall come across many instances of this in our book; to mention just one, the important notion of a saturated model (Chapter 5) goes back to the ηα-structures in the theory of simple order, due to Hausdorff (1914). The subject grew rapidly after 1950, stimulated by the papers of Henkin (1949), Tarski (1950), and Robinson (1950). The phrase 'theory of models' is due to Tarski (1954). Today the literature in the subject is quite extensive. There is a rather complete bibliography in Addison, Henkin and Tarski (1965). In recent years, the theory of models has been applied to obtain significant results in other fields, notably set theory, algebra and analysis. However, until now only a tiny part of the potential strength of model theory has been used in such applications. It will be interesting to see what happens when (and if) the full strength is used.

1.2 Model theory for sentential logic

In our introduction, Section 1.1, we gave a general idea of the flavor of model theory, but we were not yet ready to give many details. We shall now come down to earth and give a rigorous treatment of model theory for a very simple formal language, sentential logic (also known as propositional calculus). We shall quickly develop this 'toy' model theory along lines parallel to the much deeper model theory for predicate logic. The basic ideas are the decision procedure via truth tables, due to Post (1921), and Lindenbaum's theorem with the compactness theorem which follows. This section will give a preview of what lies ahead in our book.

We are assuming (see Preface) that the reader is already thoroughly familiar with sentential, and even predicate, logic. Thus we shall feel free to proceed at a fairly rapid pace. Nevertheless, we shall start from scratch, in order to show what sentential logic looks like when it is developed in the spirit of model theory.

Classical sentential logic is designed to study a set L of simple statements, and the compound statements built up from them. At the most intuitive level, an intended interpretation of these statements is a 'possible world', in which each statement is either true or false. We wish to replace these intuitive interpretations by a collection of precise mathematical objects which we may use as our models. The first thing which comes to mind is a function F which associates with each simple statement S one of the truth values 'true' or 'false'. Stripping away the inessentials, we shall instead take a model to be a subset A of L; the idea is that S [member of] A indicates that the simple statement S is true, and S [not member of] A indicates that the simple statement S is false.

1.2.1. By a model A for L we simply mean a subset A of L.

Thus the set of all models has the power 2|L|. Several relations and operations between models come to mind; for example, A [subset] B, L - A, and the intersection [intersection]i [member of] I] Ai of a set {Ai: i [member of] I} of models. Two distinguished models are the empty set Ø and the set L itself.

We now set up the sentential logic as a formal language. The symbols of our language are as follows:

connectives [conjunction] (and), [logical not] (not);

parentheses ), (;

a nonempty set L of sentence symbols.

Intuitively, the sentence symbols stand for simple statements, and the connectives [conjunction], [logical not] stand for the words used to combine simple statements into compound statements. Formally, the sentences of L are defined as follows:

1.2.2.

(i). Every sentence symbol S is a sentence.

(ii). If φ is a sentence then ([logical not] ψ) is a sentence.

(iii). If φ, ψ are sentences, then (φ [conjunction] ψ) is a sentence.

(iv). A finite sequence of symbols is a sentence only if it can be shown to be a sentence by a finite number of applications of (i)-(iii).

Our definition of L sentence of may be restated as a recursive definition based on the length of a finite sequence of symbols:

A single symbol is a sentence iff it is a sentential symbol; a sequence φ of symbols of length n > 1 is a sentence iff there are sentences ψ and θ of length less than n such that φ is either ([logical not] ψ) or (ψ [conjunction] θ).

Alternatively, our definition may be restated in set-theoretical terms:

The set of all sentences of L is the least set Σ of finite sequences of symbols of L such that each sentence symbol S belongs to Σ and, whenever ψ, θ are in Σ, then ([logical not] ψ), (ψ [conjunction] θ) belong to Σ.

No matter how we may think of sentences, the important thing is that properties of sentences can only be established through an induction based on1.2.2. More precisely, to show that every sentence φ has a given property P, we must establish three things: (1) Every sentence symbol S has the property P; (2) if φ is ([logical not] ψ) and ψ has the property P, then ψ has the property P; (3) if φ is (ψ [conjunction] θ) and ψ, θ have the property P, then φ has the property P. (The reader may check his understanding of this point by proving through induction that every sentence φ has the same number of right parentheses as it has left parentheses.)

How many sentences of L are there? This depends on the number of sentence symbols S [member of] L. Each sentence is a finite sequence of symbols. If the set is finite or countable, then there are countably many sentences of L. Of course, not every finite sequence of symbols is a sentence; for instance, (S0 [conjunction] ([logical not] S5)) is a sentence, but [conjunction][conjunction]) S3 and S0 [conjunction] [logical not] S5 are not. If the set L of sentence symbols has uncountable cardinal α, then the set of sentences of L also has power α.

Let us pause briefly to explain the role of the Greek letters φ, ψ, Σ, etc. In the above paragraphs we have used the lower case Greek letters (φ, ψ, θ, ... as names for arbitrary finite sequences of symbols of L. These letters were needed in order to write down the definition of a sentence. From now on, we shall be much more interested in sentences than in arbitrary finite sequences of symbols. We shall hereafter use the lower case Greek letters φ, ψ, θ, ... as names for arbitrary sentences of L. The situation is similar to elementary arithmetic, where we study natural numbers 0, 1,2,3, ..., but much of the time we write down letters like m, n, x, y, ... as names for arbitrary natural numbers. Just as in arithmetic where we write things like m = x + y, we shall now write, for example, φ = (ψ [conjunction] θ) to express the fact that φ and (ψ [conjunction] θ) are the same sentence. In the above paragraphs we also used capital Greek letters Σ, Τ, ... as names for arbitrary sets of finite sequences of symbols of L; hereafter we shall use the capital Greek letters as names for arbitrary sets of sentences of L. The symbols (φ, ψ, θ ..., Σ, Τ, ... are not in our list of formal symbols of our language – they are merely informal symbols which we use to talk more easily about L.

We shall introduce abbreviations to our language in the usual way, in order to make sentences more readable. The symbols [disjunction] (or), -> (implies), and <-> (if and only if) are abbreviations defined as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Of course, [disjunction], -> and <-> could just as well have been included in our list of symbols as three more connectives. However, there are certain advantages to keeping our list of symbols short. For instance, 1.2.2 and proofs by induction based on it are shorter this way. At the other extreme, we could have managed with only a single connective, whose English translation is 'neither ... nor ...'. We did not do this because 'neither ... nor ...' is a rather unnatural connective.

Another abbreviation which we shall adopt is to leave out unnecessary parentheses. For instance, we shall never bother to write outer parentheses in a sentence – thus [logical not] S is our abbreviation for the sentence ([logical not] S). We shall follow the commonly accepted usage in dropping other parentheses. Thus is considered more binding than [conjunction] and v, which in turn are more binding than -> and <->. For instance, [logical not] φ [disjunction] ψ -> θ [conjunction] φ means (([logical not] φ) [disjunction] ψ) -> (θ [conjunction] φ).

Hereafter we shall use the single symbol L to denote both the set of sentence symbols and the language built on these symbols. There is no fear of confusion in this double usage since the language is determined uniquely, modulo the connectives, by the sentence symbols.

We are now ready to build a bridge between the language L and its models, with the definition of the truth of a sentence in a model. We shall express the fact that a sentence φ is true in a model A succinctly by the special notation

A [??] φ.

(Continues...)

---

Excerpted from Model Theory by C. C. Chang, H. Jerome Keisler. Copyright © 2012 C. C. Chang and H. Jerome Keisler. Excerpted by permission of Dover Publications, Inc..
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

Preface1. Introduction2. Models contructed from constants3. Further model-theoretic constructions4. Ultraproducts5. Saturated and special models6. More about ultraproducts and generalizations7. Selected topicsAppendix A. Set theoryAppendix B. Open problems in classical model theoryHistorical notesReferencesAdditional referencesIndex of definitionsIndex of symbols