Effectively non-arithmetic $\omega$-REA degrees

Question

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

Answer 1

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