Handbook of Recursive Mathematics : Volume 1: Recursive Model Theory (Studies in Logic and the Foundations of Mathematics)

Yu. L. Ershov... et al., associate, Marek V.M. (eds.) Handbook of recursive mathematics (Elsevier, 1998., 1)(ISBN 0444500030)(O)(667s)

Excerpt

CHAPTER 1

Pure Computable Model Theory

Contents

Introduction
1. History
2. Notation and basic definitions
3. Decidable theories, and computable and decidable models
4. Effective completeness theorem
5. Model completeness and decidability
6. Omitting types and decidability
7. Decidable prime models
8. Computable saturated models and computably saturated models
9. Decidable homogeneous models
10. Vaught's theorem computably visited
11. Decidable Ehrenfeucht theories
12. Decidable theories with countably many countable models
13. Indiscernibles and decidability
14. Degrees of models
15. Automorphisms and computable models
16. Acknowledgments
References

Introduction

Exploiting the fundamental concepts of computability theory, computable model theory introduces effective analogues of model-theoretic notions. By combining methods from both fields, it has enabled the development of machinery for investigating the effective content of model-theoretic constructions. While some model-theoretic constructions can be replaced by effective ones, for others such replacement is impossible. Thus, another important objective for computable model theory is the discovery of effective counterexamples to model-theoretic results. For instance, Vaught's theorem (no complete theory has exactly two non-isomorphic countable models) cannot be effectivized.

The article begins with the foundations of computable model theory: the definitions and examples of decidable theories, and computable and decidable models. It then presents the effective completeness theorem and the effective omitting types theorem; and characterizations of decidable theories with decidable prime models, and then with decidable saturated models. The next sections characterize decidable homogeneous models, and give examples of decidable theories with exactly two non-isomorphic decidable models. The following sections present the results on decidable theories with only finitely many, and on decidable theories with only countably many, non-isomorphic countable models, and investigate the model-theoretic nature and the computability-theoretic complexity of models of such theories. Later sections study indiscernibles from the computability-theoretic point of view, and the degrees of models. Finally, we consider the isomorphisms of effective models and related subtopics, such as intrinsically c.e. relations, computably stable models, and computably categorical models.

Computable model theory was developed simultaneously and for the most part independently in the West, mainly in the United States and Australia, and in Russia. Because of poor communication between the two groups, many results were independently discovered by both groups. This article looks at computable model theory from the Western perspective. (There are articles in this volume on the Russian approach.) However, the article also presents some results of the Russian group, and often emphasizes the connections with and gives references to their results.

Almost every section contains a detailed proof with a survey of the computability-theoretic and model-theoretic background needed. The bibliography contains both Western and Russian papers in pure computable model theory, but not papers in computable algebra nor in computable combinatorics. Another survey article on this subject has been recently and independently written by Millar.

1 History

The goal of computable mathematics is to find the extent to which certain classical results of mathematics are effectively true. Although many consider the modern study of computability of algebraic constructions to have started with Fröhlich and Shepherdson in 1955–56 and Rabin in 1958–60, even van der Waerden in his book from 1930, see also, discussed the problem of carrying out certain field-theoretic procedures effectively. He also defined an explicitly given field as one whose elements are uniquely represented by distinguishable symbols with which one can perform the field operations effectively. In a pioneering paper from 1930, van der Waerden proved that there does not exist a splitting algorithm applicable to every explicit field. Fröhlich and Shepherdson used the precise notion of a computable function to obtain a collection of results and examples about explicit fields.

Rabin did a systematic study of computable groups and computable fields. In Russia, a systematic study of constructive algebraic systems and their enumerations was initiated by Mal'cev in the 1960's, and continued by Ershov and his collaborators, see.

In the 1970's, Nerode and his collaborators revived the study of computability of algebraic constructions. At the 1974 Recursive Model Theory Symposium at Monash University (Melbourne, Australia), Metakides and Nerode announced that, in addition to other computability-theoretic tools, they started using the priority method as an important tool in the algorithmic part of computable mathematics, see. Thus, they founded in the West the field of the post-Friedberg-Muchnik computable mathematics. Metakides and Nerode used the priority method in their systematic study of the effective content of specific structures, such as vector spaces, fields and structures with a dependence relation. For more information on the development of computable mathematics see. In Russia, the post-Friedberg-Muchnik constructive mathematics was founded by Nurtazin and Goncharov in the 1970's.

In the West, the computability of ordered sets has also been studied by Ash, Case, Chen, Crossley, Downey, Feiner, Feldman, Fellner, Hay, Hingston, Hird, Jockusch, Kierstead, Knight, Lerman, Manaster, Metakides, McNulty, Moses, Remmel, Richter, Rosenstein, Roy, Schmerl, Schwarz, Soare, Tennenbaum, Trotter and Watnick; the computability of vector spaces by Ash, Guhl, Guichard, Dekker, Downey, Hamilton, Kalantari, Remmel, Retzlaff, Shore, Smith and Welch; the computability of rings and fields by Ash, Hodges, Jockusch, MacIntyre, Madison, Marker, Mines, Rosenthal, Seidenberg, Shlapentokh, Smith, Staples, Tucker and van den Dries; the computability of the structures with a dependence relation by Baldwin, Downey and Remmel. The computability in other mathematical structures is also extensively studied: in groups by Ash, Barker, Ge, Kent, Knight, Lin, Oates, Richards, Richman and Smith; in graphs by Aharoni, Bean, Beigel, Burr, Carstens, Gasarch, Golze, Kierstead, Lockwood, Manaster, Magidor, Päppinghaus, Remmel, Rosenstein, Schmerl and Shore; in Boolean algebras by Carroll, Feiner, LaRoche, Remmel and Thurber; in topological spaces by Kalantari, Legett, Remmel, Retzlaff and Weitkamp. Computable Ramsey's theory has been studied by Clote, Hummel, Jockusch, Seetapun, Simpson, Solovay and Specker. Computability in analysis and physics has also been studied, see.

The generalization of the definition of a particular computable algebraic structure to an arbitrary model yields one of the basic concepts of pure computable model theory, an area of logic developed in the last twenty-five years. That is, the notion of a computable model, and a stronger notion of a decidable model. Lerman and Schmerl have given examples of theories with computable models. The first general results in computable model theory have been obtained by following the fundamental notions and results of classical model theory. For example, Millar has obtained the effective version of the omitting types theorem, and Harrington, Goncharov and Nurtazin have found when a complete decidable theory with a prime model has a decidable prime model. Millar and Morley have characterized decidable theories with decidable saturated models, and Goncharov and Peretyat'kin have characterized decidable homogeneous models. Barwise, Schlipf and Ressayre have introduced the notion of a computably saturated model. Although developed in the context of admissible sets and admissible fragments of infinitary logic, computably saturated models have also provided a useful tool for research and exposition in classical model theory.

In the West, Millar has further produced an extensive body of work on topics including effective Vaught's theorem, the structure of types in decidable models, decidability and prime, saturated and homogeneous models, decidable theories with finitely many and decidable theories with countably many non-isomorphic countable models. Reed has also studied decidable theories with finitely many non-isomorphic countable models. Kierstead and Remmel have investigated the degrees of sets of indiscernibles in decidable models. Ash, Knight, Macintyre, Marker, Nadel, Nies, Richter, Jockusch, Lachlan, Scott, Shoenfield, Shore, Soare and Tennenbaum have studied the degrees of models of various theories, including the theory of linear orders, Peano arithmetic, true arithmetic, and the theory of Boolean algebras.

The whole spectrum of questions involving the isomorphisms of abstract computable models has been investigated by Ash, Barker, Chisholm, Cholak, Crossley, Downey, Eisenberg, Guichard, Harizanov, Hird, Khoussainov, Knight, Manasse, Manaster, Millar, Moses, Nerode, Remmel, Shore, Slaman and Wehner. The lattices of computably enumerable submodels have been studied by Ash, Guichard, Carroll, Downey, Metakides, Nerode, Remmel and Smith. More recently, Nerode, Remmel and Cenzer have been developing feasible model theory (as a part of feasible mathematics), the theory of models with bounded space and time resources. They have investigated how feasible models differ from computable models. The feasible models studied include Boolean algebras, abelian groups, linear orders, models of arithmetic, and graphs.

2 Notation and Basic Definitions

The set {0, 1, 2, ...} of all natural numbers is denoted by ω. Unless explicitly stated otherwise, it is assumed that all languages considered are first-order and computable (hence at most countable), and that the domains of the considered models are subsets of ω. For a set of sentences T, by L(T) we denote its language. A set of sentences T is deductively closed if T contains every sentence σ of L(T) such that T [??] σ. A consistent deductively closed set of sentences is called a theory.

Models are denoted by script letters, and their domains by the corresponding capital Latin letters. By A [subset or equal to] B we denote that A is a submodel of B, and by A [??] B that A is an elementary submodel of B. By A [equivalent to] B we denote that A and B are elementarily equivalent, and by A [congruent to] B that A and B are isomorphic. A model is prime if it can be elementarily embedded in every model of its theory. Hence a prime model for a countable language must be countable. Two prime models of the same complete theory are isomorphic.
(Continues...) Excerpted from HANDBOOK OF RECURSIVE MATHEMATICS by Yu. L. ERSHOV. Copyright © 1998 by Elsevier Science B.V.. Excerpted by permission of Elsevier Science.
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. Since the second edition of this book (1977), Model Theory has changed radically, and is now concerned with fields such as classification (or stability) theory, nonstandard analysis, model-theoretic algebra, recursive model theory, abstract model theory, and model theories for a host of nonfirst order logics. Model theoretic methods have also had a major impact on set theory, recursion theory, and proof theory. This new edition has been updated to take account of these changes, while preserving its usefulness as a first textbook in model theory. Whole new sections have been added, as well as n