Skip to main content
Added note of no relitivizeable solution
Source Link

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

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

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

added 1 character in body
Source Link
Michael Hardy
  • 1
  • 12
  • 85
  • 126

Say that a function $f \in \omega^{\omega}$$f \in \omega^\omega$ witnesses that an $\omega$-REA set $A = \oplus_{i \in \omega} A^{[i]}$$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$.

Say that a function $f \in \omega^{\omega}$ witnesses that an $\omega$-REA set $A = \oplus_{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$.

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

Source Link

Effectively non-arithmetic $\omega$-REA degrees

Say that a function $f \in \omega^{\omega}$ witnesses that an $\omega$-REA set $A = \oplus_{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$.