Skip to main content
added caveat about non-trivial
Source Link

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? Do 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.

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? Do any?


[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}$?

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.

Added question marks
Source Link

Does every arithmetic degree below $0^\omega$ have a representative computable in $0^\omega$?

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? Do any?


[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}$?

Does every arithmetic degree below $0^\omega$ have a representative computable in $0^\omega$

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? Do any?


[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}$

Does every arithmetic degree below $0^\omega$ have a representative computable in $0^\omega$?

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? Do any?


[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}$?

Source Link

Does every arithmetic degree below $0^\omega$ have a representative computable in $0^\omega$

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? Do any?


[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}$