Googology Wiki

This wiki's URL has been migrated to the primary fandom.com domain.Read more here

READ MORE

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