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

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – Keshav Srinivasan Nov 14 '19 at 3:57
  • $\begingroup$ @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. $\endgroup$ – Noah Schweber Nov 14 '19 at 4:14
  • $\begingroup$ @KeshavSrinivasan I've added a description of how to get such a family. $\endgroup$ – Noah Schweber Nov 14 '19 at 4:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.