Kleene's O

In set theory and computability theory, Kleene's $mathcal\{O\}$ is a canonical subset of the natural numbers when regarded as ordinal notations. It contains ordinal notations for every recursive ordinal, that is, ordinals below Church–Kleene ordinal, $omega\_1^\{CK\}$. Since $omega\_1^\{CK\}$ is the first ordinal not representable in a computable system of ordinal notations the elements of $mathcal\{O\}$ can be regarded as the canonical 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.

For any notation $kappa\; ,$ the set of notations below $kappa$ is recursively enumerable. However, Kleene's $mathcal\{O\}$, when taken as a whole, is $Pi^1\_1$ (see analytical hierarchy).

Kleene (1938) described a system of notation for all recursive ordinals (those less than the Church–Kleene ordinal). It uses a subset of the natural numbers instead of finite strings of symbols. Unfortunately, there is in general no effective way to tell whether some natural number represents an ordinal, or whether two numbers represent the same ordinal. However, one can effectively find notations which represent the ordinal sum, product, and power (see ordinal arithmetic) of any two given notations in Kleene's $mathcal\{O\}$; and given any notation for an ordinal, there is a recursively enumerable set of notations which contains one element for each smaller ordinal and is effectively ordered.

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 belongs to Kleene's $mathcal\{O\}$ and denotes the ordinal 0.
* If the ordinal α is denoted by the natural number "i" which belongs to Kleene's $mathcal\{O\}$, then 2^"i" belongs to Kleene's $mathcal\{O\}$ and denotes the successor of α, i.e. α+1.
* Suppose {"e"} is the "e"-th partial recursive function, and it is total, and all its values are members of Kleene's $mathcal\{O\}$, and for any natural number "n" where is defined below. Then 3·5^"e" belongs to Kleene's $mathcal\{O\}$ and denotes the limit of γ_"k" where γ_"k" is denoted by {"e"}("k") for every natural number "k".

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 relation is a partial ordering of Kleene's $mathcal\{O\}$ defined as follows:
* If "i" belongs to Kleene's $mathcal\{O\}$, then and for any "j" such that , we also have
* If 3·5^"e" belongs to Kleene's $mathcal\{O\}$ and for some "n", then

If "i" denotes α and "j" denotes &beta; and then α<&beta;; but the converse may fail to hold.

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 recursive ordinal has a notation follows from the closure of this system of ordinal notations under successor and effective limits.

See also

* Recursive ordinal
* Large countable ordinal
* Ordinal notation

References

*citation|last=Church|url=http://www.ams.org/bull/1938-44-04/S0002-9904-1938-06720-1/ |title=The constructive second number class
journal= Bull. Amer. Math. Soc.|volume= 44 |year=1938|pages= 224-232
*citation|title= On Notation for Ordinal Numbers
first= S. C.|last= Kleene
journal= The Journal of Symbolic Logic|volume= 3|issue= 4|year= 1938|pages= 150-155
url= http://links.jstor.org/sici?sici=0022-4812%28193812%293%3A4%3C150%3AONFON%3E2.0.CO%3B2-%23
*Citation | last1=Rogers | first1=Hartley | title=The Theory of Recursive Functions and Effective Computability | origyear=1967 | publisher=First MIT press paperback edition | isbn=978-0-262-68052-3 | year=1987