Phase transitions of iterated Higman-style well-partial-orderings

Abstract

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 ${\left({\rm S}\text{\textsc{eq}}^{d}, \trianglelefteq _{d}\right)}$ in question, d >  1, we fix a natural extension of Peano Arithmetic, ${T \supseteq \sf{PA}}$ , that proves the corresponding second-order sentence ${\sf{WPO}\left({\rm S}{\textsc{eq}}^{d}, \trianglelefteq _{d}\right) }$ . Having this we consider the following parametrized first-order slow well-partial-ordering sentence ${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{d}, \trianglelefteq _{d}, r\right):}$

$$\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)$$

$$\left( \left( \forall i\leq M\right) \left( \left| x_{i}\right| < K + r \left\lceil \log _{d} \left( i+1\right) \right\rceil \right)\rightarrow \left( \exists i < j \leq M \right) \left(x_{i} \trianglelefteq _{d} x_{j}\right) \right)$$

for a natural additive Seq^d-norm |·| and r ranging over EFA-provably computable positive reals, where EFA is an abbreviation for IΔ ₀ + exp. We show that the following basic phase transition clauses hold with respect to ${T = \Pi_{1}^{0}\sf{CA}_{ < \varphi ^{_{\left( d-1\right) }} \left(0\right) }}$ and the threshold point1.

• 1. If r <  1 then ${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{d}, \trianglelefteq _{d},r \right) }$ is provable in T.

• 2. If ${r > 1}$ then ${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{d}, \trianglelefteq _{d},r \right) }$ is not provable in T.

Moreover, by the well-known proof theoretic equivalences we can just as well replace T by PA or ACA ₀ and ${\Delta _{1}^{1}\sf{CA}}$ , if d =  2 and d =  3, respectively.In the limit case d → ∞ we replaceEFA-provably computable reals r by EFA-provably computable functions ${f: \mathbb{N} \rightarrow \mathbb{R}_{+}}$ and prove analogous theorems. (In the sequel we denote by ${\mathbb{R}_{+}}$ 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

• 3. ${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{2}, \trianglelefteq _{2}, 1\right)}$ 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 ${1_{\alpha }\left( i\right)\,{:=}\,1+\frac{1}{H_{\alpha }^{-1}\left(i\right) }, H_{\alpha}}$ being the familiar fast growing Hardy function and ${H_{\alpha }^{-1}\left( i\right)\,{:=}\,\rm min \left\{ j \mid H_{\alpha } \left ( j\right) \geq i \right\}}$ the corresponding slowly growing inversion.

• 4. If ${\alpha < \varepsilon _{0}}$ , then ${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{2}, \trianglelefteq _{2}, 1_{\alpha}\right)}$ is provable in T = PA.

• 5. ${\sf{SWP}\left( {\rm S}\text{\textsc{eq}}^{2}, \trianglelefteq _{2},1_{\varepsilon _{0}}\right)}$ is not provable in T = PA.

We conjecture that this pattern is characteristic for all ${T\supseteq \sf{PA}}$ under consideration and their proof-theoretical ordinals o (T ), instead of ${\varepsilon _{0}}$ .