A Feiner Look at the Intermediate Degrees
Status: submitted
Availability: preprint
Abstract. We say that a set S is
Δ0(n)(X) if
membership of n in S is a
Δ0n(X) question,
uniformly in n. A set X is low for Δ-Feiner
if every set S that is
Δ0(n)(X)
is also Δ0(n)(∅) . It is
easy to see
that every lown set is low for Δ-Feiner, but we
show that the
converse is not true by constructing an intermediate c.e. set that is low
for Δ-Feiner. We also study variations on this notion, such as the
sets that are
Δ0(bn+a)(X),
Σ0(bn+a)(X), or
Π0(bn+a)(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.
drh@math.uchicago.edu