Search Results

Remember that an n-REA set is a set of the form $A_0 \oplus A_1 \oplus \cdots \oplus A_n$ with $A_n$ relatively r.e. in $A_m, m<n$ (so $A_0$ is r.e.) and that a degree is PA just if it computes a path …

I feel like there must be a classical result answering this question (or easily modified to do so) but a quick flip through Soare didn't produce anything so rather than waste time I figured I'd just a …

Remember, that an incomplete r.e. set $A$ is cuppable if there is an incomplete r.e. set $B$ such that $A\oplus B \equiv_T 0'$. It's relatively easy to build a low cuppable set but my question is whe …

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 …

Is there an r.e. set $A$ such that 0’ is cuppable relative to $A$? What about cappable? This is equivalent to asking if there is an r.e. $A$ such that 0’ is one half of a pair of $A$ r.e. non-$A$ co …

I’m mostly interested in this is the case where $A, \hat{A}$ are r.e. but the general case seems worth asking too. Suppose I have sets $A >_T \hat{A}$ with $A' \equiv_T \hat{A}'$. Does this imply tha …

In "A SPLITTING THEOREM FOR n−REA DEGREES" Shore and Slaman extend the following result of Sacks If $C$ is r.e., $D \leq_T C$ and $D, C \not\leq_T 0$ then there are sets $C_0, C_1$ such that $C \equ …

Just in case anyone else is a mere mortal and takes a moment to understand Slaman's answer here is a more spelled out version of his argument. I'll just do the capping side as it's the same argument …

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 …

Remember a degree $\mathbb{d}$ is the $n$-lub of $\mathbb{c}_j$ in the Turing degrees if it is the least element (not merely a minimal element) set of $\mathbb{c}^{(n)}$ such that $\mathbb{c}$ comput …

So I'm looking at the proof of the ZBC lemma in Odifreddi's Classical Recursion Theory volume 2 page 808 and I don't see why $ 0' \oplus C$ produced computes $B'$ as claimed. The positive requirement …

The answer is no. Every properly n-REA set for n < 3 (I believe Peter Cholak and I have shown this fails at 3 but could always fall apart in write-up) can be extended to a properly n+1 REA set by add …

Odifreddi doesn't give a cite (at least in proposition XI.2.10) for the proposition that every non-zero r.e. degree computes a 1-generic. What paper should I cite for this proposition?

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 …

Unfortunately, I believe I can show there are non-arithmetic $\omega$-REA degrees that aren't effectively $\omega$-REA. To this end we need to build $A$ to be $\omega$-REA with $A >_a 0$ to satisfy $$ …