Search Results

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 …

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

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?

For the benefit of others, I emailed Shore and asked him about it and he told me that while he had assumed when he proved it that it wasn't a novel result he never actually found any earlier proof (mu …

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 …

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 …

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 …

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 …

Yes, it turns out that there is such an arithmetic (indeed 3-REA) non-trivial 2-lub. In fact, $\emptyset'''$ is such a degree. Consider the construction I give here in answer to this question. This …

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 …

Ok, so unfortunately the answer is no. I've attached a proof that builds a $\omega$-REA set such that $A^{[\leq n]}$ is low for all $n$ yet $A$ computes $\emptyset'' \oplus X$ where $X$ is a natural …

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 …

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 …

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 …