4
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ Why do you say "fully $\Pi^1_1$"? The natural upper bound seems to be $\Sigma^1_1$, since the order coded by $a$ will be shorter than that of $b$ if and only if there exists an order-embeding of the $a$ order with a bounded suborder of the $b$ order. $\endgroup$
    – Joel David Hamkins
    Jun 4 at 12:25
  • $\begingroup$ I seem to remember that any ordinal $<\omega_1^{\mathrm{CK}}$ can be encoded by a well-ordering on $\mathbb{N}$ with, say, polynomial complexity. I imagine it is likewise possible to encode Kleene's $\mathcal{O}$ in such a way as to bring comparison of two elements, when they are indeed in the part admitted as $\mathcal{O}$, as low as one wishes. $\endgroup$
    – Gro-Tsen
    Jun 4 at 12:39
  • $\begingroup$ @JoelDavidHamkins I was just indicating that by complexity I was happy with an answer in terms of either the (hyper) arithmetic hierarchy or, if not not hyperarithmetic, where it occured in the lightface analytic hierarchy and didn't, say, mean the Turing degree required to compute such a relation. Specifically, I was imagining an answer exactly like given below (there are $\Sigma^1_1$ and $\Pi^1_1$ such relations but not hyperarithmetic) and was trying to indicate that was the kind of thing I was looking for. $\endgroup$
    – Peter Gerdes
    Jun 5 at 21:17
  • 1
    $\begingroup$ @Gro-Tsen Yes, you can encode any ordinal into a well-ordering on $\mathbb{N}$. The problem is that here you don't get the ordinal you get a notation for it (essentially you get a computable well-ordering with that height). The issue is that it may be (indeed is) very difficult to compare two very different computable well-orderings. $\endgroup$
    – Peter Gerdes
    Jun 5 at 21:25

1 Answer 1

Reset to default
7
$\begingroup$

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}$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Wait, surely it must be possible to reduce that by a factor of $\omega$. That is computable in $0^{b' + 1}$ where $b'$ is least s.t $\omega\cdot b' \leq |b|$ Or maybe with a 2 rather than 1. But the successor stages shouldn't be making this any more complicated right? $\endgroup$
    – Peter Gerdes
    Jun 10 at 14:42
  • $\begingroup$ Actually, I'm kinda curious about the details here. Any idea where I can find that proof? $\endgroup$
    – Peter Gerdes
    Jun 10 at 14:44
  • 1
    $\begingroup$ @PeterGerdes You're right, that's not always a tight bound (but infinitely often it is). It's Lemma 5.2 in Ash & Knight. $\endgroup$
    – Dan Turetsky
    Jun 12 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.