Kleene's O

From Wikipedia, the free encyclopedia

In set theory and computability theory, Kleene's $\mathcal{O}$ is a subset of the natural numbers when regarded as ordinal notations. It is the universal system of ordinal notations in the sense that any specific set of ordinal notations can be mapped into it in a straight-forward way. However, this very universality makes it hard to work with for some purposes. In particular, each scheme of ordinal notations which people use in practice is recursive when taken as a whole, while the well-founded part of Kleene's scheme, Kleene's $\mathcal{O}$ , is $\Pi^1_1$ when taken as a whole.

[edit] Kleene's $\mathcal{O}$

The basic idea of Kleene's system of ordinal notations is to build up ordinals programmatically. The standard definition proceeds via transfinite induction:

The natural number 0 denotes the ordinal 0.
If the ordinal α is denoted by the natural number i, then 2ⁱ denotes the successor of α, i.e. α+1.
If {e} is the e-th partial recursive function and all its values are members of Kleene's $\mathcal{O}$ , then 3·5^e denotes the limit of γ_k where γ_k is denoted by {e}(k) for every natural number k.

Kleene's $\mathcal{O}$ is then defined to be a particular set of such notations avoiding duplicates. This definition has the advantages that one can recursively enumerate the predecessors of a given ordinal (though not in order) and that the notations are downward closed, i.e., if there is a notation for γ and α < γ then there is a notation for α.

The first ordinal that doesn't have a notation is called the Church–Kleene ordinal and denoted by $\omega^{CK}_1$ . The ordinals with a notation in Kleene's $\mathcal{O}$ are exactly the recursive ordinals. The fact that every notation in Kleene's $\mathcal{O}$ corresponds to a recursive ordinal can be seen to follow from the downward closure and ability to recursively enumerate the notations for ordinals below a particular ordinal notation (define your relation for numbers below s on the ordinals enumerated by stage s). This also demonstrates that no other system of ordinal notations can denote any ordinal greater than or equal to $\omega^{CK}_1$ without sacrificing downward closure or the ability to recursively enumerate smaller notations.