Intervals without Critical Triples
Peter A. Cholak, Rodney G. Downey, Richard A. Shore · Cambridge University Press eBooks · 2017
. This paper is concerned with the construction of intervals of computably enumerable degrees in which the lattice M 5 (see Figure 1) cannot be embedded. Actually, we construct intervals I of computably enumerable degrees without any weak critical triples (this implies that M 5 cannot be embedded in I, see Section 2). Our strongest result is that there is a low 2 computably enumerable degree e such that there are no weak critical triples in either of the intervals [0; e] or [e; 0 0 ]. 1. Introduction A set of natural numbers is computably (or recursively) enumerable if it is the range of a function computed by a Turing machine. We say one set of natural numbers, A, is Turing computable from another, B, if there is a Turing machine, which using an oracle for B, computes A. Equivalence classes under this reduction are called Turing degrees or just degrees. In this paper we will restrict our attention to those degrees which contain a computably enumerable set; the computably enumer...