mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, specifically

computability Computability is the ability to solve a problem in an effective manner. 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 close ...

and

set theory Set theory is the branch of mathematical logic that studies 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 mathematics, is mostly conce ...

, an ordinal

\alpha

is said to be computable or recursive if there is a

computable Computability is the ability to solve a problem in an effective manner. 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 close ...

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

ing of a

subset In mathematics, 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 are ...

of the

natural numbers In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal n ...

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 such ...

\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'' (film), a 1996 film including Laura Girling * ''The Successor'' (TV program), a 2007 Israeli television program Mus ...

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; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest l ...

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 ordinal collapsing functions. 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 an ...

. 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 ordinals. A Gödel numbering is a function mapping t ...

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 a 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 asserts that t ...

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

See also

References