Affiliations: [a] Mathematics Department, University of Notre Dame du Lac, 255 Hurley Building, Notre Dame, IN 46556, USA | [b] Mathematics Department, Indiana University, Bloomington, Rawles Hall, 831 East 3rd St., Bloomington, IN 47405, USA
Note: [1] Thanks to two anonymous referees for many helpful comments and editing suggestions.
Note: [*] Cholak was partially supported by a Focused Research Group grant from the National Science Foundation of the United States, DMS-1854136.
Abstract: In 1982, Soare and Stob proved that if A is an r.e. set which isn’t computable then there is a set of the form A⊕We which isn’t of r.e. Turing degree. If we define a properly n+1-REA set to be an n+1-REA set which isn’t Turing equivalent to any n-REA set this result shows that every properly 1-REA set can be extended to a properly 2-REA set. This result was extended by Cholak and Hinman in 1994. They proved that every 2-REA set can be extended to a properly 3-REA set. This leads naturally to the hypothesis that every properly n-REA set can be extended to a properly n+1-REA set. Here we show this hypothesis is false and that there is a properly 3-REA set which can’t be extended to a properly 4-REA set. Moreover we show this set A can be Δ20.
Keywords: REA sets, recursively enumerable and above, Turing degree, recursively enumerable, computability theory, recursion theory
DOI: 10.3233/COM-210362
Journal: Computability, vol. 11, no. 3-4, pp. 241-267, 2022
