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 which is (an $\varepsilon$-number and) 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 and continuous), 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 $\phi _{1}\colon \alpha \mapsto \varepsilon _{\alpha }$ 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 \leq \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 \leq \phi _{3}(0)$, where $\phi _{2}$ enumerates the fixed points of $\phi _{1}\colon \alpha \mapsto \varepsilon _{\alpha }$ and $\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 _{0}$ 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, if $\alpha \mapsto \Gamma _{\alpha }$ enumerates the fixed points in question. (which can also be noted $\phi (\alpha ,0,0)$ using the many-valued Veblen functions) we have $\psi (\Omega ^{\Omega (1+\alpha )})=\Gamma _{\alpha }$, until the first fixed point of the $\alpha \mapsto \Gamma _{\alpha }$ itself, which will be $\psi (\Omega ^{\Omega ^{2}})$. In this manner:

• $\psi (\Omega ^{\Omega ^{2}})$ is the Ackermann ordinal (the range of the notation $\phi (\alpha ,\beta ,\gamma )$ defined predicatively),
• $\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-but-predicatively-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, and we can go no further with the definition we have given.

Ordinal notations up to the Bachmann-Howard ordinal

We now explain how the $\psi$ function defines notations for ordinals up to the Bachmann-Howard ordinal.

A note about base representations

Recall that if $\delta$ is an ordinal which is a power of $\omega$ (for example $\omega$ itself, or $\varepsilon _{0}$, or $\Omega$), any ordinal $\alpha$ can be uniquely expressed in the form $\delta ^{\beta _{1}}\gamma _{1}+\cdots +\delta ^{\beta _{k}}\gamma _{k}$, where $k$ is a natural number, $\gamma _{1},\ldots ,\gamma _{k}$ are non-zero ordinals less than $\delta$, and $\beta _{1}>\beta _{2}>\ldots >\beta _{k}$ are ordinal numbers (we allow $\beta _{k}=0$). This “base $\delta$ representation” is an obvious generalization of the Cantor normal form (which is the case $\delta =\omega$). Of course, it may quite well be that the expression is uninteresting, i.e., $\alpha =\delta ^{\alpha }$, but in any other case the $\beta _{i}$ must all be less than $\alpha$; it may also be the case that the expression is trivial (i.e., $\alpha <\delta$, in which case $k\leq 1$ and $\gamma _{1}=\alpha$).

If $\alpha$ is an ordinal less than $\varepsilon _{\Omega +1}$, then its base $\Omega$ representation has coefficients $\gamma _{i}<\Omega$ (by definition) and exponents $\beta _{i}<\alpha$ (because of the assumption $\alpha <\varepsilon _{\Omega +1}$): hence one can rewrite these exponents in base $\Omega$ and repeat the operation until the process terminates (any decreasing sequence of ordinals is finite). We call the resulting expression the iterated base $\Omega$ representation of $\alpha$ and the various coefficients involved (including as exponents) the pieces of the representation (they are all $<\Omega$), or, for short, the $\Omega$-pieces of $\alpha$.

Some properties of $\psi$

• The function $\psi$ is non-decreasing and continuous (this is more or less obvious from is definition).
• If $\psi (\alpha )=\psi (\beta )$ with $\beta <\alpha$ then necessarily $C(\alpha )=C(\beta )$. Indeed, no ordinal $\beta '$ with $\beta \leq \beta '<\alpha$ can belong to $C(\alpha )$ (otherwise its image by $\psi$, which is $\psi (\alpha )$ would belong to $C(\alpha )$ — impossible); so $C(\beta )$ is closed by everything under which $C(\alpha )$ is the closure, so they are equal.
• Any value $\gamma =\psi (\alpha )$ taken by $\psi$ is an $\varepsilon$-number (i.e., a fixed point of $\beta \mapsto \omega ^{\beta }$). Indeed, if it were not, then by writing it in Cantor normal form, it could be expressed using sums, products and exponentiation from elements less than it, hence in $C(\alpha )$, so it would be in $C(\alpha )$, a contradiction.
• Lemma: Assume $\delta$ is an $\varepsilon$-number and $\alpha$ an ordinal such that $\psi (\beta )<\delta$ for all $\beta <\alpha$: then the $\Omega$-pieces (defined above) of any element of $C(\alpha )$ are less than $\delta$. Indeed, let $C'$ be the set of ordinals all of whose $\Omega$-pieces are less than $\delta$. Then $C'$ is closed under addition, multiplication and exponentiation (because $\delta$ is an $\varepsilon$-number, so ordinals less than it are closed under addition, multiplication and exponentition). And $C'$ also contains every $\psi (\beta )$ for $\beta <\alpha$ by assumption, and it contains $0$, $1$, $\omega$, $\Omega$. So $C'\supseteq C(\alpha )$, which was to be shown.
• Under the hypothesis of the previous lemma, $\psi (\alpha )\leq \delta$ (indeed, the lemma shows that $\delta \not \in C(\alpha )$).
• Any $\varepsilon$-number less than some element in the range of $\psi$ is itself in the range of $\psi$ (that is, $\psi$ omits no $\varepsilon$-number). Indeed: if $\delta$ is an $\varepsilon$-number not greater than the range of $\psi$, let $\alpha$ be the least upper bound of the $\beta$ such that $\psi (\beta )<\delta$: then by the above we have $\psi (\alpha )\leq \delta$, but $\psi (\alpha )<\delta$ would contradict the fact that $\alpha$ is the least upper bound — so $\psi (\alpha )=\delta$.
• Whenever $\psi (\alpha )=\delta$, the set $C(\alpha )$ consists exactly of those ordinals $\gamma$ (less than $\varepsilon _{\Omega +1}$) all of whose $\Omega$-pieces are less than $\delta$. Indeed, we know that all ordinals less than $\delta$, hence all ordinals (less than $\varepsilon _{\Omega +1}$) whose $\Omega$-pieces are less than $\delta$, are in $C(\alpha )$. Conversely, if we assume $\psi (\beta )<\delta$ for all $\beta <\alpha$ (in other words if $\alpha$ is the least possible with $\psi (\alpha )=\delta$), the lemma gives the desired property. On the other hand, if $\psi (\alpha )=\psi (\beta )$ for some $\beta <\alpha$, then we have already remarked $C(\alpha )=C(\beta )$ and we can replace $\alpha$ by the least possible with $\psi (\alpha )=\delta$.

The ordinal notation

Using the facts above, we can define a (canonical) ordinal notation for every $\gamma$ less than the Bachmann-Howard ordinal. We do this by induction on $\gamma$.

If $\gamma$ is less than $\varepsilon _{0}$, we use the iterated Cantor normal form of $\gamma$. Otherwise, there exists a largest $\varepsilon$-number $\delta$ less or equal to $\gamma$ (this is because the set of $\varepsilon$-numbers is closed): if $\delta <\gamma$ then by induction we have defined a notation for $\delta$ and the base $\delta$ representation of $\gamma$ gives one for $\gamma$, so we are finished.

It remains to deal with the case where $\gamma =\delta$ is an $\varepsilon$-number: we have argued that, in this case, we can write $\delta =\psi (\alpha )$ for some (possibly uncountable) ordinal $\alpha <\varepsilon _{\Omega +1}$: let $\alpha$ be the greatest possible such ordinal (which exists since $\psi$ is continuous). We use the iterated base $\Omega$ representation of $\alpha$: it remains to show that every piece of this representation is less than $\delta$ (so we have already defined a notation for it). If this is not the case then, by the properties we have shown, $C(\alpha )$ does not contain $\alpha$; but then $C(\alpha +1)=C(\alpha )$ (they are closed under the same operations, since the value of $\psi$ at $\alpha$ can never be taken), so $\psi (\alpha +1)=\psi (\alpha )=\delta$, contradicting the maximality of $\alpha$.

Examples

For ordinals less than $\varepsilon _{0}=\psi (0)$, the canonical ordinal notation defined coincides with the iterated Cantor normal form (by definition).

For ordinals less than $\varepsilon _{1}=\psi (1)$, the notation coincides with iterated base $\varepsilon _{0}$ notation (the pieces being themselves written in iterated Cantor normal form): e.g., $\omega ^{\omega ^{\varepsilon _{0}+\omega }}$ will be written ${\varepsilon _{0}}^{\omega ^{\omega }}$, or, more accurately, $\psi (0)^{\omega ^{\omega }}$. For ordinals less than $\varepsilon _{2}=\psi (2)$, we similarly write in iterated base $\varepsilon _{1}$ and then write the pieces in iterated base $\varepsilon _{0}$ (and write the pieces of that in iterated Cantor normal form): so $\omega ^{\omega ^{\varepsilon _{1}+\varepsilon _{0}+1}}$ is written ${\varepsilon _{1}}^{\varepsilon _{0}\omega }$, or, more accurately, $\psi (1)^{\psi (0)\,\omega }$. Thus, up to $\zeta _{0}=\psi (\Omega )$, we always use the largest possible $\varepsilon$-number base which gives a non-trivial representation.

Beyond this, we may need to express ordinals beyond $\Omega$: this is always done in iterated $\Omega$-base, and the pieces themselves need to be expressed using the largest possible $\varepsilon$-number base which gives a non-trivial representation.

Conditions for canonicalness

The notations thus defined have the property that whenever they nest $\psi$ functions, the arguments of the “inner” $\psi$ function are always less than those of the “outer” one (this is a conseequence of the fact that the $\Omega$-pieces of $\alpha$, where $\alpha$ is the largest possible such that $\psi (\alpha )=\delta$ for some $\varepsilon$-number $\delta$, are all less than $\delta$, as we have shown above). For example, $\psi (\psi (\Omega )+1)$ does not occur as a notation: it is a well-defined expression (and it is equal to $\psi (\Omega )=\zeta _{0}$ since $\psi$ is constant between $\zeta _{0}$ and $\Omega$), but it is not a notation produced by the inductive algorithm we have outlined.

Canonicalness can be checked recursively: an expression is canonical if and only if it is either the iterated Cantor normal form of an ordinal less than $\varepsilon _{0}$, or an iterated base $\delta$ representation all of whose pieces are canonical, for some $\delta =\psi (\alpha )$ where $\alpha$ is itself written in iterated base $\Omega$ representation all of whose pieces are canonical and less than $\delta$. The order is checked by lexicographic verification at all levels (keeping in mind that $\Omega$ is greater than any expression obtained by $\psi$, and for canonical values the greater $\psi$ always trumps the lesser or even arbitrary sums, products and exponentials of the lesser).

For example, $\psi (\Omega ^{\omega +1}\,\psi (\Omega )+\psi (\Omega ^{\omega })^{\psi (\Omega ^{2})}42)^{\psi (1729)\,\omega }$ is a canonical notation for an ordinal which is less than the Feferman-Schütte ordinal: it can be written using the Veblen functions as $\phi _{1}(\phi _{\omega +1}(\phi _{2}(0))+\phi _{\omega }(0)^{\phi _{3}(0)}42)^{\phi _{1}(1729)\,\omega }$.

Concerning the order, one might point out that $\psi (\Omega ^{\Omega })$ (the Feferman-Schütte ordinal) is much more than $\psi (\Omega ^{\psi (\Omega )})=\phi _{\phi _{2}(0)}(0)$ (because $\Omega$ is greater than $\psi$ of anything), and $\psi (\Omega ^{\psi (\Omega )})=\phi _{\phi _{2}(0)}(0)$ is itself much more than $\psi (\Omega )^{\psi (\Omega )}=\phi _{2}(0)^{\phi _{2}(0)}$ (because $\Omega ^{\psi (\Omega )}$ is greater than $\Omega$, so any sum-product-or-exponential expression involving $\psi (\Omega )$ and smaller value will remain less than $\psi (\Omega ^{\Omega })$). In fact, $\psi (\Omega )^{\psi (\Omega )}$ is already less than $\psi (\Omega +1)$.