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

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

English
121 Pages
Read
Download
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Description

Gyesik LeePhase Transitions in Axiomatic Thought2005MathematikPhase Transitions in Axiomatic ThoughtInaugural-Dissertationzur Erlangung des Doktorgradesder Naturwissenschaften im FachbereichMathematik und Informatikder Mathematisch-Naturwissenschaftlichen Fakult¨atder Westf¨alischen Wilhelms-Universit¨at Mu¨nstervorgelegt vonGyesik Leeaus Kyunggi-Do, Su¨dkorea– 2005 –Dekan: Prof. Dr. K. HinrichsErster Gutachter: Prof. Dr. A. WeiermannZweiter Gutachter: Prof. Dr. R. D. SchindlerTag der mu¨ndlichen Pru¨fung: 29. 04. 2005Tag der Promotion: 13. 07. 2005iiTo my familyandall my Ourtown friendsAbstractAn aspect of the thesis is to investigate well-known ordinal notation systems forPA. It will be shown that the so-called phase transition phenomenon can beobserved, i.e., there are thresholds between provability and unprovability. Thisinvestigation 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. Weshall 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 totheParis-Harringtonprinciple.

Subjects

Informations

Published by
Published 01 January 2005
Reads 17
Language English
Report a problem

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