1 Introduction↩︎

The concept of a weak reducibility on sets of natural numbers arises by combining two general notions developed in computability theory from the year 2002 onwards: lowness properties of sets [1], [2], and partial relativisation [3]. A lowness property formalises a particular aspect of computational simplicity of a set of natural numbers (henceforth simply called a set). Three paradigms have been proposed [4]: being weak as an oracle, computed by many oracles, and inert; see Section 1.2 below. A partial relativisation of a computability theoretic concept \(\mathcal{C}\) is obtained by relativising only certain constitutents of the concept to an oracle, while the remaining constituents, typically bounds on sizes of finite sets or on the number of changes of a computable approximation of a set, are left unrelativised. See [3] for examples. It is customary to use the term “\(\mathcal{C}\) by \(X\)" for a partial relativisation of \(\mathcal{C}\) to an oracle \(X\); the constituents of the concept that are relativised are assumed to be understood from the context. Each of these two general notions was obtained by crystalising mathematical intuition that developed through series of works; the citations above merely point to some early places (known to us) where the notions were formulated.

1.1 Weak reducibilities↩︎

A pre-ordering \(\le_W\) on sets is called a weak reducibility if \(\le_W\) is arithmetical, \(X \le_{\mathrm{T}}Y\) implies \(X \le_W Y\), and \(X' \not \le_W X\) for each \(X\). This terminology [5] is chosen to be opposite to the terminology of strong reducibilities of Odifreddi [6] (such as truth table reducibility).

Given an arithmetical lowness property \(\mathcal{L}\) and a proper choice of its partial relativisation, the binary relation “\(A\) is in \(\mathcal{L}\) by \(B\)" tends to be a weak reducibility (in particular, it is transitive, and implied by \(\le_{\mathrm{T}}\)). We consider two examples. The first is the much studied LR-reducibility [1]. Let \(\rm \textsf{MLR}^X\) be the class of Martin-Löfrandom sets relative to \(X\), and recall that \(A\) is low for ML-random if \(\rm \textsf{MLR}\subseteq\rm \textsf{MLR}^A\). LR-reducibility \(\le_{{\mathrm{\scriptsize{LR}}}}\) is obtained by partially relativising this to \(B\): for \(A \le_{{\mathrm{\scriptsize{LR}}}}B\) to hold, one requires that \(\rm \textsf{MLR}^B\subseteq\rm \textsf{MLR}^A\), rather than the full relativisation to \(B\), which would be \(\rm \textsf{MLR}^B\subseteq\rm \textsf{MLR}^{A\oplus B}\).

As a second example, more relevant to the present paper, let us consider the lowness property of being jump traceable. Recall that an order function is an unbounded, nondecreasing computable function on \({\mathbb{N}}\). A c.e.trace is a uniformly c.e. sequence \({\left\langle{T_n}\right\rangle}_{n\in {\mathbb{N}}}\) of finite sets. For an order function \(h\), such a trace is \(h\)-bounded if \(|T_n| \le h(n)\) for each \(n\). A trace is computably bounded if it is \(h\)-bounded for some computable order function \(h\).

Here \(J^A\) is a universal \(A\)-partial computable function. It is easy to see that each jump traceable set is \(\mathrm{GL}_1\) [5]. The appropriate partial relativisation to an oracle \(B\), namely \(A\) is jump traceable by \(B\), asks that the trace be c.e.in \(B\), but still only \(J^A\), rather than \(J^{A\oplus B}\), is traced, and the order function bounding the trace is still computable. This yields the reducibility \(\le_\mathrm{JT}\), introduced in [5], with transitivity verified in 8.4.14. To check that \(\le_\mathrm{JT}\) is a weak reducibility, note that it is clearly \(\Sigma^0_{4}\), and implied by \(\le_{\mathrm{T}}\). Relativising the fact that each jump traceable is \(\mathrm{GL}_1\) one shows that \(X' \not \le_\mathrm{JT} X\) for each set \(X\).

The class of jump traceable sets has a perfect \(\Pi^0_{1}\) subclass. It admits superhigh members [8], so it cannot be considered a strong lowness property. If one requires that \(J^A\) has an \(h\)-bounded trace for every order function \(h\), one obtains the notion of strong jump traceability, introduced in [9]. This notion has been studied extensively [4], [10]–[16], with applications outside randomness [17]; see [18] for a survey. The central notion for this paper is a corresponding weak reducibility.

Note that a set \(A\) is strongly jump traceable iff \(A\le_{\mathrm{\scriptsize{SJT}}}\emptyset\). An argument similar to [16] or [5] shows that the relation \(\le_{\mathrm{\scriptsize{SJT}}}\) is transitive. Clearly \(X' \not \le_{\mathrm{\scriptsize{SJT}}}X\) for each set \(X\), because this already holds for \(\le_\mathrm{JT}\). The relation \(\le_{\mathrm{\scriptsize{SJT}}}\) is \(\Pi^0_{5}\). We also note that \(\le_{\mathrm{\scriptsize{SJT}}}\) is genuinely weaker than \(\le_{\mathrm{T}}\), in the sense that for each set \(B\) there is a set \(C >_T B\) such that \(C \le_{\mathrm{\scriptsize{SJT}}}B\). To see this, by relativisation of a result in [9] let \(A\) be a set such that \(A \not \le_{\mathrm{T}}B\) and \(A\) is strongly jump traceable relative to \(B\), and let \(C= A\oplus B\). Then for each order function \(h\) relative to \(B\), \(J^C\) has a \(B\)-c.e.trace bounded by \(h\).

1.2 Three lowness paradigms↩︎

As mentioned, three lowness paradigms for a set \(A\subseteq{\mathbb{N}}\) have beeen proposed. We give a brief summary; see [4] for more detail.

1. Weak as an oracle:
   \(A\) is not very useful as an oracle for Turing machines.

2. Computed by many oracles:
   the collection of oracles computing \(A\) is large. The class of such oracles is null unless \(A\) is computable, so largeness must be taken in a more specific sense. For instance, \(A\) is called a base for ML-randomness if there is an oracle in \(\rm \textsf{MLR}^A\) computing \(A\).

3. Inert:
   Recall that the Shoenfield limit lemma states that a set \(A\) is \(\Delta^0_2\) iff it can be computably approximated with a finite number of changes. Inertness means that there is such an approximation where the number of changes is in a sense small.

It is often interesting to ask whether a given lowness property has equivalent definitions according to two or even all three paradigms. We examine this for the property that a set \(A\) is low for ML-randomness: every ML-random is ML-random relative to \(A\).

1. The definition follows Paradigm (1). Another equivalent characterisation according to this paradigm is lowness for \(K\): there is a constant \(d\) such that \(K(x)\le K^A(x) + d\) for each string \(x\), where \(K\) denotes prefix free descriptive string complexity.

2. \(A\) is low for ML-randomness iff it is a base for ML-randomness, which gives a definition according to Paradigm (2) (see [5] for details and references).

3. \(A\) is low for ML-randomness iff it has a computable approximation with few changes in the sense of the cost function \(\mathbf{c}_\Omega(x,s) = \Omega_s- \Omega_x\) by [20] ; this follows Paradigm (3). An earlier version of this result for a cost function \(\mathbf{c}_K\) dates back to [1].

We note that lowness for ML-randomness also coincides with \(K\)-triviality, a property expressing that the set is far from random [1], [21].

Strong jump traceability by its definition follows Paradigm (1). In [4], [11] an equivalent characterisation following Paradigm (2) is given: a set is strongly jump traceable if and only if it is computed by every \(\omega\)-c.a.(or every superlow, or every superhigh) ML-random set¹. A related result appears in [22]: a set is strongly jump-traceable if and only if it is computable from every infinite “section” of Chaitin’s \(\Omega\). In [14] it is shown that a c.e.set is strongly jump traceable iff it obeys all benign cost functions; this yields a characterisation in terms of Paradigm (3).

1.3 Characterising SJT-reducibility according to the three paradigms.↩︎

In this paper, we suggest to apply the three paradigms not only to lowness properties, but also to the corresponding weak reducibilities. Our main results show that, under certain restrictions, the characterisations of the strongly jump traceable sets according to the three paradigms can be lifted to the case of the weak reducibility \(\le_{\mathrm{\scriptsize{SJT}}}\).

The definition of \(\le_{\mathrm{\scriptsize{SJT}}}\) follows paradigm (1), as does the definition of strong jump-traceability itself. It indicates computational weakness of the oracle \(A\) compared to \(B\), because \(J^A(n)\) is caught in an “arbitrarily small” trace set enumerated by \(B\). Our first result gives a characterisation according to Paradigm (3): for every benign cost function \(\mathbf{c}\), the set \(B\) computes an approximation of \(A\) for which the total cost of changes in the sense of \(\mathbf{c}\) is finite. For the precise definitions of the notation \(A\models_B \mathbf{c}\) and of benign cost functions, see 3 4 below.

We prove 2 in 2.

Recall that \(A \subseteq{\mathbb{N}}\) is \(K\)-trivial if \(K(A\! \upharpoonright_{n}) \le^+K(n)\) for each \(n\). There are strongly jump traceable sets outside the computable [9], yet the class lies far inside the \(K\)-trivials [12], [23]. Recent work [22], [23] reveals a rich structure inside the \(K\)-trivial Turing degrees, based on both cost functions and computability from various random sets. This, and the existing relationship between strong jump-traceability and \(K\)-triviality, leads us to expect that the weak reducibility \(\le_{\mathrm{\scriptsize{SJT}}}\) will also shed new light on the \(K\)-trivial sets and degrees. Our second result gives a variety of characterisations of \(\le_{\mathrm{\scriptsize{SJT}}}\) within the \(K\)-trivial sets, according to Paradigm (2). We quickly recall the definition of some other classes that will be required.

• A set \(Y\) is superhigh if \(\emptyset'' \le_{\mathrm{tt}}Y'\).

• A set \(Y\) is \(\omega\)-c.a.if its characteristic function is \(\omega\)-c.a.; equivalently if \(Y\le_{\mathrm{wtt}}\emptyset'\).

• A set \(Y\) is superlow if \(Y'\le_{\mathrm{tt}}\emptyset'\); equivalently, if \(Y'\) is \(\omega\)-c.a.

• Given an infinite set \(R\subseteq {\mathbb{N}}\), let \(\Omega_R\) be the result of removing from \(\Omega\) all the bits in locations not in \(R\). As mentioned above, here \(\Omega\) is any left-c.e.ML-random set.

Note that every \(K\)-trivial set is jump traceable. This was first shown by Nies [1], improving a result of Zambella (see [24]). For weak Demuth randomness, see for example [25]; we give a detailed definition in 3 (6).

1.4 The difficulties with partial relativisation↩︎

As the restrictions in the two theorems above indicate, lifting the various characterisations of strong jump traceability to the weak reducibility \(\le_{\mathrm{\scriptsize{SJT}}}\) is far from straightforward. Since arguments in computability theory almost always relativise, the difficulty lies in the fact that \(\le_{\mathrm{\scriptsize{SJT}}}\) is a partial relativisation.

One of the difficulties is in modifying adaptive arguments. In such an argument, we typically work with a strongly jump-traceable oracle \(A\), and define an \(A\)-partial computable function \(\psi\). By the recursion theorem, during the construction we have access to a c.e.trace \({\left\langle{T_n}\right\rangle}_{n\in {\mathbb{N}}}\) for \(\psi\), and we use that trace to dynamically define \(\psi\): the definition of \(\psi\) adapts to the enumerations appearing in \({\left\langle{T_n}\right\rangle}_{n\in {\mathbb{N}}}\). When \(B\ne\emptyset\), more specifically, when \(A\) does not compute \(B\), the enumeration of \({\left\langle{T_n}\right\rangle}_{n\in {\mathbb{N}}}\) is only \(B\)-computable, and so \(A\) does not have such access to the trace. In a full relativisation to \(B\) we use \(A\oplus B\) rather than \(A\), which allows us to use adaptive arguments.

Similar difficulties occur in the study of other weak reducibilities such as \(\le_{{\mathrm{\scriptsize{LR}}}}\) mentioned above. However, our characterisation in 2 will show that this problem does not occur with \(\le_{\mathrm{\scriptsize{SJT}}}\) (under the same assumption on \(A\oplus B\)):

We discuss 4, and other corollaries of our characterisations, in 4. Note that since Turing reducibility implies \(\le_{\mathrm{\scriptsize{SJT}}}\), \(A\oplus B\le_{\mathrm{\scriptsize{SJT}}}B\) if and only if \(A\oplus B \equiv_{\mathrm{\scriptsize{SJT}}} B\). Regarding \(\le_{\mathrm{\scriptsize{SJT}}}\) and joins, see 4, in particular 7 and the discussion thereafter.

2 Benign cost functions↩︎

We recall the definitions of cost functions and approximations obeying them; for background see [5] or [20].

One views \(\mathbf{c}(x,s)\) as the cost of changing an approximation at \(x\) as the least element, at a stage \(s\). The limit condition says that for large enough \(x\), changing \(A(x)\) at any stage is as cheap as one likes.

For example, the cost function \(\mathbf{c}_{\Omega}(x,s) = \Omega_s - \Omega_x\) is benign, with the bound for \(\varepsilon\) being \(1/\varepsilon\). Here \((\Omega_s)\) is an increasing computable approximation of the left-c.e., ML-random sequence \(\Omega\).

2.1 A proof of 4↩︎

We first explain how 4 follows from 2. In one direction, suppose that \(A\oplus B \le_{\mathrm{\scriptsize{SJT}}}B\); since \(A\le_{\mathrm{T}} A\oplus B\) and \(\le_{\mathrm{T}}\) implies \(\le_{\mathrm{\scriptsize{SJT}}}\), we have \(A\le_{\mathrm{\scriptsize{SJT}}}B\).

In the other direction, suppose that \(A\oplus B\) is jump-traceable and that \(A\le_{\mathrm{\scriptsize{SJT}}}B\). The assumption on \(A\oplus B\) implies that both \(A\) and \(B\) are jump-traceable, so 2 applies. Hence, \(A\models_B \mathbf{c}\) for every benign cost function \(\mathbf{c}\). This implies that \(A\oplus B\models_B \mathbf{c}\) for every benign cost function \(\mathbf{c}\): fix such a cost function \(\mathbf{c}\). Suppose that \((A_s)\) is a \(B\)-computable approximation of \(A\) witnessing that \(A\models_B \mathbf{c}\). Let \(C_s = A_s\oplus B\). The fact that \(\mathbf{c}\) is monotonic implies that the total \(\mathbf{c}\)-cost of \((C_s)\) is bounded by the total \(\mathbf{c}\)-cost of \((A_s)\), and so is finite.

The assumption on \(A\oplus B\), together with the other direction of 2, now shows that \(A\oplus B\le_{\mathrm{\scriptsize{SJT}}}B\).

In the next two sections we give a proof of 2.

2.2 Proof of (b)\(\Rightarrow\)(a) of 2↩︎

In this direction, in fact, we do not make use of the assumption that \(B\) is jump-traceable. [14] gives this direction for the case \(B=\emptyset\), under the extra assumption that \(A\) is c.e.That proof does not partially relativise; however, we can now present a simpler argument that applies more generally.

Suppose that \(A\) is jump-traceable, and that \(A\models_B \mathbf{c}\) for every benign cost function \(\mathbf{c}\). Let \(h\) be an order function; we show that \(J^A\) has a \(B\)-c.e.trace bounded by \(h\). We define an \(A\)-partial computable function \(\psi\) by setting \(\psi(n) = \sigma\) if \(J^A(n)\!\!\downarrow\) with use \(\sigma\prec A\). Since \(A\) is jump-traceable, the partial function \(\psi\) has a c.e.trace \({\left\langle{V_n}\right\rangle}_{n\in {\mathbb{N}}}\), bounded by some computable order function \(g\).

We define a cost function \(\mathbf{c}\) as follows: \[\mathbf{c}(x,s) = \max \left\{ 1/h(n) \,:\, \exists \sigma\in V_{n,s}\text{ s.t. }|\sigma|>x \right\}.\] The function \(\mathbf{c}\) is monotonic: the fact that \(V_{n,s}\subseteq V_{n,t}\) when \(s<t\) implies that it is increasing in the second variable; it is clearly decreasing in the first variable. It satisfies the limit condition because \(h\) is unbounded, and each \(V_n\) is finite. We show that \(\mathbf{c}\) is benign. Let \(\varepsilon>0\). Suppose that \(s< y \le t\) and that \(\mathbf{c}(y,t)\ge \varepsilon\). There is some \(n\) with \(1/h(n)\ge \varepsilon\) and some \(\sigma\in V_{n,t}\) with \(|\sigma|>y\). Since \(|\sigma|>s\) we may assume that \(\sigma\notin V_{m,s}\) for any \(m\). Hence, the length of a sequence \(x_1< s_1 \le x_2 < s_2 \le x_3 < s_3 \le \cdots\) with \(\mathbf{c}(x_i,s_i)\ge \varepsilon\) is bounded by the size of \[\bigcup \left\{ V_{n} \,:\, 1/h(n)\ge \varepsilon\right\},\] which is bounded by \[\sum \left\{ g(n) \,:\, 1/h(n)\ge \varepsilon\right\}.\] Since \(h\) is computable, non-decreasing and unbounded, and \(g\) is computable, this sum is finite and can be obtained computably from \(\varepsilon\).

Now suppose that \((A_s)\) is a \(B\)-computable approximation whose total \(\mathbf{c}\)-cost is finite; by ignoring finitely many stages of the approximation, we may assume that the total cost is bounded by 1. For each \(n\), let \(T_n\) be the set of values \(J_s^{A_s}(n)\) for \(s\) such that \(J_s^{A_s}(n)\downarrow\) with use \(\sigma\prec A_s\), and \(\sigma\in V_{n,s}\). If \(J^A(n)\downarrow\) then since \(\psi(n)\in V_n\), we have \(J^A(n)\in T_n\). Let \(s<t\) be two stages responsible for enumerating new values into \(T_n\); let \(\sigma\prec A_s\) with \(J_s^{A_s}(n) = J^\sigma(n)\) and \(\sigma\in V_{n,s}\). By definition, \(\mathbf{c}(x,s)\ge 1/h(n)\) for every \(x<|\sigma|\). Since \(J_t^{A_t}(n)\ne J_s^{A_s}(n)\), we have \(\sigma\nprec A_t\), so there is some stage \(r\) with \(s\le r <t\) and some \(x<|\sigma|\) such that \(A_r(x)\ne A_{r+1}(x)\). Thus, the contribution of stage \(r\) to the total \(\mathbf{c}\)-cost of the approximation \((A_s)\) is at least \(1/h(n)\). This shows that \(|T_n|\le h(n)+1\). Replacing \(h\) by \(h-1\) gives the desired result.

2.3 Proof of (a)\(\Rightarrow\)(b) of 2↩︎

We turn to the proof of the harder direction of 2. The case \(B=\emptyset\) is Theorem 1.12 of [11]. That argument is adaptive; we overcome this by using the jump-traceability of \(B\). Very roughly, we define an \(A\)-partial computable function \(\Phi^A\), which will have a \(B\)-c.e.trace \({\left\langle{U_x^B}\right\rangle}_{x\in {\mathbb{N}}}\). Instead of directly defining values of \(\Phi^A\) in reaction to elements being enumerated into the trace, we use the fact that \(B\) is jump-traceable to “trace the trace”; we will have a c.e.trace \({\left\langle{V_y}\right\rangle}_{y\in {\mathbb{N}}}\), with no oracle, that essentially traces values in \({\left\langle{U_x^B}\right\rangle}_{x\in {\mathbb{N}}}\), and we define \(\Phi^A\) in reaction to values showing up in \({\left\langle{V_y}\right\rangle}_{y\in {\mathbb{N}}}\). The thing to note is that the size of \({\left\langle{U_x^B}\right\rangle}_{x\in {\mathbb{N}}}\) will be bounded by a very slow-growing order function, making use of the assumption \(A\le_{\mathrm{\scriptsize{SJT}}}B\). However, we do not control the computable bound on the size of \({\left\langle{V_y}\right\rangle}_{y\in {\mathbb{N}}}\); this bound can grow very quickly, as the assumption is only that \(B\) is jump-traceable, not strongly so. Observe that in this direction, \(A\) being jump-traceable follows from \(B\) being jump-traceable and \(A\le_{\mathrm{\scriptsize{SJT}}}B\), since the latter implies \(A\le_{\mathrm{JT}} B\).

We will need a combinatorial lemma.

This can be proved by induction on \(n\); we omit the details. The extreme case is when the nodes \(v_i\) form a chain (they are all comparable).

Fix a benign cost function \(\mathbf{c}\). There is an \(\omega\)-c.a.function \(f\) such that \(c(f(n)) < 2^{-n}\) for all \(n\). There is a computable binary function, also denoted \(f\), such that \(\lim_s f(n, s) = f(n)\) for all \(n\), and such that for each \(n\), \(|\{ f(n, s) : s \in \omega\}| \le g(n)\), where \(g\) is some total computable function. We may assume that \(f(n,s)\) is non-decreasing in both \(n\) and \(s\).

Let us discuss the structure of the argument. It has two steps:

1. Enumeration of the functionals \(\Phi\) and \(\Psi\);

2. Using the results of (1) to define the approximation of \(A\).

The first step is a computable construction, and as we later discuss, it has to be uniform in the indices for \(\Phi\) and \(\Psi\). The second step is computable in \(B\), and uses the correct indices of \(\Phi\) and \(\Psi\), so is non-uniform in that sense too.

As discussed, the argument is adaptive, in that in the definition of \(\Phi\) and \(\Psi\), we will make use of a trace \({\left\langle{V_y}\right\rangle}_{y\in {\mathbb{N}}}\) that traces \(\Psi^B\), and an oracle trace \({\left\langle{U_x^-}\right\rangle}_{x\in {\mathbb{N}}}\) such that \({\left\langle{U_x^B}\right\rangle}_{x\in {\mathbb{N}}}\) traces \(\Phi^A\). Working with partial functions allows us to achieve this using the recursion theorem (as in [10]), however the method of a universal trace would also work here (see for example [14]).

The general idea (as in [11]) is to test potential initial segments of \(A\) by setting \(\Phi^\sigma(x)=\sigma\) for all \(\sigma\) of some particular length \(\ell\), on a variety of locations (inputs) \(x\). When \(B=\emptyset\), we can observe the result of such a test by seeing which \(\sigma\) are enumerated into \(U_x\); these values are preferred to others. The test is more useful when the bound on \(|U_x|\) is smaller, for example, when \(|U_x|=1\) we know that the unique \(\sigma\) that appears in \(U_x\) must be an initial segment of \(A\). We will start by testing the length \(\ell = f(n)\) on inputs \(x\) with \(|U_x|\le n\). Of course, we do not know the final value \(f(n)\), so we will need to test all lengths \(f(n,s)\), for all \(s\), on such inputs \(x\). Once we test a certain length on \(x\), we cannot use the same input \(x\) again for other lengths, so we need to ensure that we have sufficiently many \(x\) with \(|U_x|\le n\). Luckily, we control the bound on the size of \(U_x\), and we also know that we will encounter at most \(g(n)\) many values \(f(n,s)\), so this allows us to reserve sufficiently many \(x\) for this purpose.

The heart of the construction is a promotion process for various lengths that we test. When \(|U_x|>1\), we may get more than one result, \(\sigma_0\) and \(\sigma_1\), both enumerated in \(U_x\), and we need to devise a procedure that will tell us which of these we will believe more. In such a situation, we will (very roughly) promote the length \(\ell = |\sigma_0| = |\sigma_1|\) from level \(n\) testing to level \((n-1)\)-testing, which gives us stronger results (the actual details will be a bit different). To know that we have sufficiently many locations \(x\) for these extra tests, we need to bound the number of lengths promoted from level \(n\) to level \(n-1\). To do this, some of our tests will not use a single location \(x\), but many such locations, and we will only trust some \(\sigma\) if it appears in all \(U_x\) on which it was tested.

This process of promotion is where the construction becomes adaptive: based on enumerations into various \(U_x\), we decide to make further tests, defining more values of \(\Phi^A\). The overall structure of our construction, when \(B\ne \emptyset\), is the same, except that, as discussed, we cannot examine \(U_x^B\) during the construction. Rather, for any oracle \(Y\) (uniformly), we will define \(\Psi^Y\) while examining \({\left\langle{U_x^Y}\right\rangle}_{x\in {\mathbb{N}}}\). As mentioned, the whole construction of \(\Phi\) and \(\Psi\) will also, adaptively, examine values in another trace \({\left\langle{V_y}\right\rangle}_{y\in {\mathbb{N}}}\) (that has no oracle, and traces the “correct” \(\Psi^B\)).

For the definition of \(\Psi\), we computably partition \({\mathbb{N}}\) into sets \(R_x\) (for \(x\in {\mathbb{N}}\)) and \(Q_n\) (for \(n\in {\mathbb{N}}\)), such that \(|R_x| = x\) and \(|Q_n| = n\). We will shortly see how using the recursion theorem, during the construction, we have a c.e.trace \({\left\langle{V_y}\right\rangle}_{y\in {\mathbb{N}}}\) for \(\Psi^B\), and a computable bound \(h\) of \({\left\langle{V_y}\right\rangle}_{y\in {\mathbb{N}}}\).

Given \(h\), for the purpose of defining \(\Phi\), we now computably partition \({\mathbb{N}}\) to sets \(I_n\) and \(J_n\), so that: \[|I_n| = g(n) + \sum \big\{ h(y)\,:\, y\in Q_{n+1} \big\},\] and \(|J_n| = 2^{r_n}\), where \[r_n = \sum \Big\{ h(y) \,:\, y\in \bigcup_{x\in I_n} R_x \Big\}.\]

It would seem that \({\left\langle{V_y}\right\rangle}_{y\in {\mathbb{N}}}\), \(h\) and \({\left\langle{U_x^-}\right\rangle}_{x\in {\mathbb{N}}}\) are provided by the recursion theorem in a straightforward way. However, we note that \(h\) depends on the index of \(\Psi\), and that in general, the assumption \(A\le_{\mathrm{\scriptsize{SJT}}}B\) does not allow us to uniformly, given an order function \(k\), obtain a \(k\)-bounded trace of \(J^A\) (using a universal trace we can obtain such a trace but which may omit tracing finitely many values of \(\Phi^A\), which will amount to the same thing as we do here). We do the following.

We start with a c.e.trace of \(J^B\), bounded by some order function \(\tilde{h}\). For each \(e\), let \(h^e(y) = \tilde{h}(e,y)\). Assuming that \(J^Y(e,y) = \Phi_e^Y(y)\) for all \(Y\), \(e\) and \(y\), this gives us, uniformly in \(e\), the index of a c.e.trace \({\left\langle{V_y^e}\right\rangle}_{y\in {\mathbb{N}}}\) of \(\Psi_e^B\) bounded by \(h^e\).

The definition above then gives us, for each \(e\), a partition of \({\mathbb{N}}\) to sets \(I_n^e\) and \(J_n^e\) (\(n \in {\mathbb{N}}\)), using the bound \(h^e\). This allows us to compute an order function \(k\) such that for all \(d\), \(e\), \(n > {\left\langle{d,e}\right\rangle}\) and \(x\in I^e_n\cup J^e_n\), we have \(k(d,x)\le n\). Fix a \(k\)-bounded, \(B\)-c.e.trace \({\left\langle{\tilde{U}_x^B}\right\rangle}_{x\in {\mathbb{N}}}\) of \(J^A\); we may assume that for any oracle \(Y\), \({\left\langle{\tilde{U}_x^Y}\right\rangle}_{x\in {\mathbb{N}}}\) is \(k\)-bounded. This allows us to compute, uniformly in \(d\) and \(e\), a c.e.index of an oracle trace \({\left\langle{U_x^-}\right\rangle}_{x\in {\mathbb{N}}}\) that satisfies the required conditions when \(\Psi=\Psi_e\) and \(\Phi = \Phi_d\), where \(o = {\left\langle{d,e}\right\rangle}\).

By the recursion theorem, during the construction we know the indices \(d\) and \(e\), and so the number \(o\), the sets \(I_n\) and \(J_n\), and c.e.indices of \({\left\langle{V_y}\right\rangle}_{y\in {\mathbb{N}}}\) and \({\left\langle{U_x^-}\right\rangle}_{x\in {\mathbb{N}}}\), as promised. This shows [cl:witzi].

We are ready to give the details of the construction of \(\Phi\) and \(\Psi\). The definition of \(\Psi\) on the sets \(R_x\) is immediate:

• For all \(n>o\), for all \(x\in I_n\), for every oracle \(Y\), for all \(i<n\), if \(\ell\) is the \(i\)th number enumerated into \(U_x^Y\), and \(y\) is the \(i\)th element of \(R_x\), then we define \(\Psi^Y(y) = \ell\).

Note that we may assume that \(x\in I_n\) implies \(x\ge n\), so setting \(|R_x| = x\) is certainly sufficient to make these definitions, recalling that \(|U_x^Y|\le n\) when \(n>0\) and \(x\in I_n\).

We will have a module for each \(n > o\). This module can perform the following actions:

• Test a length on \(I_n\);

• Test a string on \(J_n\);

• For any oracle \(Y\), declare that \(Y\) believes that a length \(\ell\) should be promoted;

• Promote some lengths to the \((n-1)\)-module.

We describe what each of these means, when these actions are performed, and argue that we can indeed perform these actions.

Promoting lengths↩︎

Let \(n>o\).

• The \(n\)-module promotes every \(\ell\in \bigcup_{y\in Q_n} V_y\).

This definition applies even to the smallest module \(n = o+1\), however, for this module, no actual action will be taken.

Testing lengths on \(I_n\)↩︎

• At stage \(0\), the \(n\)-module tests \(f(n,0)\) on \(I_n\). At stage \(s>0\), if \(f(n,s)\ne f(n,s-1)\), the \(n\)-module tests \(f(n,s)\) on \(I_n\). Finally, if at some stage \(s\), the \((n+1)\)-module promotes a length \(\ell\), then the \(n\)-modules tests \(\ell\) on \(I_n\).

• Testing a length \(\ell\) on \(I_n\) at stage \(s\) means: choose some unused \(x\in I_n\), and define \(\Psi^\sigma(x)=\sigma\) for all binary strings \(\sigma\) of length \(\ell\).

We need to argue that such a fresh \(x\) can always be chosen; that is, we need to show that the \(n\)-module will test at most \(|I_n|\) many lengths during the entire construction. The number \(g(n)\) bounds the number of lengths \(f(n,s)\) ever tested on \(I_n\). By (ii), at most \(\sum \left\{ h(y) \,:\, y\in Q_{n+1} \right\}\) many lengths are every promoted by the \((n+1)\)-module. So the definition of \(|I_n|\) ensures that it is large enough.

Testing strings on \(J_n\)↩︎

• The \(n\)-module tests on \(J_n\) every string in \(\bigcup_{x\in I_n} \bigcup_{y\in R_x} V_y\).

Note that the \(n\)-module will test at most \(r_n\) many strings during the construction. Since \(|J_n| = 2^{r_n}\), for the purposes of such testing, we identify \(J_n\) with \(\{0,1\}^{r_n}\), which we think of as a hypercube of side length 2 and dimension \(r_n\). We let \(d=0,1,\dots, r_n-1\) denote the axes of this hypercube; for \(d<r_n\) we let \(J_n(d) = \{ \tau \in J_n : \tau(d) = 0\}\). This is one half of a split of the hypercube into two pieces orthogonal to axis \(d\).

• Testing a string \(\sigma\) on \(J_n\) means the following. We choose an unused axis \(d\) and define \(\Phi^\sigma(x) = \sigma\) for all unused \(x\in J_n(d)\).

Now (v) ensures that indeed, there will always be an unused axis to choose.

Seeking promotion↩︎

Let \(n>o\) and let \(Y\) be an oracle.

• We say that \(Y\) confirms a string \(\sigma\) tested on \(J_n\) if \(\sigma\in U_x^Y\) for every \(x\in J_n\) on which we defined \(\Phi^\sigma(x)=\sigma\).

• Let \(s\) be a stage; let \(\ell\) be the longest length which \(Y\) believed should be promoted prior to stage \(s\). Suppose that there are two strings, \(\sigma_0\) and \(\sigma_1\), of the same length, such that:

  • \(\sigma_0\restriction{\ell} = \sigma_1\restriction{\ell}\); and

  • \(Y\) confirms both \(\sigma_0\) and \(\sigma_1\) on \(J_n\) at stage \(s\).

  Then we say that \(Y\) believes that the length \(|\sigma_0|= |\sigma_1|\) should be promoted by the \(n\)-module.

• The action taken then is: if \(m\) is the \(i\)th length that \(Y\) believes should be promoted by the \(n\)-module, and \(i<n\), and \(y\) is the \(i\)th element of \(Q_n\), then we define \(\Psi^Y(y) = m\).

We remark that it is quite possible that some oracles will believe that more than \(n\) many lengths should be promoted by the \(n\)-module. However this will not be the case for \(Y=B\), as the next claim states.

We presented the construction in a way that makes it easier to show that it can indeed be performed. It would be good, though, to follow the steps in order:

1. A length \(\ell = f(n,s)\) is tested on \(I_n\); this defines \(\Phi\) on an element of \(I_n\) ((iii) and (iv) above).

2. This prompts strings of length \(\ell\) to appear in \(U_x^Y\), and we make a definition of \(\Psi\) on an element of \(y\in R_x\) (i).

3. This prompts some strings to appear in \(V_y\); in turn, these strings are tested on \(J_n\) ((v) and (vi)).

4. This prompts strings to show up in various \(U_x^Y\) (for \(x\in J_n\)), and \(Y\) believes that some length \(\ell\) should be promoted; a definition of \(\Psi^Y(y)\) for some \(y\in Q_n\) is made (with value \(\ell\), not a string of length \(\ell\)) ((vii), (viii) and (ix)).

5. This prompts lengths to show up in \(V_y\), and the \(n\)-module promotes them (ii). We are now back to step (1) for the \((n-1)\)-module for this promoted length.

This completes the description of the construction of \(\Phi\) and \(\Psi\).

It follows that for every length \(\ell\) which \(B\) believes should be promoted by the \(n\)-module, there is a corresponding \(y\in Q_n\) such that \(\Psi^B(y)= \ell\). Since \({\left\langle{V_y}\right\rangle}_{y\in {\mathbb{N}}}\) traces \(\Psi^B\), \(\ell\in V_y\). Thus, every length which \(B\) believes should be promoted is eventually promoted.

We now proceed to the second part of the argument, in which we fix \(Y=B\); the following construction is computable relative to \(B\).

Let \(\hat{\ell}\) be the longest length which \(B\) believes the \(o+1\) module should promote. Nonuniformly, fix \(A\! \upharpoonright_{\hat{\ell}}\). Let \(L(n,s)\) be the set of lengths being tested by the \(n\) module at stage \(s\) (tested on \(I_n\)). At a stage \(s\), define a partial sequence \(\sigma_n^s\) for \(o \le n \le s\) recursively:

• \(\sigma_o^s = A\! \upharpoonright_{\hat{\ell}}\);

• Given \(\sigma_n^s\), if there is some length which \(B\) believes should be promoted by the \(n+1\) module at stage \(s\), but which is not yet promoted, then leave \(\sigma_{n+1}^s\) undefined. Otherwise, define \(\sigma_{n+1}^s\) to be a string \(\rho\) extending \(\sigma_n^s\) with \(|\rho| = \max L(n+1,s)\), and such that for each \(\ell \in L(n+1, s)\), \(\rho\! \upharpoonright_{\ell}\) is confirmed by \(B\) at \(n+1\) by stage \(s\), if such a string \(\rho\) exists.

Define a sequence of stages \((s_t)_{t \in \omega}\) as follows:

• \(s_0 = o\).

• Given \(s_t\), \(s_{t+1}\) is the least \(s>s_t\) such that for every \(n\) with \(o < n \le t\), \(\sigma_n^s\) exists.

Define \(A_t = \sigma_t^{s_t}\).

This completes the proof of 2.

3 Computing with random sets↩︎

In this section we give a proof of 3. First we discuss the notions of Demuth randomness and weak Demuth randomness; the latter appears in the statement of the theorem, while the former will play a role in its proof. We have the implications

For further background, see [5] on Demuth randomness, and in particular why this property is still compatible with being \(\Delta^0_2\). See [25] for weak Demuth randomness.

The general idea is that a Demuth test is a sequence \((G_m)\) of effectively open (\(\Sigma^0_1\)) sets with \(\mathbf{\lambda}G_m \le 2^{-n}\), but unlike a ML-test, the sets \(G_m\) are not uniformly c.e. Rather, we think of the sets being given to us in stages, where from time to time, we are allowed to empty a component of the test and restart its enumeration. Each component is restarted only finitely many times, and in fact we require that there is a computable function bounding the number of times each component is restarted. For the formal definition, recall again that a function \(f\colon {\mathbb{N}}\to{\mathbb{N}}\) is \(\omega\)-c.a.if it has a computable approximation \(f(m,s)\) such that the number of mind-changes \(\# \{s\,:\, f(m,s)\ne f(m,s+1)\}\) is bounded by \(g(m)\), where \(g\) is some computable function.

If \((G_m)\) is a Demuth test, witnessed by an \(\omega\)-c.a.function \(p\), and \(p(m,s)\) is a computable approximation of \(p\), then we write \(G_m[s]\) for the clopen set \(W_{p(m,s),s}\): at stage \(s\), we guess that \(G_m = W_{p(m,s)}\), and we let \(G_m[s]\) be the result of enumerating that effectively open set for \(s\) many steps. We may assume that for all \(m\) and \(s\), \(\mathbf{\lambda}G_m[s]\le 2^{-m}\): we can stop enumerating clopen subsets into the component if we see that its measure will exceed \(2^{-m}\). Note that in that case, we know that \(p(m,s)\ne p(m)\), so we can wait for a new version of \(G_m\) to be started.

Thus, an “index-free” equivalent definition of a Demuth test \((G_m)\) is: there is a computable array \((G_{m,s})\) of clopen sets such that for all \(m\) and \(s\), \(\mathbf{\lambda}G_{m,s}\le 2^{-m}\), and there is a computable function \(g\) such that for all \(m\), \(\# \{s\,:\, G_{m,s}\nsubseteq G_{m,s+1}\}\) is bounded by \(g(m)\); and \(G_m = \bigcup_{s>t(m)} G_{m,s}\), where \(t= t(m)\) is any stage sufficiently late so that for all \(s\ge t\), \(G_{m,s}\subseteq G_{m,s+1}\).

Note that the capturing condition is the Solovay one, rather than requiring \(Y\in \bigcap_m G_m\). This is because in 5, we do not require that the test be nested, meaning \(G_{m+1}\subseteq G_m\) for all \(m\). This is not an issue when considering ML-randomness; every non-nested ML test \((U_m)\) can be transformed into a nested one by replacing \(U_m\) by \(\bigcup_{n>m} U_n\). Applying this transformation to a Demuth test will usually not result in a Demuth test.

An equivalent definition is: for every Demuth test \((G_m)\) (nested or not), \(Y\notin \bigcap_m G_m\). That is, rather than restricting to nested tests, we can replace the passing condition. To see this, given a Demuth test \((G_m)\), we let \(H_m = \bigcap_{n\le m} G_n\); then \((H_m)\) is a nested Demuth test that captures all \(Y\in \bigcap_m G_m\).

3.1 A proof of (a)\(\Rightarrow\)(b) of 3↩︎

In this direction, we only need the assumption that \(B\) is \(K\)-trivial. For each one of the five classes \(\mathcal{C}\) listed in 3, let (b)\(_{\mathcal{C}}\) indicate item (b) of the theorem as applied to this class: the statement that for all ML-random \(Y\in \mathcal{C}\), \(A\le_{\mathrm{T}}Y\oplus B\). Of course, if \(\mathcal{C}\subseteq \mathcal{D}\) then (b)\(_{\mathcal{D}}\) implies (b)\(_{\mathcal{C}}\). We note that among the five classes, the first, the class of sets that are not weakly Demuth random, is the largest. Namely, a weakly Demuth random set cannot be superhigh (this is a result of Kučeraand Nies [26]) and cannot be \(\omega\)-c.a.(this is essentially by definition; if \(Y\) is \(\omega\)-c.a.then \((\{Y\! \upharpoonright_{m}\})\) is a nested Demuth test capturing \(Y\)). We note that every superlow set is \(\omega\)-c.a., and that every set \(\Omega_R\) for an infinite computable \(R\) is \(\omega\)-c.a.as well.

Thus, in this direction, it suffices to show that (a) implies (b)\(_{\mathcal{C}}\) where \(\mathcal{C}\) is the class of sets that are not weakly Demuth random.

Hirschfeldt and Miller showed that for each null \(\Pi^0_{2}\) class \(\mathcal{H}\subseteq2^{ \omega}\), there is a cost function \(\mathbf{c}\) such that for each \(A, Y \in 2^{ \omega}\), if \(A \models \mathbf{c}\) and \(Y \in \rm \textsf{MLR}\cap \mathcal{H}\) then \(A \le_T Y\); see [5] for a proof of this otherwise unpublished result. For the direction under discussion, we need to show that when \(\mathcal{H}\) is the class of sets captured by some nested Demuth test, then the associated cost function \(\mathbf{c}\) is benign, and that the Hirschfeldt-Miller result partially relativises as necessary. (See also the post on weak Demuth randomness by Kučera and Nies in [27].)

Let \((G_m)\) be a nested Demuth test, with approximation \((G_{m,s})\) as discussed above. Note that we may assume that for each \(m\) and \(s\), \(G_{m+1,s}\subseteq G_{m,s}\). For \(k<t\) we let:

• \(r(k,t)\) be the smallest \(m\) such that for some \(s\) with \(k<s\le t\), \(G_{m,s-1}\nsubseteq G_{m,s}\) (the smallest \(m\) such that the \(m\)th component of the test was restarted at some stage between \(k\) and \(t\)).

• \(V_{k,t}= \bigcup_{k < s \le t} G_{r(k,s),s}\).

• \(\mathbf{c}(k,t) = \mathbf{\lambda}V_{k,t}\).

By definition, \(V_{k,t}\subseteq V_{k,t+1}\), so \(\mathbf{c}\) is increasing in the second variable. Also, \(V_{k,t}\supseteq V_{k+1,t}\): we have \(r(k,s)\le r(k+1,s)\), and so \(G_{r(k,s),s}\supseteq G_{r(k+1,s),s}\). Hence, \(\mathbf{c}\) is decreasing in the first variable, so \(\mathbf{c}\) is monotonic.

Note that if no component \(G_{m'}\) for \(m'\le m\) is restarted after stage \(k\), then \(r(k,s)>m\) for all \(s>k\), implying that \(G_{r(k,s),s}\subseteq G_{m,s}\) for all \(s>k\), and so \(V_{k,t}\subseteq G_m\) for all \(t>k\).

Suppose that \(\mathbf{c}(k,t)>2^{-m}\). Since \(\mathbf{\lambda}G_m\le 2^{-m}\), this implies that \(V_{k,t}\nsubseteq G_m\), so some component \(m'\) is restarted between stages \(k\) and \(t\). Since there is a computable bound on the number of times each component is restarted, we see that the cost function \(\mathbf{c}\) is benign.

We also observe that for all \(k\), \(\bigcap_m G_m \subseteq \bigcup_{t>k} V_{k,t}\). This is because \(\lim_t r(k,t) = m\) where \(m\) is smallest such that the \(m\)th component is restarted after stage \(k\), and so \(G_m\subseteq \bigcup_{t>k} V_{k,t}\).

Suppose now that \(A \models_B \mathbf{c}\); let \((A_s)\) be a \(B\)-computable approximation with a finite total \(\mathbf{c}\)-cost. For each stage \(s\), let \(x_s\) be the least such that \(A_s(x)\ne A_{s+1}(x)\); we let \[R_s = V_{x_s,s}.\] Each set \(R_s\) is clopen, and the sequence \((R_s)\) is computable in \(B\). Since \(\mathbf{c}(x_s,s) = \mathbf{\lambda}V_{x_s,s} = \mathbf{\lambda}R_s\), we get \(\sum_s \mathbf{\lambda}R_s < \infty\). This means that \((R_s)\) is a Solovay test relative to \(B\).

Suppose that \(Y\) is ML-random and is captured by the nested Demuth test \((G_m)\). Since \(B\) is assumed to be \(K\)-trivial, it is low for ML-random, and so \(Y\) is ML-random relative to \(B\). Since \((R_s)\) is a Solovay test relative to \(B\), \(Y\) cannot be captured by \((R_s)\), meaning that \(Y\in R_s\) for only finitely many \(s\). (Indeed, recall that a set is ML-random relative to \(B\) if and only if it passes all Solovay tests relative to \(B\).)

Let \(s_0\) be such that \(Y\notin R_s\) for all \(s\ge s_0\). We now show how to compute \(A\) given \(Y\oplus B\). We are given some \(x\) and we find \(A(x)\). To do that, using the oracle \(Y\), find some \(t\ge s_0\) such that \(Y\in V_{k,t}\); we observed above that such \(t\) exists, since \(Y\in \bigcap_m G_m\). We claim that \(A(x)= A_t(x)\) (here the oracle \(B\) is used, since the approximation \((A_t)\) is \(B\)-computable). Otherwise, \(A_s(x)\ne A_{s+1}(x)\) for some \(s\ge t\); so \(R_s = V_{y,s}\) for some \(y\le x\). Since \(V_{y,s}\supseteq V_{x,s}\supseteq V_{x,t}\), \(Y\in R_s\), contrary to the assumption on \(s_0\).

3.2 A proof of (b)\(\Rightarrow\)(a) of 3, cases (1)–(4).↩︎

In this subsection we prove that (b)\(_{\mathcal{C}}\) implies (a) for each of the first four classes \(\mathcal{C}\) mentioned in 3: not weakly Demuth random, superhigh, \(\omega\)-c.a., and superlow. The common property of these classes that is relevant here is that they are all Demuth-compatible, as defined in Nies [28]:

Using some methods from [4], Nies showed in [28] that the class of superlow sets, and the class of superhigh sets, are Demuth-compatible. Every superlow set is \(\omega\)-c.a., so the class of \(\omega\)-c.a.sets is Demuth-compatible; every \(\omega\)-c.a.is not weakly Demuth random, so the collection of sets that are not weakly Demuth random is also Demuth-compatible.

Thus, for the four classes under consideration, it suffices to show that if \(\mathcal{C}\) is any Demuth-compatible class, then (b)\(_{\mathcal{C}}\) implies (a). The argument combines methods from [28] and [25].

We remark that for this implication, we can relax the requirement that \(A\) and \(B\) be \(K\)-trivial: it suffices to assume that \(A\) and \(B\) are each computable from some c.e., jump-traceable (equivalently, superlow by [7]) set. This is because every \(K\)-trivial set is jump-traceable, and every \(K\)-trivial set is computable from some c.e.\(K\)-trivial set. [8] implies the following fact that we will use in the proof of the implication: if \(X\) is computable from a c.e., jump-traceable set, then \(X\) is low for \(\mathop{\mathrm{BLR}}{}\), as recalled next.

We note that being bounded limit-recursive is a partial relativisation of the notion of \(\omega\)-c.a.; the full relativisation would allow a \(B\)-computable bound on the number of mind-changes.

Associated with the notion of partial relativisation of being \(\omega\)-c.a.in [def:CS] is a partial relativisation of Demuth tests. A \(\mathrm{Demuth}_{\mathrm{BLR}}\langle B \rangle\) test ([25]) is defined like a Demuth test relative to \(B\), except that the function giving the \(\Sigma^0_1(B)\) index of the \(m\)th component is \(\mathop{\mathrm{BLR}}(B)\), rather than \(\omega\)-c.a.relative to \(B\). In terms of approximation, a \(\mathrm{Demuth}_{\mathrm{BLR}}\langle B \rangle\) test is the limit of a \(B\)-computable approximation \((G_{m,s})\), with a computable bound on the number of times the \(m\)th component is restarted, rather than a \(B\)-computable one.

Fix an order function \(h\), and sets \(A\) and \(B\) as described. We prove:

• There is a Demuth test as follows. If \(A\le_{\mathrm{T}}Y\oplus B\) for some \(Y\) that passes the test, then \(J^A\) has an \(h\)-bounded, \(B\)-c.e.trace.

This suffices to show the desired implications.

We will show (\(*\)) in a couple of steps. First, we will only consider a single Turing functional (reduction procedure) witnessing \(A\le_{\mathrm{T}}Y\oplus B\). We will show that there is a \(\mathrm{Demuth}_{\mathrm{BLR}}\langle B \rangle\) test as required, and then cover it by an unrelativised Demuth test. Finally, we will use a universal functional to obtain \((*)\).

For the time being, fix a Turing functional \(\Psi\).

We start by mostly following the proof of [28]. For \(m\in {\mathbb{N}}\) let \(I_m = \left\{ x\in {\mathbb{N}}\,:\, 2^m\le h(x) < 2^{m+1} \right\}\), so each \(I_m\) is a finite interval and together they partition \({\mathbb{N}}\). For \(\sigma\in 2^{<{\mathbb{N}}}\) let \[U_\sigma = \left\{ Z\in 2^{{\mathbb{N}}} \,:\, \sigma \preceq \Psi^{Z\oplus B} \right\};\] the sets \(U_\sigma\) are \(\Sigma^0_1(B)\), uniformly. For \(m\in {\mathbb{N}}\) let \[\sigma_m = \bigcup \left\{ \sigma \,:\, (\exists x\in I_m)\,\,J^A(x)\downarrow \text{ with use }\sigma\prec A\right\}.\] That is, \(\sigma_m\) is an initial segment \(\sigma\prec A\) such that for all \(x\in I_m\), \(J^A(x)\downarrow \Leftrightarrow J^\sigma(x)\downarrow\). Note that since \(J^A\) is partial, the map \(m\mapsto \sigma_m\) is not \(A\)-computable, rather, it is \(\mathop{\mathrm{BLR}}(A)\): the number of mind-changes is bounded by \(|I_m|\). By assumption on \(A\), and the lowness fact mentioned above [8], the map \(m\mapsto \sigma_m\) is \(\omega\)-c.a.; let \((\sigma_{m,s})\) be a computable approximation with a computable bound on the number of mind-changes. (For the current argument, we can allow the approximation \((\sigma_{m,s})\) to be \(B\)-computable rather than computable, but we need to keep the computable bound on the number of mind-changes.)

We recall some notation: for a \(\Sigma^0_1(B)\) set \(V\), and rational \(\varepsilon>0\), we let \(V^{(\le \varepsilon)}\) be the result of enumerating \(V\) (with oracle \(B\)), up to a point at which we see the measure exceeding \(\varepsilon\). Thus, \(V\subseteq V^{(\le \varepsilon)}\), \(\mathbf{\lambda}(V^{(\le \varepsilon)})\le \varepsilon\), and \(V = V^{(\le \varepsilon)}\) if \(\mathbf{\lambda}V\le \varepsilon\). We then let \[G_m = U_{\sigma_m}^{(\le 2^{-m})},\] and for each \(s\) we let \(G_{m,s} = U_{\sigma_{m,s},s}^{(\le 2^{-m})}\), the result of enumerating \(U_{\sigma_{m,s}}^{(\le 2^{-m})}\) for \(s\) many steps. So the approximation \((G_{m,s})\) is \(B\)-computable, and the \(m\)th component is restarted only when \(\sigma_{m,s}\ne \sigma_{m,s+1}\), for which we have a computable bound. Hence, \((G_m)\) is a \(\mathrm{Demuth}_{\mathrm{BLR}}\langle B\rangle\) test.

We claim that \((G_m)\) is close to what is required in \((*)\): if \(A = \Psi^{B\oplus Y}\) for some \(Y\) that passes the test \((G_m)\), then \(J^A\) has an \(h\)-bounded \(B\)-c.e.trace. The argument is similar to that of [28]. For each \(m\), \(x\in I_m\), and \(s\), we enumerate \(J^{\sigma_{m,s}}(x)\) into \(T_x\) if it is defined at stage \(s\), and the measure of \(G_{m,s}\) is exactly \(2^{-m}\) (the stage \(s\) version of \(G_m\) is “full”).

Suppose that \(y,z\) are distinct elements of \(T_x\); suppose that we enumerate \(y\) into \(T_x\) at stage \(s\) (so \(y=J^{\sigma_{m,s}}(x)\) and \(G_{m,s}\) is full at stage \(s\)), and we enumerate \(z\) into \(T_x\) at some stage \(t\). Since \(y\ne z\), the strings \(\sigma_{m,s}\) and \(\sigma_{m,t}\) are distinct incomparable, which implies that \(G_{m,s}\) and \(G_{m,t}\) are disjoint. Since both \(G_{m,s}\) and \(G_{m,t}\) are full, \(|T_x| \le 2^m \le h(x)\). Hence, the \(B\)-c.e.trace \((T_x)\) is \(h\)-bounded. Suppose that \(A = \Psi^{Y\oplus B}\) and that \(Y\notin G_m\). This means that \(\mathbf{\lambda}(G_m) = 2^{-m}\) (otherwise at some late point we would enumerate \(Y\) into \(G_m\)), indeed, for all but finitely many stages \(s\), \(\mathbf{\lambda}G_{m,s} = 2^{-m}\). Hence, for all \(x\in I_m\), if \(J^A(x)\) is defined then \(J^A(x)\in T_x\). So if \(A=\Psi^{B\oplus Y}\) for some \(Y\) that passes \((G_m)\), then a finite modification of \((T_x)\) traces \(J^A\).

Toward \((*)\), we use the fact that since \(B\) is computable from a c.e., jump-traceable set, it is low for \(\mathrm{Demuth}_{\mathrm{BLR}}\) ([25]): for every \(\mathrm{Demuth}_{\mathrm{BLR}}\langle B \rangle\) test \((G_m)\), there is an unrelativised Demuth test \((H_m)\) that covers \((G_m)\) in the sense that every set passing \((H_m)\) also passes \((G_m)\). Hence, there is a Demuth test \((H_m)\) with the same property as \((G_m)\): if \(A = \Psi^{B\oplus Y}\) for some \(Y\) that passes \((H_m)\), then \(J^A\) has an \(h\)-bounded \(B\)-c.e.trace.

Finally, the argument of [28] gives \((*)\). Let \((\Phi_e)\) be an effective listing of all Turing functionals, and let \(\Psi^{0^e1X} = \Phi_e^X\) for all \(e\) and \(X\). Let \((H_m)\) be a Demuth test obtained for this functional \(\Psi\). The referenced lemma states that there is a Demuth test \((S_m)\) such that for all \(Y\), if \(Y\) passes \((S_m)\) then for all \(e\), \(0^e1Y\) passes \((H_m)\). Then \((S_m)\) is as required for \((*)\); this completes the proof of (b)\(_{\mathcal{C}}\Rightarrow\)(a) for all Demuth-compatible classes \(\mathcal{C}\).

3.3 Proof of (b)\(\Rightarrow\)(a) of 3, case (5)↩︎

We now consider the remaining case of 3: if \(A\le_{\mathrm{T}}B\oplus \Omega_R\) for every infinite computable set \(R\), then \(A\le_{\mathrm{\scriptsize{SJT}}}B\). In fact, using this assumption we prove that \(A\models_B \mathbf{c}\) for every benign cost function \(\mathbf{c}\), and use 2, which applies since every \(K\)-trivial set is jump-traceable. We generally follow arguments in [22], which gives the result when \(B = \emptyset\) .

Let \(R\) be infinite and computable. For \(s>n\) we let \[k_s(n) = \left\lfloor{ - \log_2 (\Omega_s -\Omega_n)}\right\rfloor,\] and \[\mathbf{c}_{\Omega,R}(n,s) = 2^{-|R\cap k_s(n)|}\] (see [22]). The cost function \(\mathbf{c}_{\Omega,R}\) is benign ([22]). Further, if \(\mathbf{c}\) is any benign cost function, then there is some infinite computable \(R\) such that for all \(n\), \(\lim_s \mathbf{c}(n,s)\le^\times \lim_s\mathbf{c}_{\Omega,R}(n,s)\) ([22]). By [20], this implies that if \(A\models_B \mathbf{c}_{\Omega,R}\) then \(A\models_B \mathbf{c}\). Hence, to prove the desired implication, the following suffices:

This is the required partial relativisation of [22]. We will follow the proof of this lemma. As it is fairly long, we will not copy all the details; rather, we will give the overall structure of the proof, and indicate how it needs to be modified to accommodate \(B\ne \emptyset\).

The proof has two main steps. We first prove 2 assuming that \(A\) is c.e.relative to \(B\); we then show how to remove this extra assumption.

Proof of 2 assuming that \(A\) is c.e.in \(B\)↩︎

We may assume that \(R\) is co-infinite; otherwise, \(\mathbf{c}_{\Omega,R}=^\times \mathbf{c}_{\Omega}\), and since \(A\) is \(K\)-trivial, it obeys \(\mathbf{c}_\Omega\) (with no need for \(B\)’s help). For \(n\in {\mathbb{N}}\) let \[U_n = \bigcup_{s\ge n} \big[ (\Omega_s)_{R^\complement}\restriction{|R^\complement \cap n|} \big]\] (the string in the definition is the result of erasing the bits in locations in \(R\) from the string \(\Omega_s\restriction{n}\)); let \(U_{n,s}\) be the stage \(s\) enumeration of \(U_n\). Then \(\mathbf{\lambda}(U_{n,s}) \le^\times \mathbf{c}_{\Omega,R^\complement}(n,s)\) and \(\Omega_{R^\complement}\in \bigcap_n U_n\). Following the notation in [22], let \(Y = \Omega_R\) and \(X = \Omega_{R^\complement}\). Fix a \(B\)-computable functional \(\Phi\) such that \(A = \Phi^Y\). Fixing a \(B\)-computable enumeration \((A_s)\) of \(A\), we let \(E_s\), the stage \(s\) error set, be the collection of \(Z\) such that \(\Phi_s^Z\) lies strictly to the left of \(A_s\), and \(E = \bigcup_s E_s\) is the set of \(Z\) such that \(\Phi^Z\) lies to the left of \(A\). We let \(Q_s = 2^\omega\times (2^\omega\setminus E_s)\) (and \(Q = 2^\omega\times (2^\omega\setminus E)\)). We perform the “ravenous sets” construction precisely as in [22], except that now the construction is computable in \(B\). We obtain sets \(V^k_n\), and let \(V^k = \bigcup_n V^k_n\).

The main part of the verification that we need to discuss is that \((X,Y)\notin \bigcap_k V^k\cap Q\). The first step of this is the equivalence between that statement, and \(Q\) having positive density at \((X,Y)\). When \(B = \emptyset\) this is [30] (quoted as [22]). The relativisation of this fact gives:

\((\otimes)_1\)

Suppose that \(Y\) is random relative to \(B\), \(P\) is a \(\Pi^0_1(B)\)-class, and \(Y\in P\). Then \(P\) has density 0 at \(Y\) if and only if \(Y\) fails a \(B\)-difference test on \(P\).

Here a \(B\)-difference test on \(P\) is a test of the form \((P\cap O_n)\), where \((O_n)\) are uniformly \(\Sigma^0_1(B)\) and \(\mathbf{\lambda}(P\cap O_n)\le 2^{-n}\). We also need the following relativisation of a characterisation of difference randomness from [31]: if \(Y\) is a ML-random set,

\((\otimes)_2\)

\(Y\) passes all \(B\)-difference tests if and only if \(Y\oplus B\ge_{\mathrm{T}}B'\).

Now we argue as follows. Since \(Y\) is ML-random and \(B\) is \(K\)-trivial, \(Y\) is \(B\)-random. Since \(B\) is \(K\)-trivial, it is low, i.e., \(B'\equiv_{\mathrm{T}}\emptyset'\). Now \(Y\) is Turing incomplete (since \(R\) is co-infinite), that is, \(Y\not\ge_{\mathrm{T}}\emptyset'\). By a result of Day and Miller [32], since \(B\) is \(K\)-trivial, \(Y\oplus B\not\ge_{\mathrm{T}}\emptyset'\) (this result is not needed in [22]). By \((\otimes)_2\), \(Y\) passes all \(B\)-difference tests. Since \(Y\notin E\), by \((\otimes)_1\), \(2^\omega\setminus E\) has positive density at \(Y\) (again we use the fact that \(Y\) is \(B\)-random, as \(B\) is \(K\)-trivial). It follows that \(Q\) has positive density at \((X,Y)\). Again since \((X,Y)\) is ML-random, it is \(B\)-random. By \((\otimes)_1\) again, \((X,Y)\notin \bigcap_k V^k\cap Q\), as required.

The rest of the verification in [22] goes through when relativising to \(B\), finishing the proof of 2 when \(A\) is c.e.relative to \(B\).

Proof of 2 without extra assumptions↩︎

As in [22], this case follows from the special case above using two facts.

\((\otimes)_3\)

If \(A\le_{\mathrm{T}}B\oplus \Omega_R\) then there is some \(B\)-c.e., \(K\)-trivial set \(D\) such that \(A\le_{\mathrm{T}}B\oplus D\) and \(D\le_{\mathrm{T}}B\oplus \Omega_R\).

\((\otimes)_4\)

If \(D\) is \(K\)-trivial, \(D\models_B \mathbf{c}_{\Omega,R}\) and \(A\le_{\mathrm{T}}D\oplus B\) then \(A\models_B \mathbf{c}_{\Omega,R}\).

We start with the latter, following the proof in [22] (which is similar to [23]). Let \(\psi\) be the use of a computation of \(A\) from \(D\oplus B\). The \(K\)-trivial degrees are closed under taking joins, so \(D\oplus B\) is \(K\)-trivial. Hence [33] applies, so \(\Omega-\Omega_n \le^\times \Omega-\Omega_{\psi(n)}\). The rest of the proof of [22] follows without changes.

We turn to verify \((\otimes)_3\), which follows from a partial relativisation of [22]. For this, we need a partial relativisation of [22]:

\((\otimes)_5\)

Suppose that \(A\) and \(B\) are \(K\)-trivial. There is a \(B\)-computable approximation \((A_s)\) of \(A\) such that if \(X\) is ML-random and \(A = \Phi(X,B)\) then for almost all \(n\), if \(A\restriction{n}\preceq \Phi_s(X,B)\) then \(A\restriction{n} = A_t\restriction{n}\) for all \(t\ge s\).

This follows from the proof in [22], using a partially relativised version of the “main lemma” derived from the golden run construction [5]; we need the prefix-free machine \(M\) to be \(B\)-computable, and the sequence of stages \((q(i))\) to be \(B\)-computable. Again, we follow the golden run construction without changes, relativising all to \(B\). We use the fact that \(B\) is low for \(K\), so \(A\) is \(K\)-trivial relative to \(B\): \(K^B(A\restriction{n}) =^+ K(A\restriction{n}) =^+ K(n) =^+ K^B(n)\). The added constants are incorporated into the construction.

This completes the proof of 2, and so of 3.

4 Concluding remarks and open questions↩︎

In this section we mention some corollaries of our main theorems, discuss related results, and state some open questions.

The very first characterisation of strong jump-traceability was in terms of Kolmogorov complexity [9]. This extends to a characterisation of the weak reducibility \(\le_{\mathrm{\scriptsize{SJT}}}\). Informally, \(A\le_{\mathrm{\scriptsize{SJT}}}B\) if and only if the plain descriptive string complexity \(C^A\) is “almost” lower-bounded by \(C^B\). The formal version follows.

[9] states this for the case that \(B= \emptyset\) (also see [5]). The proof gives the required partial relativisation, where we still almost lower-bound \(C^A\) (rather than \(C^{A \oplus B}\)), and the functions \(h\) are computable.

4.1 The structure of the SJT degrees↩︎

Not much is known about the degree structure given by \(\le_{\mathrm{\scriptsize{SJT}}}\). We can state the following:

In particular, the \(\le_{\mathrm{\scriptsize{SJT}}}\)-degree of \(B\) is countable, and it bounds only countably many \(\le_{\mathrm{\scriptsize{SJT}}}\)-degrees.

In contrast, not all initial segments of the degree structure induced by \(\le_{\mathrm{\scriptsize{SJT}}}\) are countable: Ng [34] proved that the set \(\{A : A \le_{\mathrm{\scriptsize{SJT}}}\emptyset'\}\) contains a perfect class.

Like the \(K\)-trivials, the strongly jump-traceable degrees form an ideal. In particular, they are closed under taking joins. We ask:

By the argument of the proof of 4 (see Section 2.1), for an affirmative answer to 7, it would suffice to show that if \(A_0,A_1\le_{\mathrm{\scriptsize{SJT}}}B\) and \(B\) is jump-traceable then \(A_0\oplus A_1 \le_{\mathrm{JT}} B\). We could even hope for the following: there is a benign cost function \(\mathbf{c}\) such that if \(B\) is jump-traceable and \(A\models_B \mathbf{c}\) then \(A\) is jump-traceable (equivalently \(A\le_{\mathrm{JT}} B\)). We remark that 7 for \(B=\emptyset\) was first proved directly, without using cost functions (see [10] for the c.e.case); it would be interesting to see if ideas from that argument would be useful.

It is open whether the c.e.SJT-degrees are dense. We conjecture that for each c.e.set \(E\) that is not strongly jump traceable, there are c.e.sets \(A,B \le_{\mathrm{T}}E\) that are \(\le_{\mathrm{\scriptsize{SJT}}}\)-incomparable. A certain obstacle to showing such structural results is the theorem of Ng [34] that the least degree in the c.e.SJT-degrees, given by the strongly-jump traceable c.e.sets, has a \(\Pi^0_{4}\) complete index set. Examining the definition, one sees that the arithmetical complexity of the reducibility itself on the c.e.sets is also \(\Pi^0_{4}\). In contrast, Turing reducibility is \(\Sigma^0_{4}\), and the least degree is merely \(\Sigma^0_{3}\).

4.2 Relationship with LR-reducibility↩︎

Recall the weak reducibility \(\le_{\mathrm{\scriptsize{LR}}}\) mentioned in the introduction: \(A\le_{{\mathrm{\scriptsize{LR}}}} B\) if \(\rm \textsf{MLR}^B\subseteq \rm \textsf{MLR}^A\). Every strongly jump-traceable set is \(K\)-trivial, that is, if \(A\le_{\mathrm{\scriptsize{SJT}}}\emptyset\) then \(A \le_{\mathrm{\scriptsize{LR}}}\emptyset\).

Here 4 may be relevant: the relation \(A\oplus B \le_{{\mathrm{\scriptsize{LR}}}} B\) is much better understood than \(A\le_{{\mathrm{\scriptsize{LR}}}} B\), as it has a characterisation in terms of \(K\)-triviality. In particular, this characterisation implies that every \(\le_{{\mathrm{\scriptsize{LR}}}}\)-degree is countable, even though some \(\le_{{\mathrm{\scriptsize{LR}}}}\)-degrees bound uncountably many such degrees. In contrast, we do not know whether every \(\le_{\mathrm{\scriptsize{SJT}}}\)-degree is countable.

In general, it would be interesting to give characterisations of other weak reducibilities using the three paradigms discussed in the introduction. In particular, we suggest the reducibilities \(A\le_{\mathrm{\scriptsize{LR}}}B\), \(A\le_{\mathrm{JT}} B\), and \(A'\le_{\mathrm{tt}} B'\); see [5].

4.3 Relationship with ML-reducibility↩︎

The following relation is a main topic of the article [22]:

This relation is particularly useful in understanding the structure of the \(K\)-trivial Turing degrees. It satisfies the conditions for being a weak reducibility, except that it is not known to be an arithmetical relation, even when restricted to the \(K\)-trivials.

There are certain differences between the reducibilities \(\le_{\mathrm{ML}}\) and \(\le_{\mathrm{\scriptsize{SJT}}}\) on the \(K\)-trivial sets. For example, the least \(\le_{\mathrm{ML}}\)-degree consists only of the computable sets, not all strongly jump-traceable sets (this shows that \(\le_{\mathrm{\scriptsize{SJT}}}\) does not imply \(\le_{\mathrm{ML}}\) on the \(K\)-trivials). Further, there is a greatest \(\le_{\mathrm{ML}}\)-degree of \(K\)-trivials (called the “smart” \(K\)-trivials in [22], [35]). By the following proposition there is no greatest \(\le_{\mathrm{\scriptsize{SJT}}}\)-degree among the \(K\)-trivials; in particular, \(\le_{\mathrm{ML}}\) does not imply \(\le_{\mathrm{\scriptsize{SJT}}}\) on the \(K\)-trivials.

We conjecture that for each benign cost function \(\mathbf{c}\), for each \(B\models \mathbf{c}\), there is a c.e. set \(A \models \mathbf{c}\) such that \(A \not \le_{\mathrm{\scriptsize{SJT}}}B\). This would strengthen 9.

By [22], every ML-degree of a \(K\)-trivial set contains a c.e.set. By [11], every strongly jump-traceable set is computable from a c.e.strongly jump-traceable set. It is natural to ask:

A reducibility strictly weaker than \(\le_{\mathrm{ML}}\) is \(A\le_{\omega-\text{ML}} B\): every \(\omega\)-c.a.ML-random Turing above \(B\) is also above \(A\). This reducibility is somewhat closer to \(\le_{\mathrm{\scriptsize{SJT}}}\). 3 for the class \(\mathcal{C}\) being the \(\omega\)-c.a.sets implies:

Finally, we mention a related notion. For \(\mathcal{C} \subseteq\mathcal{P}({\mathbb{N}})\) one defines \(\mathcal{C}^\Diamond\) as the class of c.e.sets that are Turing below each ML-random set in \(\mathcal{C}\) [5]. 3 implies:

For instance, let \(\mathcal{C} = \{\Omega_R\}\) for a co-infinite computable set \(R\). This shows that the subideals, in the Turing sense, of the \(K\)-trivials considered in [22], [23] are actually closed downward under the weaker SJT-reducibility.

References↩︎

---

1. Recall that a function \(f\colon {\mathbb{N}}\to {\mathbb{N}}\) is \(\omega\)-computably approximable, or \(\omega\)-c.a., if it has a computable approximation \(f(x,s)\) such that \(n\mapsto \#\left\{ s \,:\, f(x,s)\ne f(x,s+1) \right\}\) is bounded by some computable function; equivalently, \(f\le_{\mathrm{wtt}} \emptyset'\). A set \(X\subseteq {\mathbb{N}}\) is \(\omega\)-c.a.if its characteristic function is \(\omega\)-c.a. The terminology “\(\omega\)-c.a.” was introduced for clarity, since the term “\(\omega\)-c.e.” is often used for the class \(\Sigma^{-1}_\omega\) in Ershov’s effective difference hierarchy, which is a larger class of sets (the \(\omega\)-c.a.sets are those that are both \(\omega\)-c.e.and co-\(\omega\)-c.e.)↩︎