Say that a function $f \in \omega^\omega$ witnesses that an $\omega$-REA set $A = \bigoplus\_{i \in \omega} A^{[i]}$ is non-arithmetic if $A^{[\leq f(n)]} \not\leq\_T 0^n$. Say that $A$ is effectively non-arithmetic if there is such an $f \leq\_a A$ (i.e. arithmetic in $A$)?


Is every non-arithmetic $\omega$-REA set effectively non-arithmetic?




---


Note that, we can't hope to always have $f$ arithmetic. To see this, note that we can build $0^{\omega}$ with the pieces spread out. So, if we want to ensure that $f^{k}\_i(n) = \phi\_i(0^{k}, n)$ isn't such a witness we can wait until after we've set $A^{[\leq m]} = 0^{k+1}$ at which point we can produce indexes for $A^{[m + n]}$ that yields $0^{k+2}$ if $f^{k}\_i(k+2)$ diverges or $m + n > f^{k}\_i(k+2)$ and otherwise is $\emptyset$. It is straightforward to extend this approach to ensure that no arithmetic $f^{k}\_i$ witnesses $A$ is non-arithmetic.


However, as every non-arithmetic $\omega$-REA set has a witness that's computable in $0^{\omega}$ this approach doesn't obviously extend to showing that $f$ can't be arithmetic in $A$.




---


Also note that if the claim is false it can't be false in a reletivizeable fashion since (in some sense) since given an $\omega$-REA operator A(X) that's never arithmetic in X we can take G to be $\omega$ generic below $0^\omega$ with A(G) of degree $0^\omega$ and there will be a witness to the fact that A(G) isn't arithmetic in G computable in $0^\omega$.



Effectively non-arithmetic $\omega$-REA degrees
Unfortunately, I believe I can show there are non-arithmetic $\omega$-REA degrees that aren't effectively $\omega$-REA.


To this end we need to build $A$ to be $\omega$-REA with $A >\_a 0$ to satisfy


$$R\_{n,i}: \phi\_i(A^{(n)})\downarrow \implies (\exists m,k)\left(\phi\_i(A^{(n)};m) =k \implies A^{[\leq k]} \leq\_T 0^{m} \right)$$


where $\phi\_i(A^{(n)})\downarrow$ means the function is total.


Meeting requirements $R\_{0,i}$ is relatively straightforward. Given a construction of a $\omega$-REA $A >\_a 0$ we start building $\hat{A}$ just like $A$ can simply look at approximations to the construction [1] and freeze $\hat{A}\_s$ if we see $\phi\_0(A;0)\downarrow = k$. Then simply let $\hat{A}^{[\leq k]}$ be computable and restart the original construction of $A$ at the $k+1$-st component, e.g., $\hat{A}^{[k+1]} = A^{[1]}$. If $\hat{A}^{[k\_i + 1]} = A^{[i]}$ then we don't allow $R\_{0,i+1}$ to affect $\hat{A}^{[\leq k\_i + 1]}$ but if we can make $\phi\_{i+1}(A;i+1)$ converge to $k\_{i+1}$ by freezing the approximation to $\hat{A}^{[> k\_i + 1]}$ we do so and let sufficiently many more columns be computable to ensure that $\hat{A}^{[\leq k\_{i+1} + 1]} \leq 0^{i+1}$.


However, to do this for $n > 0$ we need some way to control both the behavior of $A^{n}$ at the same time as the columns of $A$. We leverage Harrington's construction of a low $\omega$-REA set.


The short version of this is that since $A$ is just built by taking a low set and then copying over columns by jump inversion we can use the same approach with the $n$-th jump of $A$ (where we can compute $\phi\_i(A^{n})$ and the same spacing out trick on the $n$-th jump will entail spacing out in $A$. The much longer version is below.


Construction of low $\omega$-REA set
------------------------------------


Per Odifreddi vol 2 we build an $\omega$-REA operator $A(X)$ with the following properties


$$A(X)' \equiv\_T A(X) \oplus X' \equiv\_T A(X')$$
$$A(X) >\_T X$$


This ensures that $A(X)^{n}\equiv\_T A(X^{n}) \equiv\_T A(X) \oplus X^{n} \not\leq\_T X^{n}$ making $A(\emptyset)$ a non-arithmetic low (for the arithmetic jump) $\omega$-REA set.


To build this we actually build $A(X)' \equiv\_T A(X) \oplus X' \equiv\_T J\_e(X')$ and use the fixed point theorem to find $e$ with $A(X) = J\_e(X)$. The construction proceeds by first building $A^{[1]}(X) = L(X)$ where $L$ is a low non-computable r.e. set. Then, assuming that


$$A^{[\leq 2n +1]}(X)' \equiv\_T A^{[\leq 2n +1]}(X) \oplus X' \equiv J\_e^{[\leq n]}(X')$$


(via known reductions) we use the ZBC lemma (extension of Sacks jump inversion) relativized to $A^{[\leq 2n +1]}(X)$ to construct $A^{[2n +2]}(X), A^{[2n +3]}(X)$ to ensure that above equation holds for $n+1$. Finally, we allow $A^{[\geq i]}(X)$ to be frozen on a finite initial segment if we have the opportunity to place $i \in A(X)'$ thus ensuring that $A(X)' \equiv\_T \oplus\_{n \in \omega} A^{[\leq 2n +1]}(X)'$


Modifying the Construction
--------------------------


We modify the above construction by inserting extra computable columns as above. In particular, we build $A(X)$ so that the first $k\_0$ columns are computable then the next column is the low set $L(X)$ followed by more computable columns followed by the two columns from the ZBC lemma to jump to $A^{[\leq 1]}(X)$ and so on. In general we ensure that (note that the value of $k\_m$ will depend on $X$ and we mean the value relative to $X$ in these equations).


$$A^{[\leq k\_m]}(X) \leq\_T 0^m$$
$$A^{[\leq k\_m + 2]}(X)' \equiv\_T A^{[\leq m]}(X')$$


Now, we ensure that if $m = \langle n,i\rangle$ and we can cause $\phi\_i(X;m + n)\downarrow = z$ to converge by freezing some finite part of the columns extending $A^{[\leq k\_{m-1} + 2]}(X)$ we do so and ensure that $k\_m > z > k\_{m-1} + 2$. We again build $A = A(\emptyset)$ using a fixed point as above.


Now, suppose that $f$ witnessed the fact that $A$ was effectively non-arithmetic. Then, for some $n$ $f$ would be computable in $A^{n}(\emptyset) \equiv\_T A(0^{n})$ so for some $i$ we have $f = \phi\_i(A(0^{n}))$. Let $m = \langle n,i\rangle$ and $z = \phi\_i(A(0^{n});m + n)$.


The first $k^{0^n}\_{m}$ columns of $A(0^{n})$ are computable in $0^{m + n}$ hence, by induction on the second equation above using the fact that $k\_{m+1} > k\_m + 2$, so too are the first $k^{0^n}\_{m} > z$ columns of $A(\emptyset)$. Thus, showing that $R\_{n,i}$ is satisfied.


[1]: We can view the construction of an $\omega$-REA set as an enumeration of axioms and using this gives us a stagewise approximation $A\_s$ (finite binary valued partial function) with the property that if $\sigma$ is an initial segment of $A$ then infinitely often $\sigma \prec A\_s$.


