Elementary Induction on Abstract Structures (eBook)

Lev D. Beklemishev (Autor)

eBook Download: PDF

2000 | 1. Auflage
217 Seiten
Elsevier Science (Verlag)
978-0-08-095487-5 (ISBN)

Infos

Provability, Computability and Reflection

---

Elementary Induction on Abstract Structures

Inhalt

Front Cover 1
Elementary Induction on Abstract Structures 4
Copyright Page 5
Preface 8
CONTENTS 10
Introduction 12
Chapter 1. Positive elementary inductive deflnitions 17
1A. Monotone operators 17
1B. Relative positive inductive definability 19
1C. Combining inductions 23
1D. Inductive definability on a structure 28
Exercises 31
Chapter 2. The stages of an inductive definition 38
2A. The Stage Comparison Theorem 38
2B. Closure ordinals and the Closure Theorem 41
Exercises 47
Chapter 3. Structure theory for inductive relations 49
3A. Inductive norms and the Prewellordering Theorem 49
3B. Making hyperelementary selections 53
3C. The Boundedness and Covering Theorems. 56
3D. Expanding a structure by an inductive relation 58
3E. Generalization of the theory to richer languages 59
Exercises 62
Chapter 4. Games and game quantifiers 64
4A. Interpreting quantifier strings via games 64
4B. A canonical form for positive formulas 68
4C. Explicit formulas for inductive relations 70
Exercises 72
Chapter 5. Acceptable structures 76
5A. Coding schemes 76
5B. Satisfaction is hyperelementary 78
5C. The quantifier G 81
5D. Parametrizations and universal sets 84
Exercises 87
Chapter 6. Inductive second order relations 90
6A. Relativization of inductive definitions examples
6B. Transitivity, Substitutivity and Positive Induction Completeness 94
6C. Extension of the theory to second order relations 101
6D. The class of hyperelementary relations 108
Exercises 112
Chapter 7. Second order characterizations 114
7A. Inductive and S1 1 relations 114
7B. Quasistrategies 115
7C. The Second Stage Comparison Theorem 119
7D. The Abstract Spector–Gandy Theorem 126
7E. The hierarchy of hyperelementary sets 131
7F. Model theoretic characterizations 140
Exercises 141
Chapter 8. Countable acceptable structures 143
8A. The Abstract Kleene Theorem 143
8B. The Perfect Set Theorem 146
8C. The intersection of U-models of second order comprehension 149
8D. Counterexamples to special properties of arithmetic the language L .1,G
8E. The Suslin–Kleene Theorem 161
Exercises 169
Chapter 9. The next admissible set 175
9A. Spector classes of relations 175
9B. Examples of Spector classes 179
9C. Structure theory for Spector classes 182
9D. Admissible sets 189
9E. The companion of a Spector class 197
9F. The next admissible set 212
Exercises 216
References 220
Index 224
Index of symbols 229

Produkt-Details

• Erscheint lt. Verlag: 1.4.2000
• Sprache: englisch
• Themenwelt: Informatik ► Software Entwicklung ► User Interfaces (HCI)
• Themenwelt: Informatik ► Theorie / Studium ► Algorithmen
• Themenwelt: Mathematik / Informatik ► Mathematik ► Allgemeines / Lexika
• Themenwelt: Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre
• Themenwelt: Naturwissenschaften
• Themenwelt: Technik
• ISBN-10: 0-08-095487-1 / 0080954871
• ISBN-13: 978-0-08-095487-5 / 9780080954875