PDF 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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- pdf theory development the office of behavioral and social
- pdf lecture note 1 agency theory mit
- pdf program theory and logic models
- pdf basic model theory stanford university
- pdf the recent history of model theory ub
- pdf introduction to model theory dma ens
- pdf the capital asset pricing model theory and evidence
- pdf model theory edu
- pdf models and theories to support health behavior intervention
- pdf game theory ucla
Related searches
- stanford university philosophy department
- stanford university plato
- stanford university encyclopedia of philosophy
- stanford university philosophy encyclopedia
- stanford university philosophy
- stanford university ein number
- stanford university master computer science
- stanford university graduate programs
- stanford university computer science ms
- stanford university phd programs
- stanford university phd in education
- stanford university online doctoral programs