Phase transitions in axiomatic thought.

*(English)*Zbl 1082.03048
Münster: Univ. Münster, Fachbereich Mathematik und Informatik, Mathematisch-Naturwissenschaftliche Fakultät (Dissertation). viii, 110 p. (2005).

In order to understand the present work, it is useful to recall an interesting theme emerging from recent deep investigations in proof theory, the so-called phase transition phenomenon. Indeed, it has been observed by A. Weiermann [“An application of graphical enumeration to PA”, J. Symb. Log. 68, 5–16 (2003; Zbl 1041.03045)] that, once certain combinatorial statements \(A\) arising in connection with mathematical independence results are relativized to a number-theoretic function parameter \(f\), then there exists a real number \(c\) acting as a threshold between provability and unprovability. For instance, if the function parameter has the form \(f_r(n)= r\log_2 n\), the statement \(A(f_r)\) becomes provable (unprovable) with respect to a given axiomatic system as soon as \(r\leq c\) (\(c<r\)). Remarkably, Weiermann has applied analytic methods. An essential role in these investigations is played by the study of the combinatorial behavior of the norm functions naturally associated to the ordinal notation systems involved in the proof-theoretic analysis of a given theory \(T\). A norm function for a notation system is a suitable function defined on notations with values in natural numbers, such that, for each number \(k\), the inverse image of \(k\) under the given norm is finite. This is a key property for associating suitable analytic objects to notation systems (namely generating functions).

The present dissertation offers a number of new results in the same direction and investigates phase transition in relation to several ordinal notation systems for Peano arithmetic and stronger systems.

Part I consists of two chapters. In Chapter 2 the author surveys a few ordinal notation systems of interest to Peano arithmetic (e.g. the standard system based on Cantor normal forms and the binary trees based upon the binary Veblen function \(\varphi\)). The following question is considered: are there intrinsic differences among diverse natural ordinal systems or, in the opposite direction, do they share intrinsic common properties? The problem is investigated using suitable miniaturizations (i.e. number-theoretic \(\Pi^0_2\)-statements) corresponding to the well-orderedness of ordinal notations and to the well-partial-orderedness of rooted binary trees, which represent ordinals below \(\epsilon_0\). Interestingly, it turns out that the Cantor system differs intrinsically from the tree system.

Chapter 3 establishes intrinsic isomorphisms involving different notation systems, e.g. the Cantor system, the one arising from Beklemishev’s graded algebras [L. D. Beklemishev, “Provability algebras and proof-theoretic ordinals. I”, Ann. Pure Appl. Logic 128, 103–123 (2004; Zbl 1048.03045)] and the Schütte-Simpson system [described by K. Schütte and S. G. Simpson in “Ein in der reinen Zahlentheorie unbeweisbarer Satz über endliche Folgen von natürlichen Zahlen”, Arch. Math. Logik Grundlagenforsch. 25, 75–89 (1985; Zbl 0591.03041)]. The correspondences are further investigated by proving a phase transition theorem which holds uniformly for all systems considered by the author.

Part II (embracing Chapter 4 to Chapter 5) is concerned with Ramsey functions. Chapter 4 deals with a suitable generalization (KM)\(_f\) of the Kanamori-McAloon theorem and its connection with the Paris-Harrington variant of the finite Ramsey Theorem, depending on a function parameter [see A. Kanamori and K. McAloon, “On Gödel incompleteness and finite combinatorics”, Ann. Pure Appl. Logic 33, 23–41 (1987; Zbl 0627.03041); A. Weiermann, “A classification of rapidly growing Ramsey functions”, Proc. Am. Math. Soc. 132, 553–561 (2004; Zbl 1041.03044)]. The author proves results classifying those functions for which (KM)\(_f\) remains independent on Peano arithmetic and its fragments based on induction restricted to \(\Sigma_m\)-conditions.

Chapter 5 classifies those \(f\) such that Ramsey functions \(R_f\) are fast growing; it also yields a purely combinatorial proof of the fact that the Kanamori-McAloon principles imply the Paris-Harrington principles.

In Part III (Chapter 6) the author extends his investigation to the case of systems that are proof-theoretically stronger than predicative analysis. Let \(S\) be the notation system for the so-called Ackermann ordinal (with its associated norm function \(\| -\|\)); \(S\) is known from the proof-theoretic analysis of Kruskal’s theorem [M. Rathjen and A. Weiermann, “Proof-theoretic investigations on Kruskal’s theorem”, Ann. Pure Appl. Logic 60, 49–88 (1993; Zbl 0786.03042)]. \(\text{SWP}(S, \preceq, f)\) is the statement: for every \(K\) there exists \(M\) so big that, for every \(M\)-sequence of ordinal notations in \(S\), \(\alpha_1\ldots \alpha_M\), satisfying \( \|\alpha_i\|<K+f(i)\) (for \(i\leq M)\), then there exist \(i, j\) with \(i<j\) and \(\alpha_i \preceq \alpha_j\). The author shows that the phase transition phenomenon holds for the statement \(\text{SWP}(S, \preceq, f)\) for suitable choices of \(f\) with respect to the subsystem \(\text{ACA}_0+\Pi^1_2-\)BI (i.e. second-order arithmetic based on arithmetical comprehension and the schema of bar induction for \(\Pi^1_2\)-statements). Indeed, there exists a real number \(r_0\) such that, if \(r\leq r_0\), \(f_r(n)=r| n|\) and \(|n|\) is the length of the binary notation for \(n\), then \(\text{SWP}(S, \preceq, f_r)\) is already provable in primitive recursive arithmetic, while it is unprovable in the much stronger \(\text{ACA}_0+\Pi^1_2-\)BI for every \(r>r_0\).

This part requires powerful methods from concrete mathematics (e.g., complex analysis). We believe that this fact is important and it could contribute to raise the interest of the working mathematician towards very abstract parts of logic, ordinal analysis above all, usually rather far apart from mainstream mathematics and applications.

The present dissertation offers a number of new results in the same direction and investigates phase transition in relation to several ordinal notation systems for Peano arithmetic and stronger systems.

Part I consists of two chapters. In Chapter 2 the author surveys a few ordinal notation systems of interest to Peano arithmetic (e.g. the standard system based on Cantor normal forms and the binary trees based upon the binary Veblen function \(\varphi\)). The following question is considered: are there intrinsic differences among diverse natural ordinal systems or, in the opposite direction, do they share intrinsic common properties? The problem is investigated using suitable miniaturizations (i.e. number-theoretic \(\Pi^0_2\)-statements) corresponding to the well-orderedness of ordinal notations and to the well-partial-orderedness of rooted binary trees, which represent ordinals below \(\epsilon_0\). Interestingly, it turns out that the Cantor system differs intrinsically from the tree system.

Chapter 3 establishes intrinsic isomorphisms involving different notation systems, e.g. the Cantor system, the one arising from Beklemishev’s graded algebras [L. D. Beklemishev, “Provability algebras and proof-theoretic ordinals. I”, Ann. Pure Appl. Logic 128, 103–123 (2004; Zbl 1048.03045)] and the Schütte-Simpson system [described by K. Schütte and S. G. Simpson in “Ein in der reinen Zahlentheorie unbeweisbarer Satz über endliche Folgen von natürlichen Zahlen”, Arch. Math. Logik Grundlagenforsch. 25, 75–89 (1985; Zbl 0591.03041)]. The correspondences are further investigated by proving a phase transition theorem which holds uniformly for all systems considered by the author.

Part II (embracing Chapter 4 to Chapter 5) is concerned with Ramsey functions. Chapter 4 deals with a suitable generalization (KM)\(_f\) of the Kanamori-McAloon theorem and its connection with the Paris-Harrington variant of the finite Ramsey Theorem, depending on a function parameter [see A. Kanamori and K. McAloon, “On Gödel incompleteness and finite combinatorics”, Ann. Pure Appl. Logic 33, 23–41 (1987; Zbl 0627.03041); A. Weiermann, “A classification of rapidly growing Ramsey functions”, Proc. Am. Math. Soc. 132, 553–561 (2004; Zbl 1041.03044)]. The author proves results classifying those functions for which (KM)\(_f\) remains independent on Peano arithmetic and its fragments based on induction restricted to \(\Sigma_m\)-conditions.

Chapter 5 classifies those \(f\) such that Ramsey functions \(R_f\) are fast growing; it also yields a purely combinatorial proof of the fact that the Kanamori-McAloon principles imply the Paris-Harrington principles.

In Part III (Chapter 6) the author extends his investigation to the case of systems that are proof-theoretically stronger than predicative analysis. Let \(S\) be the notation system for the so-called Ackermann ordinal (with its associated norm function \(\| -\|\)); \(S\) is known from the proof-theoretic analysis of Kruskal’s theorem [M. Rathjen and A. Weiermann, “Proof-theoretic investigations on Kruskal’s theorem”, Ann. Pure Appl. Logic 60, 49–88 (1993; Zbl 0786.03042)]. \(\text{SWP}(S, \preceq, f)\) is the statement: for every \(K\) there exists \(M\) so big that, for every \(M\)-sequence of ordinal notations in \(S\), \(\alpha_1\ldots \alpha_M\), satisfying \( \|\alpha_i\|<K+f(i)\) (for \(i\leq M)\), then there exist \(i, j\) with \(i<j\) and \(\alpha_i \preceq \alpha_j\). The author shows that the phase transition phenomenon holds for the statement \(\text{SWP}(S, \preceq, f)\) for suitable choices of \(f\) with respect to the subsystem \(\text{ACA}_0+\Pi^1_2-\)BI (i.e. second-order arithmetic based on arithmetical comprehension and the schema of bar induction for \(\Pi^1_2\)-statements). Indeed, there exists a real number \(r_0\) such that, if \(r\leq r_0\), \(f_r(n)=r| n|\) and \(|n|\) is the length of the binary notation for \(n\), then \(\text{SWP}(S, \preceq, f_r)\) is already provable in primitive recursive arithmetic, while it is unprovable in the much stronger \(\text{ACA}_0+\Pi^1_2-\)BI for every \(r>r_0\).

This part requires powerful methods from concrete mathematics (e.g., complex analysis). We believe that this fact is important and it could contribute to raise the interest of the working mathematician towards very abstract parts of logic, ordinal analysis above all, usually rather far apart from mainstream mathematics and applications.

Reviewer: Andrea Cantini (Firenze)