- Not to be confused with Extended Buchholz's function, Weak Buchholz's function, or Jäger-Buchholz function.
Buchholz's psi functions are ordinal collapsing functions created by German mathematician Wilfried Buchholz. Although there are many different Buchholz's psi functions, e.g. Jäger-Buchholz function, this article explains the most well-known one in this community, which is a hierarchy of single-argument functions \(\psi_\nu(\alpha)\) introduced in 1986,^{[1]} as the other ones are not currently used in this community. These functions are a simplified version of Feferman's \(\theta\) functions, but nevertheless have the same strength as them.
Definition
Buchholz defined his functions as follows:
- \(C_\nu^0(\alpha) = \Omega_\nu\),
- \(C_\nu^{n+1}(\alpha) = C_\nu^n(\alpha) \cup \{\gamma | P(\gamma) \subseteq C_\nu^n(\alpha)\} \cup \{\psi_\mu(\xi) | \xi \in \alpha \cap C_\nu^n(\alpha) \wedge \xi \in C_\mu(\xi) \wedge \mu \leq \omega\}\),
- \(C_\nu(\alpha) = \bigcup_{n < \omega}C_\nu^n (\alpha)\),
- \(\psi_\nu(\alpha) = \min\{\gamma | \gamma \not\in C_\nu(\alpha)\}\),
where \(\omega\) is the smallest infinite ordinal,
\(\Omega_\nu=\left\{\begin{array}{lcr}1\text{ if }\nu=0\\\aleph_\nu\text{ if }\nu>0\\\end{array}\right.\)
and \(P(\gamma)=\{\gamma_1,\cdots,\gamma_k\}\) is the set of additive principal numbers in form \(\omega^\xi\),
\(P=\{\alpha\in \textrm{On}: 0<\alpha \wedge \forall \xi, \eta < \alpha (\xi+\eta < \alpha)\}=\{\omega^\xi: \xi \in \textrm{On}\}\),
the sum of which gives this ordinal \(\gamma\):
\(\gamma=\alpha_1+\alpha_2+\cdots+\alpha_k\) where \(\alpha_1\geq\alpha_2\geq\cdots\geq\alpha_k\) and \(\alpha_1,\alpha_2,\cdots,\alpha_k \in P(\gamma)\).
Note: Greek letters always denotes ordinals. \(\textrm{On}\) denotes the class of all ordinals. The convention \(\Omega_0\) depends on the context even if we are focusing on Buchholz's function. Actually, Buchholz himself uses \(\Omega_0\) as both of shorthands of \(1\) and \(\omega\)^{[1]}^{[2]}, however for the ordinal notation to correspond to Buchholz's function as intended, of the two conventions \(\Omega_0=1\) must be used. Also note that \(P(\omega+\omega)=\{\omega\}\) although the sum of all (distinct) elements of \(P(\omega+\omega)\) isn't equal to \(\omega+\omega\).
The limit of this function is the Takeuti-Feferman-Buchholz ordinal.
Properties
Buchholz showed following properties of those functions:
- \(\psi_\nu(0)=\Omega_\nu\),
- \(\psi_\nu(\alpha)\in P\),
- \(\psi_\nu(\alpha+1)=\text{min}\{\gamma\in P: \psi_\nu(\alpha)<\gamma\}\text{ if }\alpha\in C_\nu(\alpha)\),
- \(\Omega_\nu\le\psi_\nu(\alpha)<\Omega_{\nu+1}\),
- \(\alpha\le\beta\Rightarrow\psi_\nu(\alpha)\le\psi_\nu(\beta)\),
- \(\psi_0(\alpha)=\omega^\alpha \text{ if }\alpha<\varepsilon_0\),
- \(\psi_\nu(\alpha)=\omega^{\Omega_\nu+\alpha} \text{ if }\alpha<\varepsilon_{\Omega_\nu+1} \text{ and } \nu\neq 0\),
- \(\theta(\varepsilon_{\Omega_\nu+1},0)=\psi_0(\varepsilon_{\Omega_\nu+1})\) for \(0<\nu\le\omega\).
Explanation
Buchholz is working in Zermelo–Fraenkel set theory along with the von Neumann ordinals, that means every ordinal \(\alpha\) is characterized by the set \(\{\beta|\beta<\alpha\}\). Then condition \(C_\nu^0(\alpha)=\Omega_\nu\) means that set \(C_\nu^0(\alpha)\) includes all ordinals less than \(\Omega_\nu\) in other words \(C_\nu^0(\alpha)=\{\beta|\beta<\Omega_\nu\}\).
The condition \(C_\nu^{n+1}(\alpha) = C_\nu^n(\alpha) \cup \{\gamma | P(\gamma) \subseteq C_\nu^n(\alpha)\} \cup \{\psi_\mu(\xi) | \xi \in \alpha \cap C_\nu^n(\alpha) \wedge \mu \leq \omega\}\) means that set \(C_\nu^{n+1}(\alpha)\) includes:
- all ordinals from previous set \(C_\nu^n(\alpha)\),
- all ordinals that can be obtained by summation the additively principal ordinals from previous set \(C_\nu^n(\alpha)\),
- all ordinals that can be obtained by applying ordinals less than \(\alpha\) from the previous set \(C_\nu^n(\alpha)\) as arguments of functions \(\psi_\mu\), where \(\mu\le\omega\).
That is why we can rewrite this condition as:
\(C_\nu^{n+1}(\alpha) = \{\beta+\gamma,\psi_\mu(\eta)|\beta, \gamma,\eta\in C_{\nu}^n(\alpha)\wedge\eta<\alpha \wedge \mu \leq \omega\}\).
Thus union of all sets \(C_\nu^n (\alpha)\) with \(n<\omega\) i.e. \(C_\nu(\alpha) = \bigcup_{n < \omega} C_\nu^n (\alpha)\) denotes the set of all ordinals which can be generated from ordinals \(<\aleph_\nu\) by the functions + (addition) and \(\psi_{\mu}(\xi)\), where \(\mu\le\omega\) and \(\xi<\alpha\).
Then \(\psi_\nu(\alpha) = \min\{\gamma | \gamma \not\in C_\nu(\alpha)\}\) is the smallest ordinal that does not belong to this set.
Examples
Consider the following examples:
\(C_0^0(\alpha)=\{0\} =\{\beta:\beta<1\}\),
\(C_0(0)=\{0\}\) (since there is no \(\eta<0\) and 0+0=0).
Then \(\psi_0(0)=1\).
\(C_0(1)\) includes \(\psi_0(0)=1\) and all possible sums of 1s, i.e. the natural numbers. It also includes other ordinals like \(\psi_\nu(0)\) for \(\nu\le\omega\) and sums of those:
\(C_0(1)=\{0,1,2,...,\text{googol},\cdots,\text{TREE(googol)},\cdots,\psi_1(0),\cdots,\psi_1(0)+\psi_1(0),\cdots,\psi_2(0),\cdots\}\).
Then \(\psi_0(1)=\omega\) - first transfinite ordinal, which is greater than all natural numbers by its definition. Since \(\omega\) is the least ordinal not in \(C_0(1)\), we don't need to consider its transfinite elements in this case.
\(C_0(2)\) includes \(\psi_0(0)=1, \psi_0(1)=\omega\) (as well as some other uncountable ordinals) and all possible sums of them.
Then \(\psi_0(2)=\omega^2\).
For \(C_0(\omega)\) we have set \(C_0(\omega)=\{0,\psi(0)=1,...,\psi(1)=\omega,...,\psi(2)=\omega^2,...,\psi(3)=\omega^3,...,\psi_1(0),\cdots\}\).
Then \(\psi_0(\omega)=\omega^\omega\).
For \(C_0(\Omega)\) we have set \(C_0(\Omega)=\{0,\psi(0)=1,...,\psi(1)=\omega,...,\psi(\omega)=\omega^\omega,...,\psi(\omega^\omega)=\omega^{\omega^\omega},...\}\).
Then \begin{eqnarray*} & & \psi_0(\varepsilon_0)=\psi_0(\varepsilon_0+1) \\ & = & \cdots=\psi_0(\textrm{insert any countable ordinal above } \varepsilon_0 \textrm{which you like very much}) \\ & = & \cdots = \psi_0(\Omega)=\varepsilon_0. \end{eqnarray*} For \(C_0(\Omega+1)\) we have set \(C_0(\Omega)=\{0,1,...,\psi_0(\Omega)=\varepsilon_0,...,\varepsilon_0+\varepsilon_0,...\psi_1(0)=\Omega,...\}\).
Then \(\psi_0(\Omega+1)=\varepsilon_0\omega=\omega^{\varepsilon_0+1}\).
\(\psi_0(\Omega2)=\varepsilon_1\),
\(\psi_0(\Omega^2)=\zeta_0\),
\(\psi_0(\Omega^\alpha(1+\beta)) = \varphi(\alpha,\beta)\),
\(\psi_0(\Omega^\Omega)=\Gamma_0=\theta(\Omega,0)\), using Feferman theta-function,
\(\psi_0(\Omega^{\Omega^\Omega})\) is large Veblen ordinal,
\(\psi_0(\varepsilon_{\Omega+1})=\theta(\varepsilon_{\Omega+1},0)\).
Now let's research how \(\psi_1\) works:
\(C_1^0(\alpha)=\{\beta:\beta<\Omega_1\}=\{0,\psi(0)=1,2,...\text{googol},...,\psi_0(1)=\omega,...,\psi_0(\Omega)=\varepsilon_0,...\)
\(...,\psi_0(\Omega^\Omega)=\Gamma_0,...,\psi(\Omega^{\Omega^\Omega+\Omega^2}),...\}\) i.e. includes all countable ordinals.
\(C_1(\alpha)\) includes all possible sums of all countable ordinals. Then
\(\psi_1(0)=\Omega_1\) first uncountable ordinal which is greater than all countable ordinal by its definition i.e. smallest number with cardinality \(\aleph_1\).
\(C_1(1)=\{0,...,\psi_0(0)=\omega,...,\psi_1(0)=\Omega,...,\Omega+\omega,...,\Omega+\Omega,...\}\)
Then \(\psi_1(1)=\Omega\omega=\omega^{\Omega+1}\).
Then \(\psi_1(2)=\Omega\omega^2=\omega^{\Omega+2}\),
\(\psi_1(\psi_0(\Omega))=\Omega\varepsilon_0=\omega^{\Omega+\varepsilon_0}\),
\(\psi_1(\psi_0(\Omega^\Omega))=\Omega\Gamma_0=\omega^{\Omega+\Gamma_0}\),
\(\psi_1(\psi_1(0))=\psi_1(\Omega)=\Omega^2=\omega^{\Omega+\Omega}\),
\(\psi_1(\psi_1(\psi_1(0)))=\omega^{\Omega+\omega^{\Omega+\Omega}}=\omega^{\Omega\cdot\Omega}=(\omega^{\Omega})^\Omega=\Omega^\Omega\),
\((\psi_1)^4(0)=\Omega^{\Omega^\Omega}\), where the superscript denotes function iteration,
\(\psi_1(\Omega_2)=\varepsilon_{\Omega+1}\).
For case \(\psi(\Omega_2)\) the set \(C_0(\Omega_2)\) includes functions \(\psi_0\) with all arguments less than \(\Omega_2\) i.e. such arguments as \(0, \psi_1(0), \psi_1(\psi_1(0)), \psi_1^3(0),...\)
and then \(\psi_0(\Omega_2)=\psi_0(\psi_1(\Omega_2))=\psi_0(\varepsilon_{\Omega+1})\).
In general case: \(\psi_0(\Omega_{\nu+1})=\psi_0(\psi_\nu(\Omega_{\nu+1}))=\psi_0(\varepsilon_{\Omega_\nu+1})=\theta(\varepsilon_{\Omega_\nu+1},0)\).
We also can write:
\(\theta(\Omega_\nu,0)=\psi_0(\Omega_\nu^{\Omega_\nu})\) ( for \( 1\le\nu<\omega\)).
Comparison between Buchholz’s and Veblen’s functions
Up to Feferman–Schütte ordinal
Buchholz function | Veblen function |
---|---|
a natural number \(n>0\) is an abbriviation for \(\underbrace{\psi_0(0)+\cdots+\psi_0(0)}_{n\ \psi 's}\) | a natural number \(n>0\) is an abbriviation for \(\underbrace{\varphi(0,0)+\cdots+\varphi(0,0)}_{n\ \varphi 's}\) |
\(\psi_0(0)\) | \(\varphi(0,0)=1\) |
\(\psi_0(0)+\psi_0(0)\) | \(\varphi(0,0) +\varphi(0,0)=2\) |
\(\psi_0(1)\) | \(\varphi(0,1) =\omega\) |
\(\psi_0(2)\) | \(\varphi(0,2) =\omega^2\) |
\(\psi_0(\psi_0(1))\) | \(\varphi(0,\varphi(0,1)) =\omega^\omega\) |
\(\psi_0(\psi_0(2))\) | \(\varphi(0,\varphi(0,2))=\omega^{\omega^2}\) |
\(\psi_0(\psi_0(\psi_0(1)))\) | \(\varphi(0,\varphi(0,\varphi(0,1)))=\omega^{\omega^\omega}\) |
\(\psi_0(\psi_1(0))\) | \(\varphi(1,0)=\varepsilon_0\) |
\(\psi_0(\psi_1(0)+1)\) | \(\varphi(0,\varphi(1,0)+1)=\omega^{\varepsilon_0+1}=\varepsilon_0\cdot\omega\) |
\(\psi_0(\psi_1(0)+2)\) | \(\varphi(0,\varphi(1,0)+2)=\omega^{\varepsilon_0+2}=\varepsilon_0\cdot\omega^2\) |
\(\psi_0(\psi_1(0)+\psi_0(\psi_1(0)))\) | \(\varphi(0,\varphi(1,0)+\varphi(1,0))=\omega^{\varepsilon_0+\varepsilon_0}=\varepsilon_0^2\) |
\(\psi_0(\psi_1(0)+\psi_0(\psi_1(0)+1))\) | \(\varphi(0,\varphi(0,\varphi(1,0)+1))=\omega^{\omega^{\varepsilon_0+1}}\) |
\(\psi_0(\psi_1(0)+\psi_0(\psi_1(0)+\psi_0(\psi_1(0)+1)))\) | \(\varphi(0,\varphi(0,\varphi(0,\varphi(1,0)+1)))=\omega^{\omega^{\omega^{\varepsilon_0+1}}}\) |
\(\psi_0(\psi_1(0)+\psi_1(0))\) | \(\varphi(1,1)=\varepsilon_1\) |
\(\psi_0(\psi_1(0)+\psi_1(0)+\psi_1(0))\) | \(\varphi(1,2)=\varepsilon_2\) |
\(\psi_0(\psi_1(1))\) | \(\varphi(1,\varphi(0,1))=\varepsilon_\omega\) |
\(\psi_0(\psi_1(2))\) | \(\varphi(1,\varphi(0,2))=\varepsilon_{\omega^2}\) |
\(\psi_0(\psi_1(\psi_0(\psi_1(0))))\) | \(\varphi(1,\varphi(1,0))=\varepsilon_{\varepsilon_0}\) |
\(\psi_0(\psi_1(\psi_0(\psi_1(\psi_0(\psi_1(0))))))\) | \(\varphi(1,\varphi(1,\varphi(1,0)))=\varepsilon_{\varepsilon_{\varepsilon_0}}\) |
\(\psi_0(\psi_1(\psi_1(0)))\) | \(\varphi(2,0)=\zeta_0\) |
\(\psi_0(\psi_1(\psi_1(0))+1)\) | \(\varphi(0,\varphi(2,0)+1)=\omega^{\zeta_0+1}\) |
\(\psi_0(\psi_1(\psi_1(0))+\psi_0(\psi_1(\psi_1(0))+1))\) | \(\varphi(0,\varphi(0,\varphi(2,0)+1))=\omega^{\omega^{\zeta_0+1}}\) |
\(\psi_0(\psi_1(\psi_1(0))+\psi_1(0))\) | \(\varphi(1,\varphi(2,0)+1)=\varepsilon_{\zeta_0+1}\) |
\(\psi_0(\psi_1(\psi_1(0))+\psi_1(0)+1)\) | \(\varphi(0,\varphi(1,\varphi(2,0)+1)+1)=\omega^{\varepsilon_{\zeta_0+1}+1}\) |
\(\psi_0(\psi_1(\psi_1(0))+\psi_1(0)+\psi_1(0))\) | \(\varphi(1,\varphi(2,0)+2)=\varepsilon_{\zeta_0+2}\) |
\(\psi_0(\psi_1(\psi_1(0))+\psi_1(1))\) | \(\varphi(1,\varphi(2,0)+\varphi(0,1))=\varepsilon_{\zeta_0+\omega}\) |
\(\psi_0(\psi_1(\psi_1(0))+\psi_1(\psi_0(\psi_1(\psi_1(0))+\psi_1(1))))\) | \(\varphi(1,\varphi(1,\varphi(2,0)+\varphi(0,1))=\varepsilon_{\varepsilon_{\zeta_0+\omega}}\) |
\(\psi_0(\psi_1(\psi_1(0))+\psi_1(\psi_1(0)))\) | \(\varphi(2,1)=\zeta_1\) |
\(\psi_0(\psi_1(\psi_1(0)+1))\) | \(\varphi(2,\varphi(0,1))=\zeta_\omega\) |
\(\psi_0(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_1(0)+1))))\) | \(\varphi(2,\varphi(2,\varphi(0,1)))=\zeta_{\zeta_\omega}\) |
\(\psi_0(\psi_1(\psi_1(0)+\psi_1(0)))\) | \(\varphi(3,0)=\eta_0\) |
\(\psi_0(\psi_1(\psi_1(0)+\psi_1(0))+\psi_1(\psi_1(0)+\psi_1(0)))\) | \(\varphi(3,1)=\eta_1\) |
\(\psi_0(\psi_1(\psi_1(0)+\psi_1(0)+1))\) | \(\varphi(3,\varphi(0,1))=\eta_{\omega}\) |
\(\psi_0(\psi_1(\psi_1(0)+\psi_1(0)+\psi_0(\psi_1(\psi_1(0)+\psi_1(0)+1)))\) | \(\varphi(3,\varphi(3,\varphi(0,1)))=\eta_{\eta_{\omega}}\) |
\(\psi_0(\psi_1(\psi_1(0)+\psi_1(0)+\psi_1(0)))\) | \(\varphi(4,0)\) |
\(\psi_0(\psi_1(\psi_1(1)))\) | \(\varphi(\varphi(0,1),0) = \varphi(\omega,0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_0(\psi_1(\psi_1(1))))))\) | \(\varphi(\varphi(\varphi(0,1),0),0) = \varphi(\varphi(\omega,0),0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0))))\) | \(\varphi(1,0,0)=\Gamma_0\) |
Up to Large Veblen ordinal
Buchholz function | Veblen function |
---|---|
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+1)\) | \(\varphi(0,\varphi(1,0,0)+1)=\omega^{\Gamma_0+1}\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(0))\) | \(\varphi(1,\varphi(1,0,0)+1)=\varepsilon_{\Gamma_0+1}\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(1))\) | \(\varphi(1,\varphi(1,0,0)+\varphi(0,1))=\varepsilon_{\Gamma_0+\omega}\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(0)))\) | \(\varphi(2,\varphi(1,0,0)+1)=\zeta_{\Gamma_0+1}\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(0)+1))\) | \(\varphi(2,\varphi(1,0,0)+\varphi(0,1))=\zeta_{\Gamma_0+\omega}\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(0)+\psi_1(0)))\) | \(\varphi(3,\varphi(1,0,0)+1)=\eta_{\Gamma_0+1}\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(1)))\) | \(\varphi(\varphi(0,1),\varphi(1,0,0)+1)=\varphi(\omega,\Gamma_0+1)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(\psi_0(\psi_1(\psi_1(1))))))\) | \(\varphi(\varphi(\varphi(0,1),0),\varphi(1,0,0)+1)=\varphi(\varphi(\omega,0),\Gamma_0+1)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(\psi_0(\psi_1(\psi_1(\psi_1(0)))))))\) | \(\varphi(\varphi(1,0,0),1)=\varphi(\Gamma_0,1)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(\psi_0(\psi_1(\psi_1(\psi_1(0)))))+1))\) | \(\varphi(\varphi(1,0,0),\varphi(0,1))=\varphi(\Gamma_0,\omega)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(\psi_0(\psi_1(\psi_1(\psi_1(0)))))\)
\(+\psi_0(\psi_1(\psi_1(\psi_1(0))))))\) |
\(\varphi(\varphi(1,0,0),\varphi(1,0,0))=\varphi(\Gamma_0,\Gamma_0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(\psi_0(\psi_1(\psi_1(\psi_1(0)))))+\psi_1(0)))\) | \(\varphi(\varphi(1,0,0)+1,0)=\varphi(\Gamma_0+1,0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(\psi_0(\psi_1(\psi_1(\psi_1(0))))+1)))\) | \(\varphi(\varphi(0,\varphi(1,0,0)+1),0)=\varphi(\omega^{\Gamma_0+1},0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(\psi_0(\psi_1(\psi_1(\psi_1(0)))+1))))\) | \(\varphi(\varphi(0,\varphi(0,\varphi(1,0,0)+1)),0)=\varphi(\omega^{\omega^{\Gamma_0+1}},0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(0)))))\) | \(\varphi(\varphi(1,\varphi(1,0,0)+1),0)=\varphi(\varepsilon_{\Gamma_0+1},0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(1)))))\) | \(\varphi(\varphi(1,\varphi(1,0,0)+\varphi(0,1)),0)=\varphi(\varepsilon_{\Gamma_0+\omega},0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(0))))))\) | \(\varphi(\varphi(2,\varphi(1,0,0)+1),0)=\varphi(\zeta_{\Gamma_0+1},0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(0)+1)))))\) | \(\varphi(\varphi(2,\varphi(1,0,0)+\varphi(0,1)),0)=\varphi(\zeta_{\Gamma_0+\omega},0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(0)+\psi_1(0))))))\) | \(\varphi(\varphi(3,\varphi(1,0,0)+1),0)=\varphi(\eta_{\Gamma_0+1},0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(1))))))\) | \(\varphi(\varphi(\varphi(0,1),\varphi(1,0,0)+1),0)=\varphi(\varphi(\omega,\Gamma_0+1),0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)))+\psi_1(\psi_1(\psi_1(0))))\) | \(\varphi(1,0,1)=\Gamma_1\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0))+1))\) | \(\varphi(1,0,\varphi(0,1))=\Gamma_{\omega}\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0))+\psi_0(\psi_1(\psi_1(\psi_1(0))+1))))\) | \(\varphi(1,0,\varphi(1,0,\varphi(0,1)))=\Gamma_{\Gamma_{\omega}}\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0))+\psi_1(0)))\) | \(\varphi(1,1,0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0))+\psi_1(0))+\psi_1(\psi_1(\psi_1(0))+\psi_1(0)))\) | \(\varphi(1,1,1)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0))+\psi_1(0)+1))\) | \(\varphi(1,1,\varphi(0,1)) = \varphi(1,1,\omega)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0))+\psi_1(0)+\psi_1(0)))\) | \(\varphi(1,2,0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0))+\psi_1(1)))\) | \(\varphi(1,\varphi(0,1),0) = \varphi(1,\omega,0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0))+\psi_1(\psi_1(0))))\) | \(\varphi(2,0,0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)+1)))\) | \(\varphi(\varphi(0,1),0,0) = \varphi(\omega,0,0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)+\psi_0(\psi_1(\psi_1(\psi_1(0)+1))))))\) | \(\varphi(\varphi(\varphi(0,1),0,0),0,0) = \varphi(\varphi(\omega,0,0),0,0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)+\psi_1(0))))\) | \(\varphi(1,0,0,0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(0)+\psi_1(0)+\psi_1(0))))\) | \(\varphi(1,0,0,0,0)\) |
\(\psi_0(\psi_1(\psi_1(\psi_1(1))))\) | Small Veblen ordinal |
\(\psi_0(\psi_1(\psi_1(\psi_1(\psi_1(0)))))\) | Large Veblen ordinal |
Ordinal notation
Buchholz defined an ordinal notation \((OT,<)\) associated to \(\psi\) as an array notation.^{[1]} We explain the original definition of \((OT,<)\).
We simultaneously define the sets \(T\) and \(PT\) of formal strings consisting of \(0\), \(D_v\) indexed by an \(v \in \omega+1\), braces, and commas in the following recursive way:
- \(0 \in T\) and \(0 \in PT\).
- For any \((v,a) \in (\omega+1) \times T\), \(D_va \in T\) and \(D_va \in PT\).
- For any \((a_i)_{i=0}^{k} \in PT^{k+1}\) with \(k \in \mathbb{N} \setminus \{0\}\), \((a_0,\ldots,a_k) \in T\). More precisely, this condition can be formulated without using ellipses in the following way:
- For any \((a_0,a_1) \in PT^2\), \((a_0,a_1) \in T\).
- For any \((a_0,a_1) \in T \times PT\), if there exists formal strings \(s\) such that \(a_0 = (s)\), then \((s,a_1) \in T\).
Namely, \(T\) and \(PT\) are the smallest sets satisfying the conditions above. An element of \(T\) is called a term, and an element of \(PT\) is called a principal term. By the definition, \(T\) is a recursive set, \(PT\) is a recursive subset of \(T\), and every term is \(0\), a principal term, or an array of principal terms of length \(\geq 2\) in braces.
We also denote an \(a \in PT\) by \((a)\). Since the clause 3 in the definition of \(T\) and \(PT\) is applicable only to arrays of length \(\geq 2\), the additional convention does not cause serious ambiguity. By the convention, every term can be uniquely expressed as either \(0\) or a non-empty array of principal terms in braces.
We define a binary relation \(a < b\) on \(T\) in the following recursive way:
- If \(b = 0\), then \(a < b\) is false.
- If \(a = 0\), then \(a < b\) is equivalent to \(b \neq 0\).
- Suppose \(a \neq 0\) and \(b \neq 0\).
- If \(a = D_ua'\) and \(b = D_vb'\) for some \(((u,a'),(v,b')) \in ((\omega+1) \times T)^2\), \(a < b\) is equivalent to that either one of the following holds:
- \(u < v\).
- \(u = v\) and \(a' < b'\).
- If \(a = (a_0,\ldots,a_n)\) and \(b = (b_0,\ldots,b_m)\) for some \((n,m) \in \mathbb{N}^2\) with \(1 \leq n+m\), \(a < b\) is equivalent to that either one of the following holds:
- \(n < m\) and \(a_i = b_i \) for any \(i \in \mathbb{N}\) with \(i \leq n\)
- There exists some \(k \in \mathbb{N}\) such that \(k \leq \min\{n,m\}\), \(a_k < b_k\), and \(a_i = b_i\) for any \(i \in \mathbb{N}\) with \(i < k\).
- If \(a = D_ua'\) and \(b = D_vb'\) for some \(((u,a'),(v,b')) \in ((\omega+1) \times T)^2\), \(a < b\) is equivalent to that either one of the following holds:
By the definition, \(<\) is a recursive strict total ordering on \(T\). We abbreviate \((a < b) \lor (a = b)\) to \(a \leq b\). Although \(\leq\) itself is not a well-ordering, its restriction to a recursive subset \(OT \subset T\), which will be introduced later, forms a well-ordering.
In order to define \(OT\), we define a subset \(G_ua \subset T\) for each \((u,a) \in (\omega+1) \times T\) in the following recursive way:
- If \(a = 0\), then \(G_ua = \emptyset\).
- Suppose that \(a = D_va'\) for some \((v,a') \in (\omega+1) \times T\).
- If \(u \leq v\), then \(G_ua = \{a'\} \cup G_ua'\).
- If \(u > v\), then \(G_ua = \emptyset\).
- If \(a = (a_0,\ldots,a_k)\) for some \((a_i)_{i=0}^{k} \in PT^{k+1}\) with \(k \in \mathbb{N} \setminus \{0\}\),\(G_ua = \bigcup_{i=0}^{k} G_ua_i\).
By the definition, \(b \in G_ua\) is a recursive relation on \((u,a,b) \in (\omega+1) \times T^2\).
Finally, we define a subset \(OT \subset T\) in the following recursive way:
- \(0 \in OT\).
- For any \((v,a) \in (\omega+1) \times T\), \(D_va \in OT\) is equivalent to \(a \in OT\) and \(a' < a\) for any \(a' \in G_va\).
- For any \((a_i)_{i=0}^{k} \in PT^{k+1}\), \((a_0,\ldots,a_k) \in OT\) is equivalent to \((a_i)_{i=0}^{k} \in OT^{k+1}\) and \(a_k \leq \cdots \leq a_0\).
By the definition, \(OT\) is a recursive subset of \(T\). An element of \(OT\) is called an ordinal term.
We define a map \begin{eqnarray*} o \colon OT & \to & C_0(\varepsilon_{\Omega_{\omega}+1}) \\ a & \mapsto & o(a) \end{eqnarray*} in the following inductive way:
- If \(a = 0\), then \(o(a) = 0\).
- If \(a = D_va'\) for some \((v,a') \in (\omega+1) \times OT\), then \(o(a) = \psi_v(o(a'))\).
- If \(a = (a_0,\ldots,a_k)\) for some \((a_i)_{i=0}^{k} \in (OT \cap PT)^{k+1}\) with \(k \in \mathbb{N} \setminus \{0\}\), then \(o(a) = o(a_0) \# \cdots \# o(a_k)\), where \(\#\) denotes the descending sum of ordinals, which coincides with the usual addition by the definition of \(OT\).
Buchholz verified that the map \(o\) satisfies the following:^{[1]}
- The map \(o\) is an order-preserving bijective map with respect to \(<\) and \(\in\). In particular, \(<\) is a recursive strict well-ordering on \(OT\).
- For any \(a \in OT\) satisfying \(a < D_10\), \(o(a)\) coincides with the ordinal type of \(<\) restricted to the countable subset \(\{x \in OT \mid x < a\}\).
- The ordinal \(\psi_0(\varepsilon_{\Omega_{\omega}+1})\) coincides with the ordinal type of \(<\) restricted to the recursive subset \(\{x \in OT \mid x < D_10\}\). In particular, \((\{x \in OT \mid x < D_10\},<)\) is an ordinal notation equivalent to \(\psi_0(\varepsilon_{\Omega_{\omega}+1})\), and hence \((OT,<)\) is an ordinal notation whose ordinal type is strictly greater than the countable limit of \(\psi\).
- For any \(v \in \mathbb{N} \setminus \{0\}\), the well-foundedness of \(<\) restricted to the recursive subset \(\{x \in OT \mid x < D_0D_{v+1}0\}\) in the sense of the non-existence of a primitive recursive infinite descending sequence is not provable under \(\textrm{ID}_v\).
- The well-foundedness of \(<\) restricted to the recursive subset \(\{x \in OT \mid x < D_0D_{\omega}0\}\) in the same sense above is not provable under \(\Pi_1^1-\textrm{CA}_0\).
Normal form
The normal form for Buchholz's function can be defined by the pull-back of standard form for the ordinal notation associated to it by \(o\). Namely, the set \(\textrm{NF}\) of predicates on ordinals in \(C_0(\varepsilon_{\Omega_{\omega}+1})\) is defined in the following way:
- The predicate \(\alpha =_{\textrm{NF}} 0\) on an ordinal \(\alpha\) in \(C_0(\varepsilon_{\Omega_{\omega}+1})\) defined as \(\alpha = 0\) belongs to \(\textrm{NF}\).
- The predicate \(\alpha_0 =_{\textrm{NF}} \psi_{k_1}(\alpha_1)\) on ordinals \(\alpha_0, \alpha_1\) in \(C_0(\varepsilon_{\Omega_{\omega}+1})\) with \(k_1 \in \omega+1\) defined as \(\alpha_0 = \psi_{k_1}(\alpha_1)\) and \(\alpha_1 \in C_{k_1}(\alpha_1)\) belongs to \(\textrm{NF}\).
- The predicate \(\alpha_0 =_{\textrm{NF}} \alpha_1 + \cdots + \alpha_n\) on ordinals \(\alpha_0, \ldots, \alpha_n\) in \(C_0(\varepsilon_{\Omega_{\omega}+1})\) with an integer \(n > 1\) defined as \(\alpha_0 = \alpha_1 + \cdots + \alpha_n\), \(\alpha_1 \geq \cdots \geq \alpha_n\), and \(\alpha_1,\ldots,\alpha_n \in \textrm{AP}\) belongs to \(\textrm{NF}\). Here \(+\) is a function symbol rather than an actual addition, and \(\textrm{AP}\) denotes the class of additive principal numbers.
It is also useful to replace the third case by the following one obtained by combining the second condition:
- 3. The predicate \(\alpha_0 =_{\textrm{NF}} \psi_{k_1}(\alpha_1) + \cdots + \psi_{k_n}(\alpha_n)\) on ordinals \(\alpha_0, \ldots, \alpha_n\) in \(C_0(\varepsilon_{\Omega_{\omega}+1})\) with an integer \(n > 1\) and \(k_1,\ldots,k_n \in \omega+1\) defined as \(\alpha_0 = \psi_{k_1}(\alpha_1) + \cdots + \psi_{k_n}(\alpha_n)\), \(\psi_{k_1}(\alpha_1) \geq \cdots \geq \psi_{k_n}(\alpha_n)\), and \(\alpha_1 \in C_{k_1}(\alpha_1), \ldots, \alpha_n \in C_{k_n}(\alpha_n)\) belongs to \(\textrm{NF}\).
We note that those two formulations are not equivalent. For example, \(\psi_0(\Omega) + 1 =_{\textrm{NF}} \psi_0(\zeta_1) + \psi_0(0)\) is a valid formula which is false with respect to the second formulation because of \(\zeta_1 \notin C_0(\zeta_1)\), while it is a valid formula which is true with respect to the first formulation because of \(\psi_0(\Omega) + 1 = \psi_0(\zeta_1) + \psi_0(0)\), \(\psi_0(\zeta_1), \psi_0(0) \in \textrm{AP}\), and \(\psi_0(\zeta_1) \geq \psi_0(0)\). In this way, the notion of normal form heavily depends on the context.
In both formulations, every ordinal in \(C_0(\varepsilon_{\Omega_{\omega+1}})\) can be uniquely expressed in normal form for Buchholz's function.
Fundamental sequences
Buchholz essentially defined a recursive system of fundamental sequences in the first paper on Buchholz's function^{[1]} and also defined another recursive system of fundamental sequences in the other paper^{[2]}, but the other recursive system of fundamental sequences defined by Googology Wiki user Denis Maksudov is more commonly used in googology. See this section for more details.
Variants
There are many variants of Buchholz's function or the ordinal notation associated to it.
Extension
- Main article: Extended Buchholz's function
We introduce the extension of Buchholz's definition by Googology Wiki user Denis Maksudov as follows^{[3]}:
- \(C_\nu^0(\alpha) = \{\beta|\beta<\Omega_\nu\}\),
- \(C_\nu^{n+1}(\alpha) = \{\beta+\gamma,\psi_\mu(\eta)|\mu,\beta, \gamma,\eta\in C_{\nu}^n(\alpha)\wedge\eta<\alpha\}\),
- \(C_\nu(\alpha) = \bigcup_{n < \omega} C_\nu^n (\alpha)\),
- \(\psi_\nu(\alpha) = \min\{\gamma | \gamma \not\in C_\nu(\alpha)\}\),
where
\(\Omega_\nu=\left\{\begin{array}{lcr} 1\text{ if }\nu=0 \\ \text{smallest ordinal with cardinality }\aleph_\nu \text{ if }\nu>0 \\ \end{array}\right.\)
There is only one little detail difference with original Buchholz definition: ordinal \(\mu\) is not limited by \(\omega\), now ordinal \(\mu\) belongs to previous set \(C_n\).
The ordinal notation \((OT,<)\) associated to Buchholz's function is extended to the ordinal notation associated to Extended Buchholz's function by a Japanese Googology Wiki user p進大好きbot in a natural way,^{[4]} and is further extended to a \(3\)-ary notation by a Japanese Googology Wiki user kanrokoti.^{[5]} Also, the notions of normal form and fundamental sequences are extended by Denis Maksudov.
Simplification
Buchholz's function is defined by using the closure with respect to the addition, while Weak Buchholz's function is defined in the same way except that it does not use the closure with respect to the addition. Therefore the definitions directly imply that Weak Buchholz's function is bounded by Buchholz's function. One non-trivial expectation is that extensitions of the two functions, Extended Buchholz's function and Extended Weak Buchholz's function, have the same countable limit, but it has not been proved yet.
Common misconceptions
Here is a list of some common misconceptions regarding Buchholz's function and Extended Buchholz's function pointed out by p進大好きbot, which appear in many introductory articles on Buchholz's function:
Common misconceptions | Fact | Reason |
---|---|---|
Buchholz's function is computable. | Buchholz's function is not a computable function, despite the fact that the associated ordinal notation is computable. | Turing machine defines a function whose domain and codomain are sets of tuple of natural numbers, neither of which includes transfinite ordinals. |
The \(\psi\) without a subscript is an official abbreviation of \(\psi_0\) with respect to Buchholz's function or \(\psi_{\Omega}\) with respect to Rathjen's psi function. See also \(\psi(\psi_I(0))\). | The original sources for the two functions do not include such abbereviation. Although Buchholz introduced \(\psi\) in a survey^{[6]}, it is defined as an abbreviation of \(\psi_0 \upharpoonright_{\varepsilon_{\Omega+1}}\) rather than \(\psi_0\). | Perhaps people confounded them with another (possibly ill-defined) OCF created by a googologist, or confounded \(\psi_0 \upharpoonright_{\varepsilon_{\Omega+1}}\) with \(\psi_0\). |
\(\psi_0(\alpha)\) is ill-defined if \(\alpha>\varepsilon_{\Omega_\omega+1}\) | The ordinal \(\psi_{\nu}(\alpha)\) is defined for all \((\nu,\alpha) \in (\omega+1) \times \textrm{On}\). | Buchholz's original definition uses transfinite recursion on \(\alpha\) and restricts \(\nu\le\omega\). |
\(\psi_0(\alpha)\) with respect to Buchholz's function coincides with \(\psi_0(\alpha)\) with respect to Extended Buchholz's function. | Buchholz's function is neither a restriction of extended Buchholz's function nor extended Buchholz's function itself. However, some values correspond, such as \(\psi_0(\psi_1(0))\). | Some ordinals don't correspond from extended Buchholz function to Buchholz function, such as \(\psi_0(\psi_{\psi_1(0)}(0))\). |
\(\psi_0(\varepsilon_0+1) = \varepsilon_0 \times \omega\) | \(\psi_0(\varepsilon_0+1) = \varepsilon_0\). In fact, the \(\psi_0\) function's output equals \(\varepsilon_0\) for all inputs between \(\varepsilon_0\) and \(\Omega\) inclusive. | This is because \(\varepsilon_0\notin C_0(\varepsilon_0+1)\). |
\(\psi_0(\psi_1(\psi_2(\psi_3(0)))) = \psi_0(\psi_3(0))\) | \(\psi_0(\psi_1(\psi_2(\psi_3(0)))) = \psi_0(\psi_2(0))\). In fact, for any ordinal \(\alpha\geq\psi_2(0)\), we have \(\psi_0(\psi_1(\alpha))=\psi_0(\psi_2(0))\). | This is because \(\psi_1(\psi_2(\psi_3(0)))\notin C_0(\psi_1(\psi_2(\psi_3(0))))\). |
The sequence \(\psi_0(0), \psi_0(\psi_1(0)), \psi_0(\psi_1(\psi_2(0))), \psi_0(\psi_1(\psi_2(\psi_3(0)))), \ldots\) has a limit of \(\psi_0(\psi_{\omega}(0))\). | The sequence is an eventually constant sequence with limit \(\psi_0(\psi_2(0))\). | This is because for \(n>2\), \(\psi_1(\psi_2(\cdots\psi_n(0)\cdots))\notin C_0(\psi_1(\psi_2(\cdots\psi_n(0)\cdots)))\). (the reason in the above cell also applies) |
The ordinal \(\psi_I(0)\) equals the least omega fixed point where \(I\) denotes the least inaccessible cardinal. See also \(\psi(\psi_I(0))\). | The ordinal \(\psi_I(0)\) is ill-formed for Buchholz's function, and equals \(I\) for Extended Buchholz's function. | This is because \(C^0_I(0)\) is undefined for Buchholz's function and defined as \(\Omega_I=I\) for Extended Buchholz's function. |
External Links
- Buchholz ψ analyzer by Fish
- Online calculator for fast-growing hierarchy with Buchholz function by Denis Maksudov (Be careful that it is intended to support only normal form expressions.)
- Online calculator for fast-growing hierarchy with Extended Buchholz function by Denis Maksudov (Be careful that it is intended to support only normal form expressions.)
- ordex: Ordinal Expander in JavaScript by koteitan (Koteitan's online calculator for kanrokoti's \(3\)-ary extension of p進大好きbot's ordinal notation associated to Denis' extension of Buchholz's function)
Sources
- ↑ ^{1.0} ^{1.1} ^{1.2} ^{1.3} ^{1.4} W. Buchholz, A New System of Proof-Theoretic Ordinal Functions, Annals of Pure and Applied Logic, vol. 32 (1986), pp. 195--207.
- ↑ ^{2.0} ^{2.1} W. Buchholz, Relating ordinals to proofs in a perspicuous way, Reflections on the foundations of mathematics (Stanford, CA, 1998) 15 (2017): 37--59.
- ↑ Maksudov, Denis. The extension of Buchholz's function. Traveling To The Infinity. Retrieved 2017-05-18.
- ↑ p進大好きbot, Ordinal Notation Associated to Extended Buchholz's OCF, Googology Wiki user blog.
- ↑ kanrokoti, 3 variables ψ which is larger than EBOCF, Googology Wiki user blog.
- ↑ W. Buchholz, A survey on ordinal notations around the Bachmann-Howard ordinal (p.18)
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 · 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: \(V\) · \(L\) · \(\textrm{On}\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)