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)

We classify the phase transition thresholds from provability to unprovability for certain Friedman-style miniaturizations of Kruskal's Theorem and Higman's Lemma. In addition we prove a new and unexpected phase transition result for ε0. Motivated by renormalization and universality issues from statistical physics we finally state a universality hypothesis.

We give a self-contained and streamlined version of the classification of the provably computable functions of PA. The emphasis is put on illuminating as well as seems possible the intrinsic computational character of the standard cut elimination process. The article is intended to be suitable for teaching purposes and just requires basic familiarity with PA and the ordinals below ε0. (Familiarity with a cut elimination theorem for a Gentzen or Tait calculus is helpful but not presupposed).

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 consider five ordinal notation systems of ε0 which are all well-known and of interest in proof-theoretic analysis of Peano arithmetic: Cantor’s system, systems based on binary trees and on countable tree-ordinals, and the systems due to Schütte and Simpson, and to Beklemishev. The main point of this paper is to demonstrate that the systems except the system based on binary trees are equivalent as structured systems, in spite of the fact that they have their origins in different views and (...) trials in proof theory. This is true while Weiermann’s results based on Friedman-style miniaturization indicate that the system based on binary trees is of different character than the others. (shrink)

Ordinal functions may be iterated transfinitely in a natural way by taking pointwise limits at limit stages. However, this has disadvantages, especially when working in the class of normal functions, as pointwise limits do not preserve normality. To this end we present an alternative method to assign to each normal function f a family of normal functions Hyp[f]=〈fξ〉ξ∈OnHyp[f]=〈fξ〉ξ∈On, called its hyperation, in such a way that f0=idf0=id, f1=ff1=f and fα+β=fα∘fβfα+β=fα∘fβ for all α, β.Hyperations are a refinement of the Veblen hierarchy (...) of f. Moreover, if f is normal and has a well-behaved left-inverse g called a left adjoint, then g can be assigned a cohyperationcoH[g]=〈gξ〉ξ∈OncoH[g]=〈gξ〉ξ∈On, which is a family of initial functions such that gξgξ is a left adjoint to fξfξ for all ξ. (shrink)

In connection with his interest in selfdistributive algebra, Richard Laver established two deep results with potential applications in low-dimen\-sional topology, namely the existence of what is now known as the Laver tables and the well-foundedness of the standard ordering of positive braids. Here we present these results and discuss the way they could be used in topological applications.

We give a survey of current research on Gödel’s incompleteness theorems from the following three aspects: classifications of different proofs of Gödel’s incompleteness theorems, the limit of the applicability of Gödel’s first incompleteness theorem, and the limit of the applicability of Gödel’s second incompleteness theorem.

For a function $f$ with domain $[X]^{n}$, where $X\subseteq\mathbb{N}$, we say that $H\subseteq X$ is canonical for $f$ if there is a $\upsilon\subseteq n$ such that for any $x_{0},\ldots,x_{n-1}$ and $y_{0},\ldots,y_{n-1}$ in $H$, $f=f$ iff $x_{i}=y_{i}$ for all $i\in\upsilon$. The canonical Ramsey theorem is the statement that for any $n\in\mathbb{N}$, if $f:[\mathbb{N}]^{n}\rightarrow\mathbb{N}$, then there is an infinite $H\subseteq\mathbb{N}$ canonical for $f$. This paper is concerned with a model-theoretic study of a finite version of the canonical Ramsey theorem with a largeness (...) condition and also a version of the Kanamori–McAloon principle. As a consequence, we produce new indicators for cuts satisfying $\operatorname{PA}$. (shrink)