1
$\begingroup$

Suppose that $A$ is an $\omega$-REA set (so $A^{[n]}$ is r.e. in the prior columns). It is a well-known result that if each column of $A$ is computable then $A \leq_T \emptyset^2$ ($\emptyset^2$ can recover the computable index for each column from indices of prior columns and thus compute $A$).

A suggestive way to reformulate this statement is that, if each column in $A$ is computable and $(A^{[\leq n]})'' \ngeq_T X$ for all $n$ then $A \ngeq_T X$. Now you might hope to drop the requirement that the columns in $A$ be computable but this is trivially counterexampled by $\emptyset^\omega$. But what if we restrict $X$ to be $n$-REA in addition to dropping the requirement of computable columns?

I hypothesize the following, which would imply the result.

Hypothesis: If $X$ is arithmetic, $(A^{[\leq n]})'' \ngeq_T X$ and $A$ is an $\omega$-REA set then there is an upper bound $D$ of the sequence $A^{[\leq n]}$ with $D'' \ngeq_T X$.

The result would follow immediately since $D''$ can compute $A$ in the way mentioned at the start. However, I don't see any immediately obvious way to prove this or find a counterexample, so I figured I'd ask to see if there is something I'm missing. If the claim is either false generally or hard to answer I'd love to know if it's true for the simplest case where $X=\emptyset^3$.

$\endgroup$

1 Answer 1

0
$\begingroup$

Ok, so unfortunately the answer is no. I've attached a proof that builds a $\omega$-REA set such that $A^{[\leq n]}$ is low for all $n$ yet $A$ computes $\emptyset'' \oplus X$ where $X$ is a natural non-$\Delta^0_3$ set [1] r.e. in $\emptyset''$. The proof is a bit too long to attach as an image so here's a link to the pdf on my webserver

[1]: Specifically, $X$ disagrees with $\lim_{s \to \infty} \lim_{t \to \infty} p_e(e,s,t)$ when it exists, some $\emptyset''$ computable value when any of the component limits fail to exist and say 1 if all component limits exist but the double limit fails to exist. Easiest way to see this is really 3-REA is to note that for each $e$, $X(e)$ is built in a 3-REA fashion so just build whole thing by doing the construction column wise.

$\endgroup$

You must log in to answer this question.

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