Kleene's O

The basic idea of Kleene's system of ordinal notations is to build up ordinals in an effective manner. For members ${\displaystyle p}$ of ${\displaystyle {\mathcal {O}}}$, the ordinal for which ${\displaystyle p}$ is a notation is ${\displaystyle |p|}$. ${\displaystyle {\mathcal {O}}}$ and ${\displaystyle <_{\mathcal {O}}}$ (a partial ordering of Kleene's ${\displaystyle {\mathcal {O}}}$) are the smallest sets such that the following holds.

• ${\displaystyle 0\in {\mathcal {O}}\land |0|=0}$.
• ${\displaystyle i\in {\mathcal {O}}\land |i|=\alpha \rightarrow 2^{i}\in {\mathcal {O}}\land |2^{i}|=\alpha +1\land i<_{\mathcal {O}}2^{i}}$
• Suppose ${\displaystyle \{e\}}$ is the ${\displaystyle e}$-th partial computable function. If ${\displaystyle e}$ is total and ${\displaystyle {\textrm {range}}(\{e\})\subset {\mathcal {O}}\land \forall n(\{e\}(n)<_{\mathcal {O}}\{e\}(n+1))}$, then ${\displaystyle 3\cdot 5^{e}\in {\mathcal {O}}\land \forall n,\{e\}(n)<_{\mathcal {O}}3\cdot 5^{e}\land |3\cdot 5^{e}|=\lim _{k}|\{e\}(k)|}$
• ${\displaystyle p<_{\mathcal {O}}q\land q<_{\mathcal {O}}r\rightarrow p<_{\mathcal {O}}r}$

This definition has the advantages that one can computably enumerate the predecessors of a given ordinal (though not in the ${\displaystyle <_{\mathcal {O}}}$ ordering) and that the notations are downward closed, i.e., if there is a notation for ${\displaystyle \gamma }$ and ${\displaystyle \alpha <\gamma }$ then there is a notation for ${\displaystyle \alpha }$. There are alternate definitions, such as the set of indices of (partial) well-orderings of the natural numbers.[1]

• If ${\displaystyle |i|=\alpha }$ and ${\displaystyle |j|=\beta }$ and ${\displaystyle i<_{\mathcal {O}}j\,,}$ then ${\displaystyle \alpha <\beta }$; but the converse may fail to hold.
• ${\displaystyle <_{\mathcal {O}}}$ induces a tree structure on ${\displaystyle {\mathcal {O}}}$, so ${\displaystyle {\mathcal {O}}}$ is well-founded.
• ${\displaystyle {\mathcal {O}}}$ only branches at limit ordinals; and at each notation of a limit ordinal, ${\displaystyle {\mathcal {O}}}$ is infinitely branching.
• Since every computable function has countably many indices, each infinite ordinal receives countably many notations; the finite ordinals have unique notations, ${\displaystyle n}$ usually denoted ${\displaystyle n_{\mathcal {O}}}$.
• The first ordinal that doesn't receive a notation is called the Church–Kleene ordinal and is denoted by ${\displaystyle \omega _{1}^{\text{CK}}}$. Since there are only countably many computable functions, the ordinal ${\displaystyle \omega _{1}^{\text{CK}}}$ is evidently countable.
• The ordinals with a notation in Kleene's ${\displaystyle {\mathcal {O}}}$ are exactly the computable ordinals. (The fact that every computable ordinal has a notation follows from the closure of this system of ordinal notations under successor and effective limits.)
• ${\displaystyle <_{\mathcal {O}}}$ is not computably enumerable, but there is a computably enumerable relation which agrees with ${\displaystyle <_{\mathcal {O}}}$ precisely on members of ${\displaystyle {\mathcal {O}}}$.
• For any notation ${\displaystyle p}$, the set ${\displaystyle \lbrace q\mid q<_{\mathcal {O}}p\rbrace }$ of notations below ${\displaystyle p}$ is computably enumerable. However, Kleene's ${\displaystyle {\mathcal {O}}}$, when taken as a whole, is ${\displaystyle \Pi _{1}^{1}}$ (see analytical hierarchy) and not arithmetical because of the following:
• ${\displaystyle {\mathcal {O}}}$ is ${\displaystyle \Pi _{1}^{1}}$-complete (i.e. ${\displaystyle {\mathcal {O}}}$ is ${\displaystyle \Pi _{1}^{1}}$ and every ${\displaystyle \Pi _{1}^{1}}$ set is Turing reducible to it)[2] and every ${\displaystyle \Sigma _{1}^{1}}$ subset of ${\displaystyle {\mathcal {O}}}$ is effectively bounded in ${\displaystyle {\mathcal {O}}}$ (a result of Spector).
• In fact, any ${\displaystyle \Pi _{1}^{1}}$ set is many-one reducible to ${\displaystyle {\mathcal {O}}}$.[2]
• ${\displaystyle {\mathcal {O}}}$ is the universal system of ordinal notations in the sense that any specific set of ordinal notations can be mapped into it in a straightforward way. More precisely, there is a computable function ${\displaystyle f}$ such that if ${\displaystyle e}$ is an index for a computable well-ordering, then ${\displaystyle f(e)}$ is a member of ${\displaystyle {\mathcal {O}}}$ and ${\displaystyle <_{e}}$ is order-isomorphic to an initial segment of the set ${\displaystyle \{p\mid p<_{\mathcal {O}}f(e)\}}$.
• There is a computable function ${\displaystyle +_{\mathcal {O}}}$, which, for members of ${\displaystyle {\mathcal {O}}}$, mimics ordinal addition and has the property that ${\displaystyle \max\{p,q\}\leq p+_{\mathcal {O}}q}$. (Jockusch)

A path in ${\displaystyle {\mathcal {O}}}$ is a subset ${\displaystyle {\mathcal {P}}}$ of ${\displaystyle {\mathcal {O}}}$ which is totally ordered by ${\displaystyle <_{\mathcal {O}}}$ and is closed under predecessors, i.e. if ${\displaystyle p}$ is a member of a path ${\displaystyle {\mathcal {P}}}$ and ${\displaystyle q<_{\mathcal {O}}p}$ then ${\displaystyle q}$ is also a member of ${\displaystyle {\mathcal {P}}}$. A path ${\displaystyle {\mathcal {P}}}$ is maximal if there is no element of ${\displaystyle {\mathcal {O}}}$ which is above (in the sense of ${\displaystyle <_{\mathcal {O}}}$) every member of ${\displaystyle {\mathcal {P}}}$, otherwise ${\displaystyle {\mathcal {P}}}$ is non-maximal.

• A path ${\displaystyle {\mathcal {P}}}$ is non-maximal if and only if ${\displaystyle {\mathcal {P}}}$ is computably enumerable (c.e.). It follows by remarks above that every element ${\displaystyle p}$ of ${\displaystyle {\mathcal {O}}}$ determines a non-maximal path ${\displaystyle {\mathcal {P}}}$; and every non-maximal path is so determined.
• There are ${\displaystyle 2^{\aleph _{0}}}$ maximal paths through ${\displaystyle {\mathcal {O}}}$; since they are maximal, they are non-c.e.
• In fact, there are ${\displaystyle 2^{\aleph _{0}}}$ maximal paths within ${\displaystyle {\mathcal {O}}}$ of length ${\displaystyle \omega ^{2}}$. (Crossley, Schütte)
• For every non-zero ordinal ${\displaystyle \lambda <\omega _{1}^{CK}}$, there are ${\displaystyle 2^{\aleph _{0}}}$ maximal paths within ${\displaystyle {\mathcal {O}}}$ of length ${\displaystyle \omega ^{2}\cdot \lambda }$. (Aczel)
• Further, if ${\displaystyle {\mathcal {P}}}$ is a path whose length is not a multiple of ${\displaystyle \omega ^{2}}$ then ${\displaystyle {\mathcal {P}}}$ is not maximal. (Aczel)
• For each c.e. degree ${\displaystyle d}$, there is a member ${\displaystyle e_{d}}$ of ${\displaystyle {\mathcal {O}}}$ such that the path ${\displaystyle {\mathcal {P}}=\lbrace p\mid p<_{\mathcal {O}}e_{d}\rbrace }$ has many-one degree ${\displaystyle d}$. In fact, for each computable ordinal ${\displaystyle \alpha \geq \omega ^{2}}$, a notation ${\displaystyle e_{d}}$ exists with ${\displaystyle |e_{d}|=\alpha }$. (Jockusch)
• There exist ${\displaystyle \aleph _{0}}$ paths through ${\displaystyle {\mathcal {O}}}$ which are ${\displaystyle \Pi _{1}^{1}}$. Given a progression of computably enumerable theories based on iterating Uniform Reflection, each such path is incomplete with respect to the set of true ${\displaystyle \Pi _{1}^{0}}$ sentences. (Feferman & Spector)
• There exist ${\displaystyle \Pi _{1}^{1}}$ paths through ${\displaystyle {\mathcal {O}}}$ each initial segment of which is not merely c.e., but computable. (Jockusch)
• Various other paths in ${\displaystyle {\mathcal {O}}}$ have been shown to exist, each with specific kinds of reducibility properties. (See references below)

• Computable ordinal
• Large countable ordinal
• Ordinal notation

• Church, Alonzo (1938), "The constructive second number class", Bull. Amer. Math. Soc., 44 (4): 224–232, doi:10.1090/S0002-9904-1938-06720-1
• Kleene, S. C. (1938), "On Notation for Ordinal Numbers", The Journal of Symbolic Logic, Association for Symbolic Logic, 3 (4): 150–155, doi:10.2307/2267778, JSTOR 2267778, S2CID 34314018
• Rogers, Hartley (1987) [1967], The Theory of Recursive Functions and Effective Computability, First MIT press paperback edition, ISBN 978-0-262-68052-3
• Feferman, Solomon; Spector, Clifford (1962), "Incompleteness along paths in progressions of theories", Journal of Symbolic Logic, 27 (4): 383–390, doi:10.2307/2964544, JSTOR 2964544, S2CID 33892829