Ordinal notations and the Church-Kleene Ordinal

108 Views Asked by At

According to Kleene, an $r$-system is a pair $(S, |\cdot|)$ where $S\subseteq\mathbb{N}$ and $|\cdot|$ maps $S$ to countable ordinals, such that

  1. There is a partial recursive $K(x)$, such that $K(x) = 0$ iff $|x| = 0$, $K(x) = 1$ iff $|x|$ is a successor ordinal and $K(x) = 2$ iff $|x|$ is a limit ordinal.
  2. There is a partial recursive $P(x)$, such that for all $x\in S$ with $K(x) = 1$ we have $P(x)\in S$ with $|P(x)| + 1 = |x|$.
  3. There is a partial recursive $Q(x, t)$, such that for all $x\in S$ with $K(x) = 2$ we have $Q(x, t)\in S$ for all $t$ and $|Q(x, t)|$ is strictly increasing in $t$ with limit $|x|$.

Now the well-known Church-Kleene ordinal is (by definition) the supremum of all ordinals that have a name in some $r$-system.

Say we restrict to those $r$-systems where we additionally require that the set $S$ should be recursive. Then what is the limit of all ordinals that have a name in such a restricted $r$-system?

1

There are 1 best solutions below

5
On

It's still $\omega_1^{CK}$. In fact, $\omega_1^{CK}$ is extremely robust; it is for example the supremum of the ordertypes of the polynomial-time-computable well-orderings of $\mathbb{N}$, as well as the supremum of the ordertypes of the $\Sigma^1_1$ well-orderings of $\mathbb{N}$. The former claim is pretty easy to show, and is a good exercise; the latter claim is a hard theorem (see Sacks' book Higher recursion theory).

(In fact, my impression is that most modern texts do define $\omega_1^{CK}$ as the supremum of the ordertypes of the computable well-orderings of computable subsets of $\mathbb{N}$.)