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 recursive ordinal notations.

The Church–Kleene ordinal and variants

edit

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   (an ordinal   is called admissible if  .) The  -recursive subsets of   are exactly the   subsets of  .[1]

The notation   is in reference to  , the first uncountable ordinal, which is the set of all countable ordinals, analogously to how the Church-Kleene ordinal is the set of all recursive ordinals. Some old sources use   to denote the Church-Kleene ordinal.[2]

For a set  , a set is  -computable if it is computable from a Turing machine with an oracle state that queries  . The relativized Church–Kleene ordinal   is the supremum of the order types of  -computable relations. The Friedman-Jensen-Sacks theorem states that for every countable admissible ordinal  , there exists a set   such that  .[3]

 , first defined by Stephen G. Simpson[citation needed] is an extension of the Church–Kleene ordinal. This is the smallest limit of admissible ordinals, yet this ordinal is not admissible. Alternatively, this is the smallest α such that   is a model of  -comprehension.[1]

Recursively ordinals

edit

The  th admissible ordinal is sometimes denoted by  .[4][5]

Recursively "x" ordinals, where "x" typically represents a large cardinal property, are kinds of nonrecursive ordinals.[6] Rathjen has called these ordinals the "recursively large counterparts" of x,[7] however the use of "recursively large" here is not to be confused with the notion of an ordinal being recursive.

An ordinal   is called recursively inaccessible if it is admissible and a limit of admissibles. Alternatively,   is recursively inaccessible iff   is the  th admissible ordinal,[5] or iff  , an extension of Kripke–Platek set theory stating that each set is contained in a model of Kripke–Platek set theory. Under the condition that   ("every set is hereditarily countable"),   is recursively inaccessible iff   is a model of  -comprehension.[8]

An ordinal   is called recursively hyperinaccessible if it is recursively inaccessible and a limit of recursively inaccessibles, or where   is the  th recursively inaccessible. Like "hyper-inaccessible cardinal", different authors conflict on this terminology.

An ordinal   is called recursively Mahlo if it is admissible and for any  -recursive function   there is an admissible   such that   (that is,   is closed under  ).[2] Mirroring the Mahloness hierarchy,   is recursively  -Mahlo for an ordinal   if it is admissible and for any  -recursive function   there is an admissible ordinal   such that   is closed under  , and   is recursively  -Mahlo for all  .[6]

An ordinal   is called recursively weakly compact if it is  -reflecting, or equivalently,[2] 2-admissible. These ordinals have strong recursive Mahloness properties, if α is  -reflecting then   is recursively  -Mahlo.[6]

Weakenings of stable ordinals

edit

An ordinal   is stable if   is a  -elementary-substructure of  , denoted  .[9] These are some of the largest named nonrecursive ordinals appearing in a model-theoretic context, for instance greater than   for any computably axiomatizable theory  .[10]Proposition 0.7. There are various weakenings of stable ordinals:[1]

  • A countable ordinal   is called  -stable iff  .
    • The smallest  -stable ordinal is much larger than the smallest recursively weakly compact ordinal: it has been shown that the smallest  -stable ordinal is  -reflecting for all finite  .[2]
    • 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 again much larger than the smallest  -stable or the smallest  -stable for any constant  .
  • A countable ordinal   is called  -stable iff  , where   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.

Larger nonrecursive ordinals

edit

Even larger nonrecursive ordinals include:[1]

  • The least ordinal   such that   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  . This is the smallest   such that   is a model of second-order comprehension, or  , which is   without the axiom of power set.
  • The least ordinal   such that  . This ordinal has been characterized by Toshiyasu Arai.[11]
  • The least ordinal   such that  .
  • The least stable ordinal.

References

edit
  1. ^ a b c d D. Madore, A Zoo of Ordinals (2017). Accessed September 2021.
  2. ^ a b c d W. Richter, P. Aczel, Inductive Definitions and Reflecting Properties of Admissible Ordinals (1973, p.15). Accessed 2021 October 28.
  3. ^ Sacks, Gerald E. (1976), "Countable admissible ordinals and hyperdegrees", Advances in Mathematics, 19 (2): 213–262, doi:10.1016/0001-8708(76)90187-0
  4. ^ P. G. Hinman, Recursion-Theoretic Hierarchies (1978), pp.419--420. Perspectives in Mathematical Logic, ISBN 3-540-07904-1.
  5. ^ a b J. Barwise, Admissible Sets and Structures (1976), pp.174--176. Perspectives in Logic, Cambridge University Press, ISBN 3-540-07451-1.
  6. ^ a b c Rathjen, Michael (1994), "Proof theory of reflection" (PDF), Annals of Pure and Applied Logic, 68 (2): 181–224, doi:10.1016/0168-0072(94)90074-4
  7. ^ M. Rathjen, "The Realm of Ordinal Analysis" (2006). Archived 7 December 2023.
  8. ^ W. Marek, Some comments on the paper by Artigue, Isambert, Perrin, and Zalc (1976), ICM. Accessed 19 May 2023.
  9. ^ J. Barwise, Admissible Sets and Structures (1976), Cambridge University Press, Perspectives in Logic.
  10. ^ W. Marek, K. Rasmussen, Spectrum of L in libraries (WorldCat catalog) (EuDML page), Państwowe Wydawn. Accessed 2022-12-01.
  11. ^ T. Arai, A Sneak Preview of Proof Theory of Ordinals (1997, p.17). Accessed 2021 October 28.