A Model–Theoretic Approach to Proof Theory (eBook)

Henryk Kotlarski (Autor)

Zofia Adamowicz, Teresa Bigorajska, Konrad Zdanowski (Herausgeber)

eBook Download: PDF

2019 | 1st ed. 2019
XVIII, 109 Seiten
Springer International Publishing (Verlag)
978-3-030-28921-8 (ISBN)

Infos

This book presents a detailed treatment of ordinal combinatorics of large sets tailored for independence results. It uses model theoretic and combinatorial methods to obtain results in proof theory, such as incompleteness theorems or a description of the provably total functions of a theory.

In the first chapter, the authors first discusses ordinal combinatorics of finite sets in the style of Ketonen and Solovay. This provides a background for an analysis of subsystems of Peano Arithmetic as well as for combinatorial independence results. Next, the volume examines a variety of proofs of Gödel's incompleteness theorems. The presented proofs differ strongly in nature. They show various aspects of incompleteness phenomena. In additon, coverage introduces some classical methods like the arithmetized completeness theorem, satisfaction predicates or partial satisfaction classes. It also applies them in many contexts. 

The fourth chapter defines the method of indicators for obtaining independence results. It shows what amount of transfinite induction we have in fragments of Peano arithmetic. Then, it uses combinatorics of large sets of the first chapter to show independence results. The last chapter considers nonstandard satisfaction classes. It presents some of the classical theorems related to them. In particular, it covers the results by S. Smith on definability in the language with a satisfaction class and on models without a satisfaction class. 

Overall, the book's content lies on the border between combinatorics, proof theory, and model theory of arithmetic. It offers readers a distinctive approach towards independence results by model-theoretic methods.

Henryk Kotlarski (1949 - 2008) published over forty research articles, most of  them devoted to model theory of Peano arithmetic. He studied nonstandard satisfaction classes, automorphisms of models of Peano arithmetic, clasification of elementary cuts, ordinal combinatorics of finite sets in the style of Ketonen and Solovay, and independence results.

Zofa Adamowicz was a colleague of Henryk Kotlarski for about forty years. They did not write a joint paper but they had a lot of discussions and inspired one another. She shared the main interests of Henryk, in partcular the interest in the incompleteness phenomenon and various proofs of the second Gödel incompleteness theorem.

Teresa Bigorajska is a PhD student of Zofia Adamowicz and a major collaborator of Henryk Kotlarski during his last years. They worked together on ordinal combinatorics of finite sets - a notion heavily used in the book. They studied combinatorial properties of partitions and trees with respect to the notion of largness in the style of Ketonen and Solovay. They developed the machinery for proving independence results presented in the book.

Konrad Zdanowski's research interests focus on theories of arithmetic,  intuitionistic logic, and philosophy. Konrad Zdanowski worked with Henryk Kotlarski on one of his last articles and, through many conversations, he learned from Henryk  some of his approach to arithmetic.

Inhalt

A Note From the Editors 8
References 10
A Letter From Henryk Kotlarski 11
Preface 13
References 15
Contents 16
1 Some Combinatorics 1
1.1 Infinite Ramsey Theorem 18
1.2 Finite Ramsey Theorem 21
1.3 Some Lower Bounds: Classic 22
1.4 Ordinals Below ?0 24
1.5 Hardy Hierarchy 31
1.6 Approximating Functions 35
1.7 Hardy Largeness and Partitioning Elements 37
1.8 Iterations of Hardy Functions 43
1.9 An Upper Bound 44
1.10 Some Lower Bounds: Hardy 49
References 53
2 Some Model Theory 55
2.1 Unions of Chains 55
2.2 The Recursive Saturation and Resplendency 56
2.3 The Theorem of Chang and Makkai 57
References 57
3 Incompleteness 59
3.1 The Arithmetized Completeness Theorem 61
3.2 The Original Approach 64
3.3 Formalized Incompleteness Theorems 68
3.4 Satisfaction Classes 69
3.5 Tarski's Theorem 72
3.6 Scott and Kreisel's Proofs 72
3.7 Jech's Argument 74
3.8 Nonstandard Models and Incompleteness 75
3.9 Incompleteness Theorems via Berry's Paradox 78
3.10 Incompleteness via Grelling's Antinomy 81
3.11 ?1–Closed Models 82
3.12 Some Extensions of PA 84
References 86
4 Transfinite Induction 1
4.1 Indicators 88
4.2 Transfinite Induction in PA 89
4.3 Totality of Functions in Hardy Hierarchy 92
4.4 Hardy Largeness and Indicators 95
References 102
5 Satisfaction Classes 103
5.1 Satisfaction Classes: Generalities 103
5.2 Noninductive Satisfaction Classes 105
5.3 Inductive Full Satisfaction Classes 118
References 119
Appendix A Index 121
Index 121

Produkt-Details

• Erscheint lt. Verlag: 26.9.2019
• Reihe/Serie: Trends in Logic
• Reihe/Serie: Trends in Logic
• Zusatzinfo: XVIII, 109 p. 53 illus., 1 illus. in color.
• Sprache: englisch
• Themenwelt: Geisteswissenschaften ► Philosophie ► Allgemeines / Lexika
• Themenwelt: Mathematik / Informatik ► Mathematik
• Schlagworte: Arithmetized Completeness Theorem • Combinatorics of Alfa Large Sets • Gödel's Incompleteness Theorems • Hardy Hierarchy of Functions • Independence Results for Peano Arithmetic • Ketonen-Solovay Largeness Notion • model theoretic • Model Theory of Arithmetic • Nonstandard Satisfaction Classes • ordinal combinatorics • Proofs of Incompleteness Theorems • subsystems of Peano Arithmetic • Transfinite Induction in Arithmetic
• ISBN-10: 3-030-28921-4 / 3030289214
• ISBN-13: 978-3-030-28921-8 / 9783030289218