Rathjen's \(\psi\) function

Not to be confused with Rathjen's Psi function.

Rathjen's \(\psi\) function based on the least weakly Mahlo cardinal is an ordinal collapsing function. A weakly Mahlo cardinal can be defined as a cardinal \(\text M\) such that all normal functions closed in \(\text M\) are closed under some regular ordinal \(<\textrm M\). He uses this to diagonalise over the weakly inaccessible hierarchy.

Definition

Restrict \(\pi\) and \(\kappa\) to uncountable regular cardinals \(<M\) only, for a function \(f\) let \(\textrm{dom}\) denote the domain of \(f\), let \(\textrm{cl}_M(X)\) denote \(X\cup\{\alpha<M:\alpha\textrm{ limit point of }X\}\), let \(\textrm{enum}(X)\) denote the unique strictly increasing function with range exactly \(X\) and let an ordinal \(\alpha\) to be strongly critical if \(\varphi_{\alpha}(0) = \alpha\).

For \(\alpha\in\Gamma_{M+1}\) and \(\beta\in M\): \(\beta\cup\{0,M\}\subseteq B^n(\alpha,\beta) \\ \gamma=\gamma_1+\cdots\gamma_k\land\gamma_1,\cdots,\gamma_k\in B^n(\alpha,\beta)\rightarrow\gamma\in B^{n+1}(\alpha,\beta) \\ \gamma=\varphi_{\gamma_0}(\gamma_1)\land\gamma_0,\gamma_1\in B^n(\alpha,\beta)\rightarrow\gamma\in B^{n+1}(\alpha,\beta) \\ \pi\in B^n(\alpha,\beta)\land\gamma<\pi\rightarrow\gamma\in B^{n+1}(\alpha,\beta) \\ \delta,\eta\in B^n(\alpha,\beta)\land\delta<\alpha\land\eta\in\textrm{dom}(\chi_\delta)\rightarrow\chi_\delta(\eta)\in B^{n+1}(\alpha,\beta) \\ B(\alpha,\beta):=\bigcup\{B^n(\alpha,\beta):n<\omega\} \\ \chi_\alpha=\textrm{enum}(\textrm{cl}_Μ(\{\kappa:\kappa\notin B(\alpha,\kappa)\land\alpha\in B(\alpha,\kappa)\}))\)

If \(\kappa=\chi_\alpha(\beta+1)\), define \(\kappa^-:=\chi_\alpha(\beta)\), otherwise if \(\kappa=\chi_\alpha(0)\), then define \(\kappa^-:=\textrm{sup}(\textrm{SC}_M(\alpha)\cup\{0\})\), where \(\textrm{SC}_M(\alpha)\) is the set of strongly critical ordinals < M.

For \(\alpha\in\Gamma_{M+1}\): \(\kappa^-\cup\{\kappa^-,M\}\subset C_\kappa^n(\alpha) \\ \gamma=\gamma_1+\cdots\gamma_k\land\gamma_1,\cdots,\gamma_k\in C^n(\alpha)\rightarrow\gamma\in C^{n+1}(\alpha) \\ \gamma=\varphi_{\gamma_0}(\gamma_1)\land\gamma_0,\gamma_1\in C^n(\alpha,\beta)\rightarrow\gamma\in C^{n+1}(\alpha) \\ \pi\in C^n_\kappa(\alpha)\cap\kappa\land\gamma<\pi\land\pi\in\textrm R\rightarrow\gamma\in C^{n+1}_\kappa(\alpha) \\ \gamma=\chi_\delta(\eta)\land\delta,\eta\in C^n_\kappa(\alpha)\rightarrow\gamma\in C^{n+1}_\kappa(\alpha)\)
\(\gamma=\,\)\(\Phi\)‍‍\(_\delta(\eta)\land\delta,\eta\in C^n_\kappa(\alpha)\land 0<\delta\land\delta,\eta<M\rightarrow\gamma\in C^{n+1}_\kappa(\alpha)\)
\(\beta<\alpha\land\pi,\beta\in C^n_\kappa(\alpha)\land\beta\in C_\pi(\beta)\rightarrow\psi_\pi(\beta)\in C^{n+1}_\kappa(\alpha) \\ C_\kappa(\alpha):=\bigcup\{C^n_\kappa(\alpha):n<\omega\} \\ \psi_\kappa(\alpha):=\textrm{min}(\{\xi:\xi\notin C_\kappa(\alpha)\})\)

Ordinal notation

It admits an associated ordinal notation \(T(\text{M})\) whose limit (i.e. ordinal type) is \(\psi_{\Omega}(\chi_{\varepsilon_{\text{M}+1}}(0))\), which is strictly greater than \(\textrm{PTO}(\textrm{KPM})\) and is strictly smaller than the limit of countable ordinals expressed by Rathjen's \(\psi\). The ordinal \(\textrm{PTO}(\textrm{KPM})\), which is called "Rathjen's ordinal" in this community, means the proof-theoretic ordinal of \(\textbf{KPM}\), where \(\textrm{KPM}\) is Kripke–Platek set theory \(\textrm{KP}\) augmented by the axiom schema "for any \(\Delta_0\)-formula \(H(x,y)\) satifying \(\forall x, \exists y, H(x,y)\), there exists an addmissible set \(z\) satisfying \(\forall x \in z, \exists y, H(x,y)\)". It coincides with \(\psi_{\omega_1}(\psi_{\chi_{\varepsilon_{\text M+1}}(0)}(0))\) in Rathjen's \(\psi\) function.

Explanation

Due to the complexity of the original notation, the one provided below has been simplified slightly, but still emulates the several properties of the ordinal collapsing function. In order to avoid the confusion similar to above ones, we emphasise that the simplified OCF below is different from the original one, and hence we do not necessarily have an ordinal notation associated to it.

We restrict \(\pi\) to uncountable regular ordinals.

\(\text{enum}(X)\) is the unique increasing function \(f\) such that the range of \(f\) is exactly \(X\).

\(\text{cl}(X)\) is the closure of \(X\); that is \(\text{cl}(X):=X\cup\{\beta \in \textrm{Lim} \mid \sup(X\cap\beta)=\beta\}\), where \(\textrm{Lim}\) denotes the class of non-zero limit ordinals. It is also the closure under the order topology, because every non-zero ordinal \(\alpha\) admits the fundamental system \(\{(\alpha + 1) \setminus (\beta + 1) \mid \beta \in \alpha\}\) of neighbourhoods in \(\textrm{On}\).

\(\text B_0(\alpha,\beta):=\beta\cup\{0,\text M\}\)

\(\text B_{n+1}(\alpha,\beta):=\{\gamma+\delta,\,\)\(\varphi\)\(_\gamma(\delta),\chi_\mu(\delta):\gamma,\delta,\mu\in\text B_n(\alpha,\beta)\wedge\mu<\alpha\}\)

\(\text B(\alpha,\beta):=\cup_{n<\omega}\text B_n(\alpha,\beta)\)

\(\chi_\alpha:=\text{enum}(\text{cl}(\{\pi:\text B(\alpha,\pi)\cap\text M\subseteq \pi\wedge\alpha\in\text B(\alpha,\pi)\}))\)

\(\text C_0(\alpha,\beta):=\beta\cup\{0,\text M\}\)

\(\text C_{n+1}(\alpha,\beta):=\{\gamma+\delta,\varphi_\gamma(\delta),\chi_\gamma(\delta),\psi_\pi(\mu):\gamma,\delta,\mu,\pi\in\text C_n(\alpha,\beta)\wedge\mu<\alpha\}\)

\(\text C(\alpha,\beta):=\cup_{n<\omega}\text C_n(\alpha,\beta)\)

\(\psi_\pi(\alpha):=\min\{\beta:\text C(\alpha,\beta)\cap\pi\subseteq\beta\wedge\alpha\in\text C(\alpha,\beta)\}\)

Rathjen originally defined the \(\psi\) function in more complicated a way in order to create an ordinal notation associated to it. Therefore it is not certain whether the simplified OCF above yields an ordinal notation or not.

The original \(\chi\) functions used in Rathjen's original OCF are not so easy to understand, and differ from the \(\chi\) functions defined above. Instead, we explain the \(\text I\) functions, which is deeply related to the original \(\chi\) functions. The \(\text I_0\) function enumerates the uncountable cardinals less than \(\text M\). The \(\text I_1\) function enumerates the weakly inaccessible cardinals less than \(\text M\), and their limits. Similarly, for each \(\alpha<\text M\), \(\text I_{1+\alpha}\) enumerates the weakly \(\alpha\)-inaccessible cardinals less than \(\text M\) (and their limits, because the function is normal), and the function \(\text I_{\text M}\) diagonalises over these, and enumerates the weakly hyper-inaccessible cardinals and their limits less than \(\text M\). \(\text I_{\text M2}\) enumerates the weakly hyper-hyper-inaccessible cardinals and their limits less than \(\text M\), and so on and so fourth. Rathjen verified that \(\chi_{\alpha}(\beta)\) (with respect to the original \(\chi\) functions) coincides with \(\textrm I_{\alpha}(\beta)\) for any \(\alpha < \Lambda_0 := \chi_{\chi_{\chi_{\cdot_{\cdot_{\cdot}}}(0)}(0)}(0)\) and \(\beta < \text M\).

Although it may not be obvious why, the limits of these large cardinals are added to the \(\text I\) function to make it much easier to notate, say, the suprenum of the first weakly inaccessible cardinal, the second weakly inaccessible cardinal, the third weakly inaccessible cardinal, \(\ldots\), as values like these don't otherwise have any way of being notated easily. Be careful that some author denote by \(\text I_\alpha\) the \(\alpha\)th weakly inaccessible cardinal, while Rathjen denoted by \(\text I_\alpha\) a function.

Common misconceptions

Common misconception	Fact	Reason
The limit of countable ordinals expressed by Rathjen's \(\psi\) function is equal to \(\textrm{PTO}(\textrm{KPM})\).	These two ordinals aren't equal	The former one is strictly greater than the limit of \(T(\text{M})\), while the latter one is strictly smaller than it.
Rathjen's \(\psi\) and simplified Rathjen's \(\psi\) are the same OCF	Rathjen's \(\psi\) function is often confounded with another simplified Rathjen's \(\psi\), but they are distinct OCFs.	The former is known to admit an ordinal notation, while the latter isn't known to admit an ordinal notation.
Rathjen's \(\psi\) function is the same as another of Rathjen's works, a function symbol \(\psi\).	Rathjen's \(\psi\) function is often confounded with another Rathjen's function symbol \(\psi\), but they are distinct notions.	The former one is a published OCF, while the latter one is just a function symbol in an ordinal notation associated to an unpublished OCF.
Rathjen's \(\psi\) satisfies \(\psi(\psi_I(0))=\psi(\Omega_{\Omega_{\Omega_{\cdots}}})\) where \(\psi\) denotes \(\psi_\Omega\), \(\Omega_{\Omega_{\Omega_{\cdots}}}\) denotes the least Omega fixed point, and \(I\) denotes the least inaccessible cardinal	An OCF satisfying this equality must be different than Rathjen's \(\psi\)	Rathjen's \(\psi\) satisfies \(\psi(\psi_I(0)) > \psi(\Omega_{\Omega_{\Omega_{\cdots}}})\)
The page 2000 steps uses \(\psi\) to denote Rathjen's \(\psi\)	The OCFs are distinct, and also the OCF on the page is unspecified	Rathjen's \(\psi\) doesn't fit the analysis given on the page
Several complicated conditions in the definition of Rathjen's \(\psi\) function are droppable if we are interested only in googology	They are important conditions that should be kept	They're used to define and prove the isomorphism of the ordinal notation associated to it, which is required for computable googology, as OCFs aren't computable.
It's possible to define the same OCF using only a single \(\text C\) function instead of both \(\text B\) and \(\text C\)	It's not guaranteed to be the same OCF	This is not done in the original text, as it is more transparent and easier to manage values when the functions are defined separately. Moreover, such a "simplification" might not admit an ordinal notation associated to it if the replacement of the definition changes the behaviour of the functions.

Sources

Ordinals, ordinal analysis, and set theory

Basics: cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation · Absolute infinity
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 one of chess) · \(\omega_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\gamma,\zeta,\Sigma\) (Infinite time Turing machine ordinals) · gap ordinal · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Hardy hierarchy · Slow-growing hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions: enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Weak Buchholz's function · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Weak 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 · Arai'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: \(\textrm{Card}\) · \(\textrm{On}\) · \(V\) · \(L\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)