Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
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