Church-Kleene ordinal: Difference between revisions
no edit summary
RhubarbJayde (talk | contribs) (Created page with "<nowiki>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 the...") |
RhubarbJayde (talk | contribs) No edit summary |
||
Line 3:
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 numbers|epsilon number]], [[Strongly critical ordinal|strongly critical]], and more.
<nowiki>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 </nowiki>[[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<nowiki>''</nowiki>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.
<nowiki>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.</nowiki>
| |||