Calculable ordinal number

Computable ordinal numbers are the types of order of computable well- orders . They are dealt with in theoretical computer science , more precisely in computability theory . The set of calculable ordinal numbers forms a countable starting part of the natural arrangement of all ordinal numbers .

definition

An ordinal number is called calculable if there is a calculable order that is order isomorphic . ${\displaystyle \alpha }$ ${\displaystyle (M;\leq _{M})}$ ${\displaystyle \alpha }$

A well-ordering on a subset of the natural numbers is then necessary . However, not every such order of well-being is predictable. Even orders that are isomorphic to a computable ordinal number do not have to be computable themselves (see examples ). ${\displaystyle \leq _{M}}$ ${\displaystyle M\subseteq \mathbb {N} }$

Examples

• All finite ordinal numbers can be calculated.
• The natural order of the set is decidable , so the ordinal number is calculable. ${\displaystyle \mathbb {N} }$ ${\displaystyle \omega }$
• The well-order is calculable and therefore also the ordinal number . ${\displaystyle 1<3<5<\cdots <0<2<4<\cdots \ }$ ${\displaystyle \omega \cdot 2}$
• If you designate the special holding problem and its complement , then the order also has the order type , but it cannot be calculated. ${\displaystyle K=\{x_{1}<x_{2}<\cdots \}}$ ${\displaystyle {\overline {K}}=\{y_{1}<y_{2}<\cdots \}}$ ${\displaystyle x_{1}<x_{2}<\cdots <y_{1}<y_{2}<\cdots \ }$ ${\displaystyle \omega \cdot 2}$

Church-Kleene ordinal number

There are only countably many decidable relations , so the calculable ordinal numbers have at most a countable supremum , the Church-Kleene ordinal number . It is named after Alonzo Church and Stephen Cole Kleene , who were the first to deal with recursive notation systems for ordinal numbers. Because of ( see above ) the Church-Kleene ordinal number is actually countably infinite. ${\displaystyle \omega _{1}^{CK}}$ ${\displaystyle \omega <\omega _{1}^{CK}}$

The following characterization applies:

An ordinal number can only be calculated if it is really smaller than . ${\displaystyle \omega _{1}^{CK}}$

An ordinal number can still be calculated precisely if it is constructive. That is, if there is a computable notation system whose picture contains. Not every countable ordinal number is also calculable, in particular it is not. ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \omega _{1}^{CK}}$

Individual evidence

1. ^ A. Church & S. Kleene : Formal Definitions in the Theory of Ordinal Numbers. In: Fundamenta mathematicae . 28, Warsaw 1937, pp. 11-21.
2. ^ A. Church: The Constructive Second Number Class . In: Bull. Amer. Math. Soc . 44, No. 4, 1938, pp. 224-232.
3. ^ S. Kleene: On Notation for Ordinal Numbers . In: The Journal of Symbolic Logic . 3, No. 4, 1938, pp. 150-155.

literature

• H. Rogers, Jr .: Theory of Recursive Functions and Effective Computability . MIT Press, Cambridge, MA 1987, ISBN 978-0-262-68052-3 .
• P. Odifreddi : Classical Recursion Theory . North-Holland, Amsterdam 1989, ISBN 0-444-87295-7 .