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.^[1]^[2] The term was coined by Richard Platek in 1966.^[3]

The first two admissible ordinals are ω and $\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 $\omega _{\alpha }^{\mathrm {CK} }$ for the $\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 α 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 α.^[6] $\alpha$ is an admissible ordinal iff there is a standard model $M$ of KP whose set of ordinals is $\alpha$ , in fact this may be take as the definition of admissibility.^[7]^[8] The $\alpha$ th admissible ordinal is sometimes denoted by $\tau _{\alpha }$ ^[9]^[8]^p. 174 or $\tau _{\alpha }^{0}$ .^[10]

The Friedman-Jensen-Sacks theorem states that countable $\alpha$ is admissible iff there exists some $A\subseteq \omega$ such that $\alpha$ is the least ordinal not recursive in $A$ .^[11] Equivalently, for any countable admissible $\alpha$ , there is an $A\subseteq \mathbb {N}$ making $\alpha$ minimal such that $\langle L_{\alpha },\in ,A\rangle$ is an admissible structure.^[12]^{p. 264}

References

^ ^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
^ A. S. Kechris, "The Theory of Countable Analytical Sets"

This set theory-related article is a stub. You can help Wikipedia by expanding it.

[friedman-1] 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.

[fitting-2] 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.

[3] G. E. Sacks, Higher Recursion Theory (p.151). Association for Symbolic Logic, Perspectives in Logic

[4] 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.

[5] 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.

[6] K. Devlin, An introduction to the fine structure of the constructible hierarchy (1974) (p.38). Accessed 2021-05-06.

[7] K. J. Devlin, Constructibility (1984), ch. 2, "The Constructible Universe, p.95. Perspectives in Mathematical Logic, Springer-Verlag.

[Barwise76-8] J. Barwise, Admissible Sets and Structures (1976). Cambridge University Press

[9] P. G. Hinman, Recursion-Theoretic Hierarchies (1978), pp.419--420. Perspectives in Mathematical Logic, ISBN 3-540-07904-1.

[10] S. Kripke, "Transfinite Recursion, Constructible Sets, and Analogues of Cardinals" (1967), p.11. Accessed 2023-07-15.

[11] W. Marek, M. Srebrny, "Gaps in the Constructible Universe" (1973), pp.361--362. Annals of Mathematical Logic 6

[12] A. S. Kechris, "The Theory of Countable Analytical Sets"

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

See also

References