11,357
pages

Madore's $$\psi$$ function is an ordinal collapsing function introduced by David Madore (under the alias "Gro-Tsen" on Wikipedia)[1].

## Definition

Madore's $$\psi$$ function is defined as follows:

Let $$\omega$$ be the smallest transfinite ordinal and $$\Omega$$ be the smallest uncountable ordinal. Then,

$$C_0(\alpha) = \{0, 1, \omega, \Omega\}$$

$$C_{n+1}(\alpha) = \{\gamma + \delta, \gamma\delta, \gamma^{\delta}, \psi(\eta) | \gamma, \delta, \eta \in C_n (\alpha); \eta < \alpha\}$$

$$C(\alpha) = \bigcup_{n < \omega} C_n (\alpha)$$

$$\psi(\alpha) = \min\{\beta < \Omega|\beta \notin C(\alpha)\}$$

In other words, $$\psi(\alpha)$$ is the least ordinal number less than $$\Omega$$ which cannot be generated from the ordinals $$0, 1, \omega, \Omega$$ using any finite combination of addition, multiplication, exponentiation, or the $$\psi$$ function itself (with the restriction of applying $$\psi(\eta)$$ only for ordinals $$\eta < \alpha$$.

The limit of this function is the Bachmann-Howard ordinal.

## Examples

• $$\psi(0)=$$$$\varepsilon_0$$
• $$\psi(1)=\varepsilon_1$$
• $$\psi(2)=\varepsilon_2$$
• $$\psi(\omega)=\varepsilon_\omega$$
• $$\psi(\psi(0))=\psi(\varepsilon_0)=\varepsilon_{\varepsilon_0}$$
• $$\psi(\psi(\psi(0)))=\psi(\psi(\varepsilon_0))=\psi(\varepsilon_{\varepsilon_0})=\varepsilon_{\varepsilon_{\varepsilon_0}}$$
• $$\psi(\zeta_0)=$$$$\zeta_0$$
• $$\psi(\zeta_0+1)=\zeta_0$$
• $$\psi(\eta_0)=\zeta_0$$
• $$\psi(\Omega)=\zeta_0$$
• $$\psi(\Omega+1)=\varepsilon_{\zeta_0+1}$$
• $$\psi(\Omega+2)=\varepsilon_{\zeta_0+2}$$
• $$\psi(\Omega+\omega)=\varepsilon_{\zeta_0+\omega}$$
• $$\psi(\Omega+\zeta_0)=\varepsilon_{\zeta_02}$$
• $$\psi(\Omega+\zeta_02)=\varepsilon_{\zeta_03}$$
• $$\psi(\Omega+\zeta_0\omega)=\varepsilon_{\zeta_0\omega}$$
• $$\psi(\Omega+\zeta_0^2)=\varepsilon_{\zeta_0^2}$$
• $$\psi(\Omega+\varepsilon_{\zeta_0+1})=\varepsilon_{\varepsilon_{\zeta_0+1}}$$
• $$\psi(\Omega+\varepsilon_{\varepsilon_{\zeta_0+1}})=\varepsilon_{\varepsilon_{\varepsilon_{\zeta_0+1}}}$$
• $$\psi(\Omega+\zeta_1)=\zeta_1$$
• $$\psi(\Omega+\zeta_1+1)=\zeta_1$$
• $$\psi(\Omega2)=\zeta_1$$
• $$\psi(\Omega2+1)=\varepsilon_{\zeta_1+1}$$

## Fundamental sequences

Now we assign a fundamental sequence for each limit ordinal below the Bachmann-Howard ordinal. The fundamental sequence for an ordinal number $$\alpha$$ with cofinality $$\beta$$ is a strictly increasing sequence $$(\alpha[\eta])_{\eta<\beta}$$ with a length of $$\beta$$ and whose limit is $$\alpha$$, where $$\alpha[\eta]$$ is the $$\eta$$-th element of the sequence. If $$\alpha$$ is a countable limit ordinal (i.e. $$\alpha$$ is a limit ordinal less than $$\Omega$$) then $$\text{cof}(\alpha)=\omega$$. The first uncountable ordinal $$\Omega$$ is the least ordinal whose cofinality greater than $$\omega$$ since $$\text{cof}(\Omega)=\Omega$$.

First we must define the normal forms for expressions given by all relevant functions:

$$\alpha=_{NF}\alpha_1+\alpha_2+\cdots+\alpha_n$$ iff $$\alpha=\alpha_1+\alpha_2+\cdots+\alpha_n$$ and $$\alpha_1\geq\alpha_2\geq\cdots\geq\alpha_n$$

$$\alpha=_{NF}\omega^\beta$$ iff $$\alpha=\omega^\beta$$ for some $$\beta<\alpha$$

$$\alpha=_{NF}\Omega^\beta\gamma$$ iff $$\alpha=\Omega^\beta\gamma$$ for some $$\gamma<\Omega$$

$$\alpha=_{NF}\psi(\beta)$$ iff $$\alpha=\psi(\beta)$$ for some $$\beta\in C(\beta)$$

Then for these limit ordinals, when written in normal form, we can assign the fundamental sequences as follows:

1) if $$\alpha=\alpha_1+\alpha_2+\cdots+\alpha_n$$ then $$\text{cof} (\alpha)= \text{cof} (\alpha_n)$$ and $$\alpha[\eta]=\alpha_1+\alpha_2+\cdots+(\alpha_n[\eta])$$

2) if $$\alpha=\omega^\beta$$ and $$\beta$$ is a countable limit ordinal then $$\alpha[n]=\omega^{\beta[n]}$$

3) if $$\alpha=\omega^\beta$$ and $$\beta=\gamma+1$$ then $$\alpha[n]=\omega^\gamma n$$

4) if $$\alpha=\psi(0)$$ then $$\alpha[0]=1$$ and $$\alpha[n+1]=\omega^{\alpha[n]}$$

5) if $$\alpha=\psi(\beta+1)$$ then $$\alpha[0]=\psi(\beta)+1$$ and $$\alpha[n+1]=\omega^{\alpha[n]}$$

6) if $$\alpha=\Omega^{\beta}\gamma$$ and $$\text{cof} (\gamma)=\omega$$ then $$\text{cof} (\alpha)= \omega$$ and $$\alpha[\eta]=\Omega^{\beta}(\gamma[\eta])$$

7) if $$\alpha=\Omega^{\beta+1}(\gamma+1)$$ then $$\text{cof} (\alpha)=\Omega$$ and $$\alpha[\eta]=\Omega^{\beta+1}\gamma+\Omega^\beta\eta$$

8) if $$\alpha=\Omega^\beta(\gamma+1)$$ and $$\text{cof}(\beta)\geq\omega$$ then $$\text{cof}(\alpha)= \text{cof}(\beta)$$ and $$\alpha[\eta]=\Omega^\beta\gamma+\Omega^{\beta[\eta]}$$

9) if $$\alpha=\varepsilon_{\Omega+1}$$ then $$\text{cof} (\alpha)=\omega$$ and $$\alpha[0]=1$$ and $$\alpha[n+1]=\Omega^{\alpha[n]}$$

10) if $$\alpha=\psi(\beta)$$ and $$\text{cof}(\beta)=\omega$$ then $$\text{cof} (\alpha)=\omega$$ and $$\alpha[n]=\psi(\beta[n])$$

11) if $$\alpha=\psi(\beta)$$ and $$\text{cof}(\beta)=\Omega$$ then $$\text{cof} (\alpha)=\omega$$ and $$\alpha[0]=1$$ and $$\alpha[n+1]=\psi(\beta[\alpha[n]])$$

For example, the ordinal $$\psi(\Omega^{\Omega^2+\Omega3})$$ has the following fundamental sequence (using rules 1, 7, 8, 10)

$$\psi(\Omega^{\Omega^2+\Omega3})[0]=1$$,

$$\psi(\Omega^{\Omega^2+\Omega3})[1]=\psi(\Omega^{\Omega^2+\Omega2+1})$$,

$$\psi(\Omega^{\Omega^2+\Omega3})[2]=\psi\left(\Omega^{\Omega^2+\Omega2+\psi(\Omega^{\Omega^2+\Omega2+1})}\right)$$,

and so on.

Assigning fundamental sequences for any ordinal collapsing function is vital for its use in the fast-growing hierarchy, slow-growing hierarchy and Hardy hierarchy.

## Ordinal Notation

Unlike other standard ordinal collapsing functions, there seems to be no canonical ordinal notation associated to Madore's function. In order to create a computable large number by using fast-growing hierarchy applied to the system of fundamental sequences defined in set theory, we need to fix an ordinal notation associated to it.

## References

1. "Ordinal Collapsing Function". Wikipedia. Retrieved 2014-08-29.