## FANDOM

10,840 Pages

Buchholz's psi-functions are a hierarchy of single-argument ordinal functions $$\psi_\nu(\alpha)$$ introduced by german mathematician Wilfried Buchholz in 1986.[1] These functions are a simplified version of the $$\theta$$-functions, but nevertheless have the same strength as those.

## Definition Edit

Buchholz defined his functions as follows:

• $$C_\nu^0(\alpha) = \Omega_\nu$$,
• $$C_\nu^{n+1}(\alpha) = C_\nu^n(\alpha) \cup \{\gamma | P(\gamma) \subseteq C_\nu^n(\alpha)\} \cup \{\psi_\mu(\xi) | \xi \in \alpha \cap C_\nu^n(\alpha) \wedge \xi \in C_\mu(\xi) \wedge \mu \leq \omega\}$$,
• $$C_\nu(\alpha) = \bigcup_{n < \omega} C_\nu^n (\alpha)$$,
• $$\psi_\nu(\alpha) = \min\{\gamma | \gamma \not\in C_\nu(\alpha)\}$$,

where

$$\Omega_\nu=\left\{\begin{array}{lcr} 1\text{ if }\nu=0\\ \aleph_\nu\text{ if }\nu>0\\ \end{array}\right.$$

and $$P(\gamma)=\{\gamma_1,...,\gamma_k\}$$ is the set of additive principal numbers in form $$\omega^\xi$$,

$$P=\{\alpha\in On: 0<\alpha \wedge \forall \xi, \eta < \alpha (\xi+\eta < \alpha)\}=\{\omega^\xi: \xi \in On\}$$,

the sum of which gives this ordinal $$\gamma$$:

$$\gamma=\alpha_1+\alpha_2+\cdots+\alpha_k$$ where $$\alpha_1\geq\alpha_2\geq\cdots\geq\alpha_k$$ and $$\alpha_1,\alpha_2,...,\alpha_k \in P(\gamma)$$.

Note: Greek letters always denotes ordinals. $$On$$ denotes the class of all ordinals.

The limit of this notation is Takeuti-Feferman-Buchholz ordinal.

## Properties Edit

Buchholz showed following properties of those functions:

• $$\psi_\nu(0)=\Omega_\nu$$,
• $$\psi_\nu(\alpha)\in P$$,
• $$\psi_\nu(\alpha+1)=\text{min}\{\gamma\in P: \psi_\nu(\alpha)<\gamma\}\text{ if }\alpha\in C_\nu(\alpha)$$,
• $$\Omega_\nu\le\psi_\nu(\alpha)<\Omega_{\nu+1}$$,
• $$\alpha\le\beta\Rightarrow\psi_\nu(\alpha)\le\psi_\nu(\beta)$$,
• $$\psi_0(\alpha)=\omega^\alpha \text{ if }\alpha<\varepsilon_0$$,
• $$\psi_\nu(\alpha)=\omega^{\Omega_\nu+\alpha} \text{ if }\alpha<\varepsilon_{\Omega_\nu+1} \text{ and } \nu\neq 0$$,
• $$\theta(\varepsilon_{\Omega_\nu+1},0)=\psi_0(\varepsilon_{\Omega_\nu+1})$$ for $$0<\nu\le\omega$$.

## Explanation Edit

Buchholz is working in Zermelo–Fraenkel set theory, that means every ordinal $$\alpha$$ is equal to set $$\{\beta|\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|\beta<\Omega_\nu\}$$.

The condition $$C_\nu^{n+1}(\alpha) = C_\nu^n(\alpha) \cup \{\gamma | P(\gamma) \subseteq C_\nu^n(\alpha)\} \cup \{\psi_\mu(\xi) | \xi \in \alpha \cap C_\nu^n(\alpha) \wedge \mu \leq \omega\}$$ means that set $$C_\nu^{n+1}(\alpha)$$ includes:

1. all ordinals from previous set $$C_\nu^n(\alpha)$$,
2. all ordinals that can be obtained by summation the additively principal ordinals from previous set $$C_\nu^n(\alpha)$$,
3. 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)|\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}(\xi)$$, where $$\mu\le\omega$$ and $$\xi<\alpha$$.

Then $$\psi_\nu(\alpha) = \min\{\gamma | \gamma \not\in C_\nu(\alpha)\}$$ is the smallest ordinal that does not belong to this set.

### Examples Edit

Consider the following examples:

$$C_0^0(\alpha)=\{0\} =\{\beta:\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:

$$C_0(1)=\{0,1,2,...,\text{googol}, ...,\text{TREE(googol)},...\}$$.

Then $$\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.

Then $$\psi_0(2)=\omega^2$$.

For $$C_0(\omega)$$ we have set $$C_0(\omega)=\{0,\psi(0)=1,...,\psi(1)=\omega,...,\psi(2)=\omega^2,...,\psi(3)=\omega^3,...\}$$.

Then $$\psi_0(\omega)=\omega^\omega$$.

For $$C_0(\Omega)$$ we have set $$C_0(\Omega)=\{0,\psi(0)=1,...,\psi(1)=\omega,...,\psi(\omega)=\omega^\omega,...,\psi(\omega^\omega)=\omega^{\omega^\omega},...\}$$.

Then $$\psi_0(\Omega)=\varepsilon_0$$.

For $$C_0(\Omega+1)$$ we have set $$C_0(\Omega)=\{0,1,...,\psi_0(\Omega)=\varepsilon_0,...,\varepsilon_0+\varepsilon_0,...\psi_1(0)=\Omega,...\}$$.

Then $$\psi_0(\Omega+1)=\varepsilon_0\omega=\omega^{\varepsilon_0+1}$$.

$$\psi_0(\Omega2)=\varepsilon_1$$,

$$\psi_0(\Omega^2)=\zeta_0$$,

$$\varphi(\alpha,1+\beta)=\psi_0(\Omega^\alpha\beta)$$,

$$\psi_0(\Omega^\Omega)=\Gamma_0=\theta(\Omega,0)$$, using Feferman theta-function,

$$\psi_0(\Omega^{\Omega^\Omega})$$ is 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(\alpha)=\{\beta:\beta<\Omega_1\}=\{0,\psi(0)=1,2,...\text{googol},...,\psi_0(1)=\omega,...,\psi_0(\Omega)=\varepsilon_0,...$$

$$...,\psi_0(\Omega^\Omega)=\Gamma_0,...,\psi(\Omega^{\Omega^\Omega+\Omega^2}),...\}$$ i.e. includes all countable ordinals.

$$C_1(\alpha)$$ includes all possible sums of all countable ordinals. Then

$$\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$$.

$$C_1(1)=\{0,...,\psi_0(0)=\omega,...,\psi_1(0)=\Omega,...,\Omega+\omega,...,\Omega+\Omega,...\}$$

Then $$\psi_1(1)=\Omega\omega=\omega^{\Omega+1}$$.

Then $$\psi_1(2)=\Omega\omega^2=\omega^{\Omega+2}$$,

$$\psi_1(\psi_0(\Omega))=\Omega\varepsilon_0=\omega^{\Omega+\varepsilon_0}$$,

$$\psi_1(\psi_0(\Omega^\Omega))=\Omega\Gamma_0=\omega^{\Omega+\Gamma_0}$$,

$$\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(\Omega_2)=\psi_1^\omega(0)=\Omega\uparrow\uparrow\omega=\varepsilon_{\Omega+1}$$.

For case $$\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),..., \psi_1^\omega(0)$$

and then $$\psi_0(\Omega_2)=\psi_0(\psi_1(\Omega_2))=\psi_0(\varepsilon_{\Omega+1})$$.

In 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_\nu})$$ ( for $$1\le\nu<\omega$$).

## Extension Edit

We rewrite Buchholz's definition as follows[2]:

• $$C_\nu^0(\alpha) = \{\beta|\beta<\Omega_\nu\}$$,
• $$C_\nu^{n+1}(\alpha) = \{\beta+\gamma,\psi_\mu(\eta)|\mu,\beta, \gamma,\eta\in C_{\nu}^n(\alpha)\wedge\eta<\alpha\}$$,
• $$C_\nu(\alpha) = \bigcup_{n < \omega} C_\nu^n (\alpha)$$,
• $$\psi_\nu(\alpha) = \min\{\gamma | \gamma \not\in C_\nu(\alpha)\}$$,

where

$$\Omega_\nu=\left\{\begin{array}{lcr} 1\text{ if }\nu=0\\ \text{smallest ordinal with cardinality }\aleph_\nu \text{ if }\nu>0\\ \end{array}\right.$$

and $$\omega$$ is the smallest infinite ordinal.

There is only one little detail difference with original Buchholz definition: ordinal $$\mu$$ is not limited by $$\omega$$, now ordinal $$\mu$$ belongs to previous set $$C_n$$.

For example if $$C_0^0(1)=\{0\}$$ then $$C_0^1(1)=\{0,\psi_0(0)=1\}$$ and $$C_0^2(1)=\{0,...,\psi_1(0)=\Omega\}$$ and $$C_0^3(1)=\{0,...,\psi_\Omega(0)=\Omega_\Omega\}$$ and so on.

Limit of this notation must be omega fixed point $$\psi(\Omega_{\Omega_{\Omega_{...}}})=\psi(\psi_{\psi_{...}(0)}(0))$$, where $$\psi$$ without subscript denotes $$\psi_0$$.

## Normal form and fundamental sequences Edit

### Normal form Edit

The normal form for 0 is 0. If $$\alpha$$ is a nonzero ordinal number $$\alpha<\Lambda=\text{min}\{\beta|\psi_\beta(0)=\beta\}$$ 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 $$k$$ is a positive integer and $$\psi_{\nu_1}(\beta_1)\geq\psi_{\nu_2}(\beta_2)\geq\cdots\geq\psi_{\nu_k}(\beta_k)$$ and each $$\nu_i$$, $$\beta_i$$ are also written in normal form.

### Fundamental sequences Edit

The fundamental sequence for an ordinal number $$\alpha$$ with cofinality $$\text{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 $$\text{cof}(\alpha)=1$$ and the fundamental sequence has only one element $$\alpha[0]=\alpha-1$$. If $$\alpha$$ is a limit ordinal then $$\text{cof}(\alpha)\in\{\omega\}\cup\{\Omega_{\mu+1}|\mu\geq 0\}$$.

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

1. If $$\alpha=\psi_{\nu_1}(\beta_1)+\psi_{\nu_2}(\beta_2)+\cdots+\psi_{\nu_k}(\beta_k)$$ where $$k\geq2$$ then $$\text{cof}(\alpha)=\text{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])$$,
2. If $$\alpha=\psi_{0}(0)=1$$, then $$\text{cof}(\alpha)=1$$ and $$\alpha[0]=0$$,
3. If $$\alpha=\psi_{\nu+1}(0)$$, then $$\text{cof}(\alpha)=\Omega_{\nu+1}$$ and $$\alpha[\eta]=\Omega_{\nu+1}[\eta]=\eta$$,
4. If $$\alpha=\psi_{\nu}(0)$$ and $$\text{cof}(\nu)\in\{\omega\}\cup\{\Omega_{\mu+1}|\mu\geq 0\}$$, then $$\text{cof}(\alpha)=\text{cof}(\nu)$$ and $$\alpha[\eta]=\psi_{\nu[\eta]}(0)=\Omega_{\nu[\eta]}$$,
5. If $$\alpha=\psi_{\nu}(\beta+1)$$ then $$\text{cof}(\alpha)=\omega$$ and $$\alpha[\eta]=\psi_{\nu}(\beta)\cdot \eta$$ (and note: $$\psi_\nu(0)=\Omega_\nu$$),
6. If $$\alpha=\psi_{\nu}(\beta)$$ and $$\text{cof}(\beta)\in\{\omega\}\cup\{\Omega_{\mu+1}|\mu<\nu\}$$ then $$\text{cof}(\alpha)=\text{cof}(\beta)$$ and $$\alpha[\eta]=\psi_{\nu}(\beta[\eta])$$,
7. If $$\alpha=\psi_{\nu}(\beta)$$ and $$\text{cof}(\beta)\in\{\Omega_{\mu+1}|\mu\geq\nu\}$$ then $$\text{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.$$.

If $$\alpha=\Lambda$$ then $$\text{cof}(\alpha)=\omega$$ and $$\alpha[0]=0$$ and $$\alpha[\eta+1]=\psi_{\alpha[\eta]}(0)=\Omega_{\alpha[\eta]}$$.

## Sources Edit

1. Buchholz, W. "A New System of Proof-Theoretic Ordinal Functions"Annals of Pure and Applied Logic, vol. 32. Retrieved 2017-05-13.
2. Maksudov, Denis. The extension of Buchholz's functionTraveling To The Infinity. Retrieved 2017-05-18.