Extension of embeddings on the recursively enumerable degrees modulo the cappable degrees
Xiaoding Yi · Cambridge University Press eBooks · 1996
It is shown that there is a non-trivial obstruction to block the extension of embeddings on the quotient structure of the recursively enumerable degrees modulo the cappable degrees. Therefore, Shoenfield's conjecture fails on that structure, which answers a question of Ambos- Spies, Jockusch, Shore, and Soare [1984], and Schwarz [1984] (also see Slaman [1994]). Introduction The recursively enumerable (r.e.) sets are these subsets of natural numbers (denoted ω) which can enumerated by an effective procedure (or a computable function from ω to ω). There is a notion of relatively computability (or Turing reducibility) among the r.e. sets (in fact, among all sets of natural numbers), which can view that one is more complicated or harder to compute than other. The equivalence classes under this notion of relatively computability of r.e. sets are called the r.e. (Turing) degrees. The set of all r.e. degrees (denoted R ) is made into a partial ordering with least (0, the equivalence class of all recursive sets) and greatest (0′, the equivalence class which contains the halting problem) elements in the natural way, namely, the reducibility relation between r.e. sets induces a partial ordering on degrees. It is readily shown that finite supremum always exists in R . Therefore, R forms an upper semilattice.