Maximal pairs of computably enumerable sets in the computably Lipschitz degrees (Q1946505): Difference between revisions

Call \(A\) cl-reducible to \(B\) (computably Lipschitz reducible to \(B\)) if there are an oracle Turing machine \(M\), a use function for \(M\), and a constant \(k\) such that, for any \(n\), \(M[B]\) can determine whether or not \(n\in A\) by a computation using at most \(n+k\) steps. The relation was introduced in [\textit{R. G. Downey}, \textit{D. R. Hirschfeldt} and \textit{G. Laforte}, J. Comput. Syst. Sci. 68, No. 1, 96--114 (2004; Zbl 1072.03024)] as ``strong weak truth-table reducibility'', intended to be an instrument for measuring randomness of real numbers. It generates the cl-degrees. They are known not to be an upper semilattice [\textit{L. Yu} and \textit{D. Ding}, J. Symb. Log. 69, No. 4, 1163--1170 (2004; Zbl 1070.03028)]. The present paper studies \textit{maximal pairs} of c.e. cl-degrees, pairs with no c.e. cl-degree as common upper bound. Its main theorems: (1) A c.e. cl-degree that contains half of a maximal pair contains a maximal pair; (2) There is a Turing-complete set whose c.e. cl-degree is not half of a maximal pair, and ``any high c.e. Turing degree contains a c.e. cl-degree that is not half of a maximal pair''; (3) ``Above any c.e. cl-degree there is a maximal pair''; (4) There is a maximal pair that is also a minimal pair; (5) There is a pair of c.e. cl-degrees that has an upper bound but no least upper bound. Some open problems are given: (i) Characterize those c.e. Turing degrees (if there are any) in which only sets that are halves of maximal pairs are c.e.; (ii) What c.e. cl-degrees are the greatest lower bound of a maximal pair?