FINITELY AXIOMATIZABLE THEORIES


Mikhail G.Peretyatkin
Institute of Pure and Applied Mathematics
Kazakh Academy of Sciences
Almaty, Kazakhstan

To the memory of W. Hanf

 

Consultants Bureau · New York, London, and Moscow
Siberian School of Algebra and Logic is a simultaneous translation
of the book series Sibirskaya Shkola Algebry i Logiki,
which is published in and translated by
Scientific Books (RIMIBE NGU)
2, Pirogova Street, Novosibirsk 630090, Russia

ISBN 0-306-11062-8

г1997 Consultants Bureau, New York,
A Division of Plenum Publishing Corporation
233 Spring Street, New York, N.Y. 10013


Preface



   Finitely axiomatizable theories are a classical subject of mathematical logic. They attract the attention of researchers not only as object of investigation but also as an effective method of study-ing various problems. For instance, well-know result of Church on the algorithmic undecidability of predicate logic was based on a regular method of constructing finitely axiomatizable theories. This method was modified by Trakhtenbrot in order to prove the undecidability of the class finite mod-els. To prove the undecidability theories of various classes of models, Ershov created a universal method of relative elementary definability, which has its origins in the above-mentioned method.
   What can be expressed by a single formula of classical predicate logic? Posed in this general setting, the question incorporates many particular problems on the expressibility of finitely axiomatizable theories which arose as a result of the successful development of model theory in the 1950,s. Despite its timeliness, the problem of expressibility of finitely axiomatizable theories did not have a satisfactory solution for a long time. Some results were obtained in this direction, but they were fragmented and did not present the entire picture. Thus, even in the late 1970,s the above question remained open.
   As the first attempt to determine the expressibility of finitely axiomatizable theories in general, we recall the result of Kleene which asserts that any recursively axiomatizable theory of a finite signature is interpreted in a finitely axiomatizable theory of a signature containing a single auxiliary binary predicate. As a result of the active development of model theory, algorithm theory, and other branches of logic, a number of key questions concerning finitely axiomatizable theories were formu-lated. The Hanf problem on coincidence of recursive isomorphism types for the Lindenbaum alge-bras of finitely axiomatizable theories and those of recursively axiomatizable theories and the Vaught-Morley problem on the existence of a complete uncountable categorical finitely axiomatiz-able theory (which was divided by Shelah into two cases: the categorical variant and the noncate-gorical variant in countable cardinality) exert the primary influence on further development along this direction.
   Only during the past decade was the problem of expressibility of formulas of predicate logic given an exhaustive solution. The author [42] constructed an example of a complete uncountably categorical finitely axiomatizable theory. The example itself gave a positive answer to the well-know Vaught-Morley problem. Together with the profound ideas of Hanf on constructing formulas with prescribed semantic properties, this example formed the basis for a solution to the general problem on the expressibility of finitely axiomatizable theories of predicate logic. The author sug-gested that a universal construction be formulated, which showed that a majority of the natural model-theoretic properties of expressibility coincide for finitely axiomatizable theories and for re-cursively axiomatizable theories. This result enables us to regularly reduce a lot of questions on finitely axiomatizable theories to the considerably easier case of recursively axiomatizable theories.
   The book follows the same direction as the Hanf problem and the countably noncategorical variant of the Vaught-Morley problem. A lot of positive information on the expressibility of finitely axiomatizable theories was obtained in this direction. Thus, a more precise title of the book would be Expressibility of Finitely Axiomatizable Theories and Their Applications in Logic (Positive As-pects).
Notice that the countably categorical variant of the Vaught-Morley problem was negatively solved by Zil'ber [65]. The results of Zil'ber were strengthened and generalized to a wider class of support-able theories by Lachlan, Cherlin, and Harrington. These results have not been included in this book due to the great difference in notions and methods used.
   The book is based on a single, involved construction, but the contents are not reduced only to this construction and its applications.
   First, the main construction has a simpler predecessor, which is also presented in the book. Thus, the reader may approach the difficult goal of understanding the universal construction by a successive approximation of ideas that are presented initially in a simpler variant.
   Second, the book contains self-contained proofs for universal construction as well as for some results that are very interesting in themselves. These include, most importantly, a separate chapter containing a solution to the Vaught-Morley problem and a separate chapter with an intermediate construction which solves the Hanf problem. At present, the proofs of these results have been considerably simplified compared to the original proofs. Due to this, compact and self-contained exposition may be of interest to specialists in logic.
   Presently, no monograph devoted to the expressibility of finitely axiomatizable theories has been written. This book summarizes the investigations in the field at a time when considerable progress has been achieved. It treats systematically all positive obtained concerning the expressibility of finitely axiomatizable theories and states a number of new natural questions in this field, thus pro-viding prospects for further development of the theory.

ACKNOWLEDGEMENT

   I would like to thank my teacher, Yu.L. Ershov, who directed my initial steps in science. I would like to acknowledge my colleagues. S.S.Goncharov, V.L.Selivanov, E.A.Palyutin, S.D.Denisov, A.S.Morozov, and D.E.Pal'chunov for their useful discussions.
I am also grateful to A.V.Kravchenko who carefully checked the text of this book.
   I express thanks to my editor Tamara Rozhkovskaya for the extensive editorial work she performed in transforming my manuscript into a fine book.

Mikhail G.Peretyat'kin
Alma-Ata, Kazakhstan
July, 1996


Contents

    Introduction
01. Axiomatizable Theories and Recursively Enumerable Indices
02. Enumerated Models
03. Lindenbaum Algebras
04. Model-Theoretic Properties
05. Semantic Similarity of Theories
06. Main Theorem
07. Constructions of Finitely Axiomatizable Theories
   Chapter 1. Quasisuccessor Theory of Rank2
1.1 Axiomatics and the Simplest Properties
1.2. The Impossibility of Cycles
1.3. Informal Description of Models
1.4. Coordinates
1.5. Connection Between Predicates and Coordinates
1.6. Main Properties of the Quasisuccesor Theory
1.7. Exterior Properties of the Basic Theory
   Chapter 2 Binary Trees
2.1 Basic Definitions
2.2 Construction of Trees
2.3. Standard Sets
2.4. Axiomatizable Construction
   Chapter 3. The Construction over a Unary List
3.1. The Main Theorem for the Intermediate Construction
3.2. Turing Machines with Division of Cells
3.3 Signature
3.4. Axiomatics. The Frame (FRM)
3.5. Axiomatics. The Grid Structure (NET)
3.6. Description of Blocks
3.7. Axiomatics. The Turing Machine (MT)
3.8. Axiomatics. The Translator (TRN)
3.9. One-Block Models
3.10 Global Structure of Models
3.11 Admissible Turing Machines and the Normalization Axiom
3.12 Perfect Models and the Model Completeness
3.13 Criteria for Prime and Saturated Models
3.14 Computations of the Turing Machine
3.15 Programming Technique
3.16 The Last Step of the Proof of the Main Theorem
   Catalogue Catal 3.1
   Catalogue Catal 3.2
   Chapter 4. Rigid Quasisuccession
4.1. Axiomatics
3.2. The Impossibility of Cycles
4.3. Description of Models and Coordinates
4.4. Connection Between Predicates and Coordinates
4.5. Main Properties of the Quasisuccessor Theory
4.6. Rigidity Mechanism
4.7. Exterior Properties of the Basic Theory
   Chapter 5. Interpretations
5.1. Interpretations in the Basic Construction
5.2. Isostone Interpretations
5.3. Immersing Interpretations
5.4. Exact Interpretations
5.5. Prequasiexact and Immersing Interpretations
5.6. Envelopes and Quasiexact Interpretations
5.7. Theorem on Transmission of Properties
5.8. Elementary Transformations of Theories
5.9. The Elementary Transformations IG
5.10 The Elementary Transformations FG and GL.
5.11 Reduction of the Signature of the Intermediate Construction
   Chapter 6. The Universal Construction
6.1. A Sketch of the Proof of the Main Theorem
6.2. Signature
6.3. Axiomatics. Frame
6.4. General Structure of Models
6.5. Connections of Depth 2
6.6. Axiomatoics. Local Forms of Blocks
6.7. Description of Blocks
6.8. Peculiarities of Block-Zone Structure of Models
6.9. Axiomatics. Geometric Structure
6.10 Commutative Stratifications and Branchings
6.11 Axiomatics. Informational Lines
6.12 Axiomatics. Numbering of Sequences and Subdivision
6.13 Axiomatics. Interaction of Messages
6.14 General Arrangement of the Computing Block
6.15 Tree of Sequences and Subdivision of the Model Kernel
6.16 Mechanism for Computing Formulas
6.17 Computing Controller and Programming
6.18 Nonstandard Blocks and Normalization Axioms
6.19 Axiomatics. Rigidity Mechanism
6.20 Description of Models and Isomorphisms
6.21 Model Completeness and Quasiexactness
   Catalogue Catal 6.1
   Catalogue Catal 6.2
   Chapter 7. Existence Theorems
7.1. Lindenbaum Algebras and the Hanf Problem.
7.2. Complete Theories
7.3. Value of the Morley Rank
   Chapter 8. Complexity of Semantic Classes of Sentences
8.1. General Questions
8.2. Prime Models
8.3. Countable Saturated Models
8.4. Totally Transcendental Theories
Appendix. Open Questions
References
Subject index
На главную страницу