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.)

  • 2
    What is a uniform notation scheme?2011-11-17
  • 0
    I mean a finite set of rules which identify some symbolic expressions with all ordinals up to a certain point - similar to Cantor normal form for ordinals < \epsilon_0.2011-11-17
  • 0
    If I could answer this question and give you such an ordinal $\alpha$, wouldn't I have just written down a symbolic expression that describes $\alpha$?2011-11-17
  • 0
    I understand that in principle every notation can be extended in this way. My question is more about what notations have been actually described, with an algorithm allowing comparison of ordinals written in that notation.2011-11-18
  • 0
    @nikov: It seems that the only reasonable answer is "letters" let $\alpha,\beta$ be two ordinals. Either $\alpha\in\beta$, $\alpha=\beta$ or $\beta\in\alpha$. This is a nice algorithm. Also note that if you replace $\omega$ by something larger in the CNF then you just get to a "larger" epsilon-like number.2011-11-18
  • 1
    @QiaochuYuan: To make it more clear, imagine a game where you and your opponent each is given a sheet of paper and 10 min to describe a notation and a corresponding comparison algorithm. One whose notation is able to represent all elements in a bigger ordinal wins. What approach would you choose?2011-11-18
  • 0
    @nikov: this strikes me as a very different question from the body question. Do you want to edit your question?2011-11-18
  • 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".

  • 0
    "you can view each number n as a notation for a particular ordinal" - Is there an effective way to compare ordinals written in this notation?2011-11-18
  • 0
    Yes because the well ordering is computable.2011-11-18
  • 1
    But how can you effectively determine that (1) a given computable function is a well-ordering function (2) two given computable functions represent the same ordinal?2011-11-18
  • 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,1\}\\C(\alpha)_{n+1}=C(\alpha)_n\cup\{\gamma+\delta,\gamma\delta,\gamma^\delta,\omega_\gamma,\sup(C(\eta)),\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\left(\phi(\phi(\phi(\dots \phi(0)\dots)))\right)$$

Likewise, you can write almost all ordinals in between through a combination of addition, multiplication, and exponentiation.


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\\{\rm cl}(A)=A\cup\{\sup(B)~|~B\subset A\}\\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,\delta,\eta\in B_n(\alpha,\beta)\land\eta\in\alpha\}\\C_{n+1}(\alpha,\beta)=\{\gamma+\delta,\omega^\gamma,\Psi(\delta),\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)\\\Psi(\alpha)=\min\big\{\pi\in K~\big|~\pi{\rm~is~regular}\land\alpha\in{\rm cl}(B(\alpha,\pi))\land\pi=B(\alpha,\pi)\cap K\\\land\forall\gamma\big[K\cdot(\gamma+1)\subseteq\alpha\Rightarrow\Xi_\pi[\gamma]{\rm~is~stationary~in~}\pi\big]\big\}\\\psi_\mu^\sigma(\alpha)=\min\bigg\{\pi\in K~\bigg|~\pi=C(\alpha,\pi)\cap\Psi(K\cdot\sigma+\mu)\land\pi\in\bigcap_{\gamma\in\sigma}\Xi_{\pi+1}[\gamma]\bigg\}\\\Xi[\gamma]=\{\Psi(K\cdot\gamma+\delta)~|~\delta\in K\}\\\Xi_\pi[\gamma]=\begin{cases}\Xi[\gamma]\cap\pi,&\Xi[\gamma]\cap\pi\ne\varnothing\\\pi,&\Xi[\gamma]\cap\pi=\varnothing\end{cases}$$

See also.

This has a limit of $\psi_0^0(\sup(C(0,0)))$.


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

  • 0
    Note that the $\alpha_{x}$ function is equivalent to $\psi_{I}(x)$.2017-04-25
  • 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 $jCantor 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
    I think the original poster is looking for ordinals well beyond $\epsilon_{0}$, even well beyond $\Gamma_{0}$, and probably well beyond the Bachmann-Howard ordinal. I suggest he look at the many papers by Michael Rathjen, although I have to admit that the use of ordinal collapsing functions for large cardinals is well beyond anything I have personally tried to understand.2011-11-18
  • 0
    @Dave: Possibly. His post was unclear at time of posting. Only after my answer did he answered the comments and mentioned $\epsilon_0$ in his comment. I am leaving it here because it may help the OP, and it does sort of answer the question - which is not phrased clearly and well enough, as it seems.2011-11-18
  • 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