Kleene's O
Encyclopedia
In set theory
and computability theory
, Kleene
's
is a canonical subset of the natural number
s when regarded as ordinal notations. It contains ordinal notation
s for every recursive ordinal
, that is, ordinals below Church–Kleene ordinal,
. Since 
is the first ordinal not representable in a computable system of ordinal notations the elements of 
can be regarded as the canonical ordinal notations.
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 number
s 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
; 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
The basic idea of Kleene's system of ordinal notations is to build up ordinals in an effective manner. For members 
of 
, the ordinal for which 
is a notation is 
. The standard definition proceeds via transfinite induction and the ordering 
(a partial ordering of Kleene's 
) is defined simultaneously.
This definition has the advantages that one can recursively enumerate the predecessors of a given ordinal (though not in the
ordering) and that the notations are downward closed, i.e., if there is a notation for 
and 
then there is a notation for 
.
Basic properties of
Properties of paths in
A path in 
is a subset 
of 
which is totally ordered by 
and is closed under predecessors, i.e. if 
is a member of a path 
and 
then 
is also a member of 
. A path 
is maximal if there is no element of 
which is above (in the sense of 
) every member of 
, otherwise 
is non-maximal.
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
and computability theory
Computability theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
, Kleene
Stephen Cole Kleene
Stephen Cole Kleene was an American mathematician who helped lay the foundations for theoretical computer science...
's
is a canonical subset of the natural numberNatural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s when regarded as ordinal notations. It contains ordinal notation
Ordinal notation
In mathematical logic and set theory, an ordinal notation is a finite sequence of symbols from a finite alphabet which names an ordinal number according to some scheme which gives meaning to the language....
s for every recursive ordinal
Recursive ordinal
In mathematics, specifically set theory, an ordinal \alpha is said to be recursive if there is a recursive binary relation R that well-orders a subset of the natural numbers and the order type of that ordering is \alpha....
, that is, ordinals below Church–Kleene ordinal,
. Since is the first ordinal not representable in a computable system of ordinal notations the elements of can be regarded as the canonical ordinal notations.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 number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s instead of finite strings of symbols. Unfortunately, there is in general no effective
Computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
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
Ordinal arithmetic
In the mathematical field of set theory, ordinal arithmetic describes the three usual operations on ordinal numbers: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an explicit well-ordered set which represents the...
) of any two given notations in Kleene's
; and given any notation for an ordinal, there is a recursively enumerable setRecursively enumerable set
In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if:...
of notations which contains one element for each smaller ordinal and is effectively ordered.
Kleene's 
The basic idea of Kleene's system of ordinal notations is to build up ordinals in an effective manner. For members of , the ordinal for which is a notation is . The standard definition proceeds via transfinite induction and the ordering (a partial ordering of Kleene's ) is defined simultaneously.- The natural number 0 belongs to Kleene's
and 
. - If
belongs to Kleene's 
and 
, then 
belongs to Kleene's 
and 
and 
. - Suppose
is the 
-th partial recursive function. If 
is total, with range contained in 
, and for every natural number 
, we have 
, then 
belongs to Kleene's 
, 
for each 
and 
, i.e. 
is a notation for the limit of the ordinals 
where 
for every natural number 
. -
and 
imply 
(this guarantees that 
is transitive.)
This definition has the advantages that one can recursively enumerate the predecessors of a given ordinal (though not in the
ordering) and that the notations are downward closed, i.e., if there is a notation for and then there is a notation for . Basic properties of 
- If
and 
and 
then 
; but the converse may fail to hold. -
induces a tree structure on 
, so 
is well-founded. -
only branches at limit ordinals; and at each notation of a limit ordinal, 
is infinitely branching. - Since every recursive function has countably many indices, each infinite ordinal receives countably many notations; the finite ordinals have unique notations,
usually denoted 
. - The first ordinal that doesn't receive a notation is called the Church–Kleene ordinal and is denoted by
. Since there are only countably many recursive functions, the ordinal 
is evidently countable. - The ordinals with a notation in Kleene's
are exactly the recursive ordinalRecursive ordinalIn mathematics, specifically set theory, an ordinal \alpha is said to be recursive if there is a recursive binary relation R that well-orders a subset of the natural numbers and the order type of that ordering is \alpha....
s. (The fact that every recursive ordinal has a notation follows from the closure of this system of ordinal notations under successor and effective limits.) -
is not recursively enumerableRecursively enumerable setIn computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if:...
, but there is a recursively enumerable relation which agrees with
precisely on members of 
. - For any notation
, the set 
of notations below 
is recursively enumerable. However, Kleene's 
, when taken as a whole, is 
(see analytical hierarchyAnalytical hierarchyIn mathematical logic and descriptive set theory, the analytical hierarchy is a higher type analogue of the arithmetical hierarchy. It thus continues the classification of sets by the formulas that define them.-The analytical hierarchy of formulas:...
). - In fact,
is 
-complete and every 
subset of 
is effectively bounded in 
(a result of Spector). -
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 recursive function 
such that if 
is an index for a recursive well-ordering, then 
is a member of 
and 
is order-isomorphic to an initial segment of the set 
. - There is a recursive function
, which, for members of 
, mimics ordinal addition and has the property that 
. (Jockusch)
Properties of paths in 
A path in is a subset of which is totally ordered by and is closed under predecessors, i.e. if is a member of a path and then is also a member of . A path is maximal if there is no element of which is above (in the sense of ) every member of , otherwise is non-maximal.
- A path
is non-maximal if and only if 
is recursively enumerable (r.e.). It follows by remarks above that every element 
of 
determines a non-maximal path 
; and every non-maximal path is so determined. - There are
maximal paths through 
; since they are maximal, they are non-r.e. - In fact, there are
maximal paths within 
of length 
. (Crossley, Shutte) - For every non-zero ordinal
, there are 
maximal paths within 
of length 
. (Aczel) - Further, if
is a path whose length is not a multiple of 
then 
is not maximal. (Aczel) - For each r.e. degree
, there is a member 
of 
such that the path 
has many-one degree 
. In fact, for each recursive ordinal 
, a notation 
exists with 
. (Jockusch) - There exist
paths through 
which are 
. Given a progression of recursively enumerable theories based on iterating Uniform Reflection, each such path is incomplete with respect to the set of true 
sentences. (Feferman & Spector) - There exist
paths through 
each initial segment of which is not merely r.e., but recursive. (Jockusch) - Various other paths in
have been shown to exist, each with specific kinds of reducibility properties. (See references below)