# How far can an ordinal hierarchy of recursive functions go?

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?

We can whip up a family $$(f_q)_{q\in\mathbb{Q}}$$ of recursive functions such that $$p (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<.

• 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}$$.

• Can you elaborate on the family indexed by rationals? Also, why is a $\Sigma_1^1$ set of hyperarithmetic functions an interesting thing to consider? How is it related to the notation of a domination ordering being effectively achievable? – Keshav Srinivasan Nov 14 '19 at 3:57
• @KeshavSrinivasan Re: $\Sigma^1_1$ (instead of, say, recursive), I'm just illustrating how even a very loose restriction drops us all the way to $\omega_1^{CK}$. It might be snappier to say "no recursive family of recursive functions has ordertype $\omega_1^{CK}$ with respect to the domination ordering," but what I've written is much stronger than that. – Noah Schweber Nov 14 '19 at 4:14
• @KeshavSrinivasan I've added a description of how to get such a family. – Noah Schweber Nov 14 '19 at 4:31