Googology Wiki
Advertisement
Googology Wiki

An ordinal \(\alpha\) is recursively Mahlo if it is admissible and for every \(\alpha\)-recursive function \(f \colon \alpha\to\alpha\), there exists \(\beta<\alpha\) such that \(\beta\) is admissible and closed under \(f\)[1]. A recursively Mahlo ordinal fixed in the context is sometimes denoted by \(\mu_0\)[1]. In particular, when one choose the least one, the least recursively Mahlo ordinal is denoted by \(\mu_0\).[2] However, it does not mean that \(\mu_0\) always denotes the least recursively Mahlo ordinal.

\(\alpha\)-recursive Functions

\(\alpha\)-recursive functions are defined for admissible ordinals \(\alpha\). A function \(f\) is \(\alpha\)-recursive if its graph is definable on \(L\)\(_\alpha\) using a \(\Delta_1\) formula.[1]

Properties

A set \(x\) is recursively Mahlo if it is admissible, and for every \(\Sigma_0\) formula \(\phi(y,z,\vec{p})\), \(\forall\vec{p}\in x(\forall y\in x\exists z\in x\phi(y,z,\vec{p})\rightarrow\exists w\in x(w\text{ is admissible}\land\vec{p}\in w\land\forall y\in w\exists z\in w\phi(y,z,\vec{p})))\).[3] For any ordinal \(\alpha\), the following are equivalent:

  1. \(\alpha\) is a recursively Mahlo ordinal.
  2. \(L_\alpha\) is a recursively Mahlo set.
  3. \(L_\alpha \models \textsf{KPM}\), i.e. \(L_{\alpha}\) is a union of admissible sets and is a recursively Mahlo set.[4]

An ordinal \(\alpha\) is recursively Mahlo if and only if it's \(\Pi_2\)-reflecting on the class of admissible ordinals[5]. As a result, recursively Mahlo ordinals are recursively inaccessible, recursively hyper-inaccessible, recursively hyper-hyper-inaccessible, etc.[6] (i.e., recursively \(``\textrm{hyper}^n\!"\textrm -\)inaccessible with \(n\in\mathbb N\)).

See also

Basics: cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation
Theories: Robinson arithmetic · Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC
Model Theoretic Concepts: structure · elementary embedding
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\eta_0\) · \(\Gamma_0\) (Feferman–Schütte ordinal) · \(\varphi(1,0,0,0)\) (Ackermann ordinal) · \(\psi_0(\Omega^{\Omega^\omega})\) (small Veblen ordinal) · \(\psi_0(\Omega^{\Omega^\Omega})\) (large Veblen ordinal) · \(\psi_0(\varepsilon_{\Omega + 1}) = \psi_0(\Omega_2)\) (Bachmann-Howard ordinal) · \(\psi_0(\Omega_\omega)\) with respect to Buchholz's ψ · \(\psi_0(\varepsilon_{\Omega_\omega + 1})\) (Takeuti-Feferman-Buchholz ordinal) · \(\psi_0(\Omega_{\Omega_{\cdot_{\cdot_{\cdot}}}})\) (countable limit of Extended Buchholz's function)‎ · \(\omega_1^\mathfrak{Ch}\) · \(\omega_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\zeta,\Sigma,\gamma\) (ordinals on infinite time Turing machine) · gap ordinal · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Slow-growing hierarchy · Hardy hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions: enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Buchholz's function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert's Psi function
Uncountable cardinals: \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal
Classes: \(V\) · \(L\) · \(\textrm{On}\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)

Sources

  1. 1.0 1.1 1.2 M. Rathjen, Collapsing functions based on recursively large ordinals: A well–ordering proof for KPM (p.3) Archive for Mathematical Logic 33, 35-55 (1994)
  2. M. Rathjen, Ordinal notations based on a weakly Mahlo cardinal, Archive for Mathematical Logic, Volume 29, Issue 4, pp. 249--263, 1990.
  3. Anton Setzer, "Universes in Type Theory Part I – Inaccessibles and Mahlo" (p.26)
  4. M. Rathjen, Proof-theoretic analysis of KPM, Arch. Math. Logic 30 (1991) 377–403.
  5. T. Arai, Proof theory for theories of ordinals—I: recursively Mahlo ordinals, Annals of Pure and Applied Logic, Volume 122, Issues 1–-3, Pages 1--85, 2003.
  6. W. Richter, P. Aczel, Inductive Definitions and Reflecting Properties of Admissible Ordinals (1973) (p.13)
Advertisement