Model Theory: an Introduction

David Marker

Springer Graduate Texts in Mathematics 217

Introduction

Model theory is a branch of mathematical logic where we study mathematical structures by considering the first-order sentences true in those structures and the sets definable by first-order formulas. Traditionally there have been two principal themes in the subject: A good example of the first theme is Tarski's work on the field of real numbers. Tarski showed that the theory of the real field is decidable. This is a sharp contrast to Godel's Incompleteness Theorem, which showed that the theory of the seemingly simpler ring of integers is undecidable. For his proof, Tarski developed the method of quantifier elimination which can be used to show that all subsets of R^n definable in the real field are geometrically well-behaved. More recently, Wilkie extended these ideas to prove that sets definable in the real exponential field are also well-behaved.

The second theme is illustrated by Morley's Categoricity Theorem, which says that if T is a theory in a countable language and there is an uncountable cardinal $\kappa$ such that, up to isomorphism, T has a unique model of cardinality $\kappa$, then T has a unique model of cardinality $\lambda$ for every uncountable $\kappa$. This line has been extended by Shelah, who has developed deep general classification results.

For some time, these two themes seemed like opposing directions in the subject, but over the last decade or so we have come to realize that there are fascinating connections between these two lines. Classical mathematical structures, such as groups and fields, arise in surprising ways when we study general classification problems, and ideas developed in abstract settings have surprising applications to concrete mathematical structures. The most striking example of this synthesis is Hrushovski's application of very general model-theoretic methods to prove the Mordell--Lang Conjecture for function fields.

My goal was to write an introductory text in model theory that, in addition to developing the basic material, illustrates the abstract and applied directions of the subject and the interaction of these two programs.

Chapter 1 begins with the basic definitions and examples of languages, structures, and theories. Most of this chapter is routine, but, because studying definability and interpretability is one of the main themes of the subject, I have included some nontrivial examples. Section 1.3 ends with a quick introduction to $\MM^{\rm eq}$. This is a rather technical idea that will not be needed until Chapter 6 and can be omitted on first reading.

The first results of the subject, the Compactness Theorem and the Lowenheim--Skolem Theorem, are introduced in Chapter 2. In Section 2.2 we show that even these basic results have interesting mathematical consequences by proving the decidability of the theory of the complex field. Section 2.4 discusses the back-and-forth method beginning with Cantor's analysis of countable dense linear orders and moving on to Ehrenfeucht--Fra\"{\i}ss\'e Games and Scott's result that countable structures are determined up to isomorphism by a single infinitary sentence.

Chapter 3 shows how the ideas from Chapter 2 can be used to develop a model-theoretic test for quantifier elimination. We then prove quantifier elimination for the fields of real and complex numbers and use these results to study definable sets.

Chapters 4 and 5 are devoted to the main model-building tools of classical model theory. We begin by introducing types and then study structures built by either realizing or omitting types. In particular, we study prime, saturated, and homogeneous models. In Section 4.3, we show that even these abstract constructions have algebraic applications by giving a new quantifier elimination criterion and applying it to differentially closed fields. The methods of Sections 4.2 and 4.3 are used to study countable models in Section 4.4, where we examine $\aleph_0$-categorical theories and prove Morley's result on the number of countable models. The first two sections of Chapter 5 are devoted to basic results on indiscernibles. We then illustrate the usefulness of indiscernibles with two important applications---a special case of Shelah's Many-Models Theorem in Section 5.3 and the Paris--Harrington independence result in Section 5.4. Indiscernibles also later play an important role in Section 6.5.

Chapter 6 begins with a proof of Morley's Categoricity Theorem in the spirit of Baldwin and Lachlan. The Categoricity Theorem can be thought of as the beginning of modern model theory and the rest of the book is devoted to giving the flavor of the subject. I have made a conscious pedagogical choice to focus on $\omega$-stable theories and avoid the generality of stability, superstability, or simplicity. In this context, forking has a concrete explanation in terms of Morley rank. One can quickly develop some general tools and then move on to see their applications. Sections 6.2 and 6.3 are rather technical developments of the machinery of Morley rank and the basic results on forking and independence. These ideas are applied in Sections 6.4 and 6.5 to study prime model extensions and saturated models of $\omega$-stable theories.

Chapters 7 and 8 are intended to give a quick but, I hope, seductive glimpse at some current directions in the subject. It is often interesting to study algebraic objects with additional model-theoretic hypotheses. In Chapter 7 we study $\omega$-stable groups and show that they share many properties with algebraic groups over algebraically closed fields. We also include Hrushovski's theorem about recovering a group from a generically associative operation which is a generalization of Weil's theorem on group chunks. Chapter 8 begins with a seemingly abstract discussion of the combinatorial geometry of algebraic closure on strongly minimal sets, but we see in Section 8.3 that this geometry has a great deal of influence on what algebraic objects are interpretable in a structure. We conclude with an outline of Hrushovski's proof of the Mordell--Lang Conjecture in one special case.

Because I was trying to write an introductory text rather than an encyclopedic treatment, I have had to make a number of ruthless decisions about what to include and what to omit. Some interesting topics, such as ultraproducts, recursive saturation, and models of arithmetic, are relegated to the exercises. Others, such as modules, the $p$-adic field, or finite model theory, are omitted entirely. I have also frequently chosen to present theorems in special cases when, in fact, we know much more general results. Not everyone would agree with these choices.

The Reader

While writing this book I had in mind three types of readers: For the graduate student in model theory, this book should provide a firm foundation in the basic results of the subject while whetting the appetite for further exploration. My hope is that the applications given in Chapters 7 and 8 will excite students and lead them to read the advanced texts of Baldwin, Buechler, Pillay and Poizat.

The graduate student in logic outside of model theory should, in addition to learning the basics, get an idea of some of the main directions of the modern subject. I have also included a number of special topics that I think every logician should see at some point, namely the random graph, Ehrenfeucht--Fraisse Games, Scott's Isomorphism Theorem, Morley's result on the number of countable models, Shelah's Many-Models Theorem, and the Paris--Harrington Theorem.

For the mathematician interested in applications, I have tried to illustrate several of the ways that model theory can be a useful tool in analyzing classical mathematical structures. In Chapter 3, we develop the method of quantifier elimination and show how it can be used to prove results about algebraically closed fields and real closed fields. One of the areas where model-theoretic ideas have had the most fruitful impact is differential algebra. In Chapter 4, we introduce differentially closed fields. Differentially closed fields are very interesting $\omega$-stable structures. Chapters 6, 7, and 8 contain a number of illustrations of the impact of stability-theoretic ideas on differential algebra. In particular, in Section 7.4 we give Poizat's proof of Kolchin's theorem on differential Galois groups of strongly normal extensions. In Chapter 7, we look at classical mathematical objects---groups--- under additional model-theoretic assumptions---$\omega$-stability. We also use these ideas to give more information about algebraically closed fields. In Section 8.3, we give an idea of how ideas from geometric model theory can be used to answer questions in Diophantine geometry.

Prerequisites

Chapter 1 begins with the basic definitions of languages and structures. Although a mathematically sophisticated reader with little background in mathematical logic should be able to read this book, I expect that most readers will have seen this material before. The ideal reader will have already taken one graduate or undergraduate course in logic and be acquainted with mathematical structures, formal proofs, G\"odel's Completeness and Incompleteness Theorems, and the basics about computability. Shoenfield's {\em Mathematical Logic} \cite{Sh} or Ebbinghaus, Flum, and Thomas' {\em Mathematical Logic} \cite{EFT} are good references.

I will assume that the reader has some familiarity with very basic set theory, including Zorn's Lemma, ordinals, and cardinals. Appendix A summarizes all of this material. More sophisticated ideas from combinatorial set theory are needed in Chapter 5 but are developed completely in the text.

Many of the applications and examples that we will investigate come from algebra. The ideal reader will have had a year-long graduate algebra course and be comfortable with the basics about groups, commutative rings, and fields. Because I suspect that many readers will not have encountered the algebra of formally real fields that is essential in Section 3.3, I have included this material in Appendix B. Lang's {\em Algebra} \cite{Lang} is a good reference for most of the material we will need. Ideally the reader will have also seen some elementary algebraic geometry, but we introduce this material as needed.

Using This Book as a Text

I suspect that in most courses where this book is used as a text, the students will have already seen most of the material in Sections 1.1, 1.2, and 2.1. A reasonable one-semester course would cover Sections 2.2, 2.3, the beginning of 2.4, 3.1, 3.2, 4.1--4.3, the beginning of 4.4, 5.1, 5.2, and 6.1. In a year-long course, one has the luxury of picking and choosing extra topics from the remaining text. My own choices would certainly include Sections 3.3, 6.2--6.4, 7.1, and 7.2.

Exercises and Remarks

Each chapter ends with a section of exercises and remarks. The exercises range from quite easy to quite challenging. Some of the exercises develop important ideas that I would have included in a longer text. I have left some important results as exercises because I think students will benefit by working them out. Occasionally, I refer to a result or example from the exercises later in the text. Some exercises will require more comfort with algebra, computability, or set theory than I assume in the rest of the book. I mark those exercises with a dagger. The Remarks sections have two purposes. I make some historical remarks and attributions. With a few exceptions, I tend to give references to secondary sources with good presentations rather than the original source. I also use the Remarks section to describe further results and give suggestions for further reading.

Acknowledgments

My approach to model theory has been greatly influenced by many discussions with my teachers, colleagues, collaborators, students, and friends. My thesis advisor and good friend, Angus Macintyre, has been the greatest influence, but I would also like to thank John Baldwin, Elisabeth Bouscaren, Steve Buechler, Zo\'e Chatzidakis, Lou van den Dries, Bradd Hart, Leo Harrington, Kitty Holland, Udi Hrushovski, Masanori Itai, Julia Knight, Chris Laskwoski, Dugald Macpherson, Ken McAloon, Margit Messmer, Ali Nesin, Kobi Peterzil, Anand Pillay, Wai Yan Pong, Charlie Steinhorn, Alex Wilkie, Carol Wood, and Boris Zil'ber for many enlightening conversations and Alan Taylor and Bill Zwicker, who first interested me in mathematical logic.

I would also like to thank John Baldwin, Amador Martin Pizarro, Dale Radin, Kathryn Vozoris, Carol Wood, and particularly Eric Rosen for extensive comments on preliminary versions of this book.

Finally, I, like every model theorist of my generation, learned model theory from two wonderful books, C. C. Chang and H. J. Keisler's Model Theory and Gerald Sacks Saturated Model Theory. My debt to them for their elegant presentations of the subject will be clear to anyone who reads this book.