2
$\begingroup$

So a common method used to construct non-zero $\omega$-REA arithmetic degrees with various properties is to build an $\omega$-REA operator $J$ satisfying the constraints that (for all $X$)

$$\tag{1} J(X') \equiv_T J(X) \oplus X'$$ $$\tag{2} J(X) >_T X$$

Inductively, 1 implies that $J(X^n) \equiv_T J(\emptyset) \oplus X^n$. Thus, together, these constraints ensure that $J(\emptyset)$ isn't arithmetic (if $J(\emptyset) \leq_T 0^n$ then $J(0^n) \equiv_T 0^n$).

My question is whether this is fully general, i.e., if $A$ is $\omega$-REA but non-arithmetic is there some $\omega$-REA operator $J$ satisfying 1 and 2 such that $A$ and $J(\emptyset)$ have the same arithmetic degree?

Basically, I'm hoping someone will let me know if I'm missing some obvious elementary result or known result before I spend any time trying a hard construction.

$\endgroup$
1
  • $\begingroup$ Note that I edited the question to only ask about the case where A is non-arithmetic and we demand both 1 and 2 be satisfied. It is trivial to satisfy just 1 simply by setting $J(X) = X \oplus A$ $\endgroup$ Commented Dec 1, 2020 at 3:54

1 Answer 1

0
$\begingroup$

So after some careful thought I'm pretty sure it is fully general. Let $A$ be a non-arithmetic $\omega$-REA set and $K(X)$ some $\omega$-REA operator satisfying 1 and 2 (see Odifreddi volume 2 XIII.3.1 for an existence proof). We now define $J(X)$ so that $J(X) \equiv_T X \oplus A$ if $X = \emptyset^n$ for some $n$ and otherwise make $J(X) \equiv_T K(X) \oplus A$.

Claim 1: If $J(X)$ behaves as indicated then $J(X)$ satisfies (1), (2) and $J(\emptyset) = A$.

Pf: Since $A$ is non-arithmetic we trivially have (1) satisfied for any arithmetic $X$. If $X$ not arithmetic then $J(X) \geq_T K(X) >_T X$. As the jump is injective to verify (2) it is enough to note that it clearly holds separately for both $K(X) \oplus A$ and $X \oplus A$.$\square$

Claim 2: The desired operator $J(X)$ exists if there is a $\Pi^0_2$ class $P$ with $P = \lbrace X \mid (\exists k)(X = \emptyset^k) \rbrace$

Pf: Given such a $\Pi^0_2$ class $P(X) \iff \forall n \exists m Q(X\restriction_m, n, m)$ we build an r.e. operator $R(X)$ by enumerating $n$ when we've found $m$ for each $n' \leq n$ ensuring that $$R(X) =^{*} \begin{cases} \emptyset & \text{if } (\exists k)(X = \emptyset^k) \\ \omega & \text{ otherwise} \\ \end{cases}$$

We let $J^{[1]}(X) = R(X)$. Obviously, the column-wise sum of $K(X)$ and $A$ is $\omega$-REA in $X$ so we simply modify this by only enumerating elements into the $K(X)$ part if $(\exists z)(z \notin R(X))$. $\square$

We now define the computable predicate $Q(\tau, m, n)$.

Fix a totally total (i.e. total for all $X$) computable functional $\rho$ such that $\rho(Y') = Y$ and let $\tau^{k} = \rho^{k}(\tau)$ where $\rho^{k}$ denotes the application of $\rho$ $k$ times with $\rho^0$ the identity (WLOG $n \leq \lvert \tau^{n+1}\rvert \leq \lvert \tau^{n}\rvert \leq \lvert \tau\rvert = m$).

Let $$k(n,m) = \max_{k < m}\,\,\,\lvert \tau^{k}\rvert \geq n \land (\forall j < k) )(\forall x < n) (\phi_x(\tau^{j}; x)\downarrow_m \iff \tau^{j-1}(x) = 1 $$

Thus $k(n,m)$ is our guess at the maximum number $k$ such that $X = Y^{k}$ for some $Y$ and $\tau^{k(n,m)}$ our approximation to $Y$. Using this we now define

$$Q(\tau, m, n) \iff (\exists k \leq k(n,m))(\forall x < n)(\tau^k(x) = 0)$$

Claim 3: If $P(X)$ is defined to be $\forall n \exists m Q(X\restriction_m, n, m)$ then $P(X) \iff (\exists k)(X = \emptyset^k)$.

Pf: If $X = \emptyset^k$ the claim is straightforward. $\tau^{k}$ will be identically $0$ and any $m > k$ large enough to witness the convergence all the finitely many computations examined in checking $Q(X\restriction_m, n, m)$ will suffice (such .

For the other direction suppose that $k$ is the maximum such that for some $Y$, $Y^{k} = X$ (the existence of such a $k$ follows from this question). Thus, for all sufficiently large $n$, $k(n,m) \leq k$ as $m > n$ sees the failure of $\rho^{k+1}(X)' = \rho^{k}(X)$. By hypothesis no $\rho^{q}(X) \neq \emptyset$ for any $q \leq k$ so if $n$ is larger than all the witnessing locations then $\exists m Q(X\restriction_m, n, m)$ fails to hold and thus $P(X)$ fails to hold. $\square$


[1]: Specifically if we denote the $n$-th column of $J(X)$ by $J^{[n]}(X)$, we'll build

$$J^{[0]}(X) = X,J^{[1]}(X) =^{*} \emptyset, J^{[n+2]}(X) = K^{[n+1]}(X) \oplus A^{[n+1]} \text{ if } (\forall k)(X \neq \emptyset^k) \text{ and } \tag{a}$$ $$J^{[0]}(X) = X,J^{[1]}(X) =^{*} \omega, J^{[n+2]}(X) = \emptyset \oplus A^{[n+1]} \text{ if } (\exists k)(X = \emptyset^k) \tag{b}$$

$\endgroup$

You must log in to answer this question.

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