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
    Commented Jun 4, 2023 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
    Commented Jun 4, 2023 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
    Commented Jun 5, 2023 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
    Commented Jun 5, 2023 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$
6
  • $\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
    Commented Jun 10, 2023 at 14:42
  • $\begingroup$ Actually, I'm kinda curious about the details here. Any idea where I can find that proof? $\endgroup$
    – Peter Gerdes
    Commented Jun 10, 2023 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
    Commented Jun 12, 2023 at 6:04
  • $\begingroup$ So I looked up that lemma and I don't see where it says the bound is infinitely often correct. Also we can write the relation and it's negation on O^2 in a $\Sigma^1_1$ way so whether there is a $\Delta^1_1$ way to write it comes down to the question of whether we can ensure those two sets are disjoint outside off of O^2 and it's not clear to me why that's impossible. I guess the problem is for two notations that look like 'infinite' ordinals so intuitively I tend to agree but I'm not totally sure. $\endgroup$
    – Peter Gerdes
    Commented Oct 31 at 17:25
  • 1
    $\begingroup$ There's an $\alpha$-systems argument that for $\beta$ limit, given a $\Sigma^0_\beta$ formula $\theta$, we can build a computable sequence of notations $(a_n)_{n \in \omega}$ such that $|a_n| < \omega^\beta$ iff $\theta(n)$. This shows tightness of the bound whenever $|b| = \omega^{|b|}$. This is also why $|a| < |b|$ can't be $\Delta^1_1$, because otherwise take a $b$ with $|b|$ greater than the ordinal of the relation and derive a contradiction. $\endgroup$
    – Dan Turetsky
    Commented Nov 1 at 4:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .