Sentences Undecidable in Formalized Arithmetic (eBook)

Lev D. Beklemishev (Autor)

eBook Download: PDF

2000 | 1. Auflage
116 Seiten
Elsevier Science (Verlag)
978-0-08-095730-2 (ISBN)

Infos

Provability, Computability and Reflection

---

Sentences Undecidable in Formalized Arithmetic

Inhalt

Front Cover 1
Sentences Undecidable in Formalized Arithmetic: An Exposition of the Theory of Kurt Gödel 4
Copyright Page 5
Preface 6
Contents 8
Introduction 10
Chapter I. Auxiliary notions and theorems of arithmetic 23
1. Mapping of integers onto pairs and triples of integers 23
2. Mapping of integers onto finite sequences of integers 24
3. Logical symbols 26
4. Relations and functions 27
5. Inductive definitions 30
Chapter II. The system (S) and its syntax 33
1. Preliminary description of the system 33
2. Expressions and integers 34
3. Properties of functional forms and matrix forms 38
4. Explicit definitions of sets Jf, IRf, and of functions Oc, Ind, and S 41
5. Axioms of (S) 46
6. Formal proofs 49
Chapter III. Arithmetical theorems provable in (S) 52
1. Abbreviations 52
2. The propositional calculus 52
3. The functional calculus 53
4. Theory of identity 54
5. Induction 56
6. Addition and multiplication of digits 58
7. Theorems on inequalities 59
8.Matrices satisfied by exactly one digit 63
Chapter IV. Semantics of (S) 65
1. Representability of infinite sequences 65
2. Values of functional forms and the notion of satisfaction for matrix forms 66
3. Inductive definition of Val(f, m) and GtSf(F, m) 67
4. Explicit definition of Val and GtSf 69
5. Class Lr 72
Chapter V. Recursivity and definability of functions and relations 82
1. The notion of A-definability 82
2. General properties of 8-definable functions and relations 84
3. Recursivity of functions and relations corresponding to the syntactical notions 89
4. A theorem concerning the min-operator 91
5. Recursively enumerable sets 95
Chapter VI. Proofs of incompleteness theorems 97
1. A-undefinability of the set LA 97
2. Proofs of the incompleteness theorem 99
3. Generalizations 106
4. Discussion of the incompleteness theorems 108
Appendix. Some further results of gödel's theory 112
1. Undecidability of the sentence expressing the consistency of (S) 112
2. Problem of truth of undecidable sentences 116
3. Sentences provable simultaneously in (S) and (S1) 121
Bibliography 125

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 ► Logik / Mengenlehre
• Themenwelt: Naturwissenschaften
• Themenwelt: Technik
• ISBN-10: 0-08-095730-7 / 0080957307
• ISBN-13: 978-0-08-095730-2 / 9780080957302