Buchholz's function

File:Buchholz-.gif

Wilfried Buchholz

Buchholz's psi-functions are a hierarchy of single-argument ordinal functions \(\psi_\nu(\alpha)\) introduced by german mathematician Wilfried Buchholz in 1986. These functions are a simplified version of the \(\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_\nu=\left\{\begin{array}{lcr} 1\text{ if }\nu=0\\ \aleph_\nu\text{ if }\nu>0\\ \end{array}\right.\)

and \(P(\gamma)=\{\gamma_1,...,\gamma_k\}\) is the set of additive principal numbers in form \(\omega^\xi\),

\(P=\{\alpha\in On: 0<\alpha \wedge \forall \xi, \eta < \alpha (\xi+\eta < \alpha)\}=\{\omega^\xi: \xi \in 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,...,\alpha_k \in P(\gamma)\).

Note: Greek letters always denotes ordinals. \(On\) denotes the class of all ordinals.

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 \(\psi_0(\Omega)=\varepsilon_0\).

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

\(\varphi(\alpha,1+\beta)=\psi_0(\Omega^\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(\Omega\uparrow\uparrow\omega)=\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)=\psi_1^\omega(0)=\Omega\uparrow\uparrow\omega=\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),..., \psi_1^\omega(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\)).

Extension

We rewrite Buchholz's definition as follows:

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

and \(\omega\) is the smallest infinite ordinal.

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(\Omega_{\Omega_{\Omega_{...}}})=\psi(\psi_{\psi_{...}(0)}(0))\), where \(\psi\) without subscript denotes \(\psi_0\).

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 also written in normal form.

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

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)\in\{\Omega_{\mu+1}|\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.\).

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