How to compare values of Buchholz functions?

64 Views Asked by At

https://en.m.wikipedia.org/wiki/Buchholz_psi_functions

Is there a simple method to compare values of Buchholz functions? Assuming that we have two ordinals represented using addition and $\psi_\alpha$ functions, it is easy to see that the main non-trivial case is the comparison of two values of the same psi function, because we have to determine whether the values are equal (e.g. $\psi_0(\psi_1(0))$ and $\psi_0(\psi_0(\psi_1(0)))$ are both equal to $\varepsilon_0$). Is there a simple way to do it?

1

There are 1 best solutions below

0
On

The definition of Buchholz's psi function is given as

\begin{align}C_\nu^0(\alpha)&=\Omega_\nu,\\C_\nu^{n+1}(\alpha)&=C_\nu^n(\alpha)\cup\{\gamma~|~P(\gamma)\subseteq C_\nu^n(\alpha)\}\\&\hphantom{={}}{}\cup\{\psi_\mu(\xi)~|~\xi\in\alpha\cap C_\nu^n(\alpha)\land\xi\in C_\mu(\xi)\land\mu\le\omega\},\\C_\nu(\alpha)&=\bigcup_{n<\omega}C_\nu^n(\alpha),\\\psi_\nu(\alpha)&=\min\{\gamma~|~\gamma\notin C_\nu(\alpha)\},\end{align}

where

$$\Omega_\nu=\begin{cases}1,&\nu=0\\\aleph_\nu,&\nu>0\end{cases}$$

and $P(\gamma)$ is the set of powers of $\omega$ which appear in $\gamma$'s Cantor normal form.

The first inequality of interest is a fairly straightforward one:

$$\Omega_\nu\le\psi_\nu(\alpha)<\Omega_{\nu+1}\tag1$$

which follows from the fact that $C_\nu(\alpha)\supseteq C_\nu^0(\alpha)=\Omega_\nu$ which gives the lower bound, and the fact that the cofinality of $\psi_\nu(\alpha)$ is less than $\Omega_{\nu+1}$, which inductively gives the upper bound.

The second inequality of interest is also straightforward and probably of more interest to you:

$$\psi_\nu(\alpha)\le\psi_\nu(\beta)\quad\forall\alpha<\beta\tag2$$

The issue is determining when this is an equality or strict inequality. To do this, focus on the third line of the definition:

$$\{\psi_\mu(\xi)~|~\xi\in\alpha\cap C_\nu^n(\alpha)\land\xi\in C_\mu(\xi)\land\mu\le\omega\}$$

While somewhat convoluted, one could word this as

The set of $\psi_\mu(\xi)$ for every $\xi$ we can construct (less than $\alpha$ to avoid ill-defined recursion), and every $\mu\le\omega$.

By "construct", I mean that $\xi$ must be an element of both $C$'s.

Using this, we can deduce things such as $\psi_0(\psi_1(0))=\psi_0(\psi_0(\psi_1(0)))$ fairly easily. The key is to look at the function's arguments, and the arguments of the function's inside.

It is easy to see that we can, in fact, construct the argument of $\psi_0(\psi_1(0))$. We can construct $0$, and thus we can construct $\psi_1(0)$.

However, we cannot construct the argument of $\psi_0(\psi_0(\psi_1(0)))$. While it is the case that we can construct $0$, and thus $\psi_1(0)$, we cannot construct $\psi_0(\psi_1(0)))$. To see why, we apply $(1)$ to get

$$\psi_0(\psi_1(0))<\Omega_1=\psi_1(0)$$

This means we cannot include $\psi_\mu(\psi_1(0))$ since this would be recursively defining our function in terms of itself on a larger argument.

Whenever this occurs, Buchholz's function becomes constant until the next constructable argument. In this case, the smallest $\psi_\nu(\alpha)>\psi_0(\psi_1(0))$ with $\alpha$ constructable is $\psi_1(0)$ itself, hence we have

$$\psi_0(\psi_0(\psi_1(0)))=\psi_0(\psi_1(0))$$

As another example, consider $\psi_0(\psi_3(\psi_5(0))+\psi_2(0))$. The $\psi_3$ has an argument that is too large, and $\psi_4(0)$ is the smallest argument that is larger than the current argument while also being constructable. Hence we have

$$\psi_0(\psi_3(\psi_5(0))+\psi_2(0))=\psi_0(\psi_4(0))$$

This gives us the improved $(2)$:

$$\psi_\nu(\alpha)<\psi_\nu(\beta)\tag{2.1}$$

whenever $\alpha<\beta$ and $\alpha$ is constructable, and

$$\psi_\nu(\alpha)=\psi_\nu(\beta)=\psi_\nu(\delta)\tag{2.2}$$

whenever $\alpha$ and $\beta$ are not constructable and $\delta$ is the minimum larger argument that is constructable.

Using these, it is easy to compare expressions written solely in terms of $\psi_\nu$, $0$, and $+$, as it simply boils down to determining when to rewrite an expression using the function on a larger argument or not.