Difference between Kleene's O and the system $S_1$

Question

On pages 207-208, Rogers (Theory of Recursive Functions and Effective Computability) introduces two system of notations for ordinals: the first is what he calls $S_1$ and the second one is Kleene's $\mathcal{O}$.

My question is: what is the difference between the two systems?

In the definition of Kleene's $\mathcal{O}$, Rogers defines also a partial ordering $<_O$. It seems to me that the only difference is that, when defining the names for a limit ordinal, in the definition of $\mathcal{O}$ we have the additional requirement that

$$ \forall i\, \forall j\quad i<j \Rightarrow (\varphi_y(i), \varphi_y(j)) \text{ is already in} <_O$$

But I don't see how this requirement actually reduces the amount of names for a limit ordinal. I mean, if $\gamma$ is a limit ordinal and $(\varphi_y(n))_{n\in\mathbb{N}}$ is an increasing sequence of (names for) ordinals with limit $\gamma$, how can it be that we did not already put the pair $(\varphi_y(i), \varphi_y(j))$ in $<_O$?

Answer 1

Short version: the relation "$<_\mathcal{O}$" is a proper subrelation of the relation "names a smaller ordinal than."

---

The point is the distinction between names and ordinals in determining increasing-ness. Specifically, in general if $a,b$ are names for $\alpha,\beta$ in the sense of Kleene's $\mathcal{O}$ and $\alpha<\beta$, we need not have $a<_\mathcal{O}b$. In particular, we can find a sequence $(\varphi_y(n))_{n\in\mathbb{N}}$ such that

• each $\varphi_y(n)$ is in $\mathcal{O}$, and

• $\vert\varphi_y(n)\vert<\vert\varphi_y(n+1)\vert$ for each $n\in\mathbb{N}$

(where "$\vert a\vert$" is the ordinal corresponding to the name $a$), but $3\cdot 5^y$ is not in $\mathcal{O}$ since (say) $\varphi_y(0)\not<_\mathcal{O}\varphi_y(1)$.

In the system $S_1$, we only required that the values of the names be increasing; in $\mathcal{O}$, we require that this increasing-ness be witnessed in a very concrete way, namely by the relation $<_\mathcal{O}$. This is all in an attempt to make a more "constructive" system, and at this point Kleene's original paper "On notation for ordinal numbers" has a useful paragraph:

Following Church, a modification is now made in the system $S_1$, which is regarded from the finitary viewpoint as a correction, in that it eliminates the presupposition of the classical (non-constructive) second number class. The modification consists in replacing the ordering relation $<$ between ordinals by a partially ordering relation $<_\mathcal{O}$ between the notations.

(Note that he refers to the system we know and love as $\mathcal{O}$ by "$S_2$.")