In
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 clo ...
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 concer ...
, an
ordinal 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- ...
ing of a
subset
In mathematics, set ''A'' is a subset of a set ''B'' if all 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 unequal, then ''A'' is a proper subset o ...
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 ...
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 ...
.
It is easy to check that
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 of all computable ordinals is
closed 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
. 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 ordinal is computable if and only if it is smaller than
. Since there are only countably many computable relations, there are also only
countably
In mathematics, a Set (mathematics), set is countable if either it is finite set, 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 fro ...
many computable ordinals. Thus,
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 .
See also
*
Arithmetical hierarchy
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...
*
Large countable ordinal
In the mathematical discipline of set theory, there are many ways of describing specific countable set, countable ordinal number, ordinals. The smallest ones can be usefully and non-circularly expressed in terms of their Cantor normal forms. Beyond ...
*
Ordinal analysis
In proof theory, ordinal analysis assigns ordinals (often large countable ordinals) to mathematical theories as a measure of their strength.
If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory ha ...
*
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 ...
References
*
Hartley Rogers Jr. Hartley Rogers Jr. (July 6, 1926 – July 17, 2015) was a mathematician who worked in computability theory, and was a professor in the Mathematics Department of the Massachusetts Institute of Technology.
Biography
Born in 1926 in Buffalo, New York ...
''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 th ...
''Higher Recursion Theory''. Perspectives in mathematical logic, Springer-Verlag, 1990.
Set theory
Computability theory
Ordinal numbers
{{settheory-stub