FANDOM


Buchholz-

Wilfried Buchholz

Buchholz's psi functions are ordinal collapsing functions created by German mathematician Wilfried Buchholz. Although there are many Buchholz's psi functions, we explain the most famous one in this community, which is a hierarchy of single-argument functions \(\psi_\nu(\alpha)\) introduced in 1986,[1] because 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 those.

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 focussing on Buchholz's function. Actually, Buchholz himself uses \(\Omega_0\) as both of shorthands of \(1\) and \(\omega\).[1][2]

The limit of this notation is 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, that means every ordinal \(\alpha\) is equal to 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:

  1. all ordinals from previous set \(C_\nu^n(\alpha)\),
  2. all ordinals that can be obtained by summation the additively principal ordinals from previous set \(C_\nu^n(\alpha)\),
  3. 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 no functions \(\psi(\eta<0)\) and 0+0=0).

Then \(\psi_0(0)=1\).

\(C_0(1)\) includes \(\psi_0(0)=1\) and all possible sums of natural numbers:

\(C_0(1)=\{0,1,2,...,\text{googol}, ...,\text{TREE(googol)},...\}\).

Then \(\psi_0(1)=\omega\) - first transfinite ordinal, which is greater than all natural numbers by its definition.

\(C_0(2)\) includes \(\psi_0(0)=1, \psi_0(1)=\omega\) 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,...\}\).

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}\),

\(\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\omega\)
\(\psi_0(\psi_1(0)+2)\) \(\varphi(0,\varphi(1,0)+2)=\omega^{\varepsilon_0+2}=\varepsilon_0\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(\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:

  1. \(0 \in T\) and \(0 \in PT\).
  2. For any \((v,a) \in (\omega+1) \times T\), \(D_va \in T\) and \(D_va \in PT\).
  3. 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:
    1. For any \((a_0,a_1) \in PT^2\), \((a_0,a_1) \in T\).
    2. 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:

  1. If \(b = 0\), then \(a < b\) is false.
  2. If \(a = 0\), then \(a < b\) is equivalent to \(b \neq 0\).
  3. Suppose \(a \neq 0\) and \(b \neq 0\).
    1. 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:
      1. \(u < v\).
      2. \(u = v\) and \(a' < b'\).
    2. 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:
      1. \(n < m\) and \(a_i = b_i \) for any \(i \in \mathbb{N}\) with \(i \leq n\)
      2. 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\).

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:

  1. If \(a = 0\), then \(G_ua = \emptyset\).
  2. Suppose that \(a = D_va'\) for some \((v,a') \in (\omega+1) \times T\).
    1. If \(u \leq v\), then \(G_ua = \{a'\} \cup G_ua'\).
    2. If \(u > v\), then \(G_ua = \emptyset\).
  3. 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:

  1. \(0 \in OT\).
  2. 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\).
  3. 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(\epsilon_{\Omega_{\omega}+1}) \\ a & \mapsto & o(a) \end{eqnarray*} in the following inductive way:

  1. If \(a = 0\), then \(o(a) = 0\).
  2. If \(a = D_va'\) for some \((v,a') \in (\omega+1) \times OT\), then \(o(a) = \psi_v(o(a'))\).
  3. 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\).


Extension

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\).

For example if \(C_0^0(1)=\{0\}\) then \(C_0^1(1)=\{0,\psi_0(0)=1\}\) and \(C_0^2(1)=\{0,...,\psi_1(0)=\Omega\}\) and \(C_0^3(1)=\{0,...,\psi_\Omega(0)=\Omega_\Omega\}\) and so on.

Limit of this notation must be omega fixed point \(\psi_0(\Omega_{\Omega_{\Omega_{\cdots}}})=\psi_0(\psi_{\psi_{\cdots}(0)}(0)) = \psi_0(\Lambda)\) (see the next section).

Normal form and fundamental sequences

Normal form

The normal form for 0 is 0. If \(\alpha\) is a nonzero ordinal number \(\alpha<\Lambda=\text{min}\{\beta|\psi_\beta(0)=\beta\}\) then the normal form for \(\alpha\) is \(\alpha=\psi_{\nu_1}(\beta_1)+\psi_{\nu_2}(\beta_2)+\cdots+\psi_{\nu_k}(\beta_k)\) where \(k\) is a positive integer and \(\psi_{\nu_1}(\beta_1)\geq\psi_{\nu_2}(\beta_2)\geq\cdots\geq\psi_{\nu_k}(\beta_k)\) and each \(\nu_i\), \(\beta_i\) are ordinals satisfying \(\beta_i \in C_{\nu_i}(\beta_i)\) also written in normal form. More precisely, the normality of an expression of an ordinal can be described in a recursive way with respect to the corresponding ordinal notation system extending the original ordinal notation system \((OT,<)\) explained above.

Fundamental sequences

The fundamental sequence for an ordinal number \(\alpha\) with cofinality \(\text{cof}(\alpha)=\beta\) is a strictly increasing sequence \((\alpha[\eta])_{\eta<\beta}\) with length \(\beta\) and with limit \(\alpha\), where \(\alpha[\eta]\) is the \(\eta\)-th element of this sequence. If \(\alpha\) is a successor ordinal then \(\text{cof}(\alpha)=1\) and the fundamental sequence has only one element \(\alpha[0]=\alpha-1\). If \(\alpha\) is a limit ordinal then \(\text{cof}(\alpha)\in\{\omega\}\cup\{\Omega_{\mu+1}|\mu\geq 0\}\).

Although a system of fundamental sequences is not unique, there is a canonical choice of fundamental sequences in this community given by Denis. For nonzero ordinals \(\alpha<\Lambda\), written in normal form, fundamental sequences are defined as follows:

  1. If \(\alpha=\psi_{\nu_1}(\beta_1)+\psi_{\nu_2}(\beta_2)+\cdots+\psi_{\nu_k}(\beta_k)\) where \(k\geq2\) then \(\text{cof}(\alpha)=\text{cof}(\psi_{\nu_k}(\beta_k))\) and \(\alpha[\eta]=\psi_{\nu_1}(\beta_1)+\cdots+\psi_{\nu_{k-1}}(\beta_{k-1})+(\psi_{\nu_k}(\beta_k)[\eta])\),
  2. If \(\alpha=\psi_{0}(0)=1\), then \(\text{cof}(\alpha)=1\) and \(\alpha[0]=0\),
  3. If \(\alpha=\psi_{\nu+1}(0)\), then \(\text{cof}(\alpha)=\Omega_{\nu+1}\) and \(\alpha[\eta]=\Omega_{\nu+1}[\eta]=\eta\),
  4. If \(\alpha=\psi_{\nu}(0)\) and \(\text{cof}(\nu)\in\{\omega\}\cup\{\Omega_{\mu+1}|\mu\geq 0\}\), then \(\text{cof}(\alpha)=\text{cof}(\nu)\) and \(\alpha[\eta]=\psi_{\nu[\eta]}(0)=\Omega_{\nu[\eta]}\),
  5. If \(\alpha=\psi_{\nu}(\beta+1)\) then \(\text{cof}(\alpha)=\omega\) and \(\alpha[\eta]=\psi_{\nu}(\beta)\cdot \eta\) (and note: \(\psi_\nu(0)=\Omega_\nu\)),
  6. If \(\alpha=\psi_{\nu}(\beta)\) and \(\text{cof}(\beta)\in\{\omega\}\cup\{\Omega_{\mu+1}|\mu<\nu\}\) then \(\text{cof}(\alpha)=\text{cof}(\beta)\) and \(\alpha[\eta]=\psi_{\nu}(\beta[\eta])\),
  7. If \(\alpha=\psi_{\nu}(\beta)\) and \(\text{cof}(\beta) = \Omega_{\mu+1}\) for a \(\mu\geq\nu\) then \(\text{cof}(\alpha)=\omega\) and \(\alpha[\eta]=\psi_{\nu}(\beta[\gamma[\eta]])\) where \(\left\{\begin{array}{lcr} \gamma[0]=\Omega_\mu \\ \gamma[\eta+1]=\psi_\mu(\beta[\gamma[\eta]])\\ \end{array}\right.\).

It is an extension of the system of fundamental sequences up to \(\psi_0(\varepsilon_{\Omega_{\omega}+1})\) in Buchholz hierarchy given by modifying the rule ([].5) (ii) in recursive definition of the \(\textrm{dom}\) function and \([]\) in Buchholz's original paper[1] by the rule 6 in the definition of \([]\) in p.6 in Buchholz's another paper[2] applied to the convention \(\Omega_0 = 1\) except for the minor differences related to the difference \(\omega[n] = n+1\) in the original definition and \(\omega[n] = n\) in the definition here. (Please remember that \(\Omega_0\) is defined as \(1\) in the original paper, while it is defined as \(\omega\) in the other paper.) More precisely, the fundamental sequence of \(\psi_0(2) = \omega \times \omega\) is given as \(\omega \times \omega [n] = \omega \times (n+1)\) in the original definition while we have \(\omega \times \omega[n] = \omega \times n\) in the definition here, and the fundamental sequence of \(\psi_{\omega}(0) = \Omega_{\omega}\) is given as \(\Omega_{\omega}[n] = \Omega_{n+1}\) while we have \(\Omega_{\omega}[n] = \Omega_n\) in the definition here.

If \(\alpha=\Lambda\) then \(\text{cof}(\alpha)=\omega\) and \(\alpha[0]=0\) and \(\alpha[\eta+1]=\psi_{\alpha[\eta]}(0)=\Omega_{\alpha[\eta]}\).

For comparison of ordinals written in normal form use the following property:

if \(\alpha<\beta\) and \(1\le\eta<\omega\) then \(\left\{\begin{array}{lcr} 0<\psi_\alpha(\gamma)\cdot\eta <\psi_\beta(\delta)\\ 0<\psi_\gamma(\alpha)\cdot\eta<\psi_\gamma(\beta)\\ \end{array}\right.\)

The comparison of expressions of ordinals can be described in a recursive way with respect to the corresponding ordinal notation system extending the original ordinal notation system \(OT\).[1] In particular, the system of fundamental sequences above induce a recursive system of fundamental sequences on the corresponding ordinal notation, and hence the fast-growing hierarchy associated to it is recursive.


Common Misconceptions

Here is a list of some common misconceptions regarding Buchholz's function, 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.
\(\psi_0(\Omega_{\omega}+1)\) is ill-defined. 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 \(v\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(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\). This is due to the fact that the \(\psi_0\) function 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\ge 3\), \(\psi_1(\psi_2(\cdots\psi_n(0)\cdots))\notin C_0(\psi_1(\psi_2(\cdots\psi_n(0)\cdots)))\).
It equals the least omega fixed point. See also \(\psi_0(\psi_I(0))\). The ordinal \(\psi_I(0)\) equals \(I\). This is because \(C^0_I(0)\) is defined as \(\Omega_I=I\).

External Links

Sources

  1. 1.0 1.1 1.2 1.3 1.4 1.5 W. Buchholz, A New System of Proof-Theoretic Ordinal Functions, Annals of Pure and Applied Logic, vol. 32 (1986), pp. 195--207.
  2. 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.
  3. Maksudov, Denis. The extension of Buchholz's functionTraveling To The Infinity. Retrieved 2017-05-18.

See also

Ordinals, ordinal analysis, and set theory

Basics: cardinal numbers · normal function · ordinal notation · ordinal numbers · fundamental sequence · ordinal collapsing function · transfinite induction
Theories: Robinson arithmetic · Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_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}}}})\) (the 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 Mahlo ordinal · reflecting ordinal · stable ordinal · gap ordinal · \(\lambda,\zeta,\Sigma,\gamma\) (ordinals on infinite time Turing machine) · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Slow-growing hierarchy · Hardy hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal collapsing functions Madore · Buchholz · Jäger
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}\) · Class (set theory)
Other concepts: Veblen function · absolute infinity · Model

Community content is available under CC-BY-SA unless otherwise noted.