Stegert's \(\Psi\) functions are two ordinal collapsing functions created by Jan-Carl Stegert as part of his 2010 Ph.D. dissertation, alongside which he also introduced collapsing hierarchies \(\mathfrak{M}\), and developed a powerful ordinal notation based on the work of Rathjen.[1]. He then used \(\Psi\) for an analysis of an extension of Kripke-Platek set theory called \(\mathsf{Stability}\).[1] (p.141)
Overview[]
The original definition of the first OCF is long and difficult, however here is a simplified overview of it.
Reflection instances are defined using ordered quintuples, and \(\mathsf M\textrm -\mathsf P\) expressions are characterized in terms of reflection configurations, ordinals, and a number \(n\in\omega\) or \(n=-1\). For an ordinal \(\kappa\) and an \(\mathsf M\textrm -\mathsf P\)-expression \(R\), a relation \(\kappa\vDash R\) is defined (not to be confused with satifaction for models), which plays the role of translating the properties represented by the \(\mathsf M\textrm -\mathsf P\)-expression into indescribability. Then, for ordinal \(\alpha\) and reflection instance \(\mathbb X\), collapsing hierarchies \(\mathfrak M^\alpha_{\mathbb X}\) are defined that play a role superficially similar to an extension of \(M^\alpha\) in Rathjen's OCF using a weakly compact cardinal (note that there are some differences, e.g. the behavior of the 1st entry \(\pi\) of \(\mathbb X\)). Finally, an ordinal collapsing function \(\Psi\) is defined.
Fast-growing function[]
Let \(\Pi_\omega\textrm{-ref}\) denote the theory \(\textrm{KP}\) augmented by a certain first-order reflection scheme[1] (p.4). As part of a characterization of the functions provably recursive in \(\Pi_\omega\textrm{-ref}\)[1] (p.96), Stegert defines a function superficially similar to the middle-growing hierarchy (composed with tetration) along \(\mathsf T(\Xi)\), using the concept of a "norm" in place of an explicit definition of fundamental sequences[1] (p.75).
Since \(\varphi_1(\Xi+1)\subseteq\varphi_1(\Xi+1)+2\subseteq\varphi_2(\Xi+1)\subseteq\mathsf T(\Xi)\), where \(\mathsf T(\Xi)\) denotes the hull-set we use, then all of the following functions are well-defined, and the order of eventual domination is as follows:
- \(f^{\mathsf T(\Xi)}_{\Psi^{\varphi_2(\Xi+1)}_{(\omega^+;\mathsf P_0;\epsilon;\epsilon;0)}}\) will eventually dominate \(f^{\mathsf T(\Xi)}_{\Psi^{\varphi_1(\Xi+1)+2}_{(\omega^+;\mathsf P_0;\epsilon;\epsilon;0)}}\),
- Which eventually dominates \(f^{\mathsf T(\Xi)}_{\Psi^{\varphi_1(\Xi+1)}_{(\omega^+;\mathsf P_0;\epsilon;\epsilon;0)}}\).
Therefore, the function \(f^{\mathsf T(\Xi)}_{\Psi^{\varphi_2(\Xi+1)}_{(\omega^+;\mathsf P_0;\epsilon;\epsilon;0)}}\) will dominate all functions provably recursive in the theory \(\Pi_\omega\textrm{-ref}\).
Sources[]
See also[]
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)