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

* $\psi_\nu(0)=\Omega_\nu,$
* $\psi_\nu(\alpha)\in P,$
* $\psi_\nu(\alpha+1) = \min\\text \alpha\in C_\nu(\alpha),$
* $\Omega_\nu\le\psi_\nu(\alpha)<\Omega_$
* $\psi_0(\alpha)=\omega^\alpha \text\alpha<\varepsilon_0,$
* $\psi_\nu(\alpha)=\omega^ \text \alpha<\varepsilon_ \text \nu\neq 0,$
* $\theta(\varepsilon_,0)=\psi(\varepsilon_) \text 0<\nu\le\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_(\beta_1)+\psi_(\beta_2)+\cdots+\psi_(\beta_k)$ where $\nu_i\in\mathbb N_0, k\in\mathbb N_, \beta_i\in C_(\beta_i)$ and $\psi_(\beta_1)\geq\psi_(\beta_2)\geq\cdots\geq\psi_(\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(\alpha)=\beta$ is a strictly increasing sequence $(\alpha$eta_ with length $\beta$ and with limit $\alpha$, where $\alpha$eta/math> is the $\eta$-th element of this sequence. If $\alpha$ is a successor ordinal then $\operatorname(\alpha)=1$ and the fundamental sequence has only one element \alpha \alpha-1. If $\alpha$ is a limit ordinal then $\operatorname(\alpha)\in\ \cup \$.

For nonzero ordinals $\alpha<\Omega_\omega$, written in normal form, fundamental sequences are defined as follows:

#If $\alpha=\psi_(\beta_1)+\psi_(\beta_2)+\cdots+\psi_(\beta_k)$ where $k\geq2$ then $\operatorname(\alpha)=\operatorname(\psi_(\beta_k))$ and $\alpha$eta\psi_(\beta_1)+\cdots+\psi_(\beta_)+(\psi_(\beta_k)eta,
#If $\alpha=\psi_(0)=1$, then $\operatorname(\alpha)=1$ and \alpha 0,
#If $\alpha=\psi_(0)$, then $\operatorname(\alpha)=\Omega_$ and $\alpha$eta\Omega_eta\eta,
#If $\alpha=\psi_(\beta+1)$ then $\operatorname(\alpha)=\omega$ and $\alpha$eta\psi_(\beta)\cdot \eta (and note: $\psi_\nu(0)=\Omega_\nu$),
#If $\alpha=\psi_(\beta)$ and $\operatorname(\beta)\in\\cup\$ then $\operatorname(\alpha)=\operatorname(\beta)$ and $\alpha$eta\psi_(\betaeta,
#If $\alpha=\psi_(\beta)$ and $\operatorname(\beta)\in\$ then $\operatorname(\alpha)=\omega$ and $\alpha$eta\psi_\nu(\beta gamma[\eta)_where_\left\{\begin{array}{lcr}_\gamma_\Omega_\mu_\\_\gamma[\eta+1.html" ;"title="eta.html" ;"title="gamma[\eta">gamma[\eta) where \left\{\begin{array}{lcr} \gamma \Omega_\mu \\ \gamma[\eta+1">eta.html" ;"title="gamma[\eta">gamma[\eta) where \left\{\begin{array}{lcr} \gamma \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'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\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

Ordinal numbers