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 Schütte.

Definition

Buchholz defined his functions as follows:

${\begin{aligned}C_{\nu }^{0}(\alpha )={}&\Omega _{\nu },\\[6pt]C_{\nu }^{n+1}(\alpha )={}&C_{\nu }^{n}(\alpha )\cup \{\gamma \mid P(\gamma )\subseteq C_{\nu }^{n}(\alpha )\}\\&{}\cup \{\psi _{\mu }(\xi )\mid \xi \in \alpha \cap C_{\nu }^{n}(\alpha )\wedge \xi \in C_{\mu }(\xi )\wedge \mu \leq \omega \},\\[6pt]C_{\nu }(\alpha )={}&\bigcup _{n<\omega }C_{\nu }^{n}(\alpha ),\\\psi _{\nu }(\alpha )={}&\min\{\gamma \mid \gamma \not \in C_{\nu }(\alpha )\},\end{aligned}}$

where

$\Omega _{\nu }={\begin{cases}1{\text{ if }}\nu =0\\\aleph _{\nu }{\text{ if }}\nu >0\end{cases}}$

and $P(\gamma )=\{\gamma _{1},\ldots ,\gamma _{k}\}$ is the set of additive principal numbers in form $\omega ^{\xi }$,

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

Note: Greek letters always denotes ordinals.

The limit of this notation is the 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)=\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}){\text{ 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 $\operatorname {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 $\operatorname {cof} (\alpha )=1$ and the fundamental sequence has only one element $\alpha [0]=\alpha -1$. If $\alpha$ is a limit ordinal then $\operatorname {cof} (\alpha )\in \{\omega \}\cup \{\Omega _{\mu +1}\mid \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 $\operatorname {cof} (\alpha )=\operatorname {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 $\operatorname {cof} (\alpha )=1$ and $\alpha [0]=0$,
3. If $\alpha =\psi _{\nu +1}(0)$, then $\operatorname {cof} (\alpha )=\Omega _{\nu +1}$ and $\alpha [\eta ]=\Omega _{\nu +1}[\eta ]=\eta$,
4. If $\alpha =\psi _{\nu }(\beta +1)$ then $\operatorname {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 $\operatorname {cof} (\beta )\in \{\omega \}\cup \{\Omega _{\mu +1}\mid \mu <\nu \}$ then $\operatorname {cof} (\alpha )=\operatorname {cof} (\beta )$ and $\alpha [\eta ]=\psi _{\nu }(\beta [\eta ])$,
6. If $\alpha =\psi _{\nu }(\beta )$ and $\operatorname {cof} (\beta )\in \{\Omega _{\mu +1}\mid \mu \geq \nu \}$ then $\operatorname {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 \mid \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 \mid \beta <\Omega _{\nu }\}$.

The condition $C_{\nu }^{n+1}(\alpha )=C_{\nu }^{n}(\alpha )\cup \{\gamma \mid P(\gamma )\subseteq C_{\nu }^{n}(\alpha )\}\cup \{\psi _{\mu }(\xi )\mid \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 )\mid \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 \mid \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 \mid \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}(1)=\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,\ldots ,\psi (1)=\omega ,\ldots ,\psi (2)=\omega ^{2},\ldots ,\psi (3)=\omega ^{3},\ldots \}$ and $\psi _{0}(\omega )=\omega ^{\omega }$.

If $\alpha =\Omega$ then $C_{0}(\alpha )=\{0,\psi (0)=1,\ldots ,\psi (1)=\omega ,\ldots ,\psi (\omega )=\omega ^{\omega },\ldots ,\psi (\omega ^{\omega })=\omega ^{\omega ^{\omega }},\ldots \}$ 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,\ldots ,\psi _{0}(\Omega )=\varepsilon _{0},\ldots ,\varepsilon _{0}+\varepsilon _{0},\ldots ,\psi _{1}(0)=\Omega ,\ldots \}$ 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 _{\cdots }}=\zeta _{0}$ i.e. first fixed point of $\alpha =\varepsilon _{\alpha }$,

$\varphi (\alpha ,\beta )=\psi _{0}(\Omega ^{\alpha }(1+\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 the Ackermann ordinal,

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

$\psi _{0}(\Omega ^{\Omega ^{\Omega }})$ is the 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 \mid \beta <\Omega _{1}\}=\{0,\psi (0)=1,2,\ldots {\text{googol}},\ldots ,\psi _{0}(1)=\omega ,\ldots ,\psi _{0}(\Omega )=\varepsilon _{0},\ldots$

$\ldots ,\psi _{0}(\Omega ^{\Omega })=\Gamma _{0},\ldots ,\psi (\Omega ^{\Omega ^{\Omega }+\Omega ^{2}}),\ldots \}$ 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,\ldots ,\psi _{0}(0)=\omega ,\ldots ,\psi _{1}(0)=\Omega ,\ldots ,\Omega +\omega ,\ldots ,\Omega +\Omega ,\ldots \}$ 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),\ldots ,\psi _{1}^{\omega }(0)$

and then

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

In the 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 }){\text{ (for }}1\leq \nu )<\omega$

Extension

This OCF is a sophisticated extension of Buchholz's $\psi$ by mathematician Denis Maksudov. The countable limit of this system is much greater, equal to $\psi _{0}(\Omega _{\Omega _{\Omega _{...}}})$ where $\Omega _{\Omega _{\Omega _{...}}}$ denotes the first omega fixed point, sometimes referred to as Extended Buchholz's ordinal. The function is defined as follows:

• Define $\Omega _{0}=1$ and $\Omega _{\nu }=\aleph _{\nu }$ for $\nu >0$.
• $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 )\land \eta <\alpha \}$
• $C_{\nu }(\alpha )=\bigcup \limits _{n<\omega }C_{\nu }^{n}(\alpha )$
• $\psi _{\nu }(\alpha )=min(\{\gamma |\gamma \notin C_{\nu }(\alpha )\})$

Ordinal notation

Buchholz defined an ordinal notation ${\mathsf {(OT,<)}}$ associated to the $\psi$ function. We simultaneously define the sets $T$ and $PT$ as formal strings consisting of $0,D_{v}$ indexed by $v\in \omega +1$, braces and commas in the following way:

• $0\in T\land 0\in PT$,
• $\forall (v,a)\in (\omega +1)\times T(D_{v}a\in T\land D_{v}a\in PT)$.
• $\forall (a_{0},a_{1})\in PT^{2}((a_{0},a_{1})\in T)$.
• $\exists s(a_{0}=s)\land (a_{0},a_{1})\in T\times PT\rightarrow (s,a_{1})\in T$.

An element of $T$ is called a term, and an element of $PT$ is called a principal term. By definition, $T$ is a recursive set and $PT$ is a recursive subset of $T$. Every term is either $0$, a principal term or a braced array of principal terms of length $\geq 2$. We denote $a\in PT$ by $(a)$. By convention, every term can be uniquely expressed as either $0$ or a braced, non-empty array of principal terms. Since clauses 3 and 4 in the definition of $T$ and $PT$ are applicable only to arrays of length $\geq 2$, this convention does not cause serious ambiguity.

We then define a binary relation $a<b$ on $T$ in the following way:

• $b=0\rightarrow a<b=\bot$
• $a=0\rightarrow (a<b\leftrightarrow b\neq 0)$
• If $a\neq 0\land b\neq 0$, then:
  • If $a=D_{u}a'\land b=D_{v}b'$ for some $((u,a'),(v,b'))\in ((\omega +1)\times T)^{2}$, then $a<b$ is true if either of the following are true:
    • $u<v$
    • $u=v\land a'<b'$
  • If $a=(a_{0},...,a_{n})\land b=(b_{0},...,b_{m})$ for some $(n,m)\in \mathbb {N} ^{2}\land 1\leq n+m$, then $a<b$ is true if either of the following are true:
    • $\forall i\in \mathbb {N} \land i\leq n(n<m\land a_{i}=b_{i})$
    • $\exists k\in \mathbb {N} \forall i\in \mathbb {N} \land i<k(k\leq min\{n,m\}\land a_{k}<b_{k}\land a_{i}=b_{1})$

$<$ is a recursive strict total ordering on $T$. We abbreviate $(a<b)\lor (a=b)$ as $a\leq b$. Although $\leq$ itself is not a well-ordering, its restriction to a recursive subset $OT\subset T$, which will be described later, forms a well-ordering. In order to define $OT$, we define a subset $G_{u}a\subset T$ for each $(u,a)\in (\omega +1)\times T$ in the following way:

• $a=0\rightarrow G_{u}a=\varnothing$
• Suppose that $a=D_{v}a'$ for some $(v,a')\in (\omega +1)\times T$, then:
  • $u\leq v\rightarrow G_{u}a=\{a'\}\cup G_{u}a'$
  • $u>v\rightarrow G_{u}a=\varnothing$

• If $a=(a_{0},...,a_{k})$ for some $(a_{i})_{i=0}^{k}\in PT^{k+1}$ for some $k\in \mathbb {N} \backslash \{0\},G_{u}a=\bigcup _{i=0}^{k}G_{u}a_{i}$.

$b\in G_{u}a$ 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 way:

• $0\in OT$
• For any $(v,a)\in (\omega +1)\times T$, $D_{v}a\in OT$ is equivalent to $a\in OT$ and, for any $a'\in G_{v}a$, $a'<a$.
• For any $(a_{i})_{i=0}^{k}\in PT^{k+1}$, $(a_{0},...,a_{k})\in OT$ is equivalent to $(a_{i})_{i=0}^{k}\in OT$ and $a_{k}\leq ...\leq a_{0}$.

$OT$ is a recursive subset of $T$, and an element of $OT$ is called an ordinal term. We can then define a map $o:OT\rightarrow C_{0}(\varepsilon _{\Omega _{\omega }+1})$ in the following way:

• $a=0\rightarrow o(a)=0$
• If $a=D_{v}a'$ for some $(v,a')\in (\omega +1)\times OT$, then $o(a)=\psi _{v}(o(a'))$.
• If $a=(a_{0},...,a_{k})$ for some $(a_{i})_{i=0}^{k}\in (OT\cap PT)^{k+1}$ with $k\in \mathbb {N} \backslash \{0\}$, then $o(a)=o(a_{0})\#...\#o(a_{k})$, where $\#$ denotes the descending sum of ordinals, which coincides with the usual addition by the definition of $OT$.

Buchholz verified the following properties of $o$:

• The map $o$ is an order-preserving bijective map with respect to $<$ and $\in$. In particular, $o$ is a recursive strict well-ordering on $OT$.
• For any $a\in OT$ satisfying $a<D_{1}0$, $o(a)$ coincides with the ordinal type of $<$ restricted to the countable subset $\{x\in OT\;|\;x<a\}$.
• The Takeuti-Feferman-Buchholz ordinal coincides with the ordinal type of $<$ restricted to the recursive subset $\{x\in OT\;|\;x<D_{1}0\}$.
• The ordinal type of $(OT,<)$ is greater than the Takeuti-Feferman-Buchholz ordinal.
• For any $v\in \mathbb {N} \;\backslash \;\{0\}$, the well-foundedness of $<$ restricted to the recursive subset $\{x\in OT\;|\;x<D_{0}D_{v+1}0\}$ in the sense of the non-existence of a primitive recursive infinite descending sequence is not provable under ${\mathsf {ID}}_{v}$.
• The well-foundedness of $<$ restricted to the recursive subset$\{x\in OT\;|\;x<D_{0}D_{\omega }0\}$ in the same sense as above is not provable under $\Pi _{1}^{1}-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 $NF$ of predicates on ordinals in $C_{0}(\varepsilon _{\Omega _{\omega }+1})$ is defined in the following way:

• The predicate $\alpha =_{NF}0$ on an ordinal $\alpha \in C_{0}(\varepsilon _{\Omega _{\omega }+1})$ defined as $\alpha =0$ belongs to $NF$.

• The predicate $\alpha _{0}=_{NF}\psi _{k_{1}}(\alpha _{1})$ on ordinals $\alpha _{0},\alpha _{1}\in C_{0}(\varepsilon _{\Omega _{\omega }+1})$ with $k_{1}=\omega +1$ defined as $\alpha _{0}=\psi _{k_{1}}(\alpha _{1})$ and $\alpha _{1}=C_{k_{1}}(\alpha _{1})$ belongs to $NF$.
• The predicate $\alpha _{0}=_{NF}\alpha _{1}+...+\alpha _{n}$ on ordinals $\alpha _{0},\alpha _{1},...,\alpha _{n}\in C_{0}(\varepsilon _{\Omega _{\omega }+1})$ with an integer $n>1$ defined as $\alpha _{0}=\alpha _{1}+...+\alpha _{n}$, $\alpha _{1}\geq ...\geq \alpha _{n}$, and $\alpha _{1},...,\alpha _{n}\in AP$ belongs to $NF$. Here $+$ is a function symbol rather than an actual addition, and $AP$ denotes the class of additive princpal numbers.

It is also useful to replace the third case by the following one obtained by combining the second condition:

• The predicate $\alpha _{0}=_{NF}\psi _{k_{1}}(\alpha _{1})+...+\psi _{k_{n}}(\alpha _{n})$ on ordinals $\alpha _{0},\alpha _{1},...,\alpha _{n}\in C_{0}(\varepsilon _{\Omega _{\omega }+1})$ with an integer $n>1$ and $k_{1},...,k_{n}\in \omega +1$ defined as $\alpha _{0}=\psi _{k_{1}}(\alpha _{1})+...+\psi _{k_{n}}(\alpha _{n})$, $\psi _{k_{1}}(\alpha _{1})\geq ...\geq \psi _{k_{n}}(\alpha _{n})$, and $\alpha _{1}\in C_{k_{1}}(\alpha _{1}),...,\alpha _{n}\in C_{k_{n}}(\alpha _{n})\in AP$ belongs to $NF$.

We note that those two formulations are not equivalent. For example, $\psi _{0}(\Omega )+1=_{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}\neq 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 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.

Extension(s)

The ordinal notation $(OT,<)$ associated to Buchholz's function was extended by a Japanese mathematician p進大好きbot in a natural way, and is further extended to a $3$-ary notation by a Japanese mathematician kanrokoti. Also, the notions of normal form and fundamental sequences have been extended by Denis Maksudov.

Initial extension by p進大好きbot

We define the sets $T$ and $PT$ as formal strings consisting of parentheses $()$, angle brackets $\langle \rangle$ and commas in the following way:

• $()\in T$
• $\forall X_{1},X_{2}\in T,\langle X_{1},X_{2}\rangle \in T\land \langle X_{1},X_{2}\rangle \in PT$
• $\forall X_{1},...,X_{m}\in PT(2\leq m<\omega ),(X_{1},...,X_{m})\in T$

We will define an ordinal notation $OT$ whose underlying subset is a recursive subset of $T$. In $OT$, $()$ plays a role of $0$, $\langle \;,\;\rangle$ plays a role of extended Buchholz's OCF, and $(\;,...,\;)$ plays a role of the addition. We will denote ${\underline {0}}\in T$ by $()$, ${\underline {1}}\in T$ by $\langle {\underline {0}},{\underline {0}}\rangle$, ${\underline {n}}\in T$ for $1<n\in \mathbb {N}$ by $\underbrace {({\underline {1}},...,{\underline {1}})} _{n}$, and ${\underline {\omega }}\in T$ by $\langle {\underline {0}},{\underline {1}}\rangle$.

Then, for an $(X,Y)\in T^{2}$, we define the recursive $2$-ary relation $X<Y$ in the following way:

• $X={\underline {0}}\rightarrow (X<Y\leftrightarrow Y\neq 0)$
• Suppose $X=\langle X_{1},X_{2}\rangle$ for some $X_{1},X_{2}\in T$. Then:
  • $Y={\underline {0}}\rightarrow X<Y=\bot$
  • Suppose $Y=\langle Y_{1},Y_{2}\rangle$ for some $Y_{1},Y_{2}\in T$. Then:
    • $X_{1}=Y_{1}\rightarrow (X<Y\leftrightarrow X_{2}<Y_{2})$
    • $X_{1}\neq Y_{1}\rightarrow (X<Y\leftrightarrow X_{1}<Y_{1})$
  • If $Y=(Y_{1},...,Y_{m'})$ for some $Y_{1},...,Y_{m'}\in PT\land 2\leq m'<\omega$. Then, $X<Y$ is true if either of the following are true:
    • $X=Y_{1}$
    • $X<Y_{1}$

• Suppose $X=(X_{1},...,X_{m})$ for some $X_{1},...,X_{m}\in PT\land 2\leq m'<\omega$. Then:
  • $Y={\underline {0}}\rightarrow X<Y=\bot$
  • If $Y=\langle Y_{1},Y_{2}\rangle$ for some $Y_{1},Y_{2}\in T$. Then, $X<Y\leftrightarrow X_{1}<Y$
  • Suppose $Y=(Y_{1},...,Y_{m'})$ for some $Y_{1},...,Y_{m'}\in PT\land 2\leq m'<\omega$. Then, $X<Y$ is true if either of the following are true:
    • Suppose $X_{1}=Y_{1}$. Then:
      • $m=2\land m'=2\rightarrow (X<Y\leftrightarrow X_{2}<Y_{2})$
      • $m=2\land m'>2\rightarrow (X<Y\leftrightarrow X_{2}<(Y_{2},...,Y_{m'}))$
      • $m>2\land m'=2\rightarrow (X<Y\leftrightarrow (X_{2},...,X_{m})<Y_{2})$
      • $m>2\land m'>2\rightarrow (X<Y\leftrightarrow (X_{2},...,X_{m})<(Y_{2},...,Y_{m'}))$
    • $X_{1}\neq Y_{1}\rightarrow (X<Y\leftrightarrow X_{1}<Y_{1})$

$<$ is not a strict well-ordering, but it is a total ordering. We abbreviate $X<Y\lor X=Y$ to $X\leq Y$. We then define total recursive maps:

• $dom:X\rightarrow dom(X)$
• $[]:(X,Y)\rightarrow X[Y]$

in the following way:

• $X={\underline {0}}\rightarrow dom(X)={\underline {0}}\land X[Y]={\underline {0}}$
• Suppose $X=\langle X_{1},X_{2}\rangle$ for some $X_{1},X_{2}\in T$. Then:
  • Suppose $dom(X_{2})={\underline {0}}$
    • $dom(X_{1})={\underline {0}}\rightarrow dom(X)=X\land X[Y]={\underline {0}}$
    • $dom(X_{1})={\underline {1}}\rightarrow dom(X)=X\land X[Y]=Y$
    • $dom(X_{1})\notin \{{\underline {0}},{\underline {1}}\}\rightarrow dom(X)=dom(X_{1})\land X[Y]=\langle X_{1}[Y],{\underline {0}}\rangle$
  • $dom(X_{2})={\underline {1}}\rightarrow dom(X)={\underline {\omega }}$
    • $Y={\underline {1}}\rightarrow X[Y]=\langle X_{1},X_{2}[{\underline {0}}]\rangle$
    • $Y={\underline {k}}(2\leq k<\omega )\rightarrow X[Y]=\underbrace {(\langle X_{1},X_{2}[{\underline {0}}]\rangle ,...,\langle X_{1},X_{2}[{\underline {0}}]\rangle )} _{k}$
    • Otherwise, $X[Y]={\underline {0}}$
  • $dom(X_{2})={\underline {\omega }}\rightarrow dom(X)={\underline {\omega }}\land X[Y]=\langle X_{1},X_{2}[Y]\rangle$
  • Suppose $dom(X_{2})\notin \{{\underline {0}},{\underline {1}},{\underline {\omega }}\}$. Then:
    • $dom(X_{2})<X\rightarrow dom(X)=dom(X_{2})\land X[Y]=\langle X_{1},X_{2}[Y]\rangle$
    • Otherwise, $dom(X)=\omega$. Then:
      • $\exists !Z\in T(dom(X_{2})=\langle Z,{\underline {0}}\rangle )$, where $\exists !$ is uniqueness quantification.
      • $Y={\underline {h}}(1\leq h<\omega )\land X[Y[{\underline {0}}]]=\langle X_{1},\Gamma \rangle$ for a unique $\Gamma \in T$, then $X[Y]=\langle X_{1},X_{2}[\langle Z[{\underline {0}}],\Gamma \rangle ]\rangle$.
      • Otherwise, $X[Y]=\langle X_{1},X_{2}[\langle Z[{\underline {0}}],{\underline {0}}\rangle ]\rangle$.
  • If $X=(X_{1},...,X_{m})$ for some $X_{1},...,X_{m}\in PT\land 2\leq m<\omega$, $dom(X)=dom(X_{m})$. Then:
    • $X_{m}[Y]={\underline {0}}\land m=2\rightarrow X[Y]=X_{1}$
    • $X_{m}[Y]={\underline {0}}\land m>2\rightarrow X[Y]=(X_{1},...,X_{m-1})$
    • $X_{m}[Y]\in PT\rightarrow X[Y]=(X_{1},...,X_{m-1},X_{m}[Y])$
    • If $X_{m}[Y]=(Z_{1},...,Z_{m'})$ for some $Z_{1},...,Z_{m'}\in PT(2\leq m'<\omega )$, then $X[Y]=(X_{1},...,X_{m-1},Z_{1},...,Z_{m'})$

Next we will construct a recursive subset $OT\subset T$ of standard forms closed under $\{[{\underline {n}}]|n\in \mathbb {N} \}$ such that $[]$ restricted to $\{X\in OT|X<\langle {\underline {1}},{\underline {0}}\rangle \}\times \{{\underline {n}}|n\in \mathbb {N} \}$ forms a recursive system of fundamental sequences with respect to $<$. For any $(X,Y,Z)\in T^{3}$, we define a $3$-ary relation $G(X,Y)\vartriangleleft Z$ in the following way:

• $Y={\underline {0}}\rightarrow G(X,Y)\vartriangleleft Z=\top$
• Suppose $Y=\langle W_{1},W_{2}\rangle$ for some $W_{1},W_{2}\in T$:
  • $X\leq W_{1}\rightarrow (G(X,Y)\vartriangleleft Z\leftrightarrow (W_{2}<Z)\lor (G(X,W_{1})\vartriangleleft Z)\lor (G(X,W_{2})\vartriangleleft Z))$
  • $W_{1}<X\rightarrow G(X,Y)\vartriangleleft Z=\top$
• If $Y=(W_{1},...,W_{m'})$ for some $(W_{1},...,W_{m'})\in PT(2\leq m'<\omega )$, then $\forall i\in \mathbb {N} \land i<m'(G(X,Y)\vartriangleleft Z\leftrightarrow G(X,W_{i+1})\vartriangleleft Z)$

We define a recursive subset $OT\subset T$ in the following way:

• ${\underline {0}}\in OT$
• $\forall X_{1},X_{2}\in T,\langle X_{1},X_{2}\rangle \in OT\leftrightarrow X_{1}\in OT\land X_{2}\in OT\land G(X_{1},X_{2})\vartriangleleft X_{2}$
• $\forall i\in \mathbb {N} \land i<m\forall j\in \mathbb {N} \land j<m-1(X_{j+2}\leq X_{j+1})\forall X_{1},...,X_{m}\in PT(2\leq M<\omega )((X_{1},...,X_{m})\in OT\leftrightarrow X_{i+1}\in OT)$

$\Omega _{\Omega _{...}}$ denotes the least $\Omega$ fixed point. We then define a map $o:T\rightarrow \Omega _{\Omega _{...}}$ in the following way:

• $X={\underline {0}}\rightarrow o(X)=0$
• If $X=\langle Y_{1},Y_{2}\rangle$ for some $Y_{1},Y_{2}\in T$, then $o(X)=\psi _{o(Y_{1})}(o(Y_{2}))$, where $\psi$ is extended Buchholz's function.
• If $X=(Y_{1},...,Y_{m})$ for some $Y_{1},...,Y_{m}\in PT(2\leq m<\omega )$ then $o(X)=\sum _{i=1}^{m}o(Y_{i})$, where $\Sigma$ is summation.

By the construction, $(OT,<)$ forms an ordinal notation, and the restriction of $o$ gives the isomorphisms

• $(OT,<)\rightarrow (C_{0}(\Omega _{\Omega _{...}}),\in )$
• $(\{X\in OT|X<\langle {\underline {1}},{\underline {0}}\rangle \},<)\rightarrow (C_{0}(\Omega _{\Omega _{...}})\cap \Omega ,\in )$

of strictly ordered sets.

3-ary notation

EBOCF (Extended Buchholz's OCF) is a $2$-ary function. So, kanrokoti decided to extend it: $\psi _{A}(B)\implies \psi _{0}(A,B)$. Please be careful that the 3 variables ψ is neither an OCF nor ordinal notation. Kanoroki named this notation "くまくま 3 variables ψ". "くま" means "bear" in Japanese. Here is the definition:

We define sets $T$ and $PT$ as formal strings consisting of $0$, the $\psi$ function, parentheses $()$, addition $+$ and commas in the following way:

• $0\in T$
• $\forall X_{1},X_{2},X_{3}\in T(\psi _{X_{1}}(X_{2},X_{3})\in T\land \psi _{X_{1}}(X_{2},X_{3})\in PT)$
• $\forall X_{1},...,X_{m}\in PT(2\leq m<\omega )(\sum _{i=1}^{m}X_{1}\in T)$

$0$ is written as $\$0$, $\psi _{0}(0,0)=1$ is written as $\$1$, and $\underbrace {\$1+...+\$1} _{n}$ is written as $\$n$ for all $n\in \mathbb {N} \land n>1$, and $\psi _{0}(0,\$1)=\omega$ is written as $\$\omega$. Next, we will define the "magnitude" relation for the notation:

• $X=0\rightarrow (X<Y\leftrightarrow Y\neq 0)$
• Suppose $X=\psi _{X_{1}}(X_{2},X_{3})$ for some $X_{1},X_{2},X_{3}\in T$. Then:
  • $Y=0\rightarrow X<Y=\bot$
  • Suppose $Y=\psi _{Y_{1}}(Y_{2},Y_{3})$ for some $Y_{1},Y_{2},Y_{3}\in T$. Then:
    • $X_{1}=Y_{1}\land X_{2}=Y_{2}\rightarrow (X<Y\leftrightarrow X_{3}<Y_{3})$
    • $X_{1}=Y_{1}\land X_{2}\neq Y_{2}\rightarrow (X<Y\leftrightarrow X_{2}<Y_{2})$
    • $X_{1}\neq Y_{1}\rightarrow (X<Y\leftrightarrow X_{1}<Y_{1})$
  • If $Y=\sum _{i=1}^{m'}Y_{i}$ for some $Y_{1},...,Y_{m'}\in PT(2\leq m'<\omega )$, then $X<Y\leftrightarrow (X=Y_{1}\lor X<Y_{1})$
• Suppose $X=\sum _{i=1}^{m'}X_{i}$ for some $X_{1},...,X_{m}\in PT(2\leq m'<\omega )$. Then:
  • $Y=0\rightarrow X<Y=\bot$
  • Suppose $Y=\psi _{Y_{1}}(Y_{2},Y_{3})$ for some $Y_{1},Y_{2},Y_{3}\in T$, then $X<Y\leftrightarrow X_{1}<Y$.
  • Suppose $Y=\sum _{i=1}^{m'}Y_{i}$ for some $Y_{1},...,Y_{m'}\in PT(2\leq m'<\omega )$, then $X<Y\leftrightarrow (X=Y_{1}\lor X<Y_{1})$. Then:
    • Suppose $X_{1}=Y_{1}$. Then:
      • $m=2\land m'=2\rightarrow (X<Y\leftrightarrow X_{2}<Y_{2})$
      • $m=2\land m'>2\rightarrow (X<Y\leftrightarrow X_{2}<\sum _{i=2}^{m'}Y_{i})$
      • $m>2\land m'=2\rightarrow (X<Y\leftrightarrow \sum _{i=2}^{m}X_{i}<Y_{2})$
      • $m>2\land m'>2\rightarrow (X<Y\leftrightarrow \sum _{i=2}^{m}X_{i}<\sum _{i=2}^{m'}Y_{i})$.
    • $X_{1}\neq Y_{1}\rightarrow (X<Y\leftrightarrow X_{1}<Y_{1})$

We then define a total recursive map $dom:X\rightarrow dom(X)$ like so:

• $X=0\rightarrow dom(X)=0$
• Suppose $X=\psi _{X_{1}}(X_{2},X_{3})$ for some $X_{1},X_{2},X_{3}\in T$. Then:
  • Suppose $dom(X_{3})=0$. Then:
    • Suppose $dom(X_{2})=0$. Then:
      • $dom(X_{1})=0\lor dom(X_{1})=\$1\rightarrow dom(X)=X$.
      • $dom(X_{1})\notin \{0,\$1\}\rightarrow dom(X)=dom(X_{1})$.
    • $dom(X_{2})=\$1\rightarrow dom(X)=X$.
    • Suppose $dom(X_{2})\notin \{0,\$1\}$. Then:
      • $dom(X_{2})<X\rightarrow dom(X)=dom(X_{2})$
      • Otherwise, $dom(X)=\$\omega$
  • $dom(X_{3})=\$1\lor dom(X_{3})=\$\omega \rightarrow dom(X)=\$\omega$
  • Suppose $dom(X_{3})\notin \{0,\$1,\$\omega \}$. Then:
    • $dom(X_{3})<X\rightarrow dom(X)=dom(X_{3})$
    • Otherwise, $dom(X)=\$\omega$
• If $X=\sum _{i=1}^{m}X_{i}$ for some $X_{1},...,X_{m}\in PT(2\leq m<\omega )$, then $dom(X)=dom(X_{m})$.

Next, we define the fundamental sequences. We define total recursive maps $[]:(X,Y)\rightarrow X[Y]$ in the following way:

• $X=0\rightarrow X[Y]=0$
• Suppose $X=\psi _{X_{1}}(X_{2},X_{3})$ for some $X_{1},X_{2},X_{3}\in T$. Then:
  • Suppose $dom(X_{3})=0$. Then:
    • Suppose $dom(X_{2})=0$. Then:
      • $dom(X_{1})=0\rightarrow X[Y]=0$
      • $dom(X_{1})=\$1\rightarrow X[Y]=Y$
      • $dom(X_{1})\notin \{0,\$1\}\rightarrow X[Y]=\psi _{X_{1}[Y]}(X_{2},X_{3})$
    • $dom(X_{2})=\$1\rightarrow X[Y]=Y$
    • Suppose $dom(X_{2})\notin \{0,\$1\}$. Then:
      • $dom(X_{2})<X\rightarrow X[Y]=\psi _{X_{1}}(X_{2}[Y],X_{3})$
      • Otherwise, $\exists !P,Q\in T(dom(X_{3})=\psi _{P}(Q,0))$. Then:
        • Suppose $Q=0$. Then:
          • $\exists !\Gamma \in T(Y=\$h(1\leq h<\omega )\land X[Y[0]]=\psi _{X_{1}}(\Gamma ,X_{3})\rightarrow X[Y]=\psi _{X_{1}}(X_{2}[\psi _{P[0]}(\Gamma ,0)],X_{3}))$
          • Otherwise, $X[Y]=\psi _{X_{1}}(X_{2}[\psi _{P[0]}(Q,0)],X_{3})$
        • Suppose $Q\neq 0$. Then:
          • $\exists !\Gamma \in T(Y=\$h(1\leq h<\omega )\land X[Y[0]]=\psi _{X_{1}}(\Gamma ,X_{3})\rightarrow X[Y]=\psi _{X_{1}}(X_{2}[\psi _{P}(Q[0],\Gamma )],X_{3}))$
          • Otherwise, $X[Y]=\psi _{X_{1}}(X_{2}[\psi _{P}(Q[0],0)],X_{3})$
    • Suppose $dom(X_{3})=\$1$. Then:
      • $Y=\$1\rightarrow X[Y]=\psi _{X_{1}}(X_{2},X_{3}[0])$
      • If $Y=\$k(2\leq k<\omega )$, then $X[Y]=\underbrace {\psi _{X_{1}}(X_{2},X_{3}[0])+...+\psi _{X_{1}}(X_{2},X_{3}[0])} _{k}$
      • Otherwise, $X[Y]=0$
    • $dom(X_{3})=\$\omega \rightarrow X[Y]=\psi _{X_{1}}(X_{2},X_{3}[Y])$
    • Suppose $dom(X_{3})\notin \{0,\$1,\$\omega \}$. Then:
      • $dom(X_{3})<X\rightarrow X[Y]=\psi _{X_{1}}(X_{2},X_{3}[Y])$
      • Otherwise, $\exists !P,Q\in T(dom(X_{3})=\psi _{P}(Q,0))$.
        • Suppose $Q=0$. Then:
          • $\exists !\Gamma \in T(Y=\$h(1\leq h<\omega )\land X[Y[0]]=\psi _{X_{1}}(X_{2},\Gamma ))\rightarrow X[Y]=\psi _{X_{1}}(X_{2},X_{3}[\psi _{P}(Q[0],\Gamma )])$
          • Otherwise, $X[Y]=\psi _{X_{1}}(X_{2},X_{3}[\psi _{P}(Q[0],\Gamma )])$.
        • Suppose $Q\neq 0$. Then:
          • $\exists !\Gamma \in T(Y=\$h(1\leq h<\omega )\land X[Y[0]]=\psi _{X_{1}}(X_{2},\Gamma ))\rightarrow X[Y]=\psi _{X_{1}}(X_{2},X_{3}[\psi _{P}(Q[0],0)])$
          • Otherwise, $X[Y]=\psi _{X_{1}}(X_{2},X_{3}[\psi _{P}(Q[0],\Gamma )])$
• Suppose $X=\sum _{i=1}^{m}X_{i}$ for some $X_{1},...,X_{m}\in PT(2\leq m<\omega )$. Then:
  • $X_{m}[Y]=0\land m=2\rightarrow X[Y]=X_{1}$
  • $X_{m}[Y]=0\land m>2\rightarrow X[Y]=\sum _{i=1}^{m-1}X_{i}$
  • $X_{m}[Y]\neq 0\rightarrow X[Y]=(\sum _{i=1}^{m-1}X_{i})+X_{m}[Y]$

For some reason, kanrokoti never included the definition for the $\psi _{x}(y,z)$ function for $x\geq 1$. But here we have some numbers defined using the psi function:

• KumaKuma 3 variables $\psi$ ordinal:
  • We define the function $g$ such that $n=0\rightarrow g(n)=1$, otherwise $g(n)=\psi _{g(n-1)}(0,0)$.
  • We define the function $F$ such that $F(n)=f_{\psi _{0}(0,g(n))}(n)$ in the fast-growing hierarchy.
  • The KumaKuma 3 variables $\psi$ ordinal is an ordinal $x$ such that $f_{x}(n)=F^{10^{100}}(10^{100})$.
• Kuma-Bachmann-Howard ordinal:
  • The KBHO is the ordinal $\psi _{0}(0,\psi _{\$2}(0,0))$.
• Kuma-Buchholz ordinal:
  • The KBO is the ordinal $\psi _{0}(0,\psi _{\$\omega }(0,0))$.
• Extended Kuma-Buchholz ordinal:
  • The EKBO is the ordinal $\psi _{0}(0,\psi _{\Omega _{\Omega _{...}}}(0,0))$ where $\Omega _{\Omega _{...}}$ is the least omega fixed point. $\psi _{0}(0,\Omega _{\Omega _{...}})$
• KumaKuma-Bachmann-Howard ordinal:
  • The KKBHO is the ordinal $\psi _{0,0}(0,\psi _{\$2,0}(0,0))$ in the extended $4$-ary system.
• KumaKuma-Buchholz ordinal:
  • The KKBO is the ordinal $\psi _{0,0}(0,\psi _{\$\omega ,0}(0,0))$ in the extended $4$-ary system.
• Extended KumaKuma-Buchholz ordinal:
  • The EKKBO is the ordinal $\psi _{0}(0,\psi _{\psi _{\Omega _{\Omega _{...}}}(0,0)}(0,0))$ in the extended $4$-ary system.

Although there is no formal proof, it is expected that EKBO and EKKBO coincide with $\psi _{\chi _{0}(0)}(\psi _{\chi _{2}(0)}(0))$ and $\psi _{\chi _{0}(0)}(\psi _{\chi _{3}(0)}(0))$ in Rathjen's psi function, respectively.