A Feiner Look at the Intermediate Degrees

Abstract

We say that a set $S$ is ${\Delta }_{(n)}^0(X)$ if membership of $n$ in $S$ is a ${\Delta }_n^0(X)$ question, uniformly in $n$. A set $X$ is low for $\Delta$-Feiner if every set $S$ that is ${\Delta }_{(n)}^0(X)$ is also ${\Delta }_{(n)}^0(\varnothing )$. It is easy to see that every low${}_n$ set is low for $\Delta$-Feiner, but we show that the converse is not true by constructing an intermediate c.e. set that is low for $\Delta$-Feiner. We also study variations on this notion, such as the sets that are ${\Delta }_{(bn+a)}^0(X)$, ${\Sigma }_{(bn+a)}^0(X)$, or ${\Pi }_{(bn+a)}^0(X)$, and the sets that are low, intermediate, and high for these classes. In doing so, we obtain a result on the computability of Boolean algebras, namely that there is a Boolean algebra of intermediate c.e. degree with no computable copy.