Phase transitions in axiomatic thought [Elektronische Ressource] / vorgelegt von Gyesik Lee

Sujets

• Mathematics

Informations

• Publié par: westfalische_wilhelms-universitat_munster
• Publié le: 01 janvier 2005
• Nombre de lectures: 17
• Langue: English

Extrait

Gyesik Lee
Phase Transitions in Axiomatic Thought
2005Mathematik
Phase Transitions in Axiomatic Thought
Inaugural-Dissertation
zur Erlangung des Doktorgrades
der Naturwissenschaften im Fachbereich
Mathematik und Informatik
der Mathematisch-Naturwissenschaftlichen Fakult¨at
der Westf¨alischen Wilhelms-Universit¨at Mu¨nster
vorgelegt von
Gyesik Lee
aus Kyunggi-Do, Su¨dkorea
– 2005 –Dekan: Prof. Dr. K. Hinrichs
Erster Gutachter: Prof. Dr. A. Weiermann
Zweiter Gutachter: Prof. Dr. R. D. Schindler
Tag der mu¨ndlichen Pru¨fung: 29. 04. 2005
Tag der Promotion: 13. 07. 2005
iiTo my family
and
all my Ourtown friendsAbstract
An aspect of the thesis is to investigate well-known ordinal notation systems for
PA. It will be shown that the so-called phase transition phenomenon can be
observed, i.e., there are thresholds between provability and unprovability. This
investigation leads to a comparison of the ordinal notation systems.
The thesis gives also a guide how one can generally establish such phase tran-
sitions in every logic system which is strong enough in the sense of G¨odel. We
shall see that Friedman style miniaturizations play the central role.
Another point of the thesis is the parametrized version of the Kanamori-
McAloon principle. This variants of the finite Ramsey theorem is equivalent to
theParis-Harringtonprinciple. Itwill beshownthatphasetransitions occurwith
respect to the provability of the Kanamori-McAloon principle as the parameter
function varies.
vContents
Abstract v
1 Introduction 1
1.1 Phase transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.1 Well-partial-ordering . . . . . . . . . . . . . . . . . . . . . 6
1.3.2 Friedman style miniaturizations . . . . . . . . . . . . . . . 7
1.3.3 Concrete mathematics . . . . . . . . . . . . . . . . . . . . 8
1.3.4 Basic functions and conventions . . . . . . . . . . . . . . . 14
1.4 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
I Ordinal Notation Systems 17
2 Intrinsic differences 19
2.1 The Cantor system . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Binary trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Intrinsic isomorphisms 25
3.1 The graded provability algebra . . . . . . . . . . . . . . . . . . . . 26
3.2 Worms, Hydras, and tree-ordinals . . . . . . . . . . . . . . . . . . 28
3.3 Schu¨tte-Simpson’s ONS . . . . . . . . . . . . . . . . . . . . . . . 40
3.4 Phase transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
II Ramsey Functions 49
4 Finite Ramsey theorems 51
4.1 Paris-Harrington vs. Kanamori-McAloon . . . . . . . . . . . . . . 53
4.2 Ramsey functions and provability . . . . . . . . . . . . . . . . . . 57
5 Fast growing functions 63
5.1 Ackermannian Ramsey functions . . . . . . . . . . . . . . . . . . 63
5.2 Fast growing Ramsey functions . . . . . . . . . . . . . . . . . . . 66
viiIII Beyond PA 83
ω6 Kruskal’s theorem and ϑΩ 85
6.1 Kruskal’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
ω6.2 Ordinal notation systems of ϑΩ . . . . . . . . . . . . . . . . . . 87
6.3 Generating functions . . . . . . . . . . . . . . . . . . . . . . . . . 90
16.4 Phase transitions in ACA +Π -BI . . . . . . . . . . . . . . . . . 950 2
Bibliography 101
Index 107
List of Symbols 109