Recursive ordinal

In mathematics, specifically set theory, an ordinal α 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 α.

It is trivial to check that ω is recursive, the successor of a recursive ordinal is recursive, and the set of all recursive ordinals is closed downwards. We call the supremum of all recursive ordinals the Church-Kleene ordinal and denote it by $\omega^{CK}_1$. Since the recursive relations are parameterized by the natural numbers, the recursive ordinals are also parameterized by the natural numbers. Therefore, there are only countably many recursive ordinals. Thus, $\omega^{CK}_1$ is countable.

The recursive ordinals are exactly the ordinals that have an ordinal notation in Kleene's $\mathcal{O}$.

See also

• Arithmetical hierarchy
• Large countable ordinals
• Ordinal notation

References

• Rogers, H. The Theory of Recursive Functions and Effective Computability, 1967. Reprinted 1987, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
• Sacks, G. Higher Recursion Theory. Perspectives in mathematical logic, Springer-Verlag, 1990. ISBN 0-387-19305-7

This set theory-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Set theory Computability theory Ordinal numbers Set theory stubs Wikimedia Foundation. 2010. Игры ⚽ Нужно сделать НИР? Portsnap Gateway High School (San Francisco) Look at other dictionaries: Ordinal analysis — In proof theory, ordinal analysis assigns ordinals (often large countable ordinals) to mathematical theories as a measure of their strength. The field was formed when Gerhard Gentzen in 1934 used cut elimination to prove, in modern terms, that… …   Wikipedia Ordinal collapsing function — In mathematical logic and set theory, an ordinal collapsing function (or projection function) is a technique for defining (notations for) certain recursive large countable ordinals, whose principle is to give names to certain ordinals much larger …   Wikipedia 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. There are many such schemes of ordinal… …   Wikipedia Large countable ordinal — In the mathematical discipline of set theory, there are many ways of describing specific countable ordinals. The smallest ones can be usefully and non circularly expressed in terms of their Cantor normal forms. Beyond that, many ordinals of… …   Wikipedia Church–Kleene ordinal — In mathematics, the Church–Kleene ordinal, , is a large countable ordinal. It is the smallest non recursive ordinal. It is named after Alonzo Church and S. C. Kleene. References Church, Alonzo; Kleene, S. C. (1937), Formal definitions in the… …   Wikipedia Admissible ordinal — In set theory, an admissible ordinal is any ordinal number α such that Lα is a standard set model of Kripke–Platek set theory. In this case, Lα is said to be an admissible set.The first two admissible ordinals are ω and omega 1^{mathrm{CK (the… …   Wikipedia Limit ordinal — A limit ordinal is an ordinal number which is neither zero nor a successor ordinal. Various equivalent ways to express this are: *It cannot be reached via the ordinal successor operation S ; in precise terms, we say lambda; is a limit ordinal if… …   Wikipedia Primitive recursive arithmetic — Primitive recursive arithmetic, or PRA, is a quantifier free formalization of the natural numbers. It was first proposed by Skolem [Thoralf Skolem (1923) The foundations of elementary arithmetic in Jean van Heijenoort, translator and ed. (1967)… …   Wikipedia 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 …   Wikipedia Hyperarithmetical theory — In recursion theory, hyperarithmetic theory is a generalization of Turing computability. It has close connections with definability in second order arithmetic and with weak systems of set theory such as Kripke–Platek set theory. It is an… …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”