Admissible ordinal
Encyclopedia
In set theory
, an ordinal number
α is an admissible ordinal if Lα
is an admissible set
(that is, a transitive model
of Kripke–Platek set theory
); in other words, α is admissible when α is a limit ordinal and Lα⊧Σ0-collection.
The first two admissible ordinals are ω and
(the least non-recursive ordinal
, also called the Church–Kleene ordinal). Any regular
uncountable cardinal is an admissible ordinal.
By a theorem of Sacks
, the countable
admissible ordinals are exactly those constructed in a manner similar to the Church-Kleene ordinal, but for Turing machines with oracles
. One sometimes writes
for the 
-th ordinal which is either admissible or a limit of admissibles; an ordinal which is both is called recursively inaccessible: there exists a theory of large ordinals in this manner that is highly parallel to that of (small) large cardinals
(one can define recursively Mahlo cardinal
s, for example). But all these ordinals are still countable. Therefore, admissible ordinals seem to be the recursive analogue of regular cardinal number
s.
Notice that α is an admissible ordinal if and only if α is a limit ordinal and there does not exist a γ<α for which there is a Σ1(Lα) mapping from γ onto α. If M is a standard model of KP, then the set of ordinals in M is an admissible ordinal.
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, an ordinal number
Ordinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
α is an admissible ordinal if Lα
Constructible universe
In mathematics, the constructible universe , denoted L, is a particular class of sets which can be described entirely in terms of simpler sets. It was introduced by Kurt Gödel in his 1938 paper "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis"...
is an admissible set
Admissible set
In set theory, a discipline within mathematics, an admissible set is a transitive set A\, such that \langle A,\in \rangle is a model of Kripke–Platek set theory....
(that is, a transitive model
Inner model
In mathematical logic, suppose T is a theory in the languageL = \langle \in \rangleof set theory.If M is a model of L describing a set theory and N is a class of M such that \langle N, \in_M, \ldots \rangle...
of Kripke–Platek set theory
Kripke–Platek set theory
The Kripke–Platek axioms of set theory are a system of axioms for axiomatic set theory developed by Saul Kripke and Richard Platek. The axiom system, written in first-order logic, has an infinite number of axioms because an infinite axiom schema is used.KP is weaker than Zermelo–Fraenkel set theory...
); in other words, α is admissible when α is a limit ordinal and Lα⊧Σ0-collection.
The first two admissible ordinals are ω and
(the least non-recursive ordinalRecursive ordinal
In mathematics, specifically set theory, an ordinal \alpha is said to be recursive if there is a recursive binary relation R that well-orders a subset of the natural numbers and the order type of that ordering is \alpha....
, also called the Church–Kleene ordinal). Any regular
Regular cardinal
In set theory, a regular cardinal is a cardinal number that is equal to its own cofinality. So, crudely speaking, a regular cardinal is one which cannot be broken into a smaller collection of smaller parts....
uncountable cardinal is an admissible ordinal.
By a theorem of Sacks
Gerald Sacks
Gerald Sacks is a logician who holds a joint appointment at Harvard University as a Professor of Mathematical Logic and the Massachusetts Institute of Technology as a Professor Emeritus. His most important contributions have been in recursion theory...
, the countable
Countable set
In mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...
admissible ordinals are exactly those constructed in a manner similar to the Church-Kleene ordinal, but for Turing machines with oracles
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
. One sometimes writes
for the -th ordinal which is either admissible or a limit of admissibles; an ordinal which is both is called recursively inaccessible: there exists a theory of large ordinals in this manner that is highly parallel to that of (small) large cardinalsLarge cardinal property
In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers. Cardinals with such properties are, as the name suggests, generally very "large"...
(one can define recursively Mahlo cardinal
Mahlo cardinal
In mathematics, a Mahlo cardinal is a certain kind of large cardinal number. Mahlo cardinals were first described by . As with all large cardinals, none of these varieties of Mahlo cardinals can be proved to exist by ZFC ....
s, for example). But all these ordinals are still countable. Therefore, admissible ordinals seem to be the recursive analogue of regular cardinal number
Cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
s.
Notice that α is an admissible ordinal if and only if α is a limit ordinal and there does not exist a γ<α for which there is a Σ1(Lα) mapping from γ onto α. If M is a standard model of KP, then the set of ordinals in M is an admissible ordinal.