Buchholz psi functions

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

Definition

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.

Properties

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

• [math]\displaystyle{ \psi_\nu(0)=\Omega_\nu, }[/math]
• [math]\displaystyle{ \psi_\nu(\alpha)\in P, }[/math]
• [math]\displaystyle{ \psi_\nu(\alpha+1) = \min\{\gamma\in P: \psi_\nu(\alpha)\lt \gamma\}\text{ if } \alpha\in C_\nu(\alpha), }[/math]
• [math]\displaystyle{ \Omega_\nu\le\psi_\nu(\alpha)\lt \Omega_{\nu+1} }[/math]
• [math]\displaystyle{ \psi_0(\alpha)=\omega^\alpha \text{ if }\alpha\lt \varepsilon_0, }[/math]
• [math]\displaystyle{ \psi_\nu(\alpha)=\omega^{\Omega_\nu+\alpha} \text{ if } \alpha\lt \varepsilon_{\Omega_\nu+1} \text{ and } \nu\neq 0, }[/math]
• [math]\displaystyle{ \theta(\varepsilon_{\Omega_\nu+1},0)=\psi(\varepsilon_{\Omega_\nu+1}) \text{ for } 0\lt \nu\le\omega. }[/math]

Fundamental sequences and normal form for Buchholz's function

Normal form

The normal form for 0 is 0. If [math]\displaystyle{ \alpha }[/math] is a nonzero ordinal number [math]\displaystyle{ \alpha\lt \Omega_\omega }[/math] then the normal form for [math]\displaystyle{ \alpha }[/math] is [math]\displaystyle{ \alpha=\psi_{\nu_1}(\beta_1)+\psi_{\nu_2}(\beta_2)+\cdots+\psi_{\nu_k}(\beta_k) }[/math] where [math]\displaystyle{ \nu_i\in\mathbb N_0, k\in\mathbb N_{\gt 0}, \beta_i\in C_{\nu_i}(\beta_i) }[/math] and [math]\displaystyle{ \psi_{\nu_1}(\beta_1)\geq\psi_{\nu_2}(\beta_2)\geq\cdots\geq\psi_{\nu_k}(\beta_k) }[/math] and each [math]\displaystyle{ \beta_i }[/math] is also written in normal form.

Fundamental sequences

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

For nonzero ordinals [math]\displaystyle{ \alpha\lt \Omega_\omega }[/math], written in normal form, fundamental sequences are defined as follows:

1. If [math]\displaystyle{ \alpha=\psi_{\nu_1}(\beta_1)+\psi_{\nu_2}(\beta_2)+\cdots+\psi_{\nu_k}(\beta_k) }[/math] where [math]\displaystyle{ k\geq2 }[/math] then [math]\displaystyle{ \operatorname{cof}(\alpha)=\operatorname{cof}(\psi_{\nu_k}(\beta_k)) }[/math] and [math]\displaystyle{ \alpha[\eta]=\psi_{\nu_1}(\beta_1)+\cdots+\psi_{\nu_{k-1}}(\beta_{k-1})+(\psi_{\nu_k}(\beta_k)[\eta]), }[/math]
2. If [math]\displaystyle{ \alpha=\psi_{0}(0)=1 }[/math], then [math]\displaystyle{ \operatorname{cof}(\alpha)=1 }[/math] and [math]\displaystyle{ \alpha[0]=0 }[/math],
3. If [math]\displaystyle{ \alpha=\psi_{\nu+1}(0) }[/math], then [math]\displaystyle{ \operatorname{cof}(\alpha)=\Omega_{\nu+1} }[/math] and [math]\displaystyle{ \alpha[\eta]=\Omega_{\nu+1}[\eta]=\eta }[/math],
4. If [math]\displaystyle{ \alpha=\psi_{\nu}(\beta+1) }[/math] then [math]\displaystyle{ \operatorname{cof}(\alpha)=\omega }[/math] and [math]\displaystyle{ \alpha[\eta]=\psi_{\nu}(\beta)\cdot \eta }[/math] (and note: [math]\displaystyle{ \psi_\nu(0)=\Omega_\nu }[/math]),
5. If [math]\displaystyle{ \alpha=\psi_{\nu}(\beta) }[/math] and [math]\displaystyle{ \operatorname{cof}(\beta)\in\{\omega\}\cup\{\Omega_{\mu+1}\mid\mu\lt \nu\} }[/math] then [math]\displaystyle{ \operatorname{cof}(\alpha)=\operatorname{cof}(\beta) }[/math] and [math]\displaystyle{ \alpha[\eta]=\psi_{\nu}(\beta[\eta]) }[/math],
6. If [math]\displaystyle{ \alpha=\psi_{\nu}(\beta) }[/math] and [math]\displaystyle{ \operatorname{cof}(\beta)\in\{\Omega_{\mu+1}\mid\mu\geq\nu\} }[/math] then [math]\displaystyle{ \operatorname{cof}(\alpha)=\omega }[/math] and [math]\displaystyle{ \alpha[\eta]=\psi_\nu(\beta[\gamma[\eta]]) }[/math] where [math]\displaystyle{ \left\{\begin{array}{lcr} \gamma[0]=\Omega_\mu \\ \gamma[\eta+1]=\psi_\mu(\beta[\gamma[\eta]])\\ \end{array}\right. }[/math].

Explanation

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

The condition [math]\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\} }[/math] means that set [math]\displaystyle{ C_\nu^{n+1}(\alpha) }[/math] includes:

• all ordinals from previous set [math]\displaystyle{ C_\nu^n(\alpha) }[/math],
• all ordinals that can be obtained by summation the additively principal ordinals from previous set [math]\displaystyle{ C_\nu^n(\alpha) }[/math],
• all ordinals that can be obtained by applying ordinals less than [math]\displaystyle{ \alpha }[/math] from the previous set [math]\displaystyle{ C_\nu^n(\alpha) }[/math] as arguments of functions [math]\displaystyle{ \psi_\mu }[/math], where [math]\displaystyle{ \mu\le\omega }[/math].

That is why we can rewrite this condition as:

[math]\displaystyle{ C_\nu^{n+1}(\alpha) = \{\beta+\gamma,\psi_\mu(\eta)\mid\beta, \gamma,\eta\in C_\nu^n(\alpha)\wedge\eta\lt \alpha \wedge \mu \leq \omega\}. }[/math]

Thus union of all sets [math]\displaystyle{ C_\nu^n (\alpha) }[/math] with [math]\displaystyle{ n\lt \omega }[/math] i.e. [math]\displaystyle{ C_\nu(\alpha) = \bigcup_{n \lt \omega} C_\nu^n (\alpha) }[/math] denotes the set of all ordinals which can be generated from ordinals [math]\displaystyle{ \lt \aleph_\nu }[/math] by the functions + (addition) and [math]\displaystyle{ \psi_{\mu}(\eta) }[/math], where [math]\displaystyle{ \mu\le\omega }[/math] and [math]\displaystyle{ \eta\lt \alpha }[/math].

Then [math]\displaystyle{ \psi_\nu(\alpha) = \min\{\gamma \mid \gamma \not\in C_\nu(\alpha)\} }[/math] is the smallest ordinal that does not belong to this set.

Examples

Consider the following examples:

[math]\displaystyle{ C_0^0(\alpha)=\{0\} =\{\beta\mid\beta\lt 1\}, }[/math]

[math]\displaystyle{ C_0(0)=\{0\} }[/math] (since no functions [math]\displaystyle{ \psi(\eta\lt 0) }[/math] and 0 + 0 = 0).

Then [math]\displaystyle{ \psi_0(0)=1 }[/math].

[math]\displaystyle{ C_0(1) }[/math] includes [math]\displaystyle{ \psi_0(0)=1 }[/math] and all possible sums of natural numbers and therefore [math]\displaystyle{ \psi_0(1)=\omega }[/math] – first transfinite ordinal, which is greater than all natural numbers by its definition.

[math]\displaystyle{ C_0(2) }[/math] includes [math]\displaystyle{ \psi_0(0)=1, \psi_0(1)=\omega }[/math] and all possible sums of them and therefore [math]\displaystyle{ \psi_0(2)=\omega^2 }[/math].

If [math]\displaystyle{ \alpha=\omega }[/math] then [math]\displaystyle{ C_0(\alpha)=\{0,\psi(0)=1,\ldots,\psi(1)=\omega,\ldots,\psi(2)=\omega^2,\ldots,\psi(3)=\omega^3, \ldots\} }[/math] and [math]\displaystyle{ \psi_0(\omega)=\omega^\omega }[/math].

If [math]\displaystyle{ \alpha=\Omega }[/math] then [math]\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\} }[/math] and [math]\displaystyle{ \psi_0(\Omega)=\varepsilon_0 }[/math] – the smallest epsilon number i.e. first fixed point of [math]\displaystyle{ \alpha=\omega^\alpha }[/math].

If [math]\displaystyle{ \alpha=\Omega+1 }[/math] then [math]\displaystyle{ C_0(\alpha)=\{0,1,\ldots,\psi_0(\Omega)=\varepsilon_0,\ldots,\varepsilon_0+\varepsilon_0,\ldots,\psi_1(0)=\Omega,\ldots\} }[/math] and [math]\displaystyle{ \psi_0(\Omega+1)=\varepsilon_0\omega=\omega^{\varepsilon_0+1} }[/math].

[math]\displaystyle{ \psi_0(\Omega2)=\varepsilon_1 }[/math] the second epsilon number,

[math]\displaystyle{ \psi_0(\Omega^2) = \varepsilon_{\varepsilon_\cdots}=\zeta_0 }[/math] i.e. first fixed point of [math]\displaystyle{ \alpha=\varepsilon_\alpha }[/math],

[math]\displaystyle{ \varphi(\alpha,\beta)=\psi_0(\Omega^\alpha(1+\beta)) }[/math], where [math]\displaystyle{ \varphi }[/math] denotes the Veblen's function,

[math]\displaystyle{ \psi_0(\Omega^\Omega)=\Gamma_0=\varphi(1,0,0)=\theta(\Omega,0) }[/math], where [math]\displaystyle{ \theta }[/math] denotes the Feferman's function,

[math]\displaystyle{ \psi_0(\Omega^{\Omega^2})=\varphi(1,0,0,0) }[/math] is the Ackermann ordinal,

[math]\displaystyle{ \psi_0(\Omega^{\Omega^\omega}) }[/math] is the small Veblen ordinal,

[math]\displaystyle{ \psi_0(\Omega^{\Omega^\Omega}) }[/math] is the large Veblen ordinal,

[math]\displaystyle{ \psi_0(\Omega\uparrow\uparrow\omega) =\psi_0(\varepsilon_{\Omega+1}) = \theta(\varepsilon_{\Omega+1},0). }[/math]

Now let's research how [math]\displaystyle{ \psi_1 }[/math] works:

[math]\displaystyle{ C_1^0(0)=\{\beta\mid\beta\lt \Omega_1\}=\{0,\psi(0) = 1,2, \ldots \text{googol}, \ldots, \psi_0(1)=\omega, \ldots, \psi_0(\Omega) =\varepsilon_0,\ldots }[/math]

[math]\displaystyle{ \ldots,\psi_0(\Omega^\Omega)=\Gamma_0,\ldots,\psi(\Omega^{\Omega^\Omega+\Omega^2}),\ldots\} }[/math] i.e. includes all countable ordinals. And therefore [math]\displaystyle{ C_1(0) }[/math] includes all possible sums of all countable ordinals and [math]\displaystyle{ \psi_1(0)=\Omega_1 }[/math] first uncountable ordinal which is greater than all countable ordinal by its definition i.e. smallest number with cardinality [math]\displaystyle{ \aleph_1 }[/math].

If [math]\displaystyle{ \alpha=1 }[/math] then [math]\displaystyle{ C_1(\alpha)=\{0,\ldots,\psi_0(0) = \omega, \ldots, \psi_1(0) = \Omega,\ldots,\Omega+\omega,\ldots,\Omega+\Omega,\ldots\} }[/math] and [math]\displaystyle{ \psi_1(1)=\Omega\omega=\omega^{\Omega+1} }[/math].

[math]\displaystyle{ \psi_1(2)=\Omega\omega^2=\omega^{\Omega+2}, }[/math]

[math]\displaystyle{ \psi_1(\psi_1(0))=\psi_1(\Omega)=\Omega^2=\omega^{\Omega+\Omega}, }[/math]

[math]\displaystyle{ \psi_1(\psi_1(\psi_1(0))) =\omega^{\Omega+\omega^{\Omega+\Omega}} = \omega^{\Omega\cdot\Omega} = (\omega^{\Omega})^\Omega=\Omega^\Omega, }[/math]

[math]\displaystyle{ \psi_1^4(0)=\Omega^{\Omega^\Omega}, }[/math]

[math]\displaystyle{ \psi_1^{k+1}(0)=\Omega\uparrow\uparrow k }[/math] where [math]\displaystyle{ k }[/math] is a natural number, [math]\displaystyle{ k \geq 2 }[/math],

[math]\displaystyle{ \psi_1(\Omega_2) = \psi_1^\omega(0) = \Omega \uparrow\uparrow \omega = \varepsilon_{\Omega+1}. }[/math]

For case [math]\displaystyle{ \psi(\psi_2(0))=\psi(\Omega_2) }[/math] the set [math]\displaystyle{ C_0(\Omega_2) }[/math] includes functions [math]\displaystyle{ \psi_0 }[/math] with all arguments less than [math]\displaystyle{ \Omega_2 }[/math] i.e. such arguments as [math]\displaystyle{ 0, \psi_1(0), \psi_1(\psi_1(0)), \psi_1^3(0),\ldots, \psi_1^\omega(0) }[/math]

and then

[math]\displaystyle{ \psi_0(\Omega_2) = \psi_0(\psi_1(\Omega_2)) = \psi_0(\varepsilon_{\Omega+1}). }[/math]

In the general case:

[math]\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). }[/math]

We also can write:

[math]\displaystyle{ \theta(\Omega_\nu,0)=\psi_0(\Omega_\nu^\Omega) \text{ (for } 1\le\nu)\lt \omega }[/math]

Ordinal notation

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

• [math]\displaystyle{ 0 \in T \and 0 \in PT }[/math],
• [math]\displaystyle{ \forall (v, a) \in (\omega + 1) \times T( D_va \in T \and D_va \in PT) }[/math].
• [math]\displaystyle{ \forall (a_0, a_1) \in PT^2((a_0, a_1) \in T) }[/math].
• [math]\displaystyle{ \exists s (a_0 = s) \and (a_0, a_1) \in T \times PT \rightarrow (s, a_1) \in T }[/math].

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

We then define a binary relation [math]\displaystyle{ a \lt b }[/math] on [math]\displaystyle{ T }[/math] in the following way:

• [math]\displaystyle{ b = 0 \rightarrow a \lt b = \bot }[/math]
• [math]\displaystyle{ a = 0 \rightarrow (a \lt b \leftrightarrow b \neq 0) }[/math]
• If [math]\displaystyle{ a \neq 0 \and b \neq 0 }[/math], then:
  • If [math]\displaystyle{ a = D_ua' \and b = D_vb' }[/math] for some [math]\displaystyle{ ((u, a'), (v, b')) \in ((\omega + 1) \times T)^2 }[/math], then [math]\displaystyle{ a \lt b }[/math] is true if either of the following are true:
    • [math]\displaystyle{ u \lt v }[/math]
    • [math]\displaystyle{ u = v \and a' \lt b' }[/math]
  • If [math]\displaystyle{ a = (a_0, ..., a_n) \and b = (b_0, ..., b_m) }[/math] for some [math]\displaystyle{ (n, m) \in \N^2 \and 1 \leq n + m }[/math], then [math]\displaystyle{ a \lt b }[/math] is true if either of the following are true:
    • [math]\displaystyle{ \forall i \in \N \and i \leq n(n \lt m \and a_i = b_i) }[/math]
    • [math]\displaystyle{ \exists k \in \N\forall i \in \N \and i \lt k(k \leq min\{n, m\} \and a_k \lt b_k \and a_i = b_1) }[/math]

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

• [math]\displaystyle{ a = 0 \rightarrow G_ua = \varnothing }[/math]
• Suppose that [math]\displaystyle{ a = D_va' }[/math] for some [math]\displaystyle{ (v, a') \in (\omega + 1) \times T }[/math], then:
  • [math]\displaystyle{ u \leq v \rightarrow G_ua = \{a'\} \cup G_ua' }[/math]
  • [math]\displaystyle{ u \gt v \rightarrow G_ua = \varnothing }[/math]

• If [math]\displaystyle{ a = (a_0, ..., a_k) }[/math] for some [math]\displaystyle{ (a_i)_{i=0}^k \in PT^{k + 1} }[/math] for some [math]\displaystyle{ k \in \N \backslash \{0\}, G_ua = \bigcup_{i=0}^k G_ua_i }[/math].

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

• [math]\displaystyle{ 0 \in OT }[/math]
• For any [math]\displaystyle{ (v, a) \in (\omega + 1) \times T }[/math], [math]\displaystyle{ D_va \in OT }[/math] is equivalent to [math]\displaystyle{ a \in OT }[/math] and, for any [math]\displaystyle{ a' \in G_va }[/math], [math]\displaystyle{ a' \lt a }[/math].
• For any [math]\displaystyle{ (a_i)_{i=0}^k \in PT^{k + 1} }[/math], [math]\displaystyle{ (a_0, ..., a_k) \in OT }[/math] is equivalent to [math]\displaystyle{ (a_i)_{i=0}^k \in OT }[/math] and [math]\displaystyle{ a_k \leq ... \leq a_0 }[/math].

[math]\displaystyle{ OT }[/math] is a recursive subset of [math]\displaystyle{ T }[/math], and an element of [math]\displaystyle{ OT }[/math] is called an ordinal term. We can then define a map [math]\displaystyle{ o: OT \rightarrow C_0(\varepsilon_{\Omega_\omega+1}) }[/math] in the following way:

• [math]\displaystyle{ a = 0 \rightarrow o(a) = 0 }[/math]
• If [math]\displaystyle{ a = D_va' }[/math] for some [math]\displaystyle{ (v, a') \in (\omega + 1) \times OT }[/math], then [math]\displaystyle{ o(a) = \psi_v(o(a')) }[/math].
• If [math]\displaystyle{ a = (a_0, ..., a_k) }[/math] for some [math]\displaystyle{ (a_i)_{i=0}^k \in (OT \cap PT)^{k+1} }[/math] with [math]\displaystyle{ k \in \N \backslash \{0\} }[/math], then [math]\displaystyle{ o(a) = o(a_0) \# ... \# o(a_k) }[/math], where [math]\displaystyle{ \# }[/math] denotes the descending sum of ordinals, which coincides with the usual addition by the definition of [math]\displaystyle{ OT }[/math].

Buchholz verified the following properties of [math]\displaystyle{ o }[/math]:

• The map [math]\displaystyle{ o }[/math] is an order-preserving bijective map with respect to [math]\displaystyle{ \lt }[/math] and [math]\displaystyle{ \in }[/math]. In particular, [math]\displaystyle{ o }[/math] is a recursive strict well-ordering on [math]\displaystyle{ OT }[/math].
• For any [math]\displaystyle{ a \in OT }[/math] satisfying [math]\displaystyle{ a \lt D_10 }[/math], [math]\displaystyle{ o(a) }[/math] coincides with the ordinal type of [math]\displaystyle{ \lt }[/math] restricted to the countable subset [math]\displaystyle{ \{x \in OT \; | \; x \lt a\} }[/math].
• The Takeuti-Feferman-Buchholz ordinal coincides with the ordinal type of [math]\displaystyle{ \lt }[/math] restricted to the recursive subset [math]\displaystyle{ \{x \in OT \; | \; x \lt D_10\} }[/math].
• The ordinal type of [math]\displaystyle{ (OT, \lt ) }[/math] is greater than the Takeuti-Feferman-Buchholz ordinal.
• For any [math]\displaystyle{ v \in \N \; \backslash \; \{0\} }[/math], the well-foundedness of [math]\displaystyle{ \lt }[/math] restricted to the recursive subset [math]\displaystyle{ \{x \in OT \; | \; x \lt D_0D_{v+1}0\} }[/math] in the sense of the non-existence of a primitive recursive infinite descending sequence is not provable under [math]\displaystyle{ \mathsf{ID}_v }[/math].
• The well-foundedness of [math]\displaystyle{ \lt }[/math] restricted to the recursive subset[math]\displaystyle{ \{x \in OT \; | \; x \lt D_0D_\omega0\} }[/math] in the same sense as above is not provable under [math]\displaystyle{ \Pi^1_1 - CA_0 }[/math].

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 [math]\displaystyle{ o }[/math]. Namely, the set [math]\displaystyle{ NF }[/math] of predicates on ordinals in [math]\displaystyle{ C_0(\varepsilon_{\Omega_\omega + 1}) }[/math] is defined in the following way:

• The predicate [math]\displaystyle{ \alpha = _{NF}0 }[/math] on an ordinal [math]\displaystyle{ \alpha \in C_0(\varepsilon_{\Omega_\omega + 1}) }[/math] defined as [math]\displaystyle{ \alpha = 0 }[/math] belongs to [math]\displaystyle{ NF }[/math].

• The predicate [math]\displaystyle{ \alpha_0 = _{NF}\psi_{k_1}(\alpha_1) }[/math] on ordinals [math]\displaystyle{ \alpha_0, \alpha_1 \in C_0(\varepsilon_{\Omega_\omega + 1}) }[/math] with [math]\displaystyle{ k_1 = \omega + 1 }[/math] defined as [math]\displaystyle{ \alpha_0 = \psi_{k_1}(\alpha_1) }[/math] and [math]\displaystyle{ \alpha_1 = C_{k_1}(\alpha_1) }[/math] belongs to [math]\displaystyle{ NF }[/math].
• The predicate [math]\displaystyle{ \alpha_0 = _{NF}\alpha_1 + ... + \alpha_n }[/math] on ordinals [math]\displaystyle{ \alpha_0, \alpha_1, ..., \alpha_n \in C_0(\varepsilon_{\Omega_\omega + 1}) }[/math] with an integer [math]\displaystyle{ n \gt 1 }[/math] defined as [math]\displaystyle{ \alpha_0 = \alpha_1 + ... + \alpha_n }[/math], [math]\displaystyle{ \alpha_1 \geq ... \geq \alpha_n }[/math], and [math]\displaystyle{ \alpha_1, ..., \alpha_n \in AP }[/math] belongs to [math]\displaystyle{ NF }[/math]. Here [math]\displaystyle{ + }[/math] is a function symbol rather than an actual addition, and [math]\displaystyle{ AP }[/math] 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 [math]\displaystyle{ \alpha_0 = _{NF}\psi_{k_1}(\alpha_1) + ... + \psi_{k_n}(\alpha_n) }[/math] on ordinals [math]\displaystyle{ \alpha_0, \alpha_1, ..., \alpha_n \in C_0(\varepsilon_{\Omega_\omega + 1}) }[/math] with an integer [math]\displaystyle{ n \gt 1 }[/math] and [math]\displaystyle{ k_1, ..., k_n \in \omega + 1 }[/math] defined as [math]\displaystyle{ \alpha_0 = \psi_{k_1}(\alpha_1) + ... + \psi_{k_n}(\alpha_n) }[/math], [math]\displaystyle{ \psi_{k_1}(\alpha_1) \geq ... \geq \psi_{k_n}(\alpha_n) }[/math], and [math]\displaystyle{ \alpha_1 \in C_{k_1}(\alpha_1), ..., \alpha_n \in C_{k_n}(\alpha_n) \in AP }[/math] belongs to [math]\displaystyle{ NF }[/math].

We note that those two formulations are not equivalent. For example, [math]\displaystyle{ \psi_0(\Omega) + 1 = _{NF} \psi_0(\zeta_1) + \psi_0(0) }[/math] is a valid formula which is false with respect to the second formulation because of [math]\displaystyle{ \zeta_1 \neq C_0(\zeta_1) }[/math], while it is a valid formula which is true with respect to the first formulation because of [math]\displaystyle{ \psi_0(\Omega) + 1 = \psi_0(\zeta_1) + \psi_0(0) }[/math], [math]\displaystyle{ \psi_0(\zeta_1), \psi_0(0) \in AP }[/math], and [math]\displaystyle{ \psi_0(\zeta_1) \geq \psi_0(0) }[/math]. In this way, the notion of normal form heavily depends on the context. In both formulations, every ordinal in [math]\displaystyle{ C_0(\varepsilon_{\Omega_\omega + 1}) }[/math] can be uniquely expressed in normal form for Buchholz's function.