Kleene's O - 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 .

Read more about this topic:  Kleene's O

Other articles related to "kleene":

Kleene's O
... In set theory and computability theory, Kleene's is a canonical subset of the natural numbers when regarded as ordinal notations ... ordinal, that is, ordinals below Church–Kleene ordinal ... Kleene (1938) described a system of notation for all recursive ordinals (those less than the Church–Kleene ordinal) ...
Axiom Of Reducibility - Criticism of The Axiom of Reducibility - Stephen Kleene 1952
... First inferences from the paradoxes, subchapter "LOGICISM" Kleene (1952) traces the development of Russell's theory of types "To adapt the logicistic construction of mathematics to the situation ... Kleene observes that "to exclude impredicative definitions within a type, the types above type 0 are further separated into orders ... Kleene, however, parenthetically observes that "the logicistic definition of natural number now becomes predicative when the P in it is specified to range only over ...
History Of The Church–Turing Thesis - Kleene
... Kleene and Rosser transcribed Gödel's 1934 lectures in Princeton ... Recursive Functions of Natural Numbers Kleene states "A definition of general recursive function of natural numbers was suggested by Herbrand to Gödel ...
Church–Kleene Ordinal
... In mathematics, the Church–Kleene ordinal, named after Alonzo Church and S ... Kleene, is a large countable ordinal ...