Basic Model Theory - Stanford University

[Pages:141]Basic Model Theory

For personal use

Studies in Logic, Language and Information

The Studies in Logic, Language and Information book series is the official book series of the European Association for Logic, Language and Information (FoLLI).

The scope of the book series is the logical and computational foundations of natural, formal, and programming languages, as well as the different forms of human and mechanized inference and information processing. It covers the logical, linguistic, psychological and information-theoretic parts of the cognitive sciences as well as mathematical tools for them. The emphasis is on the theoretical and interdisciplinary aspects of these areas.

The series aims at the rapid dissemination of research monographs, lecture notes and edited volumes at an affordable price. Managing editor: Robin Cooper, University of Gothenburg Executive editor: Maarten de Rijke, University of Warwick Editorial board: Peter Aczel, Manchester University Nicholas Asher, The University of Austin, Texas Jon Barwise, Indiana University, Bloominton John Etchemendy, CSLI, Stanford University Dov Gabbay, Imperial College, London Hans Kamp, Universit?t Stuttgart Godehard Link, Universit?t M?nchen Fernando Pereira, AT&T Bell Laboratories, Murray Hill Dag Westerst?hl, Stockholm University

For personal use

Basic Model Theory

Kees Doets

CSLI Publications

Center for the Study of Language and Information Stanford, California

&

FoLLI

The European Association for Logic, Language and Information

For personal use

Copyright ?1996 CSLI Publications Center for the Study of Language and Information Leland Stanford Junior University Printed in the United States 00 99 98 97 96 5 4 3 2 1

Library of Congress Cataloging-in-Publication Data

Doets, Kees.

Basic model theory / Kees Doets

p.

cm.

Includes bibliographical references (p. 119?121) and indexes.

ISBN 1-57586-049-X (hardcover : alk. paper). -- ISBN 1-57586-048-1 (pbk : alk. paper)

1. Model theory. I. Title. QA9.7.D64 1996 511.3--dc20

96-20327 CIP

r?eqTuhireeamciedn-tfsreoefpthapeeAr museerdicianntNhiastiboonoakl

meets the minimum Standard for Information

Sciences--Permanence of Paper for Printed Library Materials, ANSI

Z39.48-1984.

For personal use

Contents

Introduction vii 1 Basic Notions 1 2 Relations Between Models 11

2.1 Isomorphism and Equivalence 11 2.2 (Elementary) Submodels 13

3 Ehrenfeucht-Fra sse Games 21

3.1 Finite Games 21 3.2 The Meaning of the Game 27 3.3 Applications 34 3.4 The In nite Game 44

4 Constructing Models 51

4.1 Compactness 51 4.2 Diagrams 55 4.3 Ultraproducts 60 4.4 Omitting Types 66 4.5 Saturation 72 4.6 Recursive Saturation 75 4.7 Applications 82

A Deduction and Completeness 93

A.1 Rules of Natural Deduction 94 A.2 Soundness 100 A.3 Completeness 101

B Set Theory 109

B.1 Axioms 109 B.2 Notations 109 B.3 Orderings 110 B.4 Ordinals 111 B.5 Cardinals 112

v

For personal use

vi / Contents

B.6 Axiom of Choice 112 B.7 Inductive De nitions 112 B.8 Ramsey's Theorem 115 B.9 Games 116

Bibliography 119 Name Index 123 Subject Index 125 Notation 129

For personal use

Introduction

This text is written for an audience with some working knowledge of propositional and first-order logic. To make it more self-contained, a natural deduction system and a proof of the completeness theorem are given in Appendix A. Set-theoretic preliminaries are summed up in Appendix B.

The goal of this text is to provide a speedy introduction into what is basic in (mostly: first-order) model theory.

Central results in the main body of this field are theorems like Compactness, L?owenheim-Skolem, Omitting types and Interpolation. From this central area, the following directions sprout:

? model theory for languages extending the first-order ones, abstract model theory,

? applied model theory: non-standard analysis, algebraic model theory, model theory of other special theories,

? recursive model theory, ? finite-model theory, ? classification theory. There are occasional hints at the first and the fourth, leaving the others largely untouched. Languages other than first-order discussed below are the following. ? First-order with restricted number of variables, ? (monadic) second-order, admitting quantification over sets of indi-

viduals etc., ? infinitary logic, admitting infinite conjunctions and disjunctions, ? fixed-point logic, which can refer to least fixed points of definable

monotone operators. A short proof of Lindstr?om's famous characterization of first-order logic concludes this introduction.

By then, the ideal student, but hopefully the not-so-ideal student as well, should be comfortable with the standard model theoretic notions

vii

For personal use

viii / Basic Model Theory introduced here, have some idea concerning the use of Ehrenfeucht`s game in simple, concrete situations, and have an impression as to the applicability of some of the basic model theoretic equipment.

Exercises have been printed in smaller font. Some of these require more of the student than he might be prepared for. Usually, this is indicated by a .

Digressions from the main text are indented and printed in a smaller font.

The bible for the model theory of first-order languages for more than twenty years now is the book Model Theory by Chang and Keisler 1990, the last edition of which has been updated. The newer Hodges 1993, that carries the same title, might well rise to the same level of popularity in the near future. These are the books to look for more. For a multitude of references, see Vol. III (Model Theory) of the -Bibliography of Mathematical Logic Ebbinghaus 1987, which is the reason that a detailed bibliography is omitted here.

These notes were originally written to accompany a course during the Lisbon 1993 edition of the European Summer School in Logic, Language and Information. (The presence of a course in finite-model theory there accounts for the rather large amount of space devoted to the Ehrenfeucht game in Chapter 3.) Since then, the material has been expanded and used a couple of times for the courses on logic and model theory given at the Mathematics Department, University of Amsterdam. Acknowledgments I thank Dag Westerst?ahl and an anonymous referee for their valuable critisism of an earlier version of the text, and Maarten de Rijke for his excellent editorial help.

For personal use

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download