What is the complexity (e.g. is it $\Sigma^0\_1$, arithmetic, fully $\Pi^1\_1$) of the relation $|a| < |b|$ given two notations $a, b \in \mathscr{O}$ (Kleene's O)?


What about the case where only one of the notations must be in $\mathscr{O}$ (where $b \not\in \mathscr{O} \implies |b| = \infty$)?


For instance, what is the complexity of a predicate $P(a,b)$ which is true whenever $a \in \mathscr{O} \land b \not\in \mathscr{O}$ and false whenever $a \not\in \mathscr{O} \land b \in \mathscr{O}$ (no restriction on the other cases)?


Note that P(a,b) is sorta the analog of a PA degree for well-foundedness.


--


For backgound, the Selection and Reduction chapter in Higher Recursion Theory tells us that there is a *computable* function t(a,b) such that t(a,b) is in $\mathscr{O}$ iff either a or b is in $ \mathscr{O}$ and $|t(a,b)| \geq \min(|a|,|b|)$ (but this doesn't obviously guarantee that $t(a,b) >\_{\mathscr{O}} a$ or $t(a,b) >\_{\mathscr{O}} b$).


However, I'm guessing that despite this being able to guess which of two relations is well-founded is pretty powerful. So I'm guessing that P(a,b) can be either $\Pi^1\_1$ or $\Sigma^1\_1$ depending on how you define it on the unrestrained cases but can't be $\Delta^1\_1$.



Complexity of |a| < |b| for ordinal notations?
For your first question, Spector showed that the relation $|a| < |b|$ is uniformly computable from $\emptyset^{|b|+1}$. It's not $\Delta^1\_1$, but it is both the restriction of a $\Sigma^1\_1$ relation and of a $\Pi^1\_1$ relation to $\mathcal{O}$. The $\Sigma^1\_1$ relation is "there exists an embedding of $|a|+1$ into $|b|$", while the $\Pi^1\_1$ relation is "there is no embedding of $|b|$ into $|a|$".


For your second question, it again cannot be $\Delta^1\_1$, but can be either $\Sigma^1\_1$ or $\Pi^1\_1$. For $\Sigma^1\_1$, just take "$b$ is ill-founded". For $\Pi^1\_1$, take "$a$ is well-founded".


Less trivially, there is a collection of such $P$s which form a $\Sigma^1\_1$ class: take the collection of $P$ which are true when $a$ enters $\mathcal{O}$ before $b$, and are false when $b$ enters before $a$. So there is such a $P$ which is low for $\omega\_1^{ck}$.


