User:Gro-Tsen/An ordinal collapsing function

This is an attempt to define and explicit a not-too-complicated ordinal collapsing function which should be useful for pedagogical purposes (to construct large countable ordinals). It presumably defines an ordinal notation up to the Bachmann-Howard ordinal, but I need to check this.

Definition

Let $\Omega$ stand for the first uncountable ordinal, or, in fact, any ordinal guaranteed to be greater than all the countable ordinals which will be constructed (for example, the Church-Kleene ordinal is adequate for our purposes).

We define a function $\psi$ (which will be non-decreasing), taking an arbitrary ordinal $\alpha$ to a countable ordinal $\psi (\alpha )$, recursively on $\alpha$, as follows:

Assume $\psi (\beta )$ has been defined for all $\beta <\alpha$, and we wish to define $\psi (\alpha )$.

Let $C(\alpha )$ be the set of ordinals generated starting from $0$, $1$, $\omega$ and $\Omega$ by recursively applying the following functions: ordinal addition, multiplication and exponentiation and the function $\psi \upharpoonright _{\alpha }$, i.e., the restriction of $\psi$ to ordinals $\beta <\alpha$. (Formally, we define $C(\alpha )_{0}=\{0,1,\omega ,\Omega \}$ and inductively $C(\alpha )_{n+1}=C(\alpha )_{n}\cup \{\beta _{1}+\beta _{2},\beta _{1}\beta _{2},{\beta _{1}}^{\beta _{2}}:\beta _{1},\beta _{2}\in C(\alpha )_{n}\}\cup \{\psi (\beta ):\beta \in C(\alpha )_{n}\land \beta <\alpha \}$ for all integers $n$ and we let $C(\alpha )$ be the union of the $C(\alpha )_{n}$ for all $n$.)

Then $\psi (\alpha )$ is defined as the smallest ordinal not belonging to $C(\alpha )$.

Computation of values of $\psi$

Predicative start

First consider $C(0)$. It contains ordinals $0$, $1$, $2$, $3$, $\omega$, $\omega +1$, $\omega +2$, $\omega 2$, $\omega 3$, $\omega ^{2}$, $\omega ^{3}$, $\omega ^{\omega }$, $\omega ^{\omega ^{\omega }}$ and so on. It also contains such ordinals as $\Omega$, $\Omega +1$, $\Omega \omega$, $\Omega ^{\Omega }$. The first ordinal which it does not contain is $\varepsilon _{0}$ (which is the limit of $\omega$, $\omega ^{\omega }$, $\omega ^{\omega ^{\omega }}$ and so on — less than $\Omega$ by assumption). The upper bound of the ordinals it contains is $\varepsilon _{\Omega +1}$ (the limit of $\Omega$, $\Omega ^{\Omega }$, $\Omega ^{\Omega ^{\Omega }}$ and so on), but that is not so important. This shows that $\psi (0)=\varepsilon _{0}$.

Similarly, $C(1)$ contains the ordinals which can be formed from $0$, $1$, $\omega$, $\Omega$ and this time also $\varepsilon _{0}$, using addition, multiplication and exponentiation. This contains all the ordinals up to $\varepsilon _{1}$ but not the latter, so $\psi (1)=\varepsilon _{1}$. In this manner, we prove that $\psi (\alpha )=\varepsilon _{\alpha }$ inductively on $\alpha$: the proof works, however, only as long as $\alpha <\varepsilon _{\alpha }$. We therefore have:

$\psi (\alpha )=\varepsilon _{\alpha }=\phi _{1}(\alpha )$ for all $\alpha \leq \zeta _{0}$, where $\zeta _{0}=\phi _{2}(0)$ is the smallest fixed point of $\alpha \mapsto \varepsilon _{\alpha }$.

(Here, the $\phi$ functions are the Veblen functions defined starting with $\phi _{1}(\alpha )=\varepsilon _{\alpha }$.)

Now $\psi (\zeta _{0})=\zeta _{0}$ but $\psi (\zeta _{0}+1)$ is no larger, since $\zeta _{0}$ cannot be constructed using finite applications of $\varepsilon$ and thus never belongs to a $C(\alpha )$ set for $\alpha \leq \Omega$, and the function $\psi$ remains “stuck” at $\zeta _{0}$ for some time:

$\psi (\alpha )=\zeta _{0}$ for all $\zeta _{0}\leq \alpha \leq \Omega$.

First impredicative values

Again, $\psi (\Omega )=\zeta _{0}$. However, when we come to computing $\psi (\Omega +1)$, something has changed: since $\Omega$ was (“artificially”) added to all the $C(\alpha )$, we are permitted to take the value $\psi (\Omega )=\zeta _{0}$ in the process. So $C(\Omega +1)$ contains all ordinals which can be built from $0$, $1$, $\omega$, $\Omega$, the $\phi _{1}\colon \alpha \mapsto \varepsilon _{\alpha }$ function up to $\zeta _{0}$ and this time also $\zeta _{0}$ itself, using addition, multiplication and exponentiation. The smallest ordinal not in $C(\Omega +1)$ is $\varepsilon _{\zeta _{0}+1}$ (the smallest $\varepsilon$-number after $\zeta _{0}$).

We say that the definition $\psi (\Omega )=\zeta _{0}$ and the next values of the function $\psi$ such as $\psi (\Omega +1)=\varepsilon _{\zeta _{0}+1}$ are impredicative because they use ordinals (here, $\Omega$) greater than the ones which are being defined (here, $\zeta _{0}$).

Values of $\psi$ up to the Feferman-Schütte ordinal

The fact that $\psi (\Omega +\alpha )=\varepsilon _{\zeta _{0}+\alpha }$ remains true for all $\alpha <\zeta _{1}=\phi _{2}(1)$ (note, in particular, that $\psi (\Omega +\zeta _{0})=\varepsilon _{\zeta _{0}2}$: but since now the ordinal $\zeta _{0}$ has been constructed there is nothing to prevent from going beyond this). However, at $\zeta _{1}=\phi _{2}(1)$ (the first fixed point of $\alpha \mapsto \varepsilon _{\alpha }$ beyond $\zeta _{0}$), the construction stops again, because $\zeta _{1}$ cannot be constructed from smaller ordinals and $\zeta _{0}$ by finitely applying the $\varepsilon$ function. So we have $\psi (\Omega 2)=\zeta _{1}$.

The same reasoning shows that $\psi (\Omega (1+\alpha ))=\phi _{2}(\alpha )$ for all $\alpha <\phi _{3}(0)$, where $\phi _{2}$ enumerates the fixed points of $\phi _{1}\colon \alpha \mapsto \varepsilon _{\alpha }$ an $\phi _{3}(0)$ is the first fixed point of $\phi _{2}$. We then have $\psi (\Omega ^{2})=\phi _{3}(0)$.

Again, we can see that $\psi (\Omega ^{\alpha })=\phi _{1+\alpha }(0)$ for some time: this remains true until the first fixed point $\Gamma _{1}$ of $\alpha \mapsto \phi _{\alpha }(0)$, which is the Feferman-Schütte ordinal. Thus, $\psi (\Omega ^{\Omega })=\Gamma _{0}$ is the Feferman-Schütte ordinal.

Beyond the Feferman-Schütte ordinal

We have $\psi (\Omega ^{\Omega +\alpha })=\phi _{\Gamma _{0}+\alpha }(0)$ for all $\alpha \leq \Gamma _{1}$ where $\Gamma _{1}$ is the next fixed point of $\alpha \mapsto \phi _{\alpha }(0)$. So $\psi (\Omega ^{\Omega (1+\alpha )})=\Gamma _{\alpha }$, for some time, if $\alpha \colon \Gamma _{\alpha }$ enumerates the fixed points in question. This can also be noted $\phi (\alpha ,0,0)$ using the many-valued Veblen functions: this gives us a notation for some large ordinals:

• $\psi (\Omega ^{\Omega ^{2}})$ is the Ackermann ordinal,
• $\psi (\Omega ^{\Omega ^{\omega }})$ is the “small” Veblen ordinal (the range of the notations $\phi (\ldots )$ predicatively using finitely many variables),
• $\psi (\Omega ^{\Omega ^{\Omega }})$ is the “large” Veblen ordinal (the range of the notations $\phi (\ldots )$ predicatively using transfinitely many variables),
• the limit $\psi (\varepsilon _{\Omega +1})$ of $\psi (\Omega )$, $\psi (\Omega ^{\Omega })$, $\psi (\Omega ^{\Omega ^{\Omega }})$, etc., is the Bachmann-Howard ordinal: after this our function $\psi$ is constant.