Downwards density in the n-computably enumerable Turing degrees and the uniform constructions
Mars M. Yamaleev · Mathematics and Theoretical Computer Science · 2024
In 1993, R. Downey and M. Stob showed that the downwards density of computably enumerable (c.e.) Turing degrees in the partial 2-c.e. Turing degrees cannot be obtained from a uniform construction. We generalize this result for any n > 2 and show that there is no a uniform construction for the downwards density of ( n − 1) -c.e. degrees in the structure of n -c.e. degrees. Moreover, we show that there is no a uniform construction for the downwards density in the n -c.e. degrees.