The Church-Kleene ordinal, $\omega_1^{ck}$

From Cantor's Attic
Jump to: navigation, search

The Church-Kleene ordinal $\omega_1^{ck}$ is the supremum of the computable ordinals, where an ordinal $\alpha$ is computable if there is a computable relation $\lhd$ on $\mathbb{N}$ of order type $\alpha$, that is, such that $\langle\alpha,\lt\rangle\cong\langle\mathbb{N},\lhd\rangle$.

This ordinal is closed under all of the elementary ordinal arithmetic operations, such as successor, addition, multiplication and exponentiation.

Depending on conventions, there are two possibilities for where \(\omega_1^{ck}\) appears on the hierarchy of admissible ordinals:

  • The Church-Kleene ordinal is the least admissible ordinal. This is when Kripke-Platek set theory is considered to include the axiom of infinity, so \(L_\omega\not\vDash\textrm{KP}\).
  • \(\omega\) and \(\omega_1^{ck}\) are the two smallest admissible ordinals. This is when Kripke-Platek set theory is not considered to include the axiom of infinity, so \(L_\omega\vDash\textrm{KP}\).

Relativized Church-Kleene ordinal

The Church-Kleene idea easily relativizes to oracles, where for any real $x$, we define $\omega_1^x$ to be the supremum of the $x$-computable ordinals. This is also the least admissible ordinal relative to $x$, and every countable successor admissible ordinal is $\omega_1^x$ for some $x$. Note that here, \(\omega_1^x\) doesn't denote the set defined by a relativized definition of \(\omega_1\), like what \(\omega_1^L\) often denotes.

Friedman, Jensen, and Sacks proved that any countable admissible ordinal is of the form \(\omega_1^x\) for some real \(x\). (source)


    This article is a stub. Please help us to improve Cantor's Attic by adding information.