2.1 A proof of Theorem 1.6

We first explain how Theorem 1.6 follows from Theorem 1.4. In one direction, suppose that $A\oplus B \le _{\text { {SJT}}} B$ ; since $A\le _{\text {T}} A\oplus B$ and $\le _{\text {T}}$ implies $\le _{\text { {SJT}}}$ , we have $A\le _{\text { {SJT}}} B$ .

In the other direction, suppose that $A\oplus B$ is jump-traceable and that ${A\le _{\text { {SJT}}} B}$ . The assumption on $A\oplus B$ implies that both A and B are jump-traceable, so Theorem 1.4 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 Theorem 1.4, now shows that $A\oplus B\le _{\text { {SJT}}} B$ .

In the next two sections we give a proof of Theorem 1.4.

2.2 Proof of (b) $\Rightarrow $ (a) of Theorem 1.4

In this direction, in fact, we do not make use of the assumption that B is jump-traceable. Proposition 2.1 of [Reference Greenberg and Nies18] 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:

$$\begin{align*}\mathbf{c}(x,s) = \max \left\{ 1/h(n) \,:\, \exists \sigma\in V_{n,s}\text{ s.t. }|\sigma|>x \right\}. \end{align*}$$

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

$$\begin{align*}\bigcup \left\{ V_{n} \,:\, 1/h(n)\ge \varepsilon \right\}, \end{align*}$$

which is bounded by

$$\begin{align*}\sum \left\{ g(n) \,:\, 1/h(n)\ge \varepsilon \right\}. \end{align*}$$

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 Theorem 1.4

We turn to the proof of the harder direction of Theorem 1.4. The case $B=\emptyset $ is Theorem 1.12 of [Reference Diamondstone, Greenberg and Turetsky8]. 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 _{\text { {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 _{\text { {SJT}}} B$ , since the latter implies $A\le _{\text {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. (1) Enumeration of the functionals $\Phi $ and $\Psi $ .

2. (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 [Reference Cholak, Downey and Greenberg6]), however the method of a universal trace would also work here (see, e.g., [Reference Greenberg and Nies18]).

The general idea (as in [Reference Diamondstone, Greenberg and Turetsky8]) 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:

$$\begin{align*}|I_n| = g(n) + \sum \big\{ h(y)\,:\, y\in Q_{n+1} \big\}, \end{align*}$$

and $|J_n| = 2^{r_n}$ , where

$$\begin{align*}r_n = \sum \Big\{ h(y) \,:\, y\in \bigcup_{x\in I_n} R_x \Big\}. \end{align*}$$

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 _{\text { {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 Claim 2.3.

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:

1. (i) For all $n>o$ , for all $x\in I_n$ , for every oracle Y, for all $i<n$ , if $\ell $ is the ith number enumerated into $U_x^Y$ , and y is the ith 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.

2.3.4 Seeking promotion

Let $n>o$ and let Y be an oracle.

1. (vii) 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 $ .

2. (viii) 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 }$ ;

   • – 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.

3. (ix) The action taken then is: if m is the ith length that Y believes should be promoted by the n-module, and $i<n$ , and y is the ith 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. (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. (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. (3) This prompts some strings to appear in $V_y$ ; in turn, these strings are tested on $J_n$ ((v) and (vi)).

4. (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)–(ix)).

5. (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 $ .

Claim 1.4.2. For each $n> o$ , B believes at most $n-1$ lengths should be promoted by the n-module.

Proof. Suppose not, and fix lengths $0 = \ell _0 < \ell _1 < \dots < \ell _n$ such that for $i> 0$ , B believes that $\ell _i$ is to be promoted by the n module. For each $i> 0$ , fix strings $\sigma _0^i$ and $\sigma _1^i$ on the basis of which B believes that $\ell _i$ should be promoted by the n module.

By construction, B believes that $\ell _i$ should be promoted before it believes that $\ell _{i+1}$ should be promoted, and thus $\sigma _0^{i+1}\! \upharpoonright _{\ell _i} = \sigma _1^{i+1}\! \upharpoonright _{\ell _i}$ for $i> 0$ . Clearly this also holds for $i = 0$ . Now define the following sequence of sets (note that our subscripts are decreasing):

• • $Z_n = \{ \sigma _0^{n}, \sigma _1^{n}\}$ ;

• • for $0 < i < n$ ,

  $$\begin{align*}Z_i = Z_{i+1} \cup ( \{\sigma_0^i, \sigma_1^i\} \setminus \{ \sigma\! \upharpoonright_{\ell_i} : \sigma \in Z_{i+1}\}). \end{align*}$$

Note that each $Z_i$ is an antichain, and $\{\sigma _0^i, \sigma _1^i\} \subseteq \{ \sigma \! \upharpoonright _{\ell _i} : \sigma \in Z_i\}$ by construction. Let $T = \{ \sigma \! \upharpoonright _{\ell _i} : \sigma \in Z_1 \ \& \ i \le n\}$ , which we think of as a tree. The leaves of T are precisely the elements of $Z_1$ .

For $i < n$ , let $v_i = \sigma _0^{i+1}\! \upharpoonright _{\ell _i} = \sigma _1^{i+1}\! \upharpoonright _{\ell _i}$ . Then the $v_i$ are pairwise distinct because they all have different lengths, and each has at least two children in T (namely, $\sigma _0^{i+1}$ and $\sigma _1^{i+1}$ ). By Lemma 2.3, $|Z_1| \ge n+1$ .

Let D be the set of axes chosen for various $\sigma \in Z_1$ , and define $\tau \in J_n$ by

$$\begin{align*}\tau(d) = \left\{\begin{array}{@{}cl@{}} 0 & d \in D,\\ 1 & d \not \in D. \end{array}\right. \end{align*}$$

Observe that $\tau \in J_n(d) \iff d \in D$ .

Recall that our construction will define $\Phi ^\sigma (\tau ) = \sigma $ for all $\sigma \in Z_1$ unless $\Phi ^\sigma (\tau )$ was already defined to be something else. But no $\sigma ' \not \in Z_1$ could have caused such a previous definition, as such $\sigma '$ will have an axis $d \not \in D$ , and so will not seek to make a definition at $\tau $ . And $\sigma ' \in Z_1 \setminus \{\sigma \}$ will not do this, as they will only seek to make a definition for $\Phi ^{\sigma '}(\tau )$ , and $\sigma '$ and $\sigma $ are incomparable as $Z_1$ is an antichain.

Thus $\Phi ^\sigma (\tau ) = \sigma $ for all $\sigma \in Z_1$ . And by the definition of promotion and confirmation, we have $Z_1 \subseteq U_\tau ^B$ , contradicting $|U_\tau ^B| \le n$ .

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.

Claim 1.4.3. There is at most one possible choice for $\sigma _n^s$ .

Proof. For $n = o$ , this is immediate.

For $n> o$ , suppose there were two distinct strings $\rho _0$ and $\rho _1$ which are appropriate to pick for $\sigma _n^s$ . Fix $\ell \in L(n, s)$ least with $\rho _0\! \upharpoonright _{\ell } \neq \rho _1\! \upharpoonright _{\ell }$ . Then $\rho _0\! \upharpoonright _{\ell }, \rho _1\! \upharpoonright _{\ell }$ witness that B believes that $\ell $ should be promoted at stage s, and $\ell> |\sigma _{n-1}^s|$ , as $\rho _0$ and $\rho _1$ both extend $\sigma _{n-1}^s$ . This contradicts $|\sigma _{n-1}^s| = \max L(n-1, s)$ (or contradicts the definition of $\hat {\ell }$ if $n = o+1$ ).

Claim 1.4.4. Let $\ell _n = \max \bigcup _s L(n,s)$ for $n> o+1$ , and $\ell _{o+1} = \hat {\ell }$ . Then $A\! \upharpoonright _{\ell _n} = \lim _s \sigma _n^s$ for $n> o$ .

Proof. Induction on n. The case $n = o+1$ is immediate.

For $n> o$ , first observe that $\ell _{n-1}$ is either a length promoted by the n module (and so eventually an element of $L(n,s)$ ) or is $f(n-1, s) \le f(n,s)$ for some s, and so is bounded by an element of $L(n,s)$ . Thus $\ell _{n-1} \le \ell _n$ .

Now fix $s_0$ sufficiently large such that $\sigma _m^s = A\! \upharpoonright _{\ell _m}$ for all $m < n$ and $s \ge s_0$ , and such that $L(n,s_0) = \bigcup _s L(n,s)$ . As $\Phi ^A$ is traced by ${\left \langle {U_x^B}\right \rangle }_{x\in {\mathbb {N}}}$ , there is a stage $s_1 \ge s_0$ such that each $A\! \upharpoonright _{\ell }$ for $\ell \in L(n, s_0)$ is confirmed at n. Then $A\! \upharpoonright _{\ell _n}$ is a possible choice for $\sigma _n^s$ for every $s \ge s_1$ , and thus is $\sigma _n^s$ .

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}$ .

Claim 1.4.5. The total $\mathbf {c}$ -cost of the approximation ${\left \langle {A_t}\right \rangle }$ is finite.

Proof. Suppose that $o < n \le t$ and $A_t(z) \neq A_t(z+1)$ for some z with ${c(z, t) \ge 2^{-n}}$ . As $c(z, s_t) \ge c(z, t)$ , $z < f(n, s_t) \in L(n, s_t)$ . Thus $\sigma _n^{s_t} \neq \sigma _n^{s_{t+1}}$ . Fix m least with $\sigma _m^{s_t} \neq \sigma _m^{s_{t+1}}$ . Fix $\ell \in L(m, s_t)$ least with $\sigma _m^{s_t}\! \upharpoonright _{\ell } \neq \sigma _m^{s_{t+1}}\! \upharpoonright _{\ell }$ . If no length less than $\ell $ and greater than $\max L(m-1, s_t)$ is promoted by the m module at a stage $s \in (s_t, s_{t+1}]$ , then these witness the promotion of $\ell $ at stage $s_{t+1}$ , and $\ell> \max L(m-1, s_t)$ , as both $\sigma _m^{s_t}$ and $\sigma _m^{s_{t+1}}$ extend $\sigma _{m-1}^{s_t} = \sigma _{m-1}^{s_{t+1}}$ . So whenever there is such a $z, n,$ and t, there is a promotion by an m module for $m \le n$ at a stage after $s_t$ .

There can be at most $\sum _{o < m \le n} m-1 < n^2$ such promotions over the entire construction. Thus we can bound the total $\mathbf {c}$ -cost of ${\left \langle {A_t}\right \rangle }$ by

$$\begin{align*}\sum_n n^2 \cdot 2^{-n} < \infty. \end{align*}$$

This completes the proof of Theorem 1.4.

3.1 A proof of (a) $\Rightarrow $ (b) of Theorem 1.5

In this direction, we only need the assumption that B is K-trivial. For each one of the five classes $\mathcal {C}$ listed in Theorem 1.5, 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 _{\text {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čera and Nies [Reference Kučera and Nies23, Corollary 3.6]) 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\subseteq 2^{ \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 {\textsf {MLR}} \cap \mathcal H$ then $A \le _T Y$ (see [Reference Nies28, Proof of 5.3.15] 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 [Reference Nies30].)

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 mth 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) = \boldsymbol {\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 $\boldsymbol {\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 mth 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

$$\begin{align*}R_s = V_{x_s,s}. \end{align*}$$

Each set $R_s$ is clopen, and the sequence $(R_s)$ is computable in B. Since $\mathbf {c}(x_s,s) = \boldsymbol {\lambda } V_{x_s,s} = \boldsymbol {\lambda } R_s$ , we get $\sum _s \boldsymbol {\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 Theorem 1.5, cases (1)–(4)

In this section we prove that (b) $_{\mathcal {C}}$ implies (a) for each of the first four classes $\mathcal {C}$ mentioned in Theorem 1.5: 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 [Reference Nies31].

Using some methods from [Reference Greenberg, Hirschfeldt and Nies15], Nies showed in [Reference Nies31, Section 4] 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 [Reference Bienvenu, Downey, Greenberg, Nies and Turetsky3, Reference Nies31].

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 [Reference Nies27]) 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. Corollary 2.4 of [Reference Kjos-Hanssen and Nies22] 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 $\operatorname {\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 Definition 3.4 is a partial relativisation of Demuth tests. A $\text {Demuth}_{\text {BLR}} \langle B \rangle $ test [Reference Bienvenu, Downey, Greenberg, Nies and Turetsky3, Definition 1.7] is defined like a Demuth test relative to B, except that the function giving the $\Sigma ^0_1(B)$ index of the mth component is $\operatorname {\mathrm {BLR}}(B)$ , rather than $\omega $ -c.a. relative to B. In terms of approximation, a $\text {Demuth}_{\text {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 mth 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 _{\text {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 _{\text {T}} Y\oplus B$ . We will show that there is a $\text {Demuth}_{\text {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 [Reference Nies31, Theorem 3.2]. 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

$$\begin{align*}U_\sigma = \left\{ Z\in 2^{{\mathbb{N}}} \,:\, \sigma \preceq \Psi^{Z\oplus B} \right\}; \end{align*}$$

the sets $U_\sigma $ are $\Sigma ^0_1(B)$ , uniformly. For $m\in {\mathbb {N}}$ let

$$\begin{align*}\sigma_m = \bigcup \left\{ \sigma \,:\, (\exists x\in I_m)\,\,J^A(x)\downarrow \text{ with use }\sigma\prec A\right\}. \end{align*}$$

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 $\operatorname {\mathrm {BLR}}(A)$ : the number of mind-changes is bounded by $|I_m|$ . By assumption on A, and the lowness fact mentioned above [Reference Kjos-Hanssen and Nies22, Corollary 2.4], 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 )}$ , $\boldsymbol {\lambda }(V^{(\le \varepsilon )})\le \varepsilon $ , and $V = V^{(\le \varepsilon )}$ if $\boldsymbol {\lambda } V\le \varepsilon $ . We then let

$$\begin{align*}G_m = U_{\sigma_m}^{(\le 2^{-m})}, \end{align*}$$

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 mth 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 $\text {Demuth}_{\text {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 [Reference Nies31, Theorem 3.2]. 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 $\boldsymbol {\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, $\boldsymbol {\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 $\text {Demuth}_{\text {BLR}}$ [Reference Bienvenu, Downey, Greenberg, Nies and Turetsky3, Theorem 1.8, Proposition 4.3]: for every $\text {Demuth}_{\text {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 [Reference Nies31, Lemma 2.6] 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 Theorem 1.5, case (5)

We now consider the remaining case of Theorem 1.5: if $A\le _{\text {T}} B\oplus \Omega _R$ for every infinite computable set R, then $A\le _{\text { {SJT}}} B$ . In fact, using this assumption we prove that $A\models _B \mathbf {c}$ for every benign cost function $\mathbf {c}$ , and use Theorem 1.4, which applies since every K-trivial set is jump-traceable. We generally follow arguments in [Reference Greenberg, Miller, Nies and Turetsky17], which gives the result when $B = \emptyset $ .

Let R be infinite and computable. For $s>n$ we let

$$\begin{align*}k_s(n) = \left\lfloor{ - \log_2 (\Omega_s -\Omega_n)}\right\rfloor, \end{align*}$$

and

$$\begin{align*}\mathbf{c}_{\Omega,R}(n,s) = 2^{-|R\cap k_s(n)|} \end{align*}$$

(see [Reference Greenberg, Miller, Nies and Turetsky17, Definition 6.3]). The cost function $\mathbf {c}_{\Omega ,R}$ is benign [Reference Greenberg, Miller, Nies and Turetsky17, Proposition 9.2]. 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)$ [Reference Greenberg, Miller, Nies and Turetsky17, Proposition 9.3]. By [Reference Nies, Cooper and Soskova32, Theorem 3.4], 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 [Reference Greenberg, Miller, Nies and Turetsky17, Lemma 6.9]. 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 Lemma 3.6 assuming that A is c.e. relative to B; we then show how to remove this extra assumption.

3.3.1 Proof of Lemma 3.6 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

$$\begin{align*}U_n = \bigcup_{s\ge n} \big[ (\Omega_s)_{R^\complement}\restriction{|R^\complement \cap n|} \big] \end{align*}$$

(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 $\boldsymbol {\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 [Reference Greenberg, Miller, Nies and Turetsky17], 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 [Reference Greenberg, Miller, Nies and Turetsky17], 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 [Reference Bienvenu, Hölzl, Miller and Nies5, Lemma 3.3] (quoted as [Reference Greenberg, Miller, Nies and Turetsky17, Fact 8.1]). 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 $\boldsymbol {\lambda }(P\cap O_n)\le 2^{-n}$ . We also need the following relativisation of a characterisation of difference randomness from [Reference Franklin and Ng13]: if Y is an ML-random set,

• $(\otimes )_2:$ Y passes all B-difference tests if and only if $Y\oplus B\ge _{\text {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 _{\text {T}} \emptyset '$ . Now Y is Turing incomplete (since R is co-infinite), that is, $Y\not \ge _{\text {T}} \emptyset '$ . By a result of Day and Miller [Reference Day and Miller7], since B is K-trivial, $Y\oplus B\not \ge _{\text {T}} \emptyset '$ (this result is not needed in [Reference Greenberg, Miller, Nies and Turetsky17]). 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 [Reference Greenberg, Miller, Nies and Turetsky17] goes through when relativising to B, finishing the proof of Lemma 3.6 when A is c.e. relative to B.

4.1 The structure of the SJT degrees

Not much is known about the degree structure given by $\le _{\text { {SJT}}}$ . We can state the following.

In particular, the $\le _{\text { {SJT}}}$ -degree of B is countable, and it bounds only countably many $\le _{\text { {SJT}}}$ -degrees.

In contrast, not all initial segments of the degree structure induced by $\le _{\text { {SJT}}}$ are countable: Ng [Reference Ng24, Theorem 6.2.1] proved that the set $\{A : A \le _{\text { {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 the following question.

By the argument of the proof of Theorem 1.6 (see Section 2.1), for an affirmative answer to Question 4.3, it would suffice to show that if $A_0,A_1\le _{\text { {SJT}}} B$ and B is jump-traceable then $A_0\oplus A_1 \le _{\text {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 _{\text {JT}} B$ ). We remark that Question 4.3 for $B=\emptyset $ was first proved directly, without using cost functions (see [Reference Cholak, Downey and Greenberg6] 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 _{\text {T}} E$ that are $\le _{\text { {SJT}}}$ -incomparable. A certain obstacle to showing such structural results is the theorem of Ng [Reference Ng24] 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 _{\text { {LR}}}$ mentioned in the introduction: $A\le _{{\text { {LR}}}} B$ if ${\textsf {MLR}}^B\subseteq {\textsf {MLR}}^A$ . Every strongly jump-traceable set is K-trivial, that is, if $A\le _{\text { {SJT}}} \emptyset $ then $A \le _{\text { {LR}}} \emptyset $ .

Here Theorem 1.6 may be relevant: the relation $A\oplus B \le _{{\text { {LR}}}} B$ is much better understood than $A\le _{{\text { {LR}}}} B$ , as it has a characterisation in terms of K-triviality. In particular, this characterisation implies that every $\le _{{\text { {LR}}}}$ -degree is countable, even though some $\le _{{\text { {LR}}}}$ -degrees bound uncountably many such degrees. In contrast, we do not know whether every $\le _{\text { {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 _{\text { {LR}}} B$ , $A\le _{\text {JT}} B$ , and $A'\le _{\text {tt}} B'$ (see [Reference Nies28, Section 8.4]).

4.3 Relationship with ML-reducibility

The following relation is a main topic of the article [Reference Greenberg, Miller, Nies and Turetsky17].

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 _{\text {ML}}$ and $\le _{\text { {SJT}}}$ on the K-trivial sets. For example, the least $\le _{\text {ML}}$ -degree consists only of the computable sets, not all strongly jump-traceable sets (this shows that $\le _{\text { {SJT}}}$ does not imply $\le _{\text {ML}}$ on the K-trivials). Further, there is a greatest $\le _{\text {ML}}$ -degree of K-trivials (called the “smart” K-trivials in [Reference Bienvenu, Greenberg, Kučera, Nies and Turetsky4, Reference Greenberg, Miller, Nies and Turetsky17]). By the following proposition there is no greatest $\le _{\text { {SJT}}}$ -degree among the K-trivials; in particular, $\le _{\text {ML}}$ does not imply $\le _{\text { {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 _{\text { {SJT}}} B$ . This would strengthen Proposition 4.6.

By [Reference Greenberg, Miller, Nies and Turetsky17, Theorem 3.1], every ML-degree of a K-trivial set contains a c.e. set. By [Reference Diamondstone, Greenberg and Turetsky8], every strongly jump-traceable set is computable from a c.e. strongly jump-traceable set. It is natural to ask the following question.

A reducibility strictly weaker than $\le _{\text {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 _{\text { {SJT}}}$ . Theorem 1.5 for the class $\mathcal {C}$ being the $\omega $ -c.a. sets implies the following proposition.

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}$ [Reference Nies28, Section 8.5]. Theorem 1.5 implies the following corollary.

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 [Reference Greenberg, Miller and Nies16, Reference Greenberg, Miller, Nies and Turetsky17] are actually closed downward under the weaker SJT-reducibility.