Admissible ordinal information

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]

^ ^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

[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

Admissible ordinal information

and 25 Related for: Admissible ordinal information

Admissible ordinal

Large countable ordinal

Nonrecursive ordinal

Ordinal number

Ordinal analysis

Alpha recursion theory

Woodin cardinal

Admissible set

Computation in the limit

Level of measurement

Saul Kripke

Ordinal collapsing function

Glossary of set theory

Veblen function

Axiom of constructibility

American philosophy

Indescribable cardinal

Shrewd cardinal

Rule of inference

Monotonic function

Proof theory

Hyperarithmetical theory

Constructible universe

Cardinal utility

Aggregated indices randomization method