Skip to main content

Computable in $\omega$-REA degree but not double jump of finietlyfinitely many columns

Suppose that $A$ is an $\omega$-REA set (so $A^{[n]}$ is r.e. in the prior columns). It is a well know-known result that if each column of $A$ is computable then $A \leq_T \emptyset^2$ ($\emptyset^2$ can recover the computable index for each column from indices of prior columns and thus compute $A$).

A suggestive way to reformulate this statement is that, if each column in $A$ is computable and $(A^{[\leq n]})'' \ngeq_T X$ for all $n$ then $A \ngeq_T X$. Now you might hope to drop the requirement that the columns in $A$ be computable but this is trivially counterexampled by $\emptyset^\omega$. But what if we restrict $X$ to be $n$-REA in addition to dropping the requirement of computable columns?

I hypothesize the following, which would imply the result.

Hypothesis: If $X$ is arithmetic, $(A^{[\leq n]})'' \ngeq_T X$ and $A$ is an $\omega$-REA set then there is an upper bound $D$ of the sequence $A^{[\leq n]}$ with $D'' \ngeq_T X$.

The result would follow immediately since $D''$ can compute $A$ in the way mentioned at the start. However, I don't see any immediately obvious way to prove this or sfind a counterexample, so I figured I'd ask to see if there is something I'm missing. If the claim is either false generally or hard to answer I'd love to know if it's true for the simplest case where $X=\emptyset^3$.

Computable in $\omega$-REA degree but not double jump of finietly many columns

Suppose that $A$ is an $\omega$-REA set (so $A^{[n]}$ is r.e. in the prior columns). It is a well know result that if each column of $A$ is computable then $A \leq_T \emptyset^2$ ($\emptyset^2$ can recover the computable index for each column from indices of prior columns and thus compute $A$).

A suggestive way to reformulate this statement is that, if each column in $A$ is computable and $(A^{[\leq n]})'' \ngeq_T X$ for all $n$ then $A \ngeq_T X$. Now you might hope to drop the requirement that the columns in $A$ be computable but this is trivially counterexampled by $\emptyset^\omega$. But what if we restrict $X$ to be $n$-REA in addition to dropping the requirement of computable columns?

I hypothesize the following which would imply the result.

Hypothesis: If $X$ is arithmetic, $(A^{[\leq n]})'' \ngeq_T X$ and $A$ is an $\omega$-REA set then there is an upper bound $D$ of the sequence $A^{[\leq n]}$ with $D'' \ngeq_T X$.

The result would follow immediately since $D''$ can compute $A$ in the way mentioned at the start. However, I don't see any immediately obvious way to prove this or s counterexample so I figured I'd ask to see if there is something I'm missing. If the claim is either false generally or hard to answer I'd love to know if it's true for the simplest case where $X=\emptyset^3$.

Computable in $\omega$-REA degree but not double jump of finitely many columns

Suppose that $A$ is an $\omega$-REA set (so $A^{[n]}$ is r.e. in the prior columns). It is a well-known result that if each column of $A$ is computable then $A \leq_T \emptyset^2$ ($\emptyset^2$ can recover the computable index for each column from indices of prior columns and thus compute $A$).

A suggestive way to reformulate this statement is that, if each column in $A$ is computable and $(A^{[\leq n]})'' \ngeq_T X$ for all $n$ then $A \ngeq_T X$. Now you might hope to drop the requirement that the columns in $A$ be computable but this is trivially counterexampled by $\emptyset^\omega$. But what if we restrict $X$ to be $n$-REA in addition to dropping the requirement of computable columns?

I hypothesize the following, which would imply the result.

Hypothesis: If $X$ is arithmetic, $(A^{[\leq n]})'' \ngeq_T X$ and $A$ is an $\omega$-REA set then there is an upper bound $D$ of the sequence $A^{[\leq n]}$ with $D'' \ngeq_T X$.

The result would follow immediately since $D''$ can compute $A$ in the way mentioned at the start. However, I don't see any immediately obvious way to prove this or find a counterexample, so I figured I'd ask to see if there is something I'm missing. If the claim is either false generally or hard to answer I'd love to know if it's true for the simplest case where $X=\emptyset^3$.

added 9 characters in body; edited title
Source Link
Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331

Computable in w$\omega$-REA degree but not double jump of finietly many columns

Computable in w$\omega$-REA degree but not double jump of finietly many columns

Suppose that $A$ is an $\omega$-REA set (so $A^{[n]}$ is r.e. in the prior columns). It is a well know result that if each column of $A$ is computable then $A \leq_T \emptyset^2$ ($\emptyset^2$ can recover the computable index for each column from indices of prior columns and thus compute $A$).

A suggestive way to reformulate this statement is that, if each column in $A$ is computable and $(A^{[\leq n]})'' \ngeq_T X$ for all $n$ then $A \ngeq_T X$. Now you might hope to drop the requirement that the columns in $A$ be computable but this is trivially counterexampled by $\emptyset^\omega$. But what if we restrict $X$ to be $n$-REA in addition to dropping the requirement of computable columns?

I hypothesize the following which would imply the result.

Hypothesis: If $X$ is arithmetic, $(A^{[\leq n]})'' \ngeq_T X$ and $A$ is an $\omega$-REA set then there is an upper bound $D$ of the sequence $A^{[\leq n]}$ with $D'' \ngeq_T X$.

The result would follow immediately since $D''$ can compute $A$ in the way mentioned at the start. However, I don't see any immediately obvious way to prove this or s counterexample so I figured I'd ask to see if there is something I'm missing. If the claim is either false generally or hard to answer I'd love to know if it's true for the simplest case where $X=\emptyset^3$.

Computable in w-REA degree but not double jump of finietly many columns

Suppose that $A$ is an $\omega$-REA set (so $A^{[n]}$ is r.e. in the prior columns). It is a well know result that if each column of $A$ is computable then $A \leq_T \emptyset^2$ ($\emptyset^2$ can recover the computable index for each column from indices of prior columns and thus compute $A$).

A suggestive way to reformulate this statement is that, if each column in $A$ is computable and $(A^{[\leq n]})'' \ngeq_T X$ for all $n$ then $A \ngeq_T X$. Now you might hope to drop the requirement that the columns in $A$ be computable but this is trivially counterexampled by $\emptyset^\omega$. But what if we restrict $X$ to be $n$-REA in addition to dropping the requirement of computable columns?

I hypothesize the following which would imply the result.

Hypothesis: If $X$ is arithmetic, $(A^{[\leq n]})'' \ngeq_T X$ and $A$ is an $\omega$-REA set then there is an upper bound $D$ of the sequence $A^{[\leq n]}$ with $D'' \ngeq_T X$.

The result would follow immediately since $D''$ can compute $A$ in the way mentioned at the start. However, I don't see any immediately obvious way to prove this or s counterexample so I figured I'd ask to see if there is something I'm missing. If the claim is either false generally or hard to answer I'd love to know if it's true for the simplest case where $X=\emptyset^3$.

Computable in $\omega$-REA degree but not double jump of finietly many columns

Suppose that $A$ is an $\omega$-REA set (so $A^{[n]}$ is r.e. in the prior columns). It is a well know result that if each column of $A$ is computable then $A \leq_T \emptyset^2$ ($\emptyset^2$ can recover the computable index for each column from indices of prior columns and thus compute $A$).

A suggestive way to reformulate this statement is that, if each column in $A$ is computable and $(A^{[\leq n]})'' \ngeq_T X$ for all $n$ then $A \ngeq_T X$. Now you might hope to drop the requirement that the columns in $A$ be computable but this is trivially counterexampled by $\emptyset^\omega$. But what if we restrict $X$ to be $n$-REA in addition to dropping the requirement of computable columns?

I hypothesize the following which would imply the result.

Hypothesis: If $X$ is arithmetic, $(A^{[\leq n]})'' \ngeq_T X$ and $A$ is an $\omega$-REA set then there is an upper bound $D$ of the sequence $A^{[\leq n]}$ with $D'' \ngeq_T X$.

The result would follow immediately since $D''$ can compute $A$ in the way mentioned at the start. However, I don't see any immediately obvious way to prove this or s counterexample so I figured I'd ask to see if there is something I'm missing. If the claim is either false generally or hard to answer I'd love to know if it's true for the simplest case where $X=\emptyset^3$.

Source Link

Computable in w-REA degree but not double jump of finietly many columns

Suppose that $A$ is an $\omega$-REA set (so $A^{[n]}$ is r.e. in the prior columns). It is a well know result that if each column of $A$ is computable then $A \leq_T \emptyset^2$ ($\emptyset^2$ can recover the computable index for each column from indices of prior columns and thus compute $A$).

A suggestive way to reformulate this statement is that, if each column in $A$ is computable and $(A^{[\leq n]})'' \ngeq_T X$ for all $n$ then $A \ngeq_T X$. Now you might hope to drop the requirement that the columns in $A$ be computable but this is trivially counterexampled by $\emptyset^\omega$. But what if we restrict $X$ to be $n$-REA in addition to dropping the requirement of computable columns?

I hypothesize the following which would imply the result.

Hypothesis: If $X$ is arithmetic, $(A^{[\leq n]})'' \ngeq_T X$ and $A$ is an $\omega$-REA set then there is an upper bound $D$ of the sequence $A^{[\leq n]}$ with $D'' \ngeq_T X$.

The result would follow immediately since $D''$ can compute $A$ in the way mentioned at the start. However, I don't see any immediately obvious way to prove this or s counterexample so I figured I'd ask to see if there is something I'm missing. If the claim is either false generally or hard to answer I'd love to know if it's true for the simplest case where $X=\emptyset^3$.