Phase transitions for Gödel incompleteness (Q1006619)

Phase transition is a notion borrowed from physics. An everyday version is that of ice changing into water at \(0^\circ\) C. In logic, the oldest and best-known example is the provability of transfinite induction up to \(\alpha\), \(\text{TI}(\alpha)\), in PA. Gentzen showed in 1943 that \(\text{PA}\vdash \text{TI}(\alpha)\) for any \(\alpha< \varepsilon_0\), but all of a sudden (so to speak) \(\text{PA}\not\vdash \text{TI}(\alpha)\) at \(\alpha= \varepsilon_0\). In this paper, the author considers combinatorial well-foundedness \(\text{CWF}(\beta,c,f_\alpha)\), formulated by H. Friedman. It is, by definition, \[ \forall\,K\,\exists\,L\,\forall\,\alpha_0,\dots, \alpha_L< \beta\;[\forall\,i\leq L\;(c(\alpha_i)< K+ f_\alpha(i)]\to \exists\,i< L\;(\alpha_i\leq \alpha_{i+1}), \] where \(\beta\) is an ordinal, \(c\) is a complexity measure of ordinals by natural numbers, and \(\{f_\alpha\}\) is an increasing -- with respect to majoration -- family of functions parametrized by ordinals. The author considers two complexity measures: the Mahler norm, \(M\), and the Gödel numbering, \(G\). [These are obtained from the Cantor normal form of \(\alpha\) by replacing \(\omega\) by 2, and by successive prime numbers, respectively.] First he establishes asymptotic behaviours of these measures by using Tauberian theorems, etc. (He aptly call them ``main results''.) Since the author considers not only PA but also its subsystems \(\text{I}\Sigma_d\), \(d\in\mathbb{N}\), there are four types of transition theorems: matching the two theories, PA and \(\text{I}\Sigma_d\), with the two measures, \(M\) and \(G\). For the combination of \(\text{I}\Sigma_d\) and \(M\), the theorem runs as follows. First, define the appropriate function \(f_\alpha\) from the Schwichtenberg-Wainer \(F_\alpha\) by means of repeated exponentiation, logarithm, and root. \{It is exhibited, but too complicated to reproduce here.\} Then \(\text{I}\Sigma_d\vdash\text{CWF}(\omega_{d+1}, M,f)\) if \(\alpha< \omega_d\), but \(\not\vdash\) if \(\alpha= \omega_d\). In other combinations, different functions are used, but the pattern of theorems is the same. For PA, it takes the form: \(\text{PA}\vdash\text{CWF}(\varepsilon_0,\cdot,\cdot)\), of course.