Computable Ordinal
Get Computable Ordinal essential facts below. View Videos or join the Computable Ordinal discussion. Add Computable Ordinal to your topic list for future reference or share this resource on social media.
Computable Ordinal

In mathematics, specifically computability and set theory, an ordinal is said to be computable or recursive if there is a computable well-ordering of a subset of the natural numbers having the order type .

It is easy to check that is computable. The successor of a computable ordinal is computable, and the set of all computable ordinals is closed downwards.

The supremum of all computable ordinals is called the Church-Kleene ordinal, the first nonrecursive ordinal, and denoted by . The Church-Kleene ordinal is a limit ordinal. An ordinal is computable if and only if it is smaller than . Since there are only countably many computable relations, there are also only countably many computable ordinals. Thus, is countable.

The computable ordinals are exactly the ordinals that have an ordinal notation in Kleene's .

See also


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

  This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.



Music Scenes