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.[1] One sometimes writes for the -th ordinal that is either admissible or a limit of admissibles; an ordinal that is both is called recursively inaccessible.[4] 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 ordinals, for example).[5] But all these ordinals are still countable. Therefore, admissible ordinals seem to be the recursive analogue of regular cardinal numbers.
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 α.[6] is an admissible ordinal iff there is a standard model of KP whose set of ordinals is , in fact this may be take as the definition of admissibility.[7][8] The th admissible ordinal is sometimes denoted by [9][8]p. 174 or .[10]
The Friedman-Jensen-Sacks theorem states that countable is admissible iff there exists some such that is the least ordinal not recursive in .[11]
^ abFriedman, Sy D. (1985), "Fine structure theory and its applications", Recursion theory (Ithaca, N.Y., 1982), Proc. Sympos. Pure Math., vol. 42, Amer. Math. Soc., Providence, RI, pp. 259–269, doi:10.1090/pspum/042/791062, MR 0791062. See in particular p. 265.
^ abFitting, Melvin (1981), Fundamentals of generalized recursion theory, Studies in Logic and the Foundations of Mathematics, vol. 105, North-Holland Publishing Co., Amsterdam-New York, p. 238, ISBN0-444-86171-8, MR 0644315.
^G. E. Sacks, Higher Recursion Theory (p.151). Association for Symbolic Logic, Perspectives in Logic
^Friedman, Sy D. (2010), "Constructibility and class forcing", Handbook of set theory. Vols. 1, 2, 3, Springer, Dordrecht, pp. 557–604, doi:10.1007/978-1-4020-5764-9_9, MR 2768687. See in particular p. 560.
^Kahle, Reinhard; Setzer, Anton (2010), "An extended predicative definition of the Mahlo universe", Ways of proof theory, Ontos Math. Log., vol. 2, Ontos Verlag, Heusenstamm, pp. 315–340, MR 2883363.
^K. Devlin, An introduction to the fine structure of the constructible hierarchy (1974) (p.38). Accessed 2021-05-06.
^K. J. Devlin, Constructibility (1984), ch. 2, "The Constructible Universe, p.95. Perspectives in Mathematical Logic, Springer-Verlag.
^ abJ. Barwise, Admissible Sets and Structures (1976). Cambridge University Press
^P. G. Hinman, Recursion-Theoretic Hierarchies (1978), pp.419--420. Perspectives in Mathematical Logic, ISBN 3-540-07904-1.
^S. Kripke, "Transfinite Recursion, Constructible Sets, and Analogues of Cardinals" (1967), p.11. Accessed 2023-07-15.
^W. Marek, M. Srebrny, "Gaps in the Constructible Universe" (1973), pp.361--362. Annals of Mathematical Logic 6
This set theory-related article is a stub. You can help Wikipedia by expanding it.
admissible, ordinal, theory, ordinal, number, admissible, ordinal, admissible, that, transitive, model, kripke, platek, theory, other, words, admissible, when, limit, ordinal, collection, term, coined, richard, platek, 1966, first, admissible, ordinals, displa. In set theory an ordinal number a is an admissible ordinal if La is an admissible set that is a transitive model of Kripke Platek set theory in other words a is admissible when a is a limit ordinal and La S0 collection 1 2 The term was coined by Richard Platek in 1966 3 The first two admissible ordinals are w and w 1 C K displaystyle omega 1 mathrm CK the least nonrecursive ordinal also called the Church Kleene ordinal 2 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 1 One sometimes writes w a C K displaystyle omega alpha mathrm CK for the a displaystyle alpha th ordinal that is either admissible or a limit of admissibles an ordinal that is both is called recursively inaccessible 4 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 ordinals for example 5 But all these ordinals are still countable Therefore admissible ordinals seem to be the recursive analogue of regular cardinal numbers Notice that a is an admissible ordinal if and only if a is a limit ordinal and there does not exist a g lt a for which there is a S1 La mapping from g onto a 6 a displaystyle alpha is an admissible ordinal iff there is a standard model M displaystyle M of KP whose set of ordinals is a displaystyle alpha in fact this may be take as the definition of admissibility 7 8 The a displaystyle alpha th admissible ordinal is sometimes denoted by t a displaystyle tau alpha 9 8 p 174 or t a 0 displaystyle tau alpha 0 10 The Friedman Jensen Sacks theorem states that countable a displaystyle alpha is admissible iff there exists some A w displaystyle A subseteq omega such that a displaystyle alpha is the least ordinal not recursive in A displaystyle A 11 See also edita recursion theory Large countable ordinals Constructible universe Regular cardinalReferences edit a b Friedman Sy D 1985 Fine structure theory and its applications Recursion theory Ithaca N Y 1982 Proc Sympos Pure Math vol 42 Amer Math Soc Providence RI pp 259 269 doi 10 1090 pspum 042 791062 MR 0791062 See in particular p 265 a b Fitting Melvin 1981 Fundamentals of generalized recursion theory Studies in Logic and the Foundations of Mathematics vol 105 North Holland Publishing Co Amsterdam New York p 238 ISBN 0 444 86171 8 MR 0644315 G E Sacks Higher Recursion Theory p 151 Association for Symbolic Logic Perspectives in Logic Friedman Sy D 2010 Constructibility and class forcing Handbook of set theory Vols 1 2 3 Springer Dordrecht pp 557 604 doi 10 1007 978 1 4020 5764 9 9 MR 2768687 See in particular p 560 Kahle Reinhard Setzer Anton 2010 An extended predicative definition of the Mahlo universe Ways of proof theory Ontos Math Log vol 2 Ontos Verlag Heusenstamm pp 315 340 MR 2883363 K Devlin An introduction to the fine structure of the constructible hierarchy 1974 p 38 Accessed 2021 05 06 K J Devlin Constructibility 1984 ch 2 The Constructible Universe p 95 Perspectives in Mathematical Logic Springer Verlag a b J Barwise Admissible Sets and Structures 1976 Cambridge University Press P G Hinman Recursion Theoretic Hierarchies 1978 pp 419 420 Perspectives in Mathematical Logic ISBN 3 540 07904 1 S Kripke Transfinite Recursion Constructible Sets and Analogues of Cardinals 1967 p 11 Accessed 2023 07 15 W Marek M Srebrny Gaps in the Constructible Universe 1973 pp 361 362 Annals of Mathematical Logic 6 nbsp This set theory related article is a stub You can help Wikipedia by expanding it vte Retrieved from https en wikipedia org w index php title Admissible ordinal amp oldid 1211746914, wikipedia, wiki, book, books, library,