A Feiner Look at the Intermediate Degrees

by Denis R. Hirschfeldt, Asher M. Kach, and Antonio Montalbán



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