C.C. Chang - Model Theory: Third Edition

MODEL
THEORY

THIRD EDITION

C. C. CHANG
University of California, Los Angeles

H. JEROME KEISLER
University of Wisconsin, Madison

DOVER PUBLICATIONS, INC.
MINEOLA, NEW YORK

MODEL
THEORY

Copyright

Copyright 1990, 2012 by C. C. Chang and H. Jerome Keisler
All rights reserved.

Bibliographical Note

This Dover edition, first published in 2012, is an unabridged republication of the third edition of the work, originally published as Volume 73 in the series Studies in Logic and the Foundations of Mathematics by North-Holland Press, Amsterdam and New York, in 1990. [first edition: 1973]. A new Preface to the Dover Edition has been specially prepared for this edition by H. Jerome Keisler.

Library of Congress Cataloging-in-Publication Data

Chang, Chen Chung, 1927

Model theory / C.C. Chang, H. Jerome Keisler. Dover ed.

p. cm.

Originally published: 3rd ed. Amsterdam ; New York : North-Holland Press, 1990, in series: Studies in logic and the foundations of mathematics ; v. 73.

Includes bibliographical references and index.

eISBN-13: 978-0-486-31095-4

1. Model theory. I. Keisler, H. Jerome. II. Title.

QA9.7.C45 2012
511.3' 4dc23

2011041607

Manufactured in the United States by Courier Corporation
48821701
www.doverpublications.com

Preface to the Dover Edition

Nearly four decades have gone by since the first edition of Model Theory was published in 1973. The subject of model theory has seen tremendous advances, and has grown from a single tightly focused field to a collection of thriving areas of research with varying objectives. During that time, generations of researchers have learned model theory from this book. It has been widely recognized as the classic text in the field, and as the place to learn the basic prerequisites that are needed for all parts of model theory.

This volume is a reprinting of the Third Edition of Model Theory (1990). It contains extensive additions to the First Edition. We are pleased that this book will again be available in print and accessible to students.

Here is a brief overview of some developments in model theory that took place after the publication of the Third Edition. Some recent references are given in footnotes.

In first order model theory, the material presented in

Another highly successful program in first order model theory is the study of o-minimal structures, which was inspired by Tarskis proof of quantifier elimination for the real numbers.

Much of first order model theory has been extended to model theory for infinitary logics and logics with cardinality quantifiers.

In recent years, continuous model theory has emerged as an area of research that applies many valued logic to structures in analysis in the same way that first order logic is applied to structures in algebra.

Nonstandard analysis and the ultrapower construction are two closely related model-theoretic methods that continue to be applied to analysis and topology.

Finite model theory is a flourishing field of research with applications to computer science and complexity theory. Infinitary logics play an important role in this area.

The model theory of Peano arithmetic has important applications in proof theory and reverse mathematics.

Models of set theory are central to the study of large cardinals.

First order model theory has provided a template for the development of model theories for a wide variety of other logics, including modal logic, intuitionistic logic, temporal logic, logics with non-classical quantifiers, and logics arising in theoretical computer science.

The Open Problem list in .

University of Wisconsin, Madison, October 2011.

H. J. KEISLER

See Pillay, Geometric Stability Theory (Clarendon 1996), and Bouscaren, Model Theory and Algebraic Geometry (Springer 1999).

See Wagner, Simple Theories (Kluwer 2000), and Adler, Introduction to Theories without the Independence Property, to appear in Archive for Mathematical Logic.

See van den Dries, Tame Topology and o-minimal Structures (Cambridge 1998).

See Baldwin, Categoricity (AMS 2009).

See Ersov et.al., Handbook of Recursive Mathematics, Vol. 1 Recursive Model Theory (Elsevier 1998).

For an introduction see the article Model Theory of Metric Structures by Ben Yaacov et.al., in Chatzidakis et.al., Model Theory with Applications to Algebra and Analysis vol. 2 (Cambridge 2008).

See Vth, Nonstandard Analysis (Birkhauser 2007), Arkeryd et.al., Nonstandard Analysis: Theory and Applications (Kluwer 1996), Diener et.al., Nonstandard Analysis in Practice (Springer 1995), and Bergelson et.al., Ultrafilters across Mathematics (AMS 2008).

See Libkin, Elements of Finite Model Theory (Springer 2004).

See Kaye, Models of Peano Arithmetic (Oxford 1991), and Simpson, Subsystems of Second Order Arithmetic (Cambridge 2010).

See Kanamori, The Higher Infinite (Springer 2008).

PREFACE

Model theory is the branch of mathematical logic which deals with the connection between a formal language and its interpretations, or models. In this book we shall present the model theory of first order predicate logic, which is the simplest language that has applications to the main body of mathematics. Most of the techniques in model theory were originally developed and are still best explained in terms of first order logic.

The early pioneers in the development of model theory were Lwenheim (1915), Skolem (1920), Gdel (1930), Tarski (1931), and Malcev (1936). The subject became a separate branch of mathematical logic with the work of Henkin, Robinson, and Tarski in the late 1940s and early 1950s. Since that time it has been an active area of research.

Looking over the subject as it stands today, we feel that it can best be analyzed on the basis of a few general methods of constructing models. While the methods in their pure form are quite simple, they can be iterated and combined in a great variety of ways to yield practically all the deeper results of the theory. For this reason we have organized the book on the following plan. As a rule, we introduce a method in the first section of a chapter and then give some applications of it in the remaining sections. The basic methods of constructing models are: Constants (, we present some more advanced topics which combine several of these methods. We believe that this book covers most of first-order model theory and many of its applications to algebra and set theory.

Up to now no book of this sort has been written. This has made it difficult for students and outsiders to learn about large areas of the subject. It has been necessary for them to chase down an almost unlimited number of widely scattered articles, some of which are hard to read. We do not claim to have compiled all the results in first-order model theory, but we have tried to include the important results which are indispensable for further work in this area. In addition we have included some of the more recent results which are stimulating present and probably future research. In this category are the Keisler-Shelah isomorphism theorem, the Morley categoricity theorem, the work of Ax-Kochen and Ershov in field theory, and the results of Rowbottom, Gaifman and Silver on large cardinals and the constructible universe.

First-order model theory is a prerequisite for the other types of model theory and such applications as nonstandard analysis. Other logics whose model theories have been investigated are infinitary logic, logic with additional quantifiers, many-valued logic, many sorted logic, intuitionistic logic, modal logic, second-order logic. In recent years model theory for infinitary logic has made rapid progress. Model theory for second-order logic is largely beyond present methods but has a great deal of potential importance. We hope that the availability of this book will contribute to future research in all kinds of model theory and to the discovery of more applications.