Kleene's O

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 lbrace eta mid eta <_{mathcal{O kappa brace 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" { e } (n) <_{mathcal{O { e } (n + 1) where <_{mathcal{O 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 <_{mathcal{O is a partial ordering of Kleene's mathcal{O} defined as follows:
* If "i" belongs to Kleene's mathcal{O}, then i <_{mathcal{O 2^{i} and for any "j" such that j <_{mathcal{O i , we also have j <_{mathcal{O 2^{i} ,.
* If 3·5"e" belongs to Kleene's mathcal{O} and i <_{mathcal{O { e } (n) for some "n", then i <_{mathcal{O 3 cdot 5^{e} ,.

If "i" denotes α and "j" denotes &beta; and i <_{mathcal{O j ,, 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


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • KLEENE (S. C.) — KLEENE STEPHEN COLE (1909 ) Mathématicien américain né à Hartford (Connecticut). Diplômé de l’Amherst College, Stephen C. Kleene entre, en 1930, à l’université de Princeton. Il est docteur de la même université en 1934. Dès cette époque, il… …   Encyclopédie Universelle

  • Kleene —   [kliːn], Stephen Cole, amerikanischer Mathematiker und Logiker, * Hartford (Conneticut) 5. 1. 1909; Professor in Amherst (Massachusetts) und an der Universität von Wisconsin; wichtige Beiträge zur Rekursionstheorie, zur …   Universal-Lexikon

  • kleene — kleene·boc; …   English syllables

  • Kleene — Stephen Cole Kleene (* 5. Januar 1909 in Hartford, Connecticut, USA; † 25. Januar 1994 in Madison, Wisconsin) war ein US amerikanischer Mathematiker und Logiker. Er gilt als einer der Begründer der theoretischen Informatik, besonders der formalen …   Deutsch Wikipedia

  • Kleene — Stephen Cole Kleene Stephen Cole Kleene (né le 5 janvier 1909 à Hartford, mort le 25 janvier 1994) est un mathématicien et logicien américain. Biographie et contribution scientifique Kleene est connu pour avoir fondé la branche de la logique… …   Wikipédia en Français

  • Kleene algebra — In mathematics, a Kleene algebra (named after Stephen Cole Kleene, IPAEng|ˈkleɪni as in clay knee ) is either of two different things:* A bounded distributive lattice with an involution satisfying De Morgan s laws, and the inequality x ∧− x ≤ y… …   Wikipedia

  • Kleene star — In mathematical logic and computer science, the Kleene star (or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V *. It is widely… …   Wikipedia

  • Kleene's T predicate — In computability theory, the T predicate, first studied by mathematician Stephen Cole Kleene, is a particular set of triples of natural numbers that is used to represent computable functions within formal theories of arithmetic. Informally, the T …   Wikipedia

  • Kleene'sche Hülle — Die Kleenesche Hülle (auch endlicher Abschluss, Kleene * Abschluss oder Verkettungshülle genannt) eines Alphabets Σ oder einer formalen Sprache L ist die Menge aller Wörter, die durch beliebige Konkatenation (Verknüpfung) von Symbolen des… …   Deutsch Wikipedia

  • Kleene-Abschluss — Die Kleenesche Hülle (auch endlicher Abschluss, Kleene * Abschluss oder Verkettungshülle genannt) eines Alphabets Σ oder einer formalen Sprache L ist die Menge aller Wörter, die durch beliebige Konkatenation (Verknüpfung) von Symbolen des… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”