In
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 is said to be computable or recursive if there is a
computable 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 ...
.
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'' (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 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, 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 a ...
. 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 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,
is countable.
The computable ordinals are exactly the ordinals that have an
ordinal notation 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
*
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
References
*
Hartley Rogers Jr. ''The Theory of Recursive Functions and Effective Computability'', 1967. Reprinted 1987, MIT Press, (paperback),
*
Gerald Sacks ''Higher Recursion Theory''. Perspectives in mathematical logic, Springer-Verlag, 1990.
Set theory
Computability theory
Ordinal numbers
{{settheory-stub