Nonuniformity of Downward Density in n-Computably Enumerable Turing Degrees
A. I. Talipova, Mars M. Yamaleev · Russian Mathematics · 2022
In 1993, R. Downey and M. Stob showed that the downward density of computably enumerable (c.e.) Turing degrees in the partial order of 2-c.e. Turing degrees cannot be proved by a uniform construction. In this paper their result is generalized for any $$n > 2$$ , and it is shown that there is no a uniform construction for the downward density of $$(n - 1)$$ -c.e. degrees in the structure of $$n$$ -c.e. degrees. Moreover, it is shown that there is no a uniform construction for downward density in the structure of $$n$$ -c.e. degrees.