Rathjen's psi function

Rathjen's \(\psi\) function based on the least weakly Mahlo cardinal is an ordinal collapsing function.Rathjen, Michael. "Ordinal Notations Based on a Weakly Mahlo Cardinal", Archive for Mathematical Logic 29 (1990) 249--263. A weakly Mahlo cardinal can be defined as a cardinal \(M\) such that all normal functions closed in \(M\) are closed under some regular ordinal \(<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{ is a limit point of }X\}\), and let \(\textrm{enum}(X)\) denote the enumeration of \(X\). An ordinal \(\alpha\) is said to be to be strongly critical if \(\varphi_{\alpha}(0) = \alpha\).
For \(\alpha\in\Gamma_{M+1}\) and \(\beta\in M\): \(\begin{array}{l} \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)\})) \end{array} \)
If \(\kappa = \chi_\alpha(\beta+1)\) for some \((\alpha,\beta) \in \Gamma_{M+1} \times M\), define \(\kappa^- := \chi_\alpha(\beta)\) using the unique \((\alpha,\beta)\). Otherwise if \(\kappa = \chi_\alpha(0)\) for some \(\alpha \in \Gamma_{M+1}\), then define \(\kappa^- := \textrm{sup}(\textrm{SC}_M(\alpha)\cup\{0\})\) using the unique \(\alpha\), where \(\textrm{SC}_M(\alpha)\) is a set of strongly critical ordinals < M explicitly defined in the original source. 
For \(\alpha\in\Gamma_{M+1}\): \(\begin{array}{l} \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) \end{array}\)\(\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)\)\(\begin{array}{l} \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)\}) \end{array}\)
== Ordinal notation ==
It admits an associated ordinal notation \(T(\text{M})\) whose limit (i.e. ordinal type) is \(\psi_{\Omega}(\chi_{\varepsilon_{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 \(\textrm{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 admissible set \(z\) satisfying \(\forall x \in z, \exists y, H(x,y)\)". It coincides with \(\psi_{\chi_0(0)}(\psi_{\chi_{\varepsilon_{M+1}}(0)}(0))\) in Rathjen's \(\psi\) function.Rathjen, Michael. "Collapsing functions based on recursively large ordinals: A well-ordering proof for KPM", Archive for Mathematical Logic (1994), Volume 33, Issue 1, pp 35–55.
== 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,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 M\subseteq \pi\wedge\alpha\in\text B(\alpha,\pi)\}))\)
\(\text C_0(\alpha,\beta):=\beta\cup\{0,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 \(M\). The \(\text I_1\) function enumerates the weakly inaccessible cardinals less than \(M\), and their limits. Similarly, for each \(\alpha< M\), \(\text I_{1+\alpha}\) enumerates the weakly \(\alpha\)-inaccessible cardinals less than \(M\) (and their limits, because the function is normal), and the function \(\text I_{M}\) diagonalises over these, and enumerates the weakly hyper-inaccessible cardinals and their limits less than \(M\). \(\text I_{M2}\) enumerates the weakly hyper-hyper-inaccessible cardinals and their limits less than \( 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 < 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 \(I_\alpha\) the \(\alpha\)th weakly inaccessible cardinal, while Rathjen denoted by \(\text I_\alpha\) a function.
==Common misconceptions==
Here is a list of common misconceptions in this community, originally pointed out by a Japanese Googology Wiki user p進大好きbot.A difference page of ordinal collapsing function. For more common misconceptions, see also the full list.
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.Rathjen, Michael. "The Realm of Ordinal Analysis" 	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.Rathjen, Michael. "Proof-theoretic analysis of KPM", Archive for Mathematical Logic 30 (1991) 377--403.	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}}})\) due to \(\Phi\) being included in the closure.
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 ==
Category:Ordinal collapsing functions
Category:Ordinal notations
Category:Set theory