Nonrecursive ordinal

  (Redirected from 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 variantsEdit

The smallest non-recursive ordinal is the Church Kleene ordinal,  , named after Alonzo Church and S. C. Kleene; its order type is the set of all recursive ordinals. Since the successor of a recursive ordinal is recursive, the Church–Kleene ordinal is a limit ordinal. It is also the smallest ordinal that is not hyperarithmetical, and the smallest admissible ordinal after ω. The notation   is in reference to ω
1
, the first uncountable ordinal, which is set of all countable ordinals. The  -recursive subsets of ω are exactly the   subsets of ω.

An ordinal α is called admissible if  .

The relativized Church–Kleene ordinal   is the supremum of the x-computable ordinals.

 , first defined by Stephen G. Simpson and dubbed the "Great Church–Kleene ordinal" is an extension of the Church–Kleene ordinal. This is the smallest limit of admissible ordinals, yet this ordinal is not admissible. Alternatively, his is the smallest α such that   is a model of  -comprehension.

Recursively ordinalsEdit

Recursively x ordinals, not to be confused with recursive ordinals, are kinds of nonrecursive ordinals.

An ordinal α is called recursively inaccessible if it is admissible and limit of admissibles (α is the αth admissible). Alternatively, it is recursively inaccessible if  , an extension of Kripke–Platek set theory based on an inaccessible cardinal; or, lastly, on the arithmetical side, such that   is a model of   - comprehension.

An ordinal α is called recursively hyperinaccessible if it is recursively inaccessible and a limit of recursively inaccessibles (α is the αth recursively inaccessible).

An ordinal α is called recursively Mahlo if it is admissible and for any α-recursive function f: αα there is an admissible β < α such that {f(γ) : γ ∈ β} ⊆ β (that is, β is closed under f).

An ordinal α is called recursively weakly compact if it is  -reflecting (2-admissible).

Weakenings of stable ordinalsEdit

Stable ordinals are some of the largest nonrecursive ordinals. There are various weakenings of stables:

  • A countable ordinal   is called  -stable iff  . The smallest  -stable ordinal is larger than the smallest recursively weakly compact ordinal.
    • In general, a countable ordinal   is called  -stable iff  .
  • A countable ordinal   is called  -stable iff  , where   is the smallest admissible ordinal  . The smallest  -stable ordinal is larger than the smallest  -stable.
  • A countable ordinal   is called  -stable iff  , where   and   are the two smallest admissible ordinals  . The smallest  -stable ordinal is larger than the smallest  -reflecting.
  • A countable ordinal   is called inaccessibly-stable iff  , where   is the smallest recursively inaccessible ordinal  . The smallest inaccessibly-stable ordinal is larger than the smallest  -stable.
  • A countable ordinal   is called Mahlo-stable iff  , where   is the smallest recursively Mahlo ordinal  . The smallest Mahlo-stable ordinal is larger than the smallest inaccessibly-stable.
  • A countable ordinal   is called doubly  -stable iff  . The smallest doubly  -stable ordinal is larger than the smallest Mahlo-stable.

Largest recursive ordinalsEdit

  • An ordinal   is semi-nonprojectible[citation needed] if   where β is the smallest nonprojectible ordinal.
  • An ordinal   is nonprojectible if α is a limit of α-stable ordinals, or; if the set   is unbounded in α.
  • The ordinal of ramified analysis, often written as  , is the smallest   such that   is a model of second-order comprehension, and  .
  • The "Devlin–Jech ordinal"[citation needed] is the smallest ordinal α such that  .
  • The smallest ordinal α such that  .
  • The smallest stable ordinal. A countable ordinal is called stable iff  .

ReferencesEdit

  • Church, Alonzo; Kleene, S. C. (1937), "Formal definitions in the theory of ordinal numbers.", Fundamenta mathematicae, Warszawa, 28: 11–21, JFM 63.0029.02
  • Church, Alonzo (1938), "The constructive second number class", Bull. Amer. Math. Soc., 44 (4): 224–232, doi:10.1090/S0002-9904-1938-06720-1
  • Kleene, S. C. (1938), "On Notation for Ordinal Numbers", Journal of Symbolic Logic, Vol. 3, No. 4, 3 (4): 150–155, doi:10.2307/2267778, JSTOR 2267778
  • Rogers, Hartley (1987) [1967], The Theory of Recursive Functions and Effective Computability, First MIT press paperback edition, ISBN 978-0-262-68052-3
  • Madore, David (2017), A zoo of ordinals, p. 3
  • Simpson, Stephen G. (2009) [1999], Subsystems of Second-Order Arithmetic, Perspectives in Logic, 2, Cambridge University Press, pp. 246, 267, 292–293, ISBN 978-0-521-88439-6
  • Richter, Wayne; Aczel, Peter (1974), Inductive Definitions and Reflecting Properties of Admissible Ordinals, pp. 312–313, 333, ISBN 0-7204-2276-0