Intuition behind recursive ordinals and their relationship to ordinal functions

Question

From what I understand, an ordinal $\alpha$ is recursive if it is the order type of a subset of $\mathbb{N}$ that is well-ordered by a recursive relation $\prec$ (meaning, $\mathbb{1}_\prec:\mathbb{N}\to\{0,1\}$ is recursive). I am mostly happy with this definition. I can see that the ordinals that come out of it are nice and `graspable', that we can construct many of them through standard operations + appealing to fixed points of normal, fast growing functions, though exactly why will be part of my question.

• what is the intuition here? Or in other words, why are we interested in order types of such well-orderings of $\mathbb{N}$? I can see that ordinals like $\omega^{\omega},\,\Gamma_0$ are nice to have classified in one group, (and are relevant when talking about recursive axiom systems? Not something I know much about though), but I assume there is a deeper motivation that escapes me.

• the construction of these ordinals, through functions like the Veblen function or the $\psi$ function: why exactly are the resulting ordinals recursive? I can see that the ordinals are generated recursively in the class of ordinals, but I am having trouble seeing how these functions, defined recursively, relate to the recursive well-orders we want on $\mathbb{N}$/a subset.

For example on the second point, we can define a Veblen function by $\phi_0(\alpha)=\omega^{\alpha}$ and $\phi_{\gamma}(\alpha)$ the $\alpha^{\rm th}$ common fixed point of $\phi_{\beta}$ for all $\beta<\gamma$. $\phi_{\gamma}$ is thus defined by a recursive scheme. But then why, for instance, does this mean there is a recursive well-ordering of $\mathbb{N}$ of order type say, $\phi_{\epsilon_0}(\omega^{\omega})?$ Or if we define $\Gamma_0$ as the least fixed point of $\alpha\mapsto \phi_{\alpha}(0)$, how do we know in advance $\Gamma_0$ is recursive?

The connection is probably obvious but I'm having trouble seeing how this pieces together and would love some help.

Answer 1

This is more of an extended basic remark than an answer. When thinking of a functions like $f(x)=\omega^x$ etc., one alternative perspective is to think of them in terms of their equivalent definition. For example, for the above example, we can define $f$ by writing $f(x+1)=f(x) \cdot \omega$ and when $x$ is a limit writing $f(x)=\operatorname{sup}\,\{\,f(i)\,|\,i \in \mathrm{Ord}\wedge i<x\,\}$. Now because we have $f(0) \in \omega_{CK}$, it isn't difficult to see that $f(\omega),f(\omega^2) \in \omega_{CK}$ and so on.

Note that the observations in previous paragraph are general. Whenever a function $f$ has a template such as in the first paragraph and it also satisfies the following two properties then in that case we automatically get something like $f(1),f(\omega),f(\omega^2) \in \omega_{CK}$ and so on. $(1)$ $f(0) \in \omega_{CK}$ $(2)$ The second property is a bit longer to describe. It is that there exists a (single) program, such that for any arbitrary $x$, whenever a well-order (on $\mathbb{N}$) of order-type $f(x)$ (assuming $f(x)<\omega_1$) is given to it then the program outputs some well-order (on $\mathbb{N}$) of order-type $f(x+1)$. Note that the following follows necessarily from the second condition: "$f(x) \in \omega_{CK}$ implies $f(x+1) \in \omega_{CK}$".

In fact, since we are exclusively focusing on normal functions, so let's assume $f$ to be normal. It isn't too difficult to show that the first fixed point of $f$ will always be recursive (assuming that it satisfies the two condition in previous paragraph). As such it isn't that clear why that should be the case. As a starting point, it isn't difficult to observe that we will have ordinals like $f(f(0))$, $f(f(f(0)))$ and $f^4(0)$. This is suggestive of checking $\operatorname{sup}\{\,f^n(0)\,|\,n\in \mathbb{N}^+ \,\}$.

The problem is that writing the details of something like this is definitely longer (and it becomes more and more difficult as we consider more difficult operations). In general, I suspect that this is why a direct approach like this becomes inefficient. For the specific cases I described, since they are among the simplest ones, it should be possible to write the details (in a reasonable time frame) if one is really interested. I haven't tried it though.

---

For something like $\Gamma_0$, intuitively we know that for the function $f(x)= \phi_{x}(0)$ we will have $f(0) \in \omega_{CK}$ and the second property discussed earlier true as well. Hence once we are confident about what I wrote in the first part of this answer, we can be confident that the first fixed point of this function be also be recursive.

But of course the harder part is showing that the function $x \mapsto \phi_{x}(0)$ satisfied the two conditions. I don't know whether this really helps or not but going back to a function like $f(x)=\omega^x$, let's use $f'(x)$ to denote the $x$-th fixed point of $f$. As we observed that $f'(0)$ will be recursive. We can extend this to show (once again) that something like $f'(1)$,$f'(2)$, $f'(\omega)$, $f'(\omega^2)$ will be recursive. $f'(1)$ can be shown to be recursive because it is equal to $\operatorname{sup}\{\,f^n(f'(0)+1)\,|\,n\in \mathbb{N}^+ \,\}$. Actually, once we show that $f'(0) \in \omega_{CK}$ and that there is a "uniform" way to move from $f'(x)$ to $f'(x+1)$ (second condition), we get $f''(0)$ as recursive due to the result in first half of the answer.

Answer 2

While it is of admittedly limited pedagogical value early on, there is a general result which can serve as a "nuke" for showing that many ordinals of interest are in fact recursive. Despite its complexity I do think it is at least worth mentioning early on, so I've done so here.

The standard source for this material is Sacks' book Higher recursion theory.

---

Let $\omega_1^{CK}$ be as usual the smallest non-recursive ordinal, that is, the smallest (infinite) ordinal such that there is no recursive well-ordering of $\mathbb{N}$ achieving its ordertype. The result I have in mind is the following:

$L_{\omega_1^{CK}}$ satisfies $\mathsf{KP+Inf}$.

(In fact, $\omega_1^{CK}$ is the smallest ordinal with this property - the relevant term here is "admissible ordinal.")

Here $L_{\omega_1^{CK}}$ is the $\omega_1^{CK}$th level of Godel's constructible hierarchy. This hierarchy is defined as follows:

• $L_0=\emptyset$.

• $L_\lambda=\bigcup_{\alpha<\lambda}L_\alpha$ for $\lambda$ limit.

• $L_{\alpha+1}=\mathcal{P}_{def}(L_\alpha)$, where "$\mathcal{P}_{def}$" is the definable powerset operation: $\mathcal{P}_{def}(A)$ is the set of subsets of $A$ which are definable in the structure $(A;\in)$. Note that $\vert L_{\alpha+1}\vert\le\vert L_\alpha\vert\cdot\aleph_0$ always, by counting formulas; contrast this with the cumulative ($V$-)hierarchy, which you may have seen before.

Now the $L$-hierarchy is rather complicated, but the key point for our purposes is easy to prove by transfinite induction: $$L_\alpha\cap\mathsf{Ord}=\{\beta:\beta<\alpha\}.$$ In particular, the ordinals in $L_{\omega_1^{CK}}$ are exactly the computable ordinals. $\mathsf{KP+Inf}$ meanwhile is a fragment of $\mathsf{ZFC}$ set theory. Saying that $L_{\omega_1^{CK}}\models\mathsf{KP}$, in conjunction with the observation two sentences prior, implies roughly that any ordinal $\mathsf{KP+Inf}$ can prove exists is recursive. Many basic fixed point theorems for ordinal functions can be proved in $\mathsf{KP}$, and so in turn we get that the associated least fixed points must be computable.