Gödel’s first incompleteness result from 1931 states that there are true assertions about the natural numbers which do not follow from the Peano axioms. Since 1931 many researchers have been looking for natural examples of such assertions and breakthroughs were obtained in the seventies by Jeff Paris [Some independence results for Peano arithmetic. J. Symbolic Logic 43 725–731] , Handbook of Mathematical Logic, North-Holland, Amsterdam, 1977] and Laurie Kirby [L. Kirby, Jeff Paris, Accessible independence results for Peano Arithmetic, Bull. of (...) the LMS 14 285–293]) and Harvey Friedman [S.G. Simpson, Non-provability of certain combinatorial properties of finite trees, in: Harvey Friedman’s Research on the Foundations of Mathematics, North-Holland, Amsterdam, 1985, pp. 87–117; R. Smith, The consistency strength of some finite forms of the Higman and Kruskal theorems, in: Harvey Friedman’s Research on the Foundations of Mathematics, North-Holland, Amsterdam, 1985, pp. 119–136] who produced the first mathematically interesting independence results in Ramsey theory and well-order and well-quasi-order theory .In this article we investigate Friedman-style principles of combinatorial well-foundedness for the ordinals below ε0. These principles state that there is a uniform bound on the length of decreasing sequences of ordinals which satisfy an elementary recursive growth rate condition with respect to their Gödel numbers.For these independence principles we classify their phase transitions, i.e. we classify exactly the bounding conditions which lead from provability to unprovability in the induced combinatorial well-foundedness principles.As Gödel numbering for ordinals we choose the one which is induced naturally from Gödel’s coding of finite sequences from his classical 1931 paper on his incompleteness results.This choice makes the investigation highly non-trivial but rewarding and we succeed in our objectives by using an intricate and surprising interplay between analytic combinatorics and the theory of descent recursive functions. For obtaining the required bounds on count functions for ordinals we use a classical 1961 Tauberian theorem of Parameswaran which apparently is far remote from Gödel’s theorem. (shrink)

It is well known that the Ackermann function can be defined via diagonalization from an iteration hierarchy which is built on a start function like the successor function. In this paper we study for a given start function g iteration hierarchies with a sub-linear modulus h of iteration. In terms of g and h we classify the phase transition for the resulting diagonal function from being primitive recursive to being Ackermannian.

We elaborate Weiermann-style phase transitions for well-partial-orderings (wpo) determined by iterated finite sequences under Higman-Friedman style embedding with Gordeev’s symmetric gap condition. For every d-times iterated wpo \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\left({\rm S}\text{\textsc{eq}}^{d}, \trianglelefteq _{d}\right)}$$\end{document} in question, d > 1, we fix a natural extension of Peano Arithmetic, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${T \supseteq \sf{PA}}$$\end{document}, that proves the corresponding second-order sentence \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\sf{WPO}\left({\rm (...) S}{\textsc{eq}}^{d}, \trianglelefteq _{d}\right) }$$\end{document}. Having this we consider the following parametrized first-order slow well-partial-ordering sentence \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{d}, \trianglelefteq _{d}, r\right):}$$\end{document}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left( \forall K > 0 \right) \left( \exists M > 0\right) \left( \forall x_{0},\ldots,x_{M}\in {\rm S}\text{\textsc{eq}}^{d}\right)$$\end{document}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left( \left( \forall i\leq M\right) \left( \left| x_{i}\right| 1}$$\end{document} then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{d}, \trianglelefteq _{d},r \right) }$$\end{document} is not provable in T.Moreover, by the well-known proof theoretic equivalences we can just as well replace T by PA or ACA0 and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta _{1}^{1}\sf{CA}}$$\end{document}, if d = 2 and d = 3, respectively.In the limit case d → ∞ we replaceEFA-provably computable reals r by EFA-provably computable functions \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${f: \mathbb{N} \rightarrow \mathbb{R}_{+}}$$\end{document} and prove analogous theorems. (In the sequel we denote by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{R}_{+}}$$\end{document} the set of EFA-provably computable positive reals). In the basic case T = PA we strengthen the basic phase transition result by adding the following static threshold clause\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{2}, \trianglelefteq _{2}, 1\right)}$$\end{document} is still provable in T = PA (actually in EFA). Furthermore we prove the following dynamic threshold clauses which, loosely speaking are obtained by replacing the static threshold t by slowly growing functions 1α given by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${1_{\alpha }\left( i\right)\,{:=}\,1+\frac{1}{H_{\alpha }^{-1}\left(i\right) }, H_{\alpha}}$$\end{document} being the familiar fast growing Hardy function and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${H_{\alpha }^{-1}\left( i\right)\,{:=}\,\rm min \left\{ j \mid H_{\alpha } \left ( j\right) \geq i \right\}}$$\end{document} the corresponding slowly growing inversion. If \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\alpha < \varepsilon _{0}}$$\end{document}, then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{2}, \trianglelefteq _{2}, 1_{\alpha}\right)}$$\end{document} is provable in T = PA. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\sf{SWP}\left( {\rm S}\text{\textsc{eq}}^{2}, \trianglelefteq _{2},1_{\varepsilon _{0}}\right)}$$\end{document} is not provable in T = PA. We conjecture that this pattern is characteristic for all \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${T\supseteq \sf{PA}}$$\end{document} under consideration and their proof-theoretical ordinals o (T ), instead of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varepsilon _{0}}$$\end{document}. (shrink)