FINITELY AXIOMATIZABLE THEORIES
Mikhail
G.Peretyatkin |
To the memory of W. Hanf
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.
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
На
главную
страницу