UID:
almahu_9947367548802882
Format:
1 online resource (363 p.)
Edition:
1st ed.
ISBN:
1-281-07101-3
,
9786611071011
,
0-08-052952-6
Series Statement:
Studies in logic and the foundations of mathematics ; v. 144
Content:
This book describes a program of research in computable structure theory. The goal is to find definability conditions corresponding to bounds on complexity which persist under isomorphism. The results apply to familiar kinds of structures (groups, fields, vector spaces, linear orderings Boolean algebras, Abelian p-groups, models of arithmetic). There are many interesting results already, but there are also many natural questions still to be answered. The book is self-contained in that it includes necessary background material from recursion theory (ordinal notations, the hyperarithmetical hier
Note:
Description based upon print version of record.
,
Cover; Preface; 0.1 Introduction; 0.2 Constructivizations; 0.3 Authorship and acknowledgements; Contents; Chapter 1. Computability; 1.1 Informal concepts; 1.2 Church's Thesis; 1.3 Proof by Church's Thesis; 1.4 Some basic results; 1.5 Coding functions; 1.6 Kleene's Normal Form Theorem; 1.7 Facts about c.e. sets and relations; 1.8 The standard list of c.e. sets; 1.9 The s - m - n Theorem; 1.10 The Recursion Theorem; 1.11 Relative computability; 1.12 The relativized s - m - n Theorem; 1.13 Turing reducibility; 1.14 Other reducibilities; Chapter 2. The arithmetical hierarchy; 2.1 Jumps
,
2.2 Basic definitions2.3 Basic theorems; 2.4 Combining arithmetical relations; 2.5 Alternative definitions; 2.6 Approximations; 2.7 Trees; Chapter 3. Languages and structures; 3.1 Propositional languages and structures; 3.2 Predicate languages; 3.3 Structures for a predicate language; 3.4 Satisfaction; 3.5 Enlarging a structure; 3.6 Theories and models; 3.7 Prenex normal form; 3.8 Isomorphism; 3.9 Quotient structures; 3.10 Model existence; 3.11 Compactness; 3.12 Some special kinds of structures; 3.13 Computable sets of sentences; 3.14 Complexity of structures
,
3.15 Complexity of definable relations3.16 Copies of a given structure; 3.17 Complexity of quotient structures; Chapter 4. Ordinals; 4.1 Set theoretic facts; 4.2 Inductive proofs and definitions; 4.3 Operations on ordinals; 4.4 Cantor normal form; 4.5 Constructive and computable ordinals; 4.6 Kleene's 0; 4.7 Constructive and computable ordinals; 4.8 Transfinite induction on ordinal notation; Chapter 5. The hyperarithmetical hierarchy; 5.1 The hyperarithmetical hierarchy; 5.2 The analytical hierarchy; 5.3 The Kleene-Brouwer ordering; 5.4 Relativizing; 5.5 Ershov's hierarchy
,
Chapter 6. Infinitary formulas6.1 Predicate formulas; 6.2 Sample formulas; 6.3 Subformulas and free variables; 6.4 Normalform; 6.5 Model existence; 6.6 Scott's Isomorphism Theorem; 6.7 Ranks and special Scott families; 6.8 Rigid structures and defining families; 6.9 Definability of relations; 6.10 Propositional formulas; Chapter 7. Computable infinitary formulas; 7.1 Informal definitions; 7.2 Formal definition; 7.3 Sample formulas; 7.4 Satisfaction and the hyperarithmetical hierarchy; 7.5 Further hierarchies of computable formulas; 7.6 Computable propositional formulas
,
7.7 The simplest language7.8 Hyperarithmetical formulas; 7.9 X-computable formulas; Chapter 8. The Barwise-Kreisel Compactness Theorem; 8.1 Model existence and paths through trees; 8.2 The Compactness Theorem; 8.3 Hyperarithmetical saturation; 8.4 Orderings and trees; 8.5 Boolean algebras; 8.6 Groups; 8.7 Priority constructions; 8.8 Ranks; Chapter 9. Existence of computable structures; 9.1 Equivalence structures; 9.2 Abelian p-groups; 9.3 Linear orderings; 9.4 Boolean algebras; 9.5 Results of Wehner; 9.6 Decidable homogeneous structures; Chapter 10. Completeness and forcing
,
10.1 Images of a relation
,
English
Additional Edition:
ISBN 0-444-50072-3
Language:
English
Bookmarklink
