mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, specifically

computability Computability is the ability to solve a problem by an effective procedure. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is c ...

and

set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory – as a branch of mathema ...

, an ordinal

\alpha

is said to be computable or recursive if there is a

computable Computability is the ability to solve a problem by an effective procedure. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is cl ...

well-order In mathematics, a well-order (or well-ordering or well-order relation) on a set is a total ordering on with the property that every non-empty subset of has a least element in this ordering. The set together with the ordering is then calle ...

ing of a computable

subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...

of the

natural numbers In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...

having the

order type In mathematics, especially in set theory, two ordered sets and are said to have the same order type if they are order isomorphic, that is, if there exists a bijection (each element pairs with exactly one in the other set) f\colon X \to Y su ...

\alpha

. It is easy to check that

\omega

is computable. The

successor Successor may refer to: * An entity that comes after another (see Succession (disambiguation)) Film and TV * ''The Successor'' (1996 film), a film including Laura Girling * The Successor (2023 film), a French drama film * ''The Successor'' ( ...

of a computable ordinal is computable, and the

set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

of all computable ordinals is

closed Closed may refer to: Mathematics * Closure (mathematics), a set, along with operations, for which applying those operations on members always results in a member of the set * Closed set, a set which contains all its limit points * Closed interval, ...

downwards. The

supremum In mathematics, the infimum (abbreviated inf; : infima) of a subset S of a partially ordered set P is the greatest element in P that is less than or equal to each element of S, if such an element exists. If the infimum of S exists, it is unique, ...

of all computable ordinals is called the

Church–Kleene ordinal In mathematics, particularly set theory, non-recursive ordinals are large countable ordinals greater than all the recursive ordinals, and therefore can not be expressed using recursive ordinal notations. The Church–Kleene ordinal and variant ...

, the first nonrecursive ordinal, and denoted by

\omega_1^

. The Church–Kleene ordinal is a

limit ordinal In set theory, a limit ordinal is an ordinal number that is neither zero nor a successor ordinal. Alternatively, an ordinal λ is a limit ordinal if there is an ordinal less than λ, and whenever β is an ordinal less than λ, then there exists a ...

. An ordinal is computable if and only if it is smaller than

\omega_1^

. Since there are only countably many computable relations, there are also only

countably In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...

many computable ordinals. Thus,

\omega_1^

is countable. The computable ordinals are exactly the ordinals that have an

ordinal notation In mathematical logic and set theory, an ordinal notation is a partial function mapping the set of all finite sequences of symbols, themselves members of a finite alphabet, to a countable set of ordinal number, ordinals. A Gödel numbering is a fun ...

in Kleene's

\mathcal

References

* Hartley Rogers Jr. ''The Theory of Recursive Functions and Effective Computability'', 1967. Reprinted 1987, MIT Press, (paperback), *

Gerald Sacks Gerald Enoch Sacks (1933 – October 4, 2019) was an American logician whose most important contributions were in recursion theory. Named after him is Sacks forcing, a forcing notion based on perfect sets and the Sacks Density Theorem, which asse ...

''Higher Recursion Theory''. Perspectives in mathematical logic, Springer-Verlag, 1990. Set theory Computability theory Ordinal numbers {{settheory-stub

See also

References