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{{huh|date=December 2020}} as those. Later on this approach was extended by Jäger{{cite journal|first=G|last=Jäger|title= ρ-inaccessible ordinals, collapsing functions and a recursive notation system|journal= Archiv für Mathematische Logik und Grundlagenforschung| volume = 24| issue = 1| date =1984| pages = 49–62|doi=10.1007/BF02007140|s2cid=38619369}} and Schütte.{{cite journal|first1=W.|last1=Buchholz| last2 = Schütte| first2 = K.| title = Ein Ordinalzahlensystem ftir die beweistheoretische Abgrenzung der H~-Separation und Bar-Induktion|journal=Sitzungsberichte der Bayerischen Akademie der Wissenschaften, Math.-Naturw. Klasse| date = 1983}}

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 $P$ be the class of additively principal ordinals. Buchholz showed following properties of this functions:

$\psi_\nu(0)=\Omega_\nu,$ {{Cite journal |last=Buchholz |first=W. |date=1986 |title=A new system of proof-theoretic ordinal functions |journal=Annals of Pure and Applied Logic |language=en |volume=32 |pages=195–207 |doi=10.1016/0168-0072(86)90052-7|doi-access=free |url=https://epub.ub.uni-muenchen.de/3841/1/3841.pdf }}{{rp|p=197}}
$\psi_\nu(\alpha)\in P,$ {{rp|p=197}}
$\psi_\nu(\alpha+1) = \min\{\gamma\in P: \psi_\nu(\alpha)<\gamma\}\text{ if } \alpha\in C_\nu(\alpha),$ {{rp|p=199}}
$\Omega_\nu\le\psi_\nu(\alpha)<\Omega_{\nu+1}$ {{rp|p=197}}
$\psi_0(\alpha)=\omega^\alpha \text{ if }\alpha<\varepsilon_0,$ {{rp|p=199}}
$\psi_\nu(\alpha)=\omega^{\Omega_\nu+\alpha} \text{ if } \alpha<\varepsilon_{\Omega_\nu+1} \text{ and } \nu\neq 0,$ {{rp|p=199}}
$\theta(\varepsilon_{\Omega_\nu+1},0)=\psi(\varepsilon_{\Omega_\nu+1}) \text{ for } 0<\nu\le\omega.$ {{rp|p=206}}

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:

If $\alpha=\psi_{\nu_1}(\beta_1)+\psi_{\nu_2}(\beta_2)+\cdots+\psi_{\nu_k}(\beta_k)$ where $k\geq2$ 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]),$
If $\alpha=\psi_{0}(0)=1$ , then $\operatorname{cof}(\alpha)=1$ and $\alpha[0]=0$ ,
If $\alpha=\psi_{\nu+1}(0)$ , then $\operatorname{cof}(\alpha)=\Omega_{\nu+1}$ and $\alpha[\eta]=\Omega_{\nu+1}[\eta]=\eta$ ,
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$ ),
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])$ ,
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\le\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\le\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(\Omega2)=\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 function,

$\psi_0(\Omega^\Omega)=\Gamma_0=\varphi(1,0,0)=\theta(\Omega,0)$ , where $\theta$ denotes the Feferman's function and $\Gamma_0$ is the Feferman–Schütte ordinal,

: $\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\le\nu)<\omega$

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 \and 0 \in PT$ ,
$\forall (v, a) \in (\omega + 1) \times T( D_va \in T \and D_va \in PT)$ .
$\forall (a_0, a_1) \in PT^2((a_0, a_1) \in T)$ .
$\exists s (a_0 = s) \and (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 \and b \neq 0$ , then:
If $a = D_ua' \and b = D_vb'$ 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 \and a' < b'$
If $a = (a_0, ..., a_n) \and b = (b_0, ..., b_m)$ for some $(n, m) \in \N^2 \and 1 \leq n + m$ , then $a < b$ is true if either of the following are true:
$\forall i \in \N \and i \leq n(n < m \and a_i = b_i)$
$\exists k \in \N\forall i \in \N \and i < k(k \leq min\{n, m\} \and a_k < b_k \and a_i = b_1)$

$<$ is a recursive strict total ordering on $T$ . We abbreviate $(a < b) \or (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_ua \subset T$ for each $(u, a) \in (\omega + 1) \times T$ in the following way:

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

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

$b \in G_ua$ 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_va \in OT$ is equivalent to $a \in OT$ and, for any $a' \in G_va$ , $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_va'$ 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 \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_10$ , $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_10\}$ .
The ordinal type of $(OT, <)$ is greater than the Takeuti-Feferman-Buchholz ordinal.
For any $v \in \N \; \backslash \; \{0\}$ , the well-foundedness of $<$ restricted to the recursive subset $\{x \in OT \; | \; x < D_0D_{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_0D_\omega0\}$ 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 principal 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.

References

Category:Ordinal numbers