Admissible ordinal

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_α ⊧ Σ₀-collection.{{citation

| last = Friedman | first = Sy D.|authorlink = Sy Friedman

| contribution = Fine structure theory and its applications

| doi = 10.1090/pspum/042/791062

| mr = 791062

| pages = 259–269

| publisher = Amer. Math. Soc., Providence, RI

| series = Proc. Sympos. Pure Math.

| title = Recursion theory (Ithaca, N.Y., 1982)

| volume = 42

| year = 1985}}. See in particular [https://books.google.com/books?id=2vvg3mRzDtwC&pg=PA265 p. 265].{{citation

| last = Fitting | first = Melvin|authorlink = Melvin Fitting

| isbn = 0-444-86171-8

| mr = 644315

| page = 238

| publisher = North-Holland Publishing Co., Amsterdam-New York

| series = Studies in Logic and the Foundations of Mathematics

| title = Fundamentals of generalized recursion theory

| url = https://books.google.com/books?id=GRE7AAAAQBAJ&pg=PA238

| volume = 105

| year = 1981}}. The term was coined by Richard Platek in 1966.G. E. Sacks, [https://projecteuclid.org/ebook/Download?urlId=pl%2F1235422639&isFullBook=False Higher Recursion Theory] (p.151). Association for Symbolic Logic, Perspectives in Logic

The first two admissible ordinals are ω and $\backslash omega\_1^\{\backslash mathrm\{CK\}\}$ (the least nonrecursive 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 $\backslash omega\_\backslash alpha^\{\backslash mathrm\{CK\}\}$ for the $\backslash alpha$-th ordinal that is either admissible or a limit of admissibles; an ordinal that is both is called recursively inaccessible.{{citation

| last = Friedman | first = Sy D.

| contribution = Constructibility and class forcing

| doi = 10.1007/978-1-4020-5764-9_9

| mr = 2768687

| pages = 557–604

| publisher = Springer, Dordrecht

| title = Handbook of set theory. Vols. 1, 2, 3

| year = 2010}}. See in particular [https://books.google.com/books?id=DLCyehuI0i0C&pg=PA560 p. 560]. 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).{{citation

| last1 = Kahle | first1 = Reinhard

| last2 = Setzer | first2 = Anton

| contribution = An extended predicative definition of the Mahlo universe

| mr = 2883363

| pages = 315–340

| publisher = Ontos Verlag, Heusenstamm

| series = Ontos Math. Log.

| title = Ways of proof theory

| volume = 2

| year = 2010}}. 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 Σ₁(L_α) mapping from γ onto α.K. Devlin, [https://core.ac.uk/download/pdf/30905237.pdf An introduction to the fine structure of the constructible hierarchy] (1974) (p.38). Accessed 2021-05-06. $\backslash alpha$ is an admissible ordinal iff there is a standard model $M$ of KP whose set of ordinals is $\backslash alpha$, in fact this may be take as the definition of admissibility.K. J. Devlin, Constructibility (1984), ch. 2, "The Constructible Universe, p.95. Perspectives in Mathematical Logic, Springer-Verlag.J. Barwise, Admissible Sets and Structures (1976). Cambridge University Press The $\backslash alpha$th admissible ordinal is sometimes denoted by $\backslash tau\_\backslash alpha$P. G. Hinman, Recursion-Theoretic Hierarchies (1978), pp.419--420. Perspectives in Mathematical Logic, ISBN 3-540-07904-1.^p. 174 or $\backslash tau^0\_\backslash alpha$.S. Kripke, "[https://saulkripkecenter.org/wp-content/uploads/2019/03/Transfinite-Recursion-Constructible-Sets-and-Analogues-of-Cardinals-PUBLIC.pdf Transfinite Recursion, Constructible Sets, and Analogues of Cardinals]" (1967), p.11. Accessed 2023-07-15.

The Friedman-Jensen-Sacks theorem states that countable $\backslash alpha$ is admissible iff there exists some $A\backslash subseteq\backslash omega$ such that $\backslash alpha$ is the least ordinal not recursive in $A$.W. Marek, M. Srebrny, "[https://philpapers.org/rec/MARGIT-4 Gaps in the Constructible Universe]" (1973), pp.361--362. Annals of Mathematical Logic 6 Equivalently, for any countable admissible $\backslash alpha$, there is an $A\backslash subseteq\backslash mathbb\; N$ making $\backslash alpha$ minimal such that $\backslash langle\; L\_\backslash alpha,\; \backslash in,\; A\backslash rangle$ is an admissible structure.A. S. Kechris, "[https://www.ams.org/journals/tran/1975-202-00/S0002-9947-1975-0419235-7/S0002-9947-1975-0419235-7.pdf The Theory of Countable Analytical Sets]"^{p. 264}