If $\mu$ is an ordinal, let us call a function $F : \mu\rightarrow (\mathbb{N} \rightarrow \mathbb{N})$ an ordinal hierarchy up to $\mu$ if for all $\alpha < \beta<\mu, F(\beta)$ eventually outgrows $F(\alpha)$. My question is, what is the smallest ordinal $\mu$ such that no ordinal hierarchy up to $\mu$ consists entirely of total recursive functions?
Is it $\omega_1$, or the Church-Kleene ordinal, or something in between?
Best Answer
We can whip up a family $(f_q)_{q\in\mathbb{Q}}$ of recursive functions such that $$p<q\quad\iff\quad f_p<<f_q$$ (where "$<<$" means "dominates"). Since every countable linear order embeds into $\mathbb{Q}$, this means that we can achive every countable ordinal in particular, and so the answer to your question is $\omega_1$.
In slightly more detail, for each $n$ let $\triangleleft_n$ be the lexicographic order of the set of binary strings of length $n$. So for example $n=2$ looks like $$00\triangleleft_201\triangleleft_210\triangleleft_211.$$ For each binary string $\sigma$ let $p(\sigma)$ be the position of $\sigma$ in the $\triangleleft_{\vert\sigma\vert}$-ordering (so e.g. $p(00)=0, p(01)=1,$ etc.).
Now given $f\in 2^\omega$ let $$\hat{f}:\omega\rightarrow\omega: n\mapsto p(f\upharpoonright n).$$ It's easy to check that if $f$ is lexicographically less than $g$ then $\hat{f}<<\hat{g}$.
Now consider the set $$\{\hat{f}: f\in REC, f\mbox{ not constant}\}$$ (where $REC$ is the set of recursive infinite binary sequences). This is a countable dense linear order without endpoints with respect to the domination ordering - hence isomorphic to $\mathbb{Q}$.
Addressing the obvious effectivization: since domination is $\Sigma^0_2$, the bound on "effectively achievable domination orderings" is $\omega_1^{CK}$. Specifically:
For each recursive ordinal $\alpha$ there is a recursive $\alpha$-sequence of functions $(f_\beta)_{\beta<\alpha}$ such that for all $\beta<\gamma<\alpha$ we have $f_\beta<<f_\gamma$.
If $S$ is any $\Sigma^1_1$ set of hyperarithmetic functions (that is, $S$ is a $\Sigma^1_1$ set of indices for $\Sigma^1_1$ functions - remember that a function is $\Sigma^1_1$ iff it is $\Delta^1_1$) which is well-ordered by $<<$, then the ordertype of $S$ under $<<$ is $<\omega_1^{CK}$ (by $\Sigma^1_1$-bounding, noting that domination is $\Sigma^0_2$).
So when we don't control the complexity of the whole family of functions we reach all the way up to $\omega_1$, and if we do control the complexity of the whole family we stop at $\omega_1^{CK}$.