Church-Kleene ordinal

The Church-Kleene ordinal, commonly denoted \( \omega_1^{\mathrm{CK}} \) or \( \omega_1^{ck} \) is defined as the supremum of all "recursive ordinals". A recursive ordinal is the order-type of a well-order on the natural numbers which can be computed by a Turing machine. Note that all countable ordinals are the order-type of a well-order on the natural numbers, but there are only countably many Turing machines, and uncountably many countable ordinals, meaning there must be some ordinals which are still countable but they aren't recursive - i.e: they're so large that all well-orders they code are so complex that they are uncomputable. The least such is the Church-Kleene ordinal. Note that there is still a well-order on the natural numbers with order type \( \omega_1^{\mathrm{CK}} \) that is computable with an infinite time Turing machine, since they are able to compute whether a given Turing machine computes a well-order or not,.

Also, note that given computable well-orders on the natural numbers with order types \( \alpha \) and \( \beta \), it is possible to construct computable well-orders with order-types \( \alpha + \beta \), \( \alpha \cdot \beta \) and \( \alpha^{\beta} \) and much more, meaning that the Church-Kleene ordinal is not pathological and in fact a limit ordinal, epsilon number, strongly critical, and more.

It has a variety of other convenient definitions. One of them has to do with the constructible hierarchy - \( \omega_1^{\mathrm{CK}} \) is the least admissible ordinal. In other words, it is the least limit ordinal \( \alpha > \omega \) so that, for any \( \Delta_0(L_\alpha) \)-definable function \( f: L_\alpha \to L_\alpha \), then, for all \( x \in L_\alpha \), \( f''x \in L_\alpha \). That is, the set of constructible sets with rank at most \( \omega_1^{\mathrm{CK}} \) is closed under taking preimages of an infinitary analogue of the primitive recursive functions. Note that this property still holds for \( \Sigma_1(L_\alpha) \)-functions, an infinitary analogue of Turing-computable functions, which makes sense, since the ordinals below \( \omega_1^{\mathrm{CK}} \) are a very robust class and closed under computable-esque functions. It is, in particular, equivalent to the statement: for any \( \Delta_1(L_\alpha) \)-definable function \( f: \alpha \to \alpha \), there is a closure point (equivalent to a fixed point) of \( f \) below \( \alpha \). This also is a good explanation, since it shows it's a limit of epsilon numbers (and thus itself an epsilon number), of strongly critical numbers, etc. and why it's greater than recursive ordinals like the Bird ordinal. However, the case with \( \Sigma_2(L_\alpha) \)-functions produces a much stronger notion known as \( \Sigma_2 \)-admissibility.

Note that, like how there is a fine hierarchy of recursive ordinals and functions on them, there is a fine hierarchy of nonrecursive ordinals, above \( \omega_1^{\mathrm{CK}} \), arguably richer.

One thing to note is that many known ordinal collapsing functions are, or should be, \( \Sigma_1(L_{\omega_1^{\mathrm{CK}}}) \)-definable. Thus, the countable collapse is actually a recursive collapse, and replacing \( \Omega \) with \( \omega_1^{\mathrm{CK}} \) in an ordinal collapsing function is a possibility. While many authors do this, since it allows them to use structure more efficiently and not assume large cardinal axioms, more cumbersome proofs would be necessary, and this has led many authors such as Rathjen to instead opt for the traditional options, or use uncountable intermediates between countable nonrecursive fine structure and large cardinals, such as the reducibility hierarchy.