Buchholz psi functions

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Buchholz psi functions" – news · newspapers · books · scholar · JSTOR (September 2021) (Learn how and when to remove this message)

Buchholz's psi-functions are a hierarchy of single-argument ordinal functions ${\displaystyle \psi _{\nu }(\alpha )}$ introduced by German mathematician Wilfried Buchholz in 1986. These functions are a simplified version of the ${\displaystyle \theta }$-functions, but nevertheless have the same strength^{[clarification needed]} as those. Later on this approach was extended by Jäger^[1] and Schütte.^[2]

Buchholz defined his functions as follows. Define:

• Ω_ξ = ω_ξ if ξ > 0, Ω₀ = 1

The functions ψ_v(α) for α an ordinal, v an ordinal at most ω, are defined by induction on α as follows:

• ψ_v(α) is the smallest ordinal not in C_v(α)

where C_v(α) is the smallest set such that

• C_v(α) contains all ordinals less than Ω_v
• C_v(α) is closed under ordinal addition
• C_v(α) is closed under the functions ψ_u (for u≤ω) applied to arguments less than α.

The limit of this notation is the Takeuti–Feferman–Buchholz ordinal.

Let ${\displaystyle P}$ be the class of additively principal ordinals. Buchholz showed following properties of this functions:

• ${\displaystyle \psi _{\nu }(0)=\Omega _{\nu },}$ ^[3]: 197
• ${\displaystyle \psi _{\nu }(\alpha )\in P,}$ ^[3]: 197
• ${\displaystyle \psi _{\nu }(\alpha +1)=\min\{\gamma \in P:\psi _{\nu }(\alpha )<\gamma \}{\text{ if }}\alpha \in C_{\nu }(\alpha ),}$ ^[3]: 199
• ${\displaystyle \Omega _{\nu }\leq \psi _{\nu }(\alpha )<\Omega _{\nu +1}}$ ^[3]: 197
• ${\displaystyle \psi _{0}(\alpha )=\omega ^{\alpha }{\text{ if }}\alpha <\varepsilon _{0},}$ ^[3]: 199
• ${\displaystyle \psi _{\nu }(\alpha )=\omega ^{\Omega _{\nu }+\alpha }{\text{ if }}\alpha <\varepsilon _{\Omega _{\nu }+1}{\text{ and }}\nu \neq 0,}$ ^[3]: 199
• ${\displaystyle \theta (\varepsilon _{\Omega _{\nu }+1},0)=\psi (\varepsilon _{\Omega _{\nu }+1}){\text{ for }}0<\nu \leq \omega .}$ ^[3]: 206

The normal form for 0 is 0. If ${\displaystyle \alpha }$ is a nonzero ordinal number ${\displaystyle \alpha <\Omega _{\omega }}$ then the normal form for ${\displaystyle \alpha }$ is ${\displaystyle \alpha =\psi _{\nu _{1}}(\beta _{1})+\psi _{\nu _{2}}(\beta _{2})+\cdots +\psi _{\nu _{k}}(\beta _{k})}$ where ${\displaystyle \nu _{i}\in \mathbb {N} _{0},k\in \mathbb {N} _{>0},\beta _{i}\in C_{\nu _{i}}(\beta _{i})}$ and ${\displaystyle \psi _{\nu _{1}}(\beta _{1})\geq \psi _{\nu _{2}}(\beta _{2})\geq \cdots \geq \psi _{\nu _{k}}(\beta _{k})}$ and each ${\displaystyle \beta _{i}}$ is also written in normal form.

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

For nonzero ordinals ${\displaystyle \alpha <\Omega _{\omega }}$, written in normal form, fundamental sequences are defined as follows:

1. If ${\displaystyle \alpha =\psi _{\nu _{1}}(\beta _{1})+\psi _{\nu _{2}}(\beta _{2})+\cdots +\psi _{\nu _{k}}(\beta _{k})}$ where ${\displaystyle k\geq 2}$ then ${\displaystyle \operatorname {cof} (\alpha )=\operatorname {cof} (\psi _{\nu _{k}}(\beta _{k}))}$ and ${\displaystyle \alpha [\eta ]=\psi _{\nu _{1}}(\beta _{1})+\cdots +\psi _{\nu _{k-1}}(\beta _{k-1})+(\psi _{\nu _{k}}(\beta _{k})[\eta ]),}$
2. If ${\displaystyle \alpha =\psi _{0}(0)=1}$, then ${\displaystyle \operatorname {cof} (\alpha )=1}$ and ${\displaystyle \alpha [0]=0}$,
3. If ${\displaystyle \alpha =\psi _{\nu +1}(0)}$, then ${\displaystyle \operatorname {cof} (\alpha )=\Omega _{\nu +1}}$ and ${\displaystyle \alpha [\eta ]=\Omega _{\nu +1}[\eta ]=\eta }$,
4. If ${\displaystyle \alpha =\psi _{\nu }(\beta +1)}$ then ${\displaystyle \operatorname {cof} (\alpha )=\omega }$ and ${\displaystyle \alpha [\eta ]=\psi _{\nu }(\beta )\cdot \eta }$ (and note: ${\displaystyle \psi _{\nu }(0)=\Omega _{\nu }}$),
5. If ${\displaystyle \alpha =\psi _{\nu }(\beta )}$ and ${\displaystyle \operatorname {cof} (\beta )\in \{\omega \}\cup \{\Omega _{\mu +1}\mid \mu <\nu \}}$ then ${\displaystyle \operatorname {cof} (\alpha )=\operatorname {cof} (\beta )}$ and ${\displaystyle \alpha [\eta ]=\psi _{\nu }(\beta [\eta ])}$,
6. If ${\displaystyle \alpha =\psi _{\nu }(\beta )}$ and ${\displaystyle \operatorname {cof} (\beta )\in \{\Omega _{\mu +1}\mid \mu \geq \nu \}}$ then ${\displaystyle \operatorname {cof} (\alpha )=\omega }$ and ${\displaystyle \alpha [\eta ]=\psi _{\nu }(\beta [\gamma [\eta ]])}$ where ${\displaystyle \left\{{\begin{array}{lcr}\gamma [0]=\Omega _{\mu }\\\gamma [\eta +1]=\psi _{\mu }(\beta [\gamma [\eta ]])\\\end{array}}\right.}$.

Buchholz is working in Zermelo–Fraenkel set theory, that means every ordinal ${\displaystyle \alpha }$ is equal to set ${\displaystyle \{\beta \mid \beta <\alpha \}}$. Then condition ${\displaystyle C_{\nu }^{0}(\alpha )=\Omega _{\nu }}$ means that set ${\displaystyle C_{\nu }^{0}(\alpha )}$ includes all ordinals less than ${\displaystyle \Omega _{\nu }}$ in other words ${\displaystyle C_{\nu }^{0}(\alpha )=\{\beta \mid \beta <\Omega _{\nu }\}}$.

The condition ${\displaystyle 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 ${\displaystyle C_{\nu }^{n+1}(\alpha )}$ includes:

• all ordinals from previous set ${\displaystyle C_{\nu }^{n}(\alpha )}$,
• all ordinals that can be obtained by summation the additively principal ordinals from previous set ${\displaystyle C_{\nu }^{n}(\alpha )}$,
• all ordinals that can be obtained by applying ordinals less than ${\displaystyle \alpha }$ from the previous set ${\displaystyle C_{\nu }^{n}(\alpha )}$ as arguments of functions ${\displaystyle \psi _{\mu }}$, where ${\displaystyle \mu \leq \omega }$.

That is why we can rewrite this condition as:

${\displaystyle 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 ${\displaystyle C_{\nu }^{n}(\alpha )}$ with ${\displaystyle n<\omega }$ i.e. ${\displaystyle C_{\nu }(\alpha )=\bigcup _{n<\omega }C_{\nu }^{n}(\alpha )}$ denotes the set of all ordinals which can be generated from ordinals ${\displaystyle <\aleph _{\nu }}$ by the functions + (addition) and ${\displaystyle \psi _{\mu }(\eta )}$, where ${\displaystyle \mu \leq \omega }$ and ${\displaystyle \eta <\alpha }$.

Then ${\displaystyle \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:

${\displaystyle C_{0}^{0}(\alpha )=\{0\}=\{\beta \mid \beta <1\},}$

${\displaystyle C_{0}(0)=\{0\}}$ (since no functions ${\displaystyle \psi (\eta <0)}$ and 0 + 0 = 0).

Then ${\displaystyle \psi _{0}(0)=1}$.

${\displaystyle C_{0}(1)}$ includes ${\displaystyle \psi _{0}(0)=1}$ and all possible sums of natural numbers and therefore ${\displaystyle \psi _{0}(1)=\omega }$ – first transfinite ordinal, which is greater than all natural numbers by its definition.

${\displaystyle C_{0}(2)}$ includes ${\displaystyle \psi _{0}(0)=1,\psi _{0}(1)=\omega }$ and all possible sums of them and therefore ${\displaystyle \psi _{0}(2)=\omega ^{2}}$.

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

If ${\displaystyle \alpha =\Omega }$ then ${\displaystyle 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 ${\displaystyle \psi _{0}(\Omega )=\varepsilon _{0}}$ – the smallest epsilon number i.e. first fixed point of ${\displaystyle \alpha =\omega ^{\alpha }}$.

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

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

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

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

${\displaystyle \psi _{0}(\Omega ^{\Omega })=\Gamma _{0}=\varphi (1,0,0)=\theta (\Omega ,0)}$, where ${\displaystyle \theta }$ denotes the Feferman's function and ${\displaystyle \Gamma _{0}}$ is the Feferman–Schütte ordinal,

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

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

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

${\displaystyle \psi _{0}(\Omega \uparrow \uparrow \omega )=\psi _{0}(\varepsilon _{\Omega +1})=\theta (\varepsilon _{\Omega +1},0).}$

Now let's research how ${\displaystyle \psi _{1}}$ works:

${\displaystyle 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 }$

${\displaystyle \ldots ,\psi _{0}(\Omega ^{\Omega })=\Gamma _{0},\ldots ,\psi (\Omega ^{\Omega ^{\Omega }+\Omega ^{2}}),\ldots \}}$ i.e. includes all countable ordinals. And therefore ${\displaystyle C_{1}(0)}$ includes all possible sums of all countable ordinals and ${\displaystyle \psi _{1}(0)=\Omega _{1}}$ first uncountable ordinal which is greater than all countable ordinal by its definition i.e. smallest number with cardinality ${\displaystyle \aleph _{1}}$.

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

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

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

${\displaystyle \psi _{1}(\psi _{1}(\psi _{1}(0)))=\omega ^{\Omega +\omega ^{\Omega +\Omega }}=\omega ^{\Omega \cdot \Omega }=(\omega ^{\Omega })^{\Omega }=\Omega ^{\Omega },}$

${\displaystyle \psi _{1}^{4}(0)=\Omega ^{\Omega ^{\Omega }},}$

${\displaystyle \psi _{1}^{k+1}(0)=\Omega \uparrow \uparrow k}$ where ${\displaystyle k}$ is a natural number, ${\displaystyle k\geq 2}$,

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

For case ${\displaystyle \psi (\psi _{2}(0))=\psi (\Omega _{2})}$ the set ${\displaystyle C_{0}(\Omega _{2})}$ includes functions ${\displaystyle \psi _{0}}$ with all arguments less than ${\displaystyle \Omega _{2}}$ i.e. such arguments as ${\displaystyle 0,\psi _{1}(0),\psi _{1}(\psi _{1}(0)),\psi _{1}^{3}(0),\ldots ,\psi _{1}^{\omega }(0)}$

and then

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

In the general case:

${\displaystyle \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:

${\displaystyle \theta (\Omega _{\nu },0)=\psi _{0}(\Omega _{\nu }^{\Omega }){\text{ (for }}1\leq \nu )<\omega }$

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

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

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

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

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

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

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

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

${\displaystyle b\in G_{u}a}$ is a recursive relation on ${\displaystyle (u,a,b)\in (\omega +1)\times T^{2}}$. Finally, we define a subset ${\displaystyle OT\subset T}$ in the following way:

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

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

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

Buchholz verified the following properties of ${\displaystyle o}$:

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

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 ${\displaystyle o}$. Namely, the set ${\displaystyle NF}$ of predicates on ordinals in ${\displaystyle C_{0}(\varepsilon _{\Omega _{\omega }+1})}$ is defined in the following way:

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

• The predicate ${\displaystyle \alpha _{0}=_{NF}\psi _{k_{1}}(\alpha _{1})}$ on ordinals ${\displaystyle \alpha _{0},\alpha _{1}\in C_{0}(\varepsilon _{\Omega _{\omega }+1})}$ with ${\displaystyle k_{1}=\omega +1}$ defined as ${\displaystyle \alpha _{0}=\psi _{k_{1}}(\alpha _{1})}$ and ${\displaystyle \alpha _{1}=C_{k_{1}}(\alpha _{1})}$ belongs to ${\displaystyle NF}$.
• The predicate ${\displaystyle \alpha _{0}=_{NF}\alpha _{1}+...+\alpha _{n}}$ on ordinals ${\displaystyle \alpha _{0},\alpha _{1},...,\alpha _{n}\in C_{0}(\varepsilon _{\Omega _{\omega }+1})}$ with an integer ${\displaystyle n>1}$ defined as ${\displaystyle \alpha _{0}=\alpha _{1}+...+\alpha _{n}}$, ${\displaystyle \alpha _{1}\geq ...\geq \alpha _{n}}$, and ${\displaystyle \alpha _{1},...,\alpha _{n}\in AP}$ belongs to ${\displaystyle NF}$. Here ${\displaystyle +}$ is a function symbol rather than an actual addition, and ${\displaystyle 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:

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

We note that those two formulations are not equivalent. For example, ${\displaystyle \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 ${\displaystyle \zeta _{1}\neq C_{0}(\zeta _{1})}$, while it is a valid formula which is true with respect to the first formulation because of ${\displaystyle \psi _{0}(\Omega )+1=\psi _{0}(\zeta _{1})+\psi _{0}(0)}$, ${\displaystyle \psi _{0}(\zeta _{1}),\psi _{0}(0)\in AP}$, and ${\displaystyle \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 ${\displaystyle C_{0}(\varepsilon _{\Omega _{\omega }+1})}$ can be uniquely expressed in normal form for Buchholz's function.