2
$\begingroup$

What is the largest known ordinal number $\alpha$ such that a uniform notation scheme has been developed for all ordinals up to $\alpha$ (there should be no "gaps" in what ordinals are representable), with an algorithm allowing to effectively compare any two ordinals written in that notation?

(I understand that every such scheme can in principle be extended by adding ad hoc symbol for $\alpha$ itself, but I am interested in notations that have been actually described.)

  • 0
    @VladimirReshetnikov Hm, that sounds like a fun game for a googologist.2017-04-26

3 Answers 3

3

It will depend on what you mean by a "notation scheme". In general, for any computable well-ordering $\prec$ of $\mathbb{N}$ you can view each number $n$ as a notation for a particular ordinal $|n|_\prec = \{ |m|_\prec : m \prec n\}$. For any computable well-ordering $\prec$ the set of such ordinals is countable and downward closed, and is thus itself a countable ordinal. In general any order type of a computable well-ordering of $\mathbb{N}$ is called a computable ordinal.

The supremum of the computable ordinals is known as $\omega_1^{CK}$ after Church and Kleene. This is a countable limit ordinal, and there is no computable well-ordering of $\mathbb{N}$ with this order type, but for any $\alpha < \omega_1^{CK}$ there is such a computable well-ordering of $\mathbb{N}$ of order type $\alpha$.

So I would say that the answer to your question, in generality, is $\omega_1^{CK}$ if by "system of ordinal notations" you simply mean "computable well ordering of $\mathbb{N}$". Depending on how the question is read, the answer might instead be "every ordinal up to $\omega_1^{CK}$ but not $\omega_1^{CK}$ itself".

  • 2
    You can effectively compare ordinals encoded using the *same* computable well-ordering. You cannot effectively compare two ordinals represented by codes of computable well-orderings, that would be tantamount to making $\omega_1^{CK}$ a computable ordinal, and it would also contradict Rice's theorem.2012-04-05
3

As far as computable ordinals go, the ordinal collapsing function goes pretty far. Here is one, for example:

$$C(\alpha)_0=\{0\}\\C(\alpha)_{n+1}=C(\alpha)_n\cup\{\gamma+\delta,\omega^\delta,\omega_\gamma,\psi_\gamma(\eta)|\gamma,\delta,\eta\in C(\alpha)_n,\eta\in\alpha\}\\C(\alpha)=\bigcup_{n\in\omega}C(\alpha)_n\\\psi_\beta(\alpha)=\sup(C(\alpha)\cap\omega_{\beta+1})$$

It then follows that $\psi_0(\alpha)$ produces extremely large computable ordinals. A couple of values:

$\psi_0(0)=\sup\left\{\omega,\omega^\omega,\omega^{\omega^\omega},\dots\right\}\\ \psi_0(1)=\sup\left\{\psi_0(0),\psi_0(0)^{\psi_0(0)},\psi_0(0)^{\psi_0(0)^{\psi_0(0)}},\dots\right\}$

$\psi_0(2)=\sup\left\{\psi_0(1),\psi_0(1)^{\psi_0(1)},\psi_0(1)^{\psi_0(1)^{\psi_0(1)}},\dots\right\}$

$\vdots$

$\psi_0(\omega)=\sup\left\{\psi_0(1),\psi_0(2),\psi_0(3),\dots\right\}\\ \psi_0(\omega+1)=\sup\left\{\psi_0(\omega),\psi_0(\omega)^{\psi_0(\omega)},\psi_0(\omega)^{\psi_0(\omega)^{\psi_0(\omega)}},\dots\right\} $

$\vdots$

$\psi_0(\zeta_0)=\psi_0(\omega_1)=\sup\{\psi_0(0),\psi_0(\psi_0(0)),\psi_0(\psi_0(\psi_0(0))),\dots\}\\ \psi_0(\omega_1+1)=\sup\left\{\psi_0(\omega_1),\psi_0(\omega_1)^{\psi_0(\omega_1)},\psi_0(\omega_1)^{\psi_0(\omega_1)^{\psi_0(\omega_1)}},\dots\right\}$

And it just keeps going from there. If we were to define an ordinal as follows:

$D(\beta)_0=\{0\}\\D(\beta)=D(\beta)\cup\{\gamma+\delta,\omega_\gamma,\phi(\eta)|\gamma,\delta,\eta\in D(\alpha),\alpha\in\beta,\eta\in\beta\}\\\phi(\beta)=\sup D(\beta)$

The last rule pertaining to limit ordinals. Within the above notation, the computable supremum is given by...

$$\psi_0(\omega_\star)$$

where $\omega_\star$ is the first fixed-point of $\gamma\mapsto\omega_\gamma$ given by $\sup\{\omega,\omega_\omega,\omega_{\omega_\omega},\dots\}$.

And you can write all ordinals less than the above through a combination of addition, base omega exponentiation, initial ordinals, and $\psi$, the four operations in our $C$.


There exists much stronger notations that can extend this pretty far, though you start having to include things like the axiom of inaccessible cardinals and stuff, things beyond ZFC.

Another note is that the ordinal collapsing function uses larger uncountable ordinals (many uncountable ordinals) and collapses them down into smaller uncountable ordinals until it reaches countable ordinals, which then yields a large result.


A stronger one that I've made is as follows:

$${\rm Assume~there~exists~a~weakly~compact~cardinal~}K\\B_0(\alpha,\beta)=C_0(\alpha,\beta)=\beta\cup\{0,1,K\}\\B_{n+1}(\alpha,\beta)=\{\gamma+\delta,\omega^\gamma,\Psi_\eta(\gamma)~|~\gamma,\delta,\eta\in B_n(\alpha,\beta)\land\eta\in\alpha\}\\C_{n+1}(\alpha,\beta)=\{\gamma+\delta,\omega^\gamma,\psi_\delta^\gamma(\eta)~|~\gamma,\delta,\eta\in C_n(\alpha,\beta)\land\eta\in\alpha\}\\B(\alpha,\beta)=\bigcup_{n\in\omega}B_n(\alpha,\beta)\\C(\alpha,\beta)=\bigcup_{n\in\omega}C_n(\alpha,\beta)\\\Xi[\alpha]=\bigg\{\beta~|~\beta\notin B(\alpha,\beta)\land\alpha\in B(\alpha,\beta)\land\bigcap_{\eta\in\alpha\cap B(\alpha,\beta)}\Xi[\eta]\text{ is stationary}\bigg\}\\\Psi_\alpha=\operatorname{enum}(\Xi[\alpha])\\\psi_\mu^\pi(\alpha)=\min\{\beta\in\Xi[\mu]~|~\beta=\Psi_{\mu+1}(\pi)\cap C(\alpha,\beta)\}$$

This has a limit of $\psi_0^0(\sup(C(0,0)))=\psi_0^0(\sup\{K,\psi_K^K(0),\psi_{\psi_K^K(0)}^K(0),\dots\})$.


Stronger notations may be found on googology.wikia, mainly Deedlit's OCFs and Tarnovski's C. See here.


9/23/19:

Simply because I feel like leaving this here, one can see here for my more recent ordinal collapsing which uses Greatly Mahlos (and generalizations) instead of the weakly compacts like above.

  • 0
    @CalculatorFeline Not in my notation, but yes, in common notation, that would be the case, and the supremum of the above is then $\psi_0(\psi_I(I))$.2017-04-25
2

Ordinal arithmetics say that given an ordinal $\alpha>0$, and $\beta$ we can write $\beta$ uniquely as a polynomial in $\alpha$, that is: $\beta=\sum_{i=1}^n \alpha^{\tau_i}\cdot\sigma_i$ Where $\sigma_i<\alpha$, and $\tau_i<\tau_j$ for $j (we must have this since ordinal arithmetics are hardly commutative). When $\alpha=\omega$ this is called Cantor normal form. If you wish to consider this as the "proper" way to write up ordinals, which makes sense because then the coefficients $\sigma_i$ are finite numbers, you may want to consider $\epsilon_0$, which is a countable ordinal.

$\epsilon_0$ is the least ordinal $\alpha$ for which $\alpha=\omega^\alpha$. It can be defined as the limit of $\alpha_n$ where $\alpha_0=\omega$ and $\alpha_{n+1}=\omega^{\alpha_n}$.

Below this ordinal, you can write every ordinal in a Cantor normal form in a very nice way. Above $\epsilon_0$ you can still write every ordinal in a Cantor normal form, but you have "circular" forms because $\epsilon_0 = \omega^{\epsilon_0}$, and so it is its Cantor normal form.

Of course $\epsilon_0$ is not the only number with this property, there are uncountably many countable $\epsilon$-ordinals. In fact, one can even consider $\omega_1$ as $\epsilon_{\omega_1}$ since $\omega^{\omega_1}=\omega_1$. However it is often usual to talk about countable $\epsilon$-ordinals.

As for how big is this? Well, not very big. While this order type is nearly incomprehensible it is still only countable, thus very very small in terms of cardinality. This ordinal arises naturally in complexity proofs.

  • 0
    That helps with my confusion, since I figured you would be well aware that $\epsilon_{0}$ is just out of the starting gate for ordinal notations (even Veblen went way, way beyond this in his well-known 1908 paper). I had forgotten how the original statements of questions at this site can often change in the first hour or two of their appearance.2011-11-18