Madore's \(\psi\) function is an ordinal collapsing function introduced by David Madore (username Gro-Tsen on Wikipedia) in 2008[1] and updated until 2013.[2]
Definition[]
Madore's \(\psi\) function is defined as follows:
Let \(\omega\) be the smallest transfinite ordinal and \(\Omega\) be the smallest uncountable ordinal. Then,
\(C_0(\alpha) = \{0, 1, \omega, \Omega\}\)
\(C_{n+1}(\alpha) = \{\gamma + \delta, \gamma\delta, \gamma^{\delta} \mid \gamma, \delta \in C_n (\alpha)\} \cup \{\psi(\eta) \mid \eta \in C_n (\alpha) \land \eta < \alpha\} \)
\(C(\alpha) = \bigcup_{n < \omega} C_n (\alpha) \)
\(\psi(\alpha) = \min\{\beta < \Omega|\beta \notin C(\alpha)\} \)
In other words, \(\psi(\alpha)\) is the least ordinal number less than \(\Omega\) which cannot be generated from the ordinals \(0, 1, \omega, \Omega\) using any finite combination of addition, multiplication, exponentiation, or the \(\psi\) function itself (with the restriction of applying \(\psi(\eta)\) only for ordinals \(\eta < \alpha\) that have already been constructed).
The limit of this function is the Bachmann-Howard ordinal.
Examples[]
- \(\psi(0)=\) \(\varepsilon_0\)
- \(\psi(1)=\varepsilon_1\)
- \(\psi(2)=\varepsilon_2\)
- \(\psi(\omega)=\varepsilon_\omega\)
- \(\psi(\psi(0))=\psi(\varepsilon_0)=\varepsilon_{\varepsilon_0}\)
- \(\psi(\psi(\psi(0)))=\psi(\psi(\varepsilon_0))=\psi(\varepsilon_{\varepsilon_0})=\varepsilon_{\varepsilon_{\varepsilon_0}}\)
- \(\psi(\zeta_0)=\) \(\zeta_0\)
- \(\psi(\zeta_0+1)=\zeta_0\)
- \(\psi(\eta_0)=\zeta_0\)
- \(\psi(\Omega)=\zeta_0\)
- \(\psi(\Omega+1)=\varepsilon_{\zeta_0+1}\)
- \(\psi(\Omega+2)=\varepsilon_{\zeta_0+2}\)
- \(\psi(\Omega+\omega)=\varepsilon_{\zeta_0+\omega}\)
- \(\psi(\Omega+\zeta_0)=\varepsilon_{\zeta_02}\)
- \(\psi(\Omega+\zeta_02)=\varepsilon_{\zeta_03}\)
- \(\psi(\Omega+\zeta_0\omega)=\varepsilon_{\zeta_0\omega}\)
- \(\psi(\Omega+\zeta_0^2)=\varepsilon_{\zeta_0^2}\)
- \(\psi(\Omega+\varepsilon_{\zeta_0+1})=\varepsilon_{\varepsilon_{\zeta_0+1}}\)
- \(\psi(\Omega+\varepsilon_{\varepsilon_{\zeta_0+1}})=\varepsilon_{\varepsilon_{\varepsilon_{\zeta_0+1}}}\)
- \(\psi(\Omega+\zeta_1)=\zeta_1\)
- \(\psi(\Omega+\zeta_1+1)=\zeta_1\)
- \(\psi(\Omega2)=\zeta_1\)
- \(\psi(\Omega2+1)=\varepsilon_{\zeta_1+1}\)
- \(\psi(\Omega3)=\zeta_2\)
- \(\psi(\Omega^2)=\) \(\eta_0 = \varphi(3,0)\)
- \(\psi(\Omega^3)=\varphi(4,0)\)
- \(\psi(\Omega^4)=\varphi(5,0)\)
- \(\psi(\Omega^{\omega})=\varphi(\omega,0)\)
- \(\psi(\Omega^{\omega+1})=\varphi(\omega+1,0)\)
- \(\psi(\Omega^{\omega2})=\varphi(\omega2,0)\)
- \(\psi(\Omega^{\omega^2})=\varphi(\omega^2,0)\)
- \(\psi(\Omega^{\Omega})=\) \(\Gamma_0\)
- \(\psi(\Omega^{\Omega+1})=\) \(\varphi(1,1,0)\)
- \(\psi(\Omega^{\Omega 2})=\) \(\varphi(2,0,0)\)
- \(\psi(\Omega^{\Omega^{3}})=\) \(\varphi(1,0,0,0,0)\)
- \(\psi(\Omega^{\Omega^{\omega}})=\) SVO
- \(\psi(\Omega^{\Omega^{\Omega}})=\) LVO
- \(\psi(\varepsilon_{\Omega+1})=\) BHO
We can note that the Madore's \(\psi\) function relates to the binary Veblen function by the following way: \(\psi(\Omega^{\alpha}) = \varphi(\alpha+1,0)\), where \(0 < \alpha < \omega\).
Fundamental sequences[]
Now we assign a fundamental sequence for each limit ordinal below the Bachmann-Howard ordinal. The fundamental sequence for an ordinal number \(\alpha\) with cofinality \(\beta\) is a strictly increasing sequence \((\alpha[\eta])_{\eta<\beta}\) with a length of \(\beta\) and whose limit is \(\alpha\), where \(\alpha[\eta]\) is the \(\eta\)-th element of the sequence. If \(\alpha\) is a countable limit ordinal (i.e. \(\alpha\) is a limit ordinal less than \(\Omega\)) then \(\text{cof}(\alpha)=\omega\). The first uncountable ordinal \(\Omega\) is the least ordinal whose cofinality greater than \(\omega\) since \(\text{cof}(\Omega)=\Omega\).
First we must define the normal forms for expressions given by all relevant functions:
\(\alpha=_{NF}\alpha_1+\alpha_2+\cdots+\alpha_n\) iff \(\alpha=\alpha_1+\alpha_2+\cdots+\alpha_n\) and \(\alpha_1\geq\alpha_2\geq\cdots\geq\alpha_n\)
\(\alpha=_{NF}\omega^\beta\) iff \(\alpha=\omega^\beta\) for some \(\beta<\alpha\)
\(\alpha=_{NF}\Omega^\beta\gamma\) iff \(\alpha=\Omega^\beta\gamma\) for some \(\gamma<\Omega\)
\(\alpha=_{NF}\psi(\beta)\) iff \(\alpha=\psi(\beta)\) for some \(\beta\in C(\beta)\)
Then for these limit ordinals, when written in normal form, we can assign the fundamental sequences as follows:
1) if \(\alpha=\alpha_1+\alpha_2+\cdots+\alpha_n\) then \(\text{cof} (\alpha)= \text{cof} (\alpha_n)\) and \(\alpha[\eta]=\alpha_1+\alpha_2+\cdots+(\alpha_n[\eta])\)
2) if \(\alpha=\omega^\beta\) and \(\beta\) is a countable limit ordinal then \(\alpha[n]=\omega^{\beta[n]}\)
3) if \(\alpha=\omega^\beta\) and \(\beta=\gamma+1\) then \(\alpha[n]=\omega^\gamma n\)
4) if \(\alpha=\psi(0)\) then \(\alpha[0]=1\) and \(\alpha[n+1]=\omega^{\alpha[n]}\)
5) if \(\alpha=\psi(\beta+1)\) then \(\alpha[0]=\psi(\beta)+1\) and \(\alpha[n+1]=\omega^{\alpha[n]}\)
6) if \(\alpha=\Omega^{\beta}\gamma\) and \(\text{cof} (\gamma)=\omega\) then \(\text{cof} (\alpha)= \omega\) and \(\alpha[\eta]=\Omega^{\beta}(\gamma[\eta])\)
7) if \(\alpha=\Omega^{\beta+1}(\gamma+1)\) then \(\text{cof} (\alpha)=\Omega \) and \(\alpha[\eta]=\Omega^{\beta+1}\gamma+\Omega^\beta\eta\)
8) if \(\alpha=\Omega^\beta(\gamma+1)\) and \(\text{cof}(\beta)\geq\omega\) then \(\text{cof}(\alpha)= \text{cof}(\beta)\) and \(\alpha[\eta]=\Omega^\beta\gamma+\Omega^{\beta[\eta]}\)
9) if \(\alpha=\varepsilon_{\Omega+1}\) then \(\text{cof} (\alpha)=\omega\) and \(\alpha[0]=1\) and \(\alpha[n+1]=\Omega^{\alpha[n]}\)
10) if \(\alpha=\psi(\beta)\) and \(\text{cof}(\beta)=\omega\) then \(\text{cof} (\alpha)=\omega\) and \(\alpha[n]=\psi(\beta[n])\)
11) if \(\alpha=\psi(\beta)\) and \(\text{cof}(\beta)=\Omega\) then \(\text{cof} (\alpha)=\omega\) and \(\alpha[0]=1\) and \(\alpha[n+1]=\psi(\beta[\alpha[n]])\)
For example, the ordinal \(\psi(\Omega^{\Omega^2+\Omega3})\) has the following fundamental sequence (using rules 1, 7, 8, 10)
\(\psi(\Omega^{\Omega^2+\Omega3})[0]=1\),
\(\psi(\Omega^{\Omega^2+\Omega3})[1]=\psi(\Omega^{\Omega^2+\Omega2+1})\),
\(\psi(\Omega^{\Omega^2+\Omega3})[2]=\psi\left(\Omega^{\Omega^2+\Omega2+\psi(\Omega^{\Omega^2+\Omega2+1})}\right)\),
and so on.
Assigning fundamental sequences for any ordinal collapsing function is vital for its use in the fast-growing hierarchy, slow-growing hierarchy and Hardy hierarchy.
Ordinal Notation[]
Unlike other standard ordinal collapsing functions, there seems to be no canonical ordinal notation associated to Madore's function. In order to create a computable large number by using fast-growing hierarchy applied to the system of fundamental sequences defined in set theory, we need to fix an ordinal notation associated to it.
References[]
- ↑ "Ordinal Collapsing Function". Wikipedia. 2008-04-16.
- ↑ "Ordinal Collapsing Function". Wikipedia. 2013-02-23.
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 · Berkeley cardinal · (Club Berkeley cardinal · limit club Berkeley cardinal)
Classes: \(\textrm{Card}\) · \(\textrm{On}\) · \(V\) · \(L\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)