• Images
• Videos
• Documents
• Books
• Articles

Definition

Buchholz defined his functions as follows. Define:

• Ωξ = ωξ if ξ > 0, Ω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 Cv(α)

where Cv(α) is the smallest set such that

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

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

Properties

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

• ψ ν ( 0 ) = Ω ν , {\displaystyle \psi _{\nu }(0)=\Omega _{\nu },} ³: 197 
• ψ ν ( α ) ∈ P , {\displaystyle \psi _{\nu }(\alpha )\in P,} ⁴: 197 
• ψ ν ( α + 1 ) = min { γ ∈ P : ψ ν ( α ) < γ }  if  α ∈ C ν ( α ) , {\displaystyle \psi _{\nu }(\alpha +1)=\min\{\gamma \in P:\psi _{\nu }(\alpha )<\gamma \}{\text{ if }}\alpha \in C_{\nu }(\alpha ),} ⁵: 199 
• Ω ν ≤ ψ ν ( α ) < Ω ν + 1 {\displaystyle \Omega _{\nu }\leq \psi _{\nu }(\alpha )<\Omega _{\nu +1}} ⁶: 197 
• ψ 0 ( α ) = ω α  if  α < ε 0 , {\displaystyle \psi _{0}(\alpha )=\omega ^{\alpha }{\text{ if }}\alpha <\varepsilon _{0},} ⁷: 199 
• ψ ν ( α ) = ω Ω ν + α  if  α < ε Ω ν + 1  and  ν ≠ 0 , {\displaystyle \psi _{\nu }(\alpha )=\omega ^{\Omega _{\nu }+\alpha }{\text{ if }}\alpha <\varepsilon _{\Omega _{\nu }+1}{\text{ and }}\nu \neq 0,} ⁸: 199 
• θ ( ε Ω ν + 1 , 0 ) = ψ ( ε Ω ν + 1 )  for  0 < ν ≤ ω . {\displaystyle \theta (\varepsilon _{\Omega _{\nu }+1},0)=\psi (\varepsilon _{\Omega _{\nu }+1}){\text{ for }}0<\nu \leq \omega .} ⁹: 206 

Fundamental sequences and normal form for Buchholz's function

Normal form

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 α = ψ ν 1 ( β 1 ) + ψ ν 2 ( β 2 ) + ⋯ + ψ ν k ( β k ) {\displaystyle \alpha =\psi _{\nu _{1}}(\beta _{1})+\psi _{\nu _{2}}(\beta _{2})+\cdots +\psi _{\nu _{k}}(\beta _{k})} where ν i ∈ N 0 , k ∈ N > 0 , β i ∈ C ν i ( β i ) {\displaystyle \nu _{i}\in \mathbb {N} _{0},k\in \mathbb {N} _{>0},\beta _{i}\in C_{\nu _{i}}(\beta _{i})} and ψ ν 1 ( β 1 ) ≥ ψ ν 2 ( β 2 ) ≥ ⋯ ≥ ψ ν k ( β k ) {\displaystyle \psi _{\nu _{1}}(\beta _{1})\geq \psi _{\nu _{2}}(\beta _{2})\geq \cdots \geq \psi _{\nu _{k}}(\beta _{k})} and each β i {\displaystyle \beta _{i}} is also written in normal form.

Fundamental sequences

The fundamental sequence for an ordinal number α {\displaystyle \alpha } with cofinality cof ⁡ ( α ) = β {\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 cof ⁡ ( α ) = 1 {\displaystyle \operatorname {cof} (\alpha )=1} and the fundamental sequence has only one element α [ 0 ] = α − 1 {\displaystyle \alpha [0]=\alpha -1} . If α {\displaystyle \alpha } is a limit ordinal then cof ⁡ ( α ) ∈ { ω } ∪ { Ω μ + 1 ∣ μ ≥ 0 } {\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 α = ψ ν 1 ( β 1 ) + ψ ν 2 ( β 2 ) + ⋯ + ψ ν k ( β k ) {\displaystyle \alpha =\psi _{\nu _{1}}(\beta _{1})+\psi _{\nu _{2}}(\beta _{2})+\cdots +\psi _{\nu _{k}}(\beta _{k})} where k ≥ 2 {\displaystyle k\geq 2} then cof ⁡ ( α ) = cof ⁡ ( ψ ν k ( β k ) ) {\displaystyle \operatorname {cof} (\alpha )=\operatorname {cof} (\psi _{\nu _{k}}(\beta _{k}))} and α [ η ] = ψ ν 1 ( β 1 ) + ⋯ + ψ ν k − 1 ( β k − 1 ) + ( ψ ν k ( β k ) [ η ] ) , {\displaystyle \alpha [\eta ]=\psi _{\nu _{1}}(\beta _{1})+\cdots +\psi _{\nu _{k-1}}(\beta _{k-1})+(\psi _{\nu _{k}}(\beta _{k})[\eta ]),}
2. If α = ψ 0 ( 0 ) = 1 {\displaystyle \alpha =\psi _{0}(0)=1} , then cof ⁡ ( α ) = 1 {\displaystyle \operatorname {cof} (\alpha )=1} and α [ 0 ] = 0 {\displaystyle \alpha [0]=0} ,
3. If α = ψ ν + 1 ( 0 ) {\displaystyle \alpha =\psi _{\nu +1}(0)} , then cof ⁡ ( α ) = Ω ν + 1 {\displaystyle \operatorname {cof} (\alpha )=\Omega _{\nu +1}} and α [ η ] = Ω ν + 1 [ η ] = η {\displaystyle \alpha [\eta ]=\Omega _{\nu +1}[\eta ]=\eta } ,
4. If α = ψ ν ( β + 1 ) {\displaystyle \alpha =\psi _{\nu }(\beta +1)} then cof ⁡ ( α ) = ω {\displaystyle \operatorname {cof} (\alpha )=\omega } and α [ η ] = ψ ν ( β ) ⋅ η {\displaystyle \alpha [\eta ]=\psi _{\nu }(\beta )\cdot \eta } (and note: ψ ν ( 0 ) = Ω ν {\displaystyle \psi _{\nu }(0)=\Omega _{\nu }} ),
5. If α = ψ ν ( β ) {\displaystyle \alpha =\psi _{\nu }(\beta )} and cof ⁡ ( β ) ∈ { ω } ∪ { Ω μ + 1 ∣ μ < ν } {\displaystyle \operatorname {cof} (\beta )\in \{\omega \}\cup \{\Omega _{\mu +1}\mid \mu <\nu \}} then cof ⁡ ( α ) = cof ⁡ ( β ) {\displaystyle \operatorname {cof} (\alpha )=\operatorname {cof} (\beta )} and α [ η ] = ψ ν ( β [ η ] ) {\displaystyle \alpha [\eta ]=\psi _{\nu }(\beta [\eta ])} ,
6. If α = ψ ν ( β ) {\displaystyle \alpha =\psi _{\nu }(\beta )} and cof ⁡ ( β ) ∈ { Ω μ + 1 ∣ μ ≥ ν } {\displaystyle \operatorname {cof} (\beta )\in \{\Omega _{\mu +1}\mid \mu \geq \nu \}} then cof ⁡ ( α ) = ω {\displaystyle \operatorname {cof} (\alpha )=\omega } and α [ η ] = ψ ν ( β [ γ [ η ] ] ) {\displaystyle \alpha [\eta ]=\psi _{\nu }(\beta [\gamma [\eta ]])} where { γ [ 0 ] = Ω μ γ [ η + 1 ] = ψ μ ( β [ γ [ η ] ] ) {\displaystyle \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 α {\displaystyle \alpha } is equal to set { β ∣ β < α } {\displaystyle \{\beta \mid \beta <\alpha \}} . Then condition C ν 0 ( α ) = Ω ν {\displaystyle C_{\nu }^{0}(\alpha )=\Omega _{\nu }} means that set C ν 0 ( α ) {\displaystyle C_{\nu }^{0}(\alpha )} includes all ordinals less than Ω ν {\displaystyle \Omega _{\nu }} in other words C ν 0 ( α ) = { β ∣ β < Ω ν } {\displaystyle C_{\nu }^{0}(\alpha )=\{\beta \mid \beta <\Omega _{\nu }\}} .

The condition C ν n + 1 ( α ) = C ν n ( α ) ∪ { γ ∣ P ( γ ) ⊆ C ν n ( α ) } ∪ { ψ μ ( ξ ) ∣ ξ ∈ α ∩ C ν n ( α ) ∧ μ ≤ ω } {\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 C ν n + 1 ( α ) {\displaystyle C_{\nu }^{n+1}(\alpha )} includes:

• all ordinals from previous set C ν n ( α ) {\displaystyle C_{\nu }^{n}(\alpha )} ,
• all ordinals that can be obtained by summation the additively principal ordinals from previous set C ν n ( α ) {\displaystyle C_{\nu }^{n}(\alpha )} ,
• all ordinals that can be obtained by applying ordinals less than α {\displaystyle \alpha } from the previous set C ν n ( α ) {\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:

C ν n + 1 ( α ) = { β + γ , ψ μ ( η ) ∣ β , γ , η ∈ C ν n ( α ) ∧ η < α ∧ μ ≤ ω } . {\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 C ν n ( α ) {\displaystyle C_{\nu }^{n}(\alpha )} with n < ω {\displaystyle n<\omega } i.e. C ν ( α ) = ⋃ n < ω C ν n ( α ) {\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 ψ ν ( α ) = min { γ ∣ γ ∉ C ν ( α ) } {\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:

C 0 0 ( α ) = { 0 } = { β ∣ β < 1 } , {\displaystyle C_{0}^{0}(\alpha )=\{0\}=\{\beta \mid \beta <1\},} C 0 ( 0 ) = { 0 } {\displaystyle C_{0}(0)=\{0\}} (since no functions ψ ( η < 0 ) {\displaystyle \psi (\eta <0)} and 0 + 0 = 0).

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

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

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

If α = ω {\displaystyle \alpha =\omega } then C 0 ( α ) = { 0 , ψ ( 0 ) = 1 , … , ψ ( 1 ) = ω , … , ψ ( 2 ) = ω 2 , … , ψ ( 3 ) = ω 3 , … } {\displaystyle C_{0}(\alpha )=\{0,\psi (0)=1,\ldots ,\psi (1)=\omega ,\ldots ,\psi (2)=\omega ^{2},\ldots ,\psi (3)=\omega ^{3},\ldots \}} and ψ 0 ( ω ) = ω ω {\displaystyle \psi _{0}(\omega )=\omega ^{\omega }} .

If α = Ω {\displaystyle \alpha =\Omega } then C 0 ( α ) = { 0 , ψ ( 0 ) = 1 , … , ψ ( 1 ) = ω , … , ψ ( ω ) = ω ω , … , ψ ( ω ω ) = ω ω ω , … } {\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 ψ 0 ( Ω ) = ε 0 {\displaystyle \psi _{0}(\Omega )=\varepsilon _{0}} – the smallest epsilon number i.e. first fixed point of α = ω α {\displaystyle \alpha =\omega ^{\alpha }} .

If α = Ω + 1 {\displaystyle \alpha =\Omega +1} then C 0 ( α ) = { 0 , 1 , … , ψ 0 ( Ω ) = ε 0 , … , ε 0 + ε 0 , … , ψ 1 ( 0 ) = Ω , … } {\displaystyle C_{0}(\alpha )=\{0,1,\ldots ,\psi _{0}(\Omega )=\varepsilon _{0},\ldots ,\varepsilon _{0}+\varepsilon _{0},\ldots ,\psi _{1}(0)=\Omega ,\ldots \}} and ψ 0 ( Ω + 1 ) = ε 0 ω = ω ε 0 + 1 {\displaystyle \psi _{0}(\Omega +1)=\varepsilon _{0}\omega =\omega ^{\varepsilon _{0}+1}} .

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

ψ 0 ( Ω 2 ) = ε ε ⋯ = ζ 0 {\displaystyle \psi _{0}(\Omega ^{2})=\varepsilon _{\varepsilon _{\cdots }}=\zeta _{0}} i.e. first fixed point of α = ε α {\displaystyle \alpha =\varepsilon _{\alpha }} ,

φ ( α , β ) = ψ 0 ( Ω α ( 1 + β ) ) {\displaystyle \varphi (\alpha ,\beta )=\psi _{0}(\Omega ^{\alpha }(1+\beta ))} , where φ {\displaystyle \varphi } denotes the Veblen function,

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

ψ 0 ( Ω Ω 2 ) = φ ( 1 , 0 , 0 , 0 ) {\displaystyle \psi _{0}(\Omega ^{\Omega ^{2}})=\varphi (1,0,0,0)} is the Ackermann ordinal, ψ 0 ( Ω Ω ω ) {\displaystyle \psi _{0}(\Omega ^{\Omega ^{\omega }})} is the small Veblen ordinal, ψ 0 ( Ω Ω Ω ) {\displaystyle \psi _{0}(\Omega ^{\Omega ^{\Omega }})} is the large Veblen ordinal, ψ 0 ( Ω ↑↑ ω ) = ψ 0 ( ε Ω + 1 ) = θ ( ε Ω + 1 , 0 ) . {\displaystyle \psi _{0}(\Omega \uparrow \uparrow \omega )=\psi _{0}(\varepsilon _{\Omega +1})=\theta (\varepsilon _{\Omega +1},0).}

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

C 1 0 ( 0 ) = { β ∣ β < Ω 1 } = { 0 , ψ ( 0 ) = 1 , 2 , … googol , … , ψ 0 ( 1 ) = ω , … , ψ 0 ( Ω ) = ε 0 , … {\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 }

… , ψ 0 ( Ω Ω ) = Γ 0 , … , ψ ( Ω Ω Ω + Ω 2 ) , … } {\displaystyle \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 ) {\displaystyle C_{1}(0)} includes all possible sums of all countable ordinals and ψ 1 ( 0 ) = Ω 1 {\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 ℵ 1 {\displaystyle \aleph _{1}} .

If α = 1 {\displaystyle \alpha =1} then C 1 ( α ) = { 0 , … , ψ 0 ( 0 ) = ω , … , ψ 1 ( 0 ) = Ω , … , Ω + ω , … , Ω + Ω , … } {\displaystyle C_{1}(\alpha )=\{0,\ldots ,\psi _{0}(0)=\omega ,\ldots ,\psi _{1}(0)=\Omega ,\ldots ,\Omega +\omega ,\ldots ,\Omega +\Omega ,\ldots \}} and ψ 1 ( 1 ) = Ω ω = ω Ω + 1 {\displaystyle \psi _{1}(1)=\Omega \omega =\omega ^{\Omega +1}} .

ψ 1 ( 2 ) = Ω ω 2 = ω Ω + 2 , {\displaystyle \psi _{1}(2)=\Omega \omega ^{2}=\omega ^{\Omega +2},} ψ 1 ( ψ 1 ( 0 ) ) = ψ 1 ( Ω ) = Ω 2 = ω Ω + Ω , {\displaystyle \psi _{1}(\psi _{1}(0))=\psi _{1}(\Omega )=\Omega ^{2}=\omega ^{\Omega +\Omega },} ψ 1 ( ψ 1 ( ψ 1 ( 0 ) ) ) = ω Ω + ω Ω + Ω = ω Ω ⋅ Ω = ( ω Ω ) Ω = Ω Ω , {\displaystyle \psi _{1}(\psi _{1}(\psi _{1}(0)))=\omega ^{\Omega +\omega ^{\Omega +\Omega }}=\omega ^{\Omega \cdot \Omega }=(\omega ^{\Omega })^{\Omega }=\Omega ^{\Omega },} ψ 1 4 ( 0 ) = Ω Ω Ω , {\displaystyle \psi _{1}^{4}(0)=\Omega ^{\Omega ^{\Omega }},} ψ 1 k + 1 ( 0 ) = Ω ↑↑ k {\displaystyle \psi _{1}^{k+1}(0)=\Omega \uparrow \uparrow k} where k {\displaystyle k} is a natural number, k ≥ 2 {\displaystyle k\geq 2} , ψ 1 ( Ω 2 ) = ψ 1 ω ( 0 ) = Ω ↑↑ ω = ε Ω + 1 . {\displaystyle \psi _{1}(\Omega _{2})=\psi _{1}^{\omega }(0)=\Omega \uparrow \uparrow \omega =\varepsilon _{\Omega +1}.}

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

and then

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

In the general case:

ψ 0 ( Ω ν + 1 ) = ψ 0 ( ψ ν ( Ω ν + 1 ) ) = ψ 0 ( ε Ω ν + 1 ) = θ ( ε Ω ν + 1 , 0 ) . {\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:

θ ( Ω ν , 0 ) = ψ 0 ( Ω ν Ω )  (for  1 ≤ ν ) < ω {\displaystyle \theta (\Omega _{\nu },0)=\psi _{0}(\Omega _{\nu }^{\Omega }){\text{ (for }}1\leq \nu )<\omega }

Ordinal notation

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

• 0 ∈ T ∧ 0 ∈ P T {\displaystyle 0\in T\land 0\in PT} ,
• ∀ ( v , a ) ∈ ( ω + 1 ) × T ( D v a ∈ T ∧ D v a ∈ P T ) {\displaystyle \forall (v,a)\in (\omega +1)\times T(D_{v}a\in T\land D_{v}a\in PT)} .
• ∀ ( a 0 , a 1 ) ∈ P T 2 ( ( a 0 , a 1 ) ∈ T ) {\displaystyle \forall (a_{0},a_{1})\in PT^{2}((a_{0},a_{1})\in T)} .
• ∃ s ( a 0 = s ) ∧ ( a 0 , a 1 ) ∈ T × P T → ( s , a 1 ) ∈ 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 T {\displaystyle T} is called a term, and an element of P T {\displaystyle PT} is called a principal term. By definition, T {\displaystyle T} is a recursive set and P T {\displaystyle PT} is a recursive subset of T {\displaystyle T} . Every term is either 0 {\displaystyle 0} , a principal term or a braced array of principal terms of length ≥ 2 {\displaystyle \geq 2} . We denote a ∈ P T {\displaystyle a\in PT} by ( a ) {\displaystyle (a)} . By convention, every term can be uniquely expressed as either 0 {\displaystyle 0} or a braced, non-empty array of principal terms. Since clauses 3 and 4 in the definition of T {\displaystyle T} and P T {\displaystyle PT} are applicable only to arrays of length ≥ 2 {\displaystyle \geq 2} , this convention does not cause serious ambiguity.

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

• b = 0 → a < b = ⊥ {\displaystyle b=0\rightarrow a<b=\bot }
• a = 0 → ( a < b ↔ b ≠ 0 ) {\displaystyle a=0\rightarrow (a<b\leftrightarrow b\neq 0)}
• If a ≠ 0 ∧ b ≠ 0 {\displaystyle a\neq 0\land b\neq 0} , then:
  • If a = D u a ′ ∧ b = D v b ′ {\displaystyle a=D_{u}a'\land b=D_{v}b'} for some ( ( u , a ′ ) , ( v , b ′ ) ) ∈ ( ( ω + 1 ) × T ) 2 {\displaystyle ((u,a'),(v,b'))\in ((\omega +1)\times T)^{2}} , then a < b {\displaystyle a<b} is true if either of the following are true:
    • u < v {\displaystyle u<v}
    • u = v ∧ a ′ < b ′ {\displaystyle u=v\land a'<b'}
  • If a = ( a 0 , . . . , a n ) ∧ b = ( b 0 , . . . , b m ) {\displaystyle a=(a_{0},...,a_{n})\land b=(b_{0},...,b_{m})} for some ( n , m ) ∈ N 2 ∧ 1 ≤ n + m {\displaystyle (n,m)\in \mathbb {N} ^{2}\land 1\leq n+m} , then a < b {\displaystyle a<b} is true if either of the following are true:
    • ∀ i ∈ N ∧ i ≤ n ( n < m ∧ a i = b i ) {\displaystyle \forall i\in \mathbb {N} \land i\leq n(n<m\land a_{i}=b_{i})}
    • ∃ k ∈ N ∀ i ∈ N ∧ i < k ( k ≤ m i n { n , m } ∧ a k < b k ∧ a i = b 1 ) {\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 T {\displaystyle T} . We abbreviate ( a < b ) ∨ ( a = b ) {\displaystyle (a<b)\lor (a=b)} as a ≤ b {\displaystyle a\leq b} . Although ≤ {\displaystyle \leq } itself is not a well-ordering, its restriction to a recursive subset O T ⊂ T {\displaystyle OT\subset T} , which will be described later, forms a well-ordering. In order to define O T {\displaystyle OT} , we define a subset G u a ⊂ T {\displaystyle G_{u}a\subset T} for each ( u , a ) ∈ ( ω + 1 ) × T {\displaystyle (u,a)\in (\omega +1)\times T} in the following way:

• a = 0 → G u a = ∅ {\displaystyle a=0\rightarrow G_{u}a=\varnothing }
• Suppose that a = D v a ′ {\displaystyle a=D_{v}a'} for some ( v , a ′ ) ∈ ( ω + 1 ) × T {\displaystyle (v,a')\in (\omega +1)\times T} , then:
  • u ≤ v → G u a = { a ′ } ∪ G u a ′ {\displaystyle u\leq v\rightarrow G_{u}a=\{a'\}\cup G_{u}a'}
  • u > v → G u a = ∅ {\displaystyle u>v\rightarrow G_{u}a=\varnothing }

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

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

• 0 ∈ O T {\displaystyle 0\in OT}
• For any ( v , a ) ∈ ( ω + 1 ) × T {\displaystyle (v,a)\in (\omega +1)\times T} , D v a ∈ O T {\displaystyle D_{v}a\in OT} is equivalent to a ∈ O T {\displaystyle a\in OT} and, for any a ′ ∈ G v a {\displaystyle a'\in G_{v}a} , a ′ < a {\displaystyle a'<a} .
• For any ( a i ) i = 0 k ∈ P T k + 1 {\displaystyle (a_{i})_{i=0}^{k}\in PT^{k+1}} , ( a 0 , . . . , a k ) ∈ O T {\displaystyle (a_{0},...,a_{k})\in OT} is equivalent to ( a i ) i = 0 k ∈ O T {\displaystyle (a_{i})_{i=0}^{k}\in OT} and a k ≤ . . . ≤ a 0 {\displaystyle a_{k}\leq ...\leq a_{0}} .

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

• a = 0 → o ( a ) = 0 {\displaystyle a=0\rightarrow o(a)=0}
• If a = D v a ′ {\displaystyle a=D_{v}a'} for some ( v , a ′ ) ∈ ( ω + 1 ) × O T {\displaystyle (v,a')\in (\omega +1)\times OT} , then o ( a ) = ψ v ( o ( a ′ ) ) {\displaystyle o(a)=\psi _{v}(o(a'))} .
• If a = ( a 0 , . . . , a k ) {\displaystyle a=(a_{0},...,a_{k})} for some ( a i ) i = 0 k ∈ ( O T ∩ P T ) k + 1 {\displaystyle (a_{i})_{i=0}^{k}\in (OT\cap PT)^{k+1}} with k ∈ N ∖ { 0 } {\displaystyle k\in \mathbb {N} \backslash \{0\}} , then o ( a ) = o ( a 0 ) # . . . # o ( a k ) {\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 O T {\displaystyle OT} .

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

• The map o {\displaystyle o} is an order-preserving bijective map with respect to < {\displaystyle <} and ∈ {\displaystyle \in } . In particular, o {\displaystyle o} is a recursive strict well-ordering on O T {\displaystyle OT} .
• For any a ∈ O T {\displaystyle a\in OT} satisfying a < D 1 0 {\displaystyle a<D_{1}0} , o ( a ) {\displaystyle o(a)} coincides with the ordinal type of < {\displaystyle <} restricted to the countable subset { x ∈ O T | x < a } {\displaystyle \{x\in OT\;|\;x<a\}} .
• The Takeuti-Feferman-Buchholz ordinal coincides with the ordinal type of < {\displaystyle <} restricted to the recursive subset { x ∈ O T | x < D 1 0 } {\displaystyle \{x\in OT\;|\;x<D_{1}0\}} .
• The ordinal type of ( O T , < ) {\displaystyle (OT,<)} is greater than the Takeuti-Feferman-Buchholz ordinal.
• For any v ∈ N ∖ { 0 } {\displaystyle v\in \mathbb {N} \;\backslash \;\{0\}} , the well-foundedness of < {\displaystyle <} restricted to the recursive subset { x ∈ O T | x < D 0 D v + 1 0 } {\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 I D v {\displaystyle {\mathsf {ID}}_{v}} .
• The well-foundedness of < {\displaystyle <} restricted to the recursive subset { x ∈ O T | x < D 0 D ω 0 } {\displaystyle \{x\in OT\;|\;x<D_{0}D_{\omega }0\}} in the same sense as above is not provable under Π 1 1 − C A 0 {\displaystyle \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 {\displaystyle o} . Namely, the set N F {\displaystyle NF} of predicates on ordinals in C 0 ( ε Ω ω + 1 ) {\displaystyle C_{0}(\varepsilon _{\Omega _{\omega }+1})} is defined in the following way:

• The predicate α = N F 0 {\displaystyle \alpha =_{NF}0} on an ordinal α ∈ C 0 ( ε Ω ω + 1 ) {\displaystyle \alpha \in C_{0}(\varepsilon _{\Omega _{\omega }+1})} defined as α = 0 {\displaystyle \alpha =0} belongs to N F {\displaystyle NF} .

• The predicate α 0 = N F ψ k 1 ( α 1 ) {\displaystyle \alpha _{0}=_{NF}\psi _{k_{1}}(\alpha _{1})}  on ordinals α 0 , α 1 ∈ C 0 ( ε Ω ω + 1 ) {\displaystyle \alpha _{0},\alpha _{1}\in C_{0}(\varepsilon _{\Omega _{\omega }+1})}  with k 1 = ω + 1 {\displaystyle k_{1}=\omega +1}  defined as α 0 = ψ k 1 ( α 1 ) {\displaystyle \alpha _{0}=\psi _{k_{1}}(\alpha _{1})}  and α 1 = C k 1 ( α 1 ) {\displaystyle \alpha _{1}=C_{k_{1}}(\alpha _{1})}  belongs to N F {\displaystyle NF} .
• The predicate α 0 = N F α 1 + . . . + α n {\displaystyle \alpha _{0}=_{NF}\alpha _{1}+...+\alpha _{n}} on ordinals α 0 , α 1 , . . . , α n ∈ C 0 ( ε Ω ω + 1 ) {\displaystyle \alpha _{0},\alpha _{1},...,\alpha _{n}\in C_{0}(\varepsilon _{\Omega _{\omega }+1})}  with an integer n > 1 {\displaystyle n>1}  defined as α 0 = α 1 + . . . + α n {\displaystyle \alpha _{0}=\alpha _{1}+...+\alpha _{n}} , α 1 ≥ . . . ≥ α n {\displaystyle \alpha _{1}\geq ...\geq \alpha _{n}} , and α 1 , . . . , α n ∈ A P {\displaystyle \alpha _{1},...,\alpha _{n}\in AP}  belongs to N F {\displaystyle NF} . Here + {\displaystyle +}  is a function symbol rather than an actual addition, and A P {\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 α 0 = N F ψ k 1 ( α 1 ) + . . . + ψ k n ( α n ) {\displaystyle \alpha _{0}=_{NF}\psi _{k_{1}}(\alpha _{1})+...+\psi _{k_{n}}(\alpha _{n})} on ordinals α 0 , α 1 , . . . , α n ∈ C 0 ( ε Ω ω + 1 ) {\displaystyle \alpha _{0},\alpha _{1},...,\alpha _{n}\in C_{0}(\varepsilon _{\Omega _{\omega }+1})}  with an integer n > 1 {\displaystyle n>1}  and k 1 , . . . , k n ∈ ω + 1 {\displaystyle k_{1},...,k_{n}\in \omega +1} defined as α 0 = ψ k 1 ( α 1 ) + . . . + ψ k n ( α n ) {\displaystyle \alpha _{0}=\psi _{k_{1}}(\alpha _{1})+...+\psi _{k_{n}}(\alpha _{n})} , ψ k 1 ( α 1 ) ≥ . . . ≥ ψ k n ( α n ) {\displaystyle \psi _{k_{1}}(\alpha _{1})\geq ...\geq \psi _{k_{n}}(\alpha _{n})} , and α 1 ∈ C k 1 ( α 1 ) , . . . , α n ∈ C k n ( α n ) ∈ A P {\displaystyle \alpha _{1}\in C_{k_{1}}(\alpha _{1}),...,\alpha _{n}\in C_{k_{n}}(\alpha _{n})\in AP}  belongs to N F {\displaystyle NF} .

We note that those two formulations are not equivalent. For example, ψ 0 ( Ω ) + 1 = N F ψ 0 ( ζ 1 ) + ψ 0 ( 0 ) {\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 ζ 1 ≠ C 0 ( ζ 1 ) {\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 ψ 0 ( Ω ) + 1 = ψ 0 ( ζ 1 ) + ψ 0 ( 0 ) {\displaystyle \psi _{0}(\Omega )+1=\psi _{0}(\zeta _{1})+\psi _{0}(0)} , ψ 0 ( ζ 1 ) , ψ 0 ( 0 ) ∈ A P {\displaystyle \psi _{0}(\zeta _{1}),\psi _{0}(0)\in AP} , and ψ 0 ( ζ 1 ) ≥ ψ 0 ( 0 ) {\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 C 0 ( ε Ω ω + 1 ) {\displaystyle C_{0}(\varepsilon _{\Omega _{\omega }+1})}  can be uniquely expressed in normal form for Buchholz's function.

References

1. Jäger, G (1984). "ρ-inaccessible ordinals, collapsing functions and a recursive notation system". Archiv für Mathematische Logik und Grundlagenforschung. 24 (1): 49–62. doi:10.1007/BF02007140. S2CID 38619369. /wiki/Doi_(identifier) ↩

2. Buchholz, W.; Schütte, K. (1983). "Ein Ordinalzahlensystem ftir die beweistheoretische Abgrenzung der H~-Separation und Bar-Induktion". Sitzungsberichte der Bayerischen Akademie der Wissenschaften, Math.-Naturw. Klasse. ↩

3. Buchholz, W. (1986). "A new system of proof-theoretic ordinal functions" (PDF). Annals of Pure and Applied Logic. 32: 195–207. doi:10.1016/0168-0072(86)90052-7. https://epub.ub.uni-muenchen.de/3841/1/3841.pdf ↩

4. Buchholz, W. (1986). "A new system of proof-theoretic ordinal functions" (PDF). Annals of Pure and Applied Logic. 32: 195–207. doi:10.1016/0168-0072(86)90052-7. https://epub.ub.uni-muenchen.de/3841/1/3841.pdf ↩

5. Buchholz, W. (1986). "A new system of proof-theoretic ordinal functions" (PDF). Annals of Pure and Applied Logic. 32: 195–207. doi:10.1016/0168-0072(86)90052-7. https://epub.ub.uni-muenchen.de/3841/1/3841.pdf ↩

6. Buchholz, W. (1986). "A new system of proof-theoretic ordinal functions" (PDF). Annals of Pure and Applied Logic. 32: 195–207. doi:10.1016/0168-0072(86)90052-7. https://epub.ub.uni-muenchen.de/3841/1/3841.pdf ↩

7. Buchholz, W. (1986). "A new system of proof-theoretic ordinal functions" (PDF). Annals of Pure and Applied Logic. 32: 195–207. doi:10.1016/0168-0072(86)90052-7. https://epub.ub.uni-muenchen.de/3841/1/3841.pdf ↩

8. Buchholz, W. (1986). "A new system of proof-theoretic ordinal functions" (PDF). Annals of Pure and Applied Logic. 32: 195–207. doi:10.1016/0168-0072(86)90052-7. https://epub.ub.uni-muenchen.de/3841/1/3841.pdf ↩

9. Buchholz, W. (1986). "A new system of proof-theoretic ordinal functions" (PDF). Annals of Pure and Applied Logic. 32: 195–207. doi:10.1016/0168-0072(86)90052-7. https://epub.ub.uni-muenchen.de/3841/1/3841.pdf ↩

10. Buchholz, W. (1986). "A new system of proof-theoretic ordinal functions" (PDF). Annals of Pure and Applied Logic. 32: 195–207. doi:10.1016/0168-0072(86)90052-7. https://epub.ub.uni-muenchen.de/3841/1/3841.pdf ↩