Suppose that $A \leq\_a 0^\omega$ (i.e. $A$ is arithmetic in $0^\omega$) does there exist $\widehat{A} \equiv\_a A$ with $\widehat{A} \leq\_T 0^\omega$ [1]?


More generally, say that a set $X$ is aT-complete (better name?) if every arithmetic degree $\mathbf{a} \leq\_a X$ has a representative $A \leq\_T X$. Does every arithmetic degree contain an aT-complete set? Are there any non-trivial degrees containing aT-complete sets (clearly any arithmetic degree bounding only finitely many arithmetic degrees will contain an aT-complete set [2])




---


[1]: In other words, if $A \leq\_T 0^{\omega + n}$ does there exist $\widehat{A} \leq\_T 0^\omega$, $m \in \omega$ such that $\widehat{A}^m \geq\_T A$ and $A^m \geq\_T \widehat{A}$?


[2]: Suppose the only arithmetic degrees (strictly) below $\mathbf{a}$ are $b\_1, \ldots, b\_n$ with representatives $A, B\_1, \ldots, B\_n$ respectively. Let $m\_i$ be such that $A^{m\_i} \geq\_T B\_i$ and $m = \max m\_i$. Then $A^{m}$ is aT-complete.



Does every arithmetic degree below $0^\omega$ have a representative computable in $0^\omega$?
Ok, I'm pretty sure the answer is no to the basic question. We build a set $A$ to satisfy the following conditions.


$P\_e: A \neq \phi\_i(0^{n})$
$R\_{i,j}: X = \phi\_i(0^\omega) \land (\forall i)\left(X(i) = A \models \psi\_j(i)\right) \implies (\exists n)(X \leq\_T 0^{n})$


Where $\phi\_i$ is a Turing reduction and $\psi\_j$ is an arithmetic formula with one free variable.


We build $A$ via sequence of perfect trees $T\_n$ with $T\_{n+1}$ a subtree of $T\_n$ as in the construction of a minimal arithmetic degree to meet the above requirements with $\lvert T\_n(0) \rvert \geq n$. We ensure that each $T\_n$ is arithmetic and is uniformly computable from $0^{\omega + 1}$ and set $T\_{-1} = 2^{< \omega}$


To meet $P\_e$ we simply insist that $T\_e(0)$ disagrees with $\phi\_i(0^{n})$. Given an index for $T\_{e - 1}$ we can find an index for a subtree $\hat{T}\_e$ with this property and with $\lvert T\_n(0) \rvert \geq e$ computably in $0^{\omega}$.


To meet $R\_{i,j}$ with $e = \langle i,j \rangle$ now ask if there is a string $\tau$ on $\hat{T}\_e$ and an $x$ such that $\tau \Vdash \psi\_j(x) = k \land \phi\_i(0^{n};x) = 1 -x$ (here we are using local forcing on $\hat{T}\_e$). If so we let $T\_e$ be the subtree of $\hat{T}\_e$ above $\tau$ and otherwise let it be $\hat{T}\_e$. Note that this whole construction can be carried out computably in $0^{\omega +1}$


It's obvious that the requirements $P\_e$ are satisfied and we've constructed $A \leq\_T 0^{\omega+1}$ so $A$ clearly satisfies $0 <\_a A \leq\_A 0^{\omega}$. If $R\_{i,j}$ is also satisfied then we are done since any $\widehat{A} \leq\_a A$ with $\widehat{A} \leq\_T 0^{\omega}$ would necessarily be arithmetic and therefore $A$ couldn't be arithmetic in $\widehat{A}$.


So suppose that for some $i,j,n, X$ we have a $\Sigma^0\_n$ formula $\psi\_j$ defining $X$ from $A$ and $X = \phi\_i(0^{\omega})$. Now since $\hat{T}\_{\langle i,j \rangle}$ is arithmetic we can find an arithmetic path $Z$ through $\hat{T}\_{\langle i,j \rangle}$ that's $n$-generic under local forcing. Thus, the set defined by $\psi\_j$ applied to $Z$ is also arithmetic and by construction must be equal to $\phi\_i(0^{\omega}) = X$ (or we'd have found a disagreement). Hence, $X$ is arithmetic (i.e. computable from $0^{m}$ for some $m$).


Note that the above argument can actually build an $A$ computable in $0^{\omega + n +1}$ witnessing that $0^{\omega +n}$ isn't aT-complete. Hence the arithmetic degree containing $0^{\omega}$ doesn't contain an aT-complete set.




---


However, there are 'non-trivial' arithmetic degrees containing aT-complete sets if by non-trivial we mean having infinitely many predecessors. Consider the usual construction of a Turing degree $\mathbf{d}$ with $\mathscr{D}(<, \mathbf{d})$ equal to $\omega$. We build $A$ using uniform trees $T\_n$ where if $\lvert \sigma \rvert = \langle m, i \rangle$ then $T\_n(\sigma\hat{}0)$ and $T\_n(\sigma\hat{}1)$ only disagree on locations of the form $\langle i, x \rangle$. We then perform the construction so that $A\_0 = A^{[0]}$ is a minimal degree, $A\_1 = A^{[\leq 1]}$ is a strong minimal cover of $A^{[0]}$ and so on with any set computable from $A$ either computable in some $A\_i$ or computing $A$.


Now modify this construction to use local forcing and arithmetic rather than computable trees as in the construction of a minimal arithmetic degree. As $A$ explicitly computes a representative $A\_i = A^{[\leq i]}$ of every arithmetic degree below $A$ it's aT-complete.




---


You might hope to be able to construct an arithmetic degree containing an aT-complete set above any arithmetic degree $X$. However, I think this is impossible. By relativising the argument given above to $X$ we can show that the arithmetic degree of $X^{\omega}$ doesn't contain an aT-complete set. Hence, no upper cone (in Turing or arithmetic degrees) contains only sets whose arithmetic degree is an aT-complete set. Thus, by Martin's cone theorem (since this is a Borel, degree invariant property) there must be an upper cone none of whose members is arithmetically equivalent to an aT-complete set.


Actually, we can show that $0^{\omega}$ is the base of such a cone. Note that for any $C$ there is an $A$ with $A^{\omega} \equiv\_T 0^{\omega} \oplus C$ (code $C$ into an $\omega$-generic). By the argument above the arithmetic degree of $A^{\omega}$ doesn't contain an aT-complete set.


