Buchholz psi functions

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. Later on this approach was extended by Jaiger and Schtitte.

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.

The limit of this notation is Takeuti-Feferman-Buchholz ordinal.

Properties

Buchholz showed following properties of this 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 }\leq \psi _{\nu }(\alpha )<\Omega _{\nu +1}$,
• $\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 (\varepsilon _{\Omega _{\nu }+1})$ for $0<\nu \leq \omega$.

Fundamental sequences and normal form for Buchholz's function

Normal form

The normal form for 0 is 0. If $\alpha$ is a nonzero ordinal number $\alpha <\Omega _{\omega }$ 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 $\nu _{i}\in \mathbb {N} _{0},k\in \mathbb {N} _{>0},\beta _{i}\in C_{\nu _{i}}(\beta _{i})$ and $\psi _{\nu _{1}}(\beta _{1})\geq \psi _{\nu _{2}}(\beta _{2})\geq \cdots \geq \psi _{\nu _{k}}(\beta _{k})$ and each $\beta _{i}$ is 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 <\Omega _{\omega }$, 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\geq 2$ 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 }(\beta +1)$ then ${\text{cof}}(\alpha )=\omega$ and $\alpha [\eta ]=\psi _{\nu }(\beta )\cdot \eta$ (and note: $\psi _{\nu }(0)=\Omega _{\nu }$),
5. 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 ])$,
6. 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.$.

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:

• 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 \leq \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 }(\eta )$, where $\mu \leq \omega$ and $\eta <\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 and therefore $\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}(0)=\omega$ and all possible sums of them and therefore $\psi _{0}(2)=\omega ^{2}$.

If $\alpha =\omega$ then $C_{0}(\alpha )=\{0,\psi (0)=1,...,\psi (1)=\omega ,...,\psi (2)=\omega ^{2},...,\psi (3)=\omega ^{3},...\}$ and $\psi _{0}(\omega )=\omega ^{\omega }$.

If $\alpha =\Omega$ then $C_{0}(\alpha )=\{0,\psi (0)=1,...,\psi (1)=\omega ,...,\psi (\omega )=\omega ^{\omega },...,\psi (\omega ^{\omega })=\omega ^{\omega ^{\omega }},...\}$ and $\psi _{0}(\Omega )=\varepsilon _{0}$ - the smallest epsilon number i.e. first fixed point of $\alpha =\omega ^{\alpha }$.

If $\alpha =\Omega +1$ then $C_{0}(\alpha )=\{0,1,...,\psi _{0}(\Omega )=\varepsilon _{0},...,\varepsilon _{0}+\varepsilon _{0},...\psi _{1}(0)=\Omega ,...\}$ and $\psi _{0}(\Omega +1)=\varepsilon _{0}\omega =\omega ^{\varepsilon _{0}+1}$.

$\psi _{0}(\Omega 2)=\varepsilon _{1}$ the second epsilon number,

$\psi _{0}(\Omega ^{2})=\varepsilon _{\varepsilon _{...}}=\zeta _{0}$ i.e. first fixed point of $\alpha =\varepsilon _{\alpha }$,

$\varphi (\alpha ,1+\beta )=\psi _{0}(\Omega ^{\alpha }\beta )$, where $\varphi$ denotes the Veblen's function,

$\psi _{0}(\Omega ^{\Omega })=\Gamma _{0}=\varphi (1,0,0)=\theta (\Omega ,0)$, where $\theta$ denotes the Feferman's function,

$\psi _{0}(\Omega ^{\Omega ^{2}})=\varphi (1,0,0,0)$ is Ackermann ordinal,

$\psi _{0}(\Omega ^{\Omega ^{\omega }})$ is small Veblen ordinal,

$\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}(0)=\{\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. And therefore $C_{1}(0)$ includes all possible sums of all countable ordinals and $\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}$.

If $\alpha =1$ then $C_{1}(\alpha )=\{0,...,\psi _{0}(0)=\omega ,...,\psi _{1}(0)=\Omega ,...,\Omega +\omega ,...,\Omega +\Omega ,...\}$ and $\psi _{1}(1)=\Omega \omega =\omega ^{\Omega +1}$.

$\psi _{1}(2)=\Omega \omega ^{2}=\omega ^{\Omega +2}$,

$\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}^{k+1}(0)=\Omega \uparrow \uparrow k$ where $k$ is a natural number, $k\geq 2$,

$\psi _{1}(\Omega _{2})=\psi _{1}^{\omega }(0)=\Omega \uparrow \uparrow \omega =\varepsilon _{\Omega +1}$.

For case $\psi (\psi _{2}(0))=\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 })$ ( for $1\leq \nu <\omega$).