Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Computable ordinal
Summary
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 computable 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 .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.