9
$\begingroup$

What classification of countable ordinals above the Church–Kleene ordinal $\omega_1^{CK}$ exists?
Are there such things as $\omega_2^{CK}$, $\omega_{\omega_\omega^{CK}}^{CK}$ or $\omega_{\omega_{\omega_{._{._.}}^{CK}}^{CK}}^{CK}$ (a fixed point of $\alpha\mapsto\omega_\alpha^{CK}$)?

$\endgroup$
  • 3
    $\begingroup$ You should read about admissible ordinals. $\endgroup$ – Asaf Karagila Aug 12 '13 at 0:23
11
$\begingroup$

For any real $x$, the ordinal $\omega_1^{CK}(x)$ is well-defined, being the first ordinal $\alpha$ larger than $\omega$ such that $L_\alpha[x]$ is a model of the theory $\mathsf{KP}$.

The ordinals $\alpha$ such that $L_\alpha\models\mathsf{KP}$ are the admissible ordinals, and admissibility is downward absolute, meaning that if $L_\alpha[x]\models\mathsf{KP}$, then $\alpha$ is admissible, see here. The converse is also true, in the sense that if $\alpha$ is countable, and $L_\alpha\models\mathsf{KP}$, then there is a real $x$ such that $\alpha=\omega_1^{CK}(x)$ (and this can be appropriately generalized to include uncountable ordinals).

I have never seen the notation you suggest, but it would be reasonable to use $(\omega_\alpha^{CK}\mid\alpha\in\mathsf{ORD})$ as the increasing enumeration of the admissible ordinals (letting $\omega_0^{CK}=\omega$, if one insists). Of course, once we have this, then fixed points, etc, make sense.

Admissible ordinals have been studied extensively. A very neat result due to Jensen is that, given any increasing sequence of countable admissible ordinals, there is a real $x$ such that those ordinals are the first $\omega$ ordinals admissible over $x$, that is, the first $\omega$ values of $\alpha$ such that $L_\alpha[x]\models\mathsf{KP}$. This he achieved by careful use of class forcing, see Admissible sets in Jensen's page, here. This result has been extensively generalized as well, particularly by Sy Friedman.

Whether there is a different "classification" is possible, but I am not aware of one. For example, one may reasonably want to study the ordinals $\alpha$ such that $L_\alpha\prec L_{\omega_1}$, but all these ordinals are admissible. So are all ordinals that are the height of a transitive model of set theory, or the ordinals that form the well-founded (ordinal) part of an ill-founded $\omega$-model of set theory. These are all certainly interesting subclasses of the admissible ordinals, that deserve their own treatment, as are the ordinals that correspond to the height of models of $\Sigma_n$-$\mathsf{KP}$, see here for some properties.

The study of "computability" over an admissible ordinal is the subject of what is called either higher recursion theory or alpha recursion theory, a subject that makes a neat interplay of classical computability and set theory. A good introduction is Sacks's book.

| cite | improve this answer | |
$\endgroup$

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.