Logical Approaches to Computational Barriers

A sharp phase transition threshold for elementary descent recursive functions

Speaker:
| Andreas Weiermann |

Author(s): |
Andreas Weiermann and Arnoud den Boer |

Slot: |
Array, 17:00-17:20, col. 3 |

Harvey Friedman introduced natural independence results for the Peano axioms via certain schemes of combinatorial well-foundedness. We consider here parameterized versions of this scheme and classify exactly the threshold for the transition from provability to unprovability in $\PA$. For this purpose we fix a natural bijection between the ordinals below $\eo$ and the positive integers and obtain an induced natural well ordering $\prec$ on the positive integers. We classify the asymptotic of the associated global count functions. Using these asymptotics we classify precisely the phase transition for the parameterized hierarchy of elementary descent recursive functions and hence for the combinatorial well-foundedness scheme. Let $\CWF(g)$ be the assertion $$(\forall K)(\exists M)(\forall m_0,\ldots,m_M)[ \forall i\leq M(m_i\leq K+g(i))\rightarrow \exists i<M(m_i\preceq m_{i+1})].$$ Let $f_\al(i):=i^{H_\al^{-1}(i)}$ where $H_\al^{-1}$ denotes the functional inverse of the $\al$-th function from the Hardy hierarchy. Then $$\PA\vdash \CWF(f_\al)\iff \al<\eo.$$

websites: Arnold Beckmann | 2006-06-23 |