Skip to main content
2 of 3
deleted 193 characters in body
Noah Schweber
  • 21.2k
  • 10
  • 110
  • 331

This is actually much simpler than you may suspect: $\omega_\alpha^{CK}$ is well-defined for every ordinal $\alpha$, not just the countable ones, if we use the set-theoretic as opposed to computability-theoretic definition. Specifically, we define $\omega_\alpha^{CK}$ as the unique ordinal $\eta$ such that

  • $L_\eta\models$ KP (that is, $\eta$ is admissible)

and

  • $\{\gamma<\eta: L_\gamma\models\mbox{ KP}\}$ has ordertype $\alpha$.

That is, $\omega_\alpha^{CK}$ is the $\alpha$th admissible ordinal. The agreement with the computability-theoretic definition at countable levels is a theorem of Sacks: specifically, a countable ordinal is admissible iff it is the least ordinal with no $r$-computable copy for some real $r$.

For example, it's easy to check that in fact $$\omega_1=\omega^{CK}_{\omega_1}$$ that is, $\omega_1$ is a fixed point of the "admissible-counting" function. (It's definitely not the least fixed point, of course.)


Via forcing, we can give a computability-theoretic interpretation of $\omega_\alpha^{CK}$ even when $\alpha$ is uncountable (CAVEAT: this is my own work, so you should take my approval of it with a grain of salt):

  • Say that an ordinal $\gamma$ is generically Church-Kleene if in some generic extension of the universe in which $\gamma$ is countable, there is some real $r$ such that $\gamma$ is the least ordinal with no $r$-computable copy.

  • By Shoenfield's absoluteness theorem, we can replace "some generic extension" with "every generic extension" above; in particular, this means that this agrees with the usual notion when $\gamma$ is countable.

  • Then we can prove - by "genericizing" Sacks' theorem - that $\omega^{CK}_\alpha$ is exactly the $\alpha$th generically Church-Kleene ordinal; that is, $\omega_\alpha^{CK}$ is the unique generically Church-Kleene ordinal such that the set of smaller generically Church-Kleene ordinals has ordertype $\alpha$.

It's worth contrasting this with the perspective given by admissible recursion theory: in general, the supremum of the $\alpha$-recursive well-orderings of $\alpha$ is vastly smaller than the next admissible above $\alpha$. This is true, for example, when $\alpha=\omega_1$. Ordinals where this doesn't happen are called Gandy ordinals, and in a precise sense, most ordinals - even most countable ordinals - are not Gandy.

Noah Schweber
  • 21.2k
  • 10
  • 110
  • 331