STRONG JUMP-TRACEABILITY II : K-TRIVIALITY

ROD DOWNEY AND NOAM GREENBERG

Abstract. We show that every strongly jump-traceable set isK-trivial. Un- like other results, we do not assume that the sets in question are computably enumerable.

1. Introduction

The last decade has seen an explosion of research connecting fundamental notions
of algorithmic randomness to computational power. One of the most remarkable
series of results concerns classes of reals which are close to being computable, as by
various measures they have very low complexity. The main example is the notion
ofK-triviality, which originates in the work of Solovay [26], and was more recently
developed starting with Downey, Hirschfeldt, Nies and Stephan [8]. Although this
notion is defined in terms of initial-segment complexity (A is K-trivial if for all
n, K(An)6^{+} K(n)^{1}), the celebrated work of Nies, Hirschfeldt and others shows
thatK triviality coincides with notions such as lowness forK, lowness for Martin-
L¨of randomness, lowness for weak 2-randomness, and being a base for randomness.

All of these notions express feebleness of an oracle with respect to some notion of algorithmic randomness: for example, a realAis low for Martin-L¨of randomness if every real which is Martin-L¨of random remains Martin-L¨of random relative to A;

in other words,Acannot detect patterns in Martin-L¨of random sets. We refer the reader to [7, 9, 23, 24, 25] for details of such results.

Terwijn [27], and then Terwijn and Zambella [29], found a new direction in this investigation. They introduced tracing as a key concept that clarifies and calibrates lowness notions.

Definition 1.1. A trace for a partial function ψ: ω → ω is a sequence hSni of finite sets such that for alln∈domψ,ψ(n)∈Sn.

Thus, a trace for a partial function ψ indirectly specifies the values of ψ by providing finitely many possibilities for each value; it provides a way of “guessing”

the values of the function ψ. Such a trace will be useful if it is easier to compute than the functionψ. In general,ψwill not be computable, but the tracehSxiwill be computable or uniformly c.e.:

Definition 1.2. LethSnibe a trace for a partial functionψ.

Both authors are supported by the Marsden Fund of New Zealand. Additionally the first author was supported by a James Cook Fellowship.

1HereKdenotes prefix-free Kolmogorov complexity. Aset, or a real, is an element of Can-
tor space 2^{ω}. Ifh, g:ω →ω, we say that h 6^{+} g if there is somed < ω such that for all n,
h(n)6g(n) +d. We assume that the reader is familiar with the rudiments of algorithmic ran-
domness as described in initial segments of Downey and Hirschfeldt [7], Nies [25], or Li-Vitanyi
[17]. We will be following the notation of Downey and Hirschfeldt [7].

1

(1) The trace is computable if the function n7→Sn is computable, that is, if there is a computable function g such that for all n, Sn = Dg(n), where hDmiis an effective enumeration of all finite sets of numbers.

(2) The trace is c.e. if the sequencehSniis uniformly c.e., that is, if there is a
computable function g such that for alln, S_{n} =W_{g(n)}, wherehWmiis an
effective enumeration of all computably enumerable sets of numbers.

We can, for example, recast classical concepts in the language of traces: a Turing degree a is hyperimmune-free if and only if every (total) function g computable from a has a computable trace. Terwijn and Zambella used a uniform version of hyperimmunity to characterise a notion of lowness.

Definition 1.3. Anorder functionis a nondecreasing, computable and unbounded
functionhsuch thath(0)>0. Ifhis an order function andhS_{n}iis a trace, then we
say thathS_{n}iis anh-trace (or that hS_{n}iis bounded byh) if for alln,|S_{n}|6h(n).

Terwijn and Zambella showed that a realA is low for Schnorr null tests if and only if there is some order functionhsuch that every (total) function computable from Ahas a computableh-trace. This was later extended by Kjos-Hanssen, Nies and Stephan[14] to show that such reals are exactly those that are low for Schnorr randomness.

Zambella (see Terwijn [27]) observed that ifAis low for Martin-L¨of randomness then there is an order functionhsuch that every function computable fromAhas a c.e.h-trace. This was improved by Nies [23], who showed that one can replace total by partial functions. In some sense it is natural to expect a connection between uniform traceability and lowness notions such as K-triviality; if every function computable (or partial computable) fromAhas a c.e.h-trace, for some slow-growing order function h, then the value ψ(n) of any such function can be described by logn+ logh(n) many bits.

The question arises: is all of this merely an interesting footnote to the study of algorithmic randomness? Or might it be possible to understand lowness and more generally randomness using purely computability-theoretic tools such as tracing?

As a test question, we would like to characterizeK-triviality by tracing, as was done with respect to Schnorr randomness, probably with respect to a family of order functions. This problem still remains open. However, an attempt toward a solution lead to the introduction of what seems now a fairly fundamental concept, which is not only interesting in its own right, but now has been shown to have deep connections with randomness.

Definition 1.4 (Figuiera, Nies and Stephan [5]). Leth be an order function. A realAish-jump-traceableif everyA-partial computable function has a c.e.h-trace.

A real isstrongly jump-traceable if it ish-jump-traceable for every order function h.

Figuiera, Nies and Stephan gave a “cost function” construction of a strongly
jump-traceable c.e. set. Answering a question from Miller and Nies [18], together
with Peter Cholak, in part I of this paper [2], the authors showed that the strongly
jump-traceable c.e. sets form a proper subclass of the c.e. K-trivial reals. They
also showed that the class formed an ideal in the c.e. degrees. This ideal was later
shown to be Π^{0}_{4} complete by Ng [19, 20], giving an alternative proof of the proper
containment, as the K-trivial c.e. sets form a Σ^{0}_{3} ideal. The paper [2] introduced

new combinatorial tools for dealing with the class of c.e., strongly jump-traceable sets, collectively known as the “box-promotion” technique.

Subsequently, the class of c.e., strongly jump-traceable sets has been shown to have remarkable connections with randomness. Greenberg, Hirschfeldt, and Nies [10] proved that a c.e. set is strongly jump-traceable if and only if it is computable from every superlow random sets, if and only if it is computable from every su- perhigh random set. Kuˇcera and Nies [15] showed that every c.e. set which is computable from a Demuth random set is strongly jump-traceable, relating such random sets with the “benign cost functions” which by work of Greenberg and Nies [11] characterise c.e., strong jump-traceability. Other attractive spin-offs in the arena of randomness include Nies’s new work on the calculus of cost functions [22]. This material is only just beginning to work itself out and we expect a lot more to grow from these ideas.

Additionally, strongly jump-traceable sets have proven to have applications in
classical computability. To illustrate, relativising the construction of Figueira, Nies
and Stephan of a noncomputable, strongly jump-traceable c.e. set yields a pseudo-
jump operator, which when inverted (Jockusch and Shore [12, 13]) yields an incom-
plete c.e. setA relative to which∅^{0} is strongly jump-traceable. Such sets are very
high, in that they resemble∅^{0}: they are all superhigh, and are almost everywhere
dominating in the sense of Dobrinen and Simpson^{2} [4]. In [6], the authors have
recently solved a question of Coles, Downey, Jockusch and LaForte [3] implicitly
going back to Jockusch and Shore [12], by showing that the pseudo-jump operator
which constructs a relative strongly jump-traceable set cannot be inverted with
avoiding upper cones in the c.e. Turing degrees. Indeed, there is a noncomputable
c.e. set which is computable fromall c.e. sets relative to which∅^{0}is strongly jump-
traceable.

All of this brings us to the present paper. Notable is the lack in all of this material of anything about non-c.e. strongly jump-traceable reals. In fact, Nies has shown that there is some order function h such that there are continuum many h-jump-traceable reals. This result could discourage attempts to show that all strongly jump-traceable sets areK-trivial.

Up to now, no adaptation of the box-promotion technique for non-c.e. sets has
been developed. In the c.e. case, the constructions make heavy usage of the fact
that a computation from a c.e. oracle, once destroyed, can never come back, clearing
the deck for future computations; this is not so in the ∆^{0}_{2}case. Translated to box-
promotion, the problem is that in the c.e. case, when boxes are promoted, they
remain promoted for ever, while in the ∆^{0}_{2}case, boxes can be demoted, introducing
seemingly unsurpassable problems. Moreover, in the general case we do not even
assume that the given strongly jump-traceable set is ∆^{0}_{2}, so no approximation to
the set is given, so it is not at all clear what it is that we trace.

In this paper we show how to overcome these difficulties, and prove the following theorem.

Theorem 1.5. There is a computable orderhsuch that everyh-jump-traceable set isK-trivial.

2Ais almost everywhere dominating if for almost all realsX, every function computable from X is dominated by some function computable fromA.

Beyond this result, much is unknown. Do the strongly jump-traceable sets form an ideal? Can they be characterised by randomness? The strongest conjecture is the following:

Conjecture 1.6. Every strongly jump-traceable set is computable from some c.e., strongly jump-traceable set.

Despite removing the assumption of computable enumerability, the construction in the current paper is similar to the earlier box-promotion constructions in that it is

“adaptive”, that is, definition of theA-partial computable function depends on what
values show up in the trace of the function. This severely restricts the applicability
of this proof to an oracle version which is obtained by partial relativisation. Nies
defined a weak reducibility associated with strong jump-traceability: for realsAand
B, A 6SJT B if for every order function h, every A-partial computable function
has aB-c.e. h-trace. This partial relativisation (A instead of A⊕B, computable
order functions instead ofB-computable order functions) is necessary to make this
relation transitive. Similarly, the weak reducibility associated with K-triviality
(really, with lowness for randomness / forK) is LR-reducibility, where A6^{LR}B if
every B-random set isA-random, or equivalently, if K^{B} 6^{+}K^{A}. The difficulty in
partially relativising an adaptive construction means that we still do not know the
answer to the following question:

Question 1.7. DoesA6SJTB implyA6LRB?

2. Solovay functions and k-trees The rest of the paper is devoted to the proof of Theorem 1.5.

Recall that a real A isK-trivial if K(A^{n})6K(n). To simplify our presenta-
tion, we replace the right hand side by a computable function. Recall that by the
minimality of K, if g is any computable function, then K6^{+} g if and only if the
sumP

n2^{−g(n)} is finite.

Definition 2.1. ASolovay function is a computable functiongsuch thatK6^{+}g
and there is an infinite setS such thatgS 6^{+} KS.

Solovay [26] showed the existence of a Solovay function. More recently, Downey and Bienvenu gave a systematic study of these functions.

Theorem 2.2.

(1) Let g be a computable function such that K 6^{+} g. Then g is a Solovay
function if and only if the numberP

n2^{−g(n)} is Martin-L¨of random.

(2) There is a Solovay functiongsuch that for all realsA,AisK-trivial if and
only ifK(An)6^{+}g(n).

We remark that in recent research, Bienvenu, Merkle and Nies extended part (2) of Theorem 2.2 and showed the equivalence holds for any Solovay function.

We fix, therefore, a Solovay function g, so Theorem 2.2(2) holds for g. By changinggby an additive constant, we assume that P

n2^{−g(n)}<1.

Definition 2.3. Forn < ω, letc(n) =P

m6n2^{−g(m)}.

The idea is that if we believe that a stringσis an initial segment of A, then we believe that every initial segment of σ is also an initial segment ofA, and so the

“cost” of asking for short descriptions ofσand all of its initial segments isc(|σ|).

We letc(ω) =P

n2^{−g(n)}. This is a left-c.e. real: the collection of rational numbers
q < c(ω) is computably enumerable.

The general plan is to enumerate a tree T which consists of strings which have short descriptions, which contains every initial segment ofA. To ensure that indeed every string onT has a short description, we use a KC (bounded request) set; so we need to show that the total cost of all strings onT is finite. This will be obtained by limiting the size of finite subsets ofT which are determined by granularity of cost.

Definition 2.4. Letq < c(ω) be a binary rational number. We letnq be the least natural numbernsuch thatc(n)>q.

Thus the functionn7→n_{q} is partial computable, as its domain is c.e. (and not
computable). Note thatn_{0}= 0.

Fork < ω, let

Qk=

0,2^{−k},2·2^{−k},3·2^{−k}, . . . ,2^{k−1}·2^{−k},1 ;
so the set of binary rationals in the interval [0,1] isS

kQk. We let Nk ={nq : q∈Qk, q < c(ω)}.

Definition 2.5. Letk < ω. Ak-tree is a set of strings T such that:

(1) For all σ∈T,|σ| ∈Nk.

(2) Ifσ∈T,n∈Nk andn <|σ|, thenσ^{n}∈T.

Ordered by extension, ak-tree is a graph-theoretic tree, and so we call an element of such a treeT with no proper extension inT aleaf ofT.

Proposition 2.6. LetAbe strongly jump-traceable. Then there is somee < ωand
a uniformly c.e. sequencehTki_{k}_{>}_{e} such that:

(1) everyTk is ak-tree;

(2) for allk > e, if σ∈Tk and|σ| ∈N_{k−1} thenσ∈T_{k−1};
(3) for allk,Tk has at mostkmany nonempty leaves; and
(4) for allk, for all n∈Nk,A^{n}∈Tk.

Proposition 2.6 details the combinatorial heart of the proof. It will be proved in the next section, using a “generalised” box-promotion argument. We now show that it is sufficient to prove the main theorem.

Proof of Theorem 1.5, given Proposition 2.6. LetT =S

k>eT_{k}.
Lemma 2.7. For alln < ω,A^{n}∈T.

Proof. This follows from the fact that S

k>eNk = ω. Let n > 0. Since c(n)> c(n−1), the interval (c(n−1), c(n)] contains some binary rational number q. Thenn=nq. Sinceq6c(n) we haveq < c(ω). There is somek>e such that

q∈Qk, son∈Nk.

Fixk>e. For everyσ∈T_{k}, we letq_{k}(σ) be the leastq∈Q_{k}such that|σ|=n_{q}.
Ifσis nonempty, thenq_{k}(σ)>0, andq_{k}(σ) is the uniqueq∈Q_{k} such that|σ|=q

andnq 6=n_{q−2}^{−k}. For nonemptyσ∈Tk, we let
S_{k}(σ) =n

τ : σn

qk(σ)−2−k ⊂τ ⊆σo

;

note thatσn_{qk}_{(σ)}−2^{−k} isσ’s immediate predecessor onTk. For the empty stringλ
we letS_{k}(λ) ={λ}.

For k > e, let L_{k} be the collection of nonempty leaves σ of T_{k} such that

|σ| ∈Nk\N_{k−1}; by property (2),Lk is the set of leavesσofTksuch thatσ /∈T_{k−1}.
We letLe=Te.

Lemma 2.8. Let k > e. For anyσ∈L_{k},
X

τ∈S_{k}(σ)

2^{−g(|τ|)}<2^{−k+1}.

Proof. Letq=qk(σ); sinceσis nonempty,q >0. The sum is X

τ∈Sk(σ)

2^{−g(|τ|)}=X n

2^{−g(l)} : n_{q−2}−k < l6n_{q}o

=c(n_{q})−c(n_{q−2}−k).

Now by definition, we havec(n_{q−2}−k)>q−2^{−k}. We also assumed thatn_{q} ∈/N_{k−1}.
Hence q /∈ Q_{k−1}. This implies that q+ 2^{−k} ∈ Q_{k}; so either q+ 2^{−k} > q(ω)
or n_{q+2}−k > n_{q}. In the former case, we have c(n_{q}) < c(ω) < q + 2^{−k}; in
the latter case, we have, by minimality of n_{q+2}^{−k}, c(nq) < q+ 2^{−k}. In either
case we see that c(nq) < q + 2^{−k}. Together with c(n_{q−2}−k) > q−2^{−k} we get

c(nq)−c(n_{q−2}−k)<2·2^{−k} as required.

Fork>e, let

Gk = [

σ∈Lk

Sk(σ).

Lemma 2.8 and property (3) imply that fork > e, X

τ∈G_{k}

2^{−g(|τ|)}6k2^{−k+1}.
LetG=S

k>eGk. Then X

τ∈G

2^{−g(|τ|)}6 X

τ∈Ge

2^{−g(|τ|)}+X

k>e

2k2^{−k}
which is finite becauseGeis finite.

Lemma 2.9. T ⊆G.

(In fact, T = G; the argument of Lemma 2.7 can be used to show that T is closed under taking initial segments.)

Proof. By induction onk>e, we show that for allσ∈T_{k},S_{k}(σ)⊂G. The lemma
follows, since for allσ andk,σ∈S_{k}(σ).

Fork=e, we definedL_{e}=T_{e}so for allσ∈T_{e},S_{e}(σ)⊆G_{e}.

Letk > e, and letσ∈Tk be nonempty. Letq=qk(σ). There are three cases:

• Ifn_{q} ∈N_{k−1}, then by property (2),σ∈T_{k−1}. Certainlyσ^{n}_{q−2}−(k−1) ⊆σ^{n}q−2−k,
soSk(σ)⊆Sk−1(σ). By induction,Sk−1(σ)⊂G, soSk(σ)⊂G.

• Ifn_{q}∈/N_{k−1} andσis a leaf ofT_{k}, thenσ∈L_{k}, in which case by definition
ofG_{k}, we haveS_{k}(σ)⊂G.

• If nq ∈/ Nk−1 and σ is not a leaf of Tk, then there is some ρ ∈ Tk ex-
tending σ such that |ρ| =q+ 2^{−k}. Since nq ∈/ N_{k−1} we have q /∈Q_{k−1},
so q+ 2^{−k} ∈ Qk−1; since n_{q+2}^{−k} is defined, we have n_{q+2}^{−k} ∈ Nk−1.
By property (2), ρ ∈ T_{k−1}. We have ρ^{n}_{q+2}−k−2−(k−1) = ρ^{n}q−2−k, so
Sk(σ)⊂Sk−1(ρ), so by induction,Sk(σ)⊂G.

It follows that

X

σ∈T

2^{−g(|σ|)}

is finite. SinceT is c.e., by the KC Theorem, there is a constantdsuch that for all
σ∈T,K(σ)6g(|σ|) +d. By Lemma 2.7, for alln,K(A^{n})6g(n) +d. The choice
ofg shows thatAisK-trivial. This completes the proof of Theorem 1.5.

3. A non-c.e. box-promotion argument

It remains to prove Proposition 2.6. As promised, this is done by a box-promotion argument. LetA be strongly jump-traceable.

3.1. The overhead of the Recursion Theorem. As standard in a box-
promotion argument, we define a partial computable functional Ψ, and by the
Recursion (fixed point) Theorem, we obtain a c.e. trace hSzi for Ψ^{A}. The trace
will be bounded by a computable functionhthat we define ahead of time, except
for finitely many inputs due to overhead from the Recursion Theorem.

Formally, this is done as follows. Let hΨ_{e}i be an enumeration of all partial
computable functionals; recall thatJ is a partial computable functional such that
for allX∈2^{ω},J^{X} is a universalA-partial computable function.

Lemma 3.1 (Cholak, Downey, and Greenberg [2]). Let h be an order function.

There is an order functionh˜ such that for allA, from a (c.e. index for a) c.e. ˜h-
trace forJ^{A}we can obtain, uniformly ine, a (c.e. index for a) c.e.max{e, h}-trace
forΨ^{A}_{e}.

By the Recursion Theorem we obtain an indexesuch that Ψ = Ψ_{e}; thiseis fixed
for the rest of the construction. We also fix, ahead of time, a c.e. ˜h-trace forJ^{A}.
Lemma 3.1 then yields a c.e. tracehSzifor Ψ^{A}, which is bounded by max{e, h(n)}.

Also ahead of time, we define a partition hIki of ω into intervals, which is of
course determined by specifying|Ik| for eachk. This defineshsince we let, for all
k, for allz∈I_{k},h(z) =k. Thus, for allk>e, for allz∈I_{k}, we have|Sz|6k.

3.2. The general idea. As in other constructions, we use Ψ and the trace hS_{z}i
totest possible initial segments ofA. Recall that the purpose is to enumerate the
sequence ofk-trees hTkiof Proposition 2.6. IfA were computable, we could have
of course letTk be the single branch consisting of initial segments ofA. SinceAis
not computable, we need to enumerate several strings intoTk. With an associated
degree of confidence, we believe they may be initial segments of A. We need to
ensure that the correct initial segments are enumerated, but that not too many
strings are enumerated.

Totest a stringσon inputz, we let Ψ^{σ}(z) =σ. The test is successful ifσ∈Sz.
Ifσis an initial segment ofA, then the test will be successful. Note that consistency
of Ψ means that we cannot test comparable strings on the same input.

Unlike the c.e. case, we do not have an approximation forA, and so we need to test arbitrary strings. The combinatorial heart of the argument is the mechanism

for deciding which strings are tested on which inputs. The general aim is to “make
the opponent pay dearly” for successful tests of wrong initial segments. To ensure
that each Tk has at most k many leaves, we will guess the sets of leaves of each
level ofT_{k}, and in that way amplify (or promote) boxes.

3.3. The construction. We let|Ik|= 2^{k}+ 1 + (2^{k})^{2}^{k}. Forq∈Qk, fix (distinct)
z(k, q)∈Ik. We let

M^{k}(λ) =Ik\ {z(k, q) : q∈Qk};

so |M^{k}(λ) = (2^{k})^{2}^{k}. Now we define M^{k}(ν) for every ν which is a sequence of
subsets of {1,2, . . . , k} of length at most 2^{k}. M^{k}(λ) has just been defined; ifν is
a sequence of subsets of{1,2, . . . , k} and|ν|<2^{k}, andM^{k}(ν) is defined, then by
induction,

|M^{k}(ν)|= (2^{k})^{2}^{k}^{−|ν|},
and we let

M^{k}(νB) : B ⊆ {1,2, . . . , k}

be a partition ofM^{k}(ν) into 2^{k}subsets of equal size, namely (2^{k})^{2}^{k}^{−|ν|−1}= (2^{k})^{2}^{k}^{−|νB|}.
Note that ifν ⊂µthenM^{k}(µ)⊂M^{k}(ν), but ifν andµare not comparable, then
M^{k}(ν) andM^{k}(µ) are disjoint.

Let

Q¯k =

q∈Qk : q >0, q < c(ω) & nq > n_{q−2}−k .
Q¯_{k} is c.e., uniformly ink.

Initial testing. For allk>e, for allq∈Q¯_{k}, we test all binary strings of lengthn_{q}
at inputz(k, q). Note that indeed all of these strings are incomparable, so this test keeps
Ψ consistent.

Approval and general testing. By induction on k > e, and then by induction on
q∈Q¯k, we describe how to further test strings that show up inS_{z(k,q)}; and decide
which strings of length nq are enumerated intoTk (we also enumerate the empty
string into everyTk).

Fork>andq∈Q¯k, letP(k, q) be the collection of all pairs (k^{0}, q^{0}) such that:

• e6k^{0}< k, q^{0}∈Q¯k^{0}, and n^{0}_{q}6nq; or

• k^{0} =k,q^{0}∈Q¯k, andq^{0}< q.

We note that since ¯Qk is not computable, neither is the domain of the function
(k, q)7→ P(k, q); but this function is partial computable. That is, once we know
that q ∈Q¯k, we can effectively compute all of P(k, q). For all (k^{0}, q^{0}) ∈P(k, q),
n_{q}^{0} 6n_{q}.

We say that a stringσ∈S_{z(k,q)}is (k, q)-preapproved if for all (k^{0}, q^{0})∈P(k, q),
we haveσn_{q}0 ∈T_{k}^{0}. Now we note that since: 1. The treeshTkiare uniformly c.e.;

2. Sz(k,q) is c.e., uniformly ink andq; and 3. The map (k, q)7→P(k, q) is partial computable; the collection of (k, q)-preapproved strings is c.e., uniformly ink and q.

Letσ_{1}(k, q), σ_{2}(k, q), . . .be an effective list of the (k, q)-preapproved strings. The
list has length at mostk, since |Sz(k,q)|6k. Note, though, that this is a c.e. list,
in the sense that if fewer than kmany such strings have been listed, we can never
be sure that no more strings will be listed in the future.

Suppose thatσ=σ_{i}(k, q) is (k, q)-preapproved. Let
m(k, q) =

q^{0}∈Q¯_{k} : q^{0}< q ;

note thatm62^{k}andm>1. We further testσon all the elements of several boxes
M^{k}(ν), whereν is a sequence of subsets of{1,2, . . . , k} of lengthm(k, q). Which
such sequences? We testσon the elements ofM^{k}(B1, . . . , Bm(k,q)) if:

(1) i∈B_{m(k,q)};

(2) For allq^{0}∈Q¯k such thatq^{0}< q, ifσj(k, q^{0}) is an initial segment ofσ, then
j /∈B_{m(k,q}0).

For the second condition, note that sinceσis (k, q) approved and (k, q^{0})∈P(k, q),
and since Sz(k,q^{0})is an antichain of strings, there is a unique j such thatσj(k, q^{0})
is defined and is an initial segment of σ, and such aj is already present when we
testσ.

Finally, ifσis a (k, q)-preapproved string, then we enumerateσintoT_{k}if for all
z on which we testedσwe haves∈S_{z}, that is, all tests ofσ are successful. Since
hS_{z}iare uniformly c.e., and since the collection of (k, q)-preapproved strings is c.e.,
uniformly inkandq, we get thatTk are uniformly c.e. as required.

Further, we notice that the testing procedure keeps Ψ consistent:

Lemma 3.2. No comparable strings are tested on an input z.

Proof. Let z ∈ Ik, and suppose that strings σ0 and σ1 are tested on z; we show
thatσ0andσ1 are incomparable. We must havez∈M^{k}(λ). There areq0, q1∈Q¯k

and indicesi0, i16ksuch that σ0=σi_{0}(k, q0) andσ1=σi_{1}(k, q1); without loss of
generality, q0 6q1. There is some ν = (B1, . . . , Bm) of lengthm=m(k, q1) such
thatz∈M^{k}(ν).

Now there are two cases. If q0 =q1, thenσ0, σ1 are both of lengthnq_{0} and so
are incomparable. Otherwise,q0 < q1; letm0=m(k, q0) which is smaller thanm.

There is a unique j such thatσ_{j}(k, q_{0}) is an initial segment of σ_{1}, and j /∈B_{m}_{0}.
Nowν_{0}= (B_{1}, . . . , B_{m}_{0}) is the only sequenceµof subsets of{1,2, . . . , k}of length
m_{0} such thatz ∈ M^{k}(µ); the fact that σ_{0} is tested on z means that σ_{0} is tested
onM^{k}(ν_{0}), which in turn implies thati_{0} ∈ B_{m}_{0}. Since j /∈B_{m}_{0} we have i_{0} 6=j,
and so σ_{0} =σ_{i}_{0}(k, q_{0}) is not an initial segment ofσ_{1}. Since|σ_{0}|=n_{q}_{0} < n_{q}_{1}, we

conclude thatσ0 andσ1are incomparable.

3.4. Verification. We show that the sequencehTki_{k}_{>}_{e} satisfies the properties re-
quired by Proposition 2.6.

By construction, the sequencehT_{k}i_{k}_{>}_{e} is uniformly c.e., and eachT_{k} consists of
strings of lengthn_{q} for someq∈Q_{k}. We first establish properties (1) and (2).

Lemma 3.3. Let σ∈Tk.

(1) Ifn∈N_{k} andn <|σ|, thenσn ∈T_{k}.
(2) Ifk > eand|σ| ∈N_{k−1}, then σ∈T_{k−1}.

Proof. We haveNk={0} ∪ {nq q∈Q¯k}. Letq∈Q¯k such that|σ|=nq. Nowσis
(k, q)-preapproved: for all (k^{0}, q^{0})∈P(k, q) we have σ^{n}q0 ∈Tk^{0}.

If n ∈ Nk, n < |σ|, then either n = 0, in which case certainly σ^{n} ∈ Tk; or
n=nq^{0} for someq^{0}∈Q¯k smaller thanq. In this case we have (k, q^{0})∈P(k, q), and
soσ^{n}∈Tk.

Now suppose thatk > eand|σ|=nq ∈Nk−1. Letq^{0}∈Q¯k−1such thatnq=nq^{0};
then (k−1, q^{0})∈P(k, q). It follows thatσ=σn_{q}0 ∈T_{k−1}.

We verify property (3):

Lemma 3.4. For allk>e,Tk has at mostkmany leaves.

Proof. Fixk>e. Forq∈Q¯k, let Lk be the set of leaves of Tk. Form=m(k, q), let

Bm={i∈ {1,2, . . . , k} : σi(k, q)∈Lk}.

Consider the sequenceν = (B1, B2, . . . , Bm^{∗}) (wherem^{∗}=m(k, q^{∗}) forq^{∗}= max{Q¯k}).

Now L is an antichain of strings. It follows that for all q ∈ Q¯k, every σ ∈ L of
lengthnq is tested on M^{k}(B1, . . . , B_{m(k,q)}), and so on every input in M^{k}(ν); and
since such σ is actually enumerated into Tk, these tests must be successful. We
conclude that for allz∈M^{k}(ν) we haveL⊆Sz. The conclusion follows from the

fact that|Sz|6kfor allz∈Ik.

And finally, property (4):

Lemma 3.5. For allk>e, for alln∈Nk,A^{n}∈Tk.

Proof. We enumerated the empty string into every Tk, so it remains to show the
lemma for every nonempty initial segment ofA. Fork >e and nonzero n∈Nk,
there is someq∈Q¯_{k}such thatn=n_{q}; so we show that for allk>e, for allq∈Q¯_{k},
Anq∈T_{k}. This is proved by induction onk, and then onq.

Let k > e and q ∈ Q¯k. By induction, for all (k^{0}, q^{0}) ∈ P(k, q), we have
Anq^{0} ∈Tk^{0}. Letσ=A^{n}q. The string σis tested onz(k, q), and sinceσ⊂A we
haveσ∈S_{z(k,q)}. Henceσis (k, q)-preapproved. Nowσis tested on the elements o
variousM^{k}(ν)’s, and since it is an initial segment ofA, all these tests are successful,

soσis enumerated into Tk as required.

References

[1] L. Bienvenu and R. Downey. Kolmogorov complexity and Solovay functions. In S. Albers and J.-Y. Marion, editors,26th Annual Symposium on Theoretical Aspects of Computer Science, (STACS 2009), volume 3 ofLeibniz International Proceedings in Informatics, pages 147–158.

Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, Germany, Dagstuhl, Germany, 2009.

[2] P. Cholak, R. Downey, and N. Greenberg. Strong-jump traceablilty I: The computably enu- merable case.Advances in Mathematics, 217:2045–2074, 2008.

[3] R. Coles, R. Downey, C. Jockusch, and G. LaForte. Completing pseudojump operators.An- nals of Pure and Applied Logic, 136:297–333, 2005.

[4] N. L. Dobrinen and S. G. Simpson. Almost everywhere domination.The Journal of Symbolic Logic, 69(3):914–922, 2004.

[5] S. Figueira, A. Nies, and F. Stephan. Lowness properties and approximations of the jump.

In Proceedings of the 12th Workshop of Logic, Language, Information and Computation (WoLLIC 2005), volume 143 of Electronic Notes in Theoretical Computer Science, pages 45–57. Elsevier, 2006.

[6] R. Downey and N. Greenberg. Failure of cone avoidance for the strong jump-traceability pseudojump operator. In preparation.

[7] R. Downey and D. Hirschfeldt, Algorithmic Randomness and Complexity, Springer-Verlag, 2010.

[8] R. Downey, D. Hirschfeldt, A. Nies, and F. Stephan. Trivial reals. In Proceedings of the 7th and 8th Asian Logic Conferences, pages 103–131. Singapore University Press and World Scientific, Singapore, 2003.

[9] R. Downey, D. Hirschfeldt, A. Nies, and S. Terwijn. Calibrating randomness.The Bulletin of Symbolic Logic, 12:411–491, 2006.

[10] N. Greenberg, D. Hirschfeldt, and A. Nies. Characterizing the strongly jump traceable sets via randomness. In preparation.

[11] N. Greenberg and A. Nies. Benign cost functions and lowness properties. To appear inThe Journal of Symbolic Logic.

[12] C. Jockusch and R. Shore. Pseudojump operators I: The r.e. case.Transactions of the Amer- ican Mathematical Society, 275(2):599–609, 1983.

[13] C. Jockusch and R. Shore. Pseudojump operators II: Transfinite iterations, hierarchies, and minimal covers.The Journal of Symbolic Logic, 49:1205–1236, 1984.

[14] B. Kjos-Hanssen, A. Nies, and F. Stephan. Lowness for the class of Schnorr random sets.

SIAM Journal on Computing, 35:647–657, 2005.

[15] A. Kuˇcera and A. Nies. Demuth randomness and computational complexity. Submitted for publication.

[16] A. Kuˇcera and S. Terwijn. Lowness for the class of random sets.The Journal of Symbolic Logic, 64:1396–1402, 1999.

[17] M. Li and P. Vitanyi.An introduction to Kolmogorov Complexity and its Applications. Texts and Monographs in Computer Science. Springer-Verlag, 1993.

[18] J. S. Miller and A. Nies. Randomness and computability: open questions. The Bulletin of Symbolic Logic, 12(3):390–410, 2006.

[19] K. M. Ng. On strongly jump traceable reals.Annals of Pure and Applied Logic, 154:51–69, 2008.

[20] K. M. Ng. Computability, Traceability and Beyond. PhD thesis, Victoria University of Wellington, 2009.

[21] A. Nies. Reals which compute little. In Z. Chatzidakis, P. Koepke, and W. Pohlers, editors, Logic Colloquium 2002, number 27 in Lecture Notes in Logic, pages 261–275. Association for Symbolic Logic, 2002.

[22] A. Nies. Calculus of cost functions. In preparation.

[23] A. Nies. Lowness properties and randomness.Advances in Mathematics, 197:274–305, 2005.

[24] A. Nies. Eliminating concepts. In C. Chong, Q. Feng, T. A. Slaman, W. H. Woodin, and Y. Yang, editors,Computational Prospects of Infinity: Part II. Presented Talks, National University of Singapore, Institute for Mathematical Sciences, volume 15 ofLecture Notes Series. Institute for Mathematical Sciences. National University of Singapore, pages 225–

248. World Scientific Publishing Company, Singapore, 2008.

[25] A. Nies. Computability and Randomness. Oxford Logic Guides. Oxford University Press, 2009.

[26] R. Solovay. Draft of paper (or series of papers) on Chaitin’s work. unpublished notes, May 1975. 215 pages.

[27] S. Terwijn.Computability and Measure. PhD thesis, The Institute for Logic, Language and Computation (ILLC), University of Amsterdam, 1998.

[28] S. Terwijn. Complexity and randomness.Rendiconti del Seminario Matematico di Torino, 62(1):1–38, 2004. Notes for a course given at the University of Auckland, March 2003.

[29] S. Terwijn and D. Zambella. Algorithmic randomness and lowness.The Journal of Symbolic Logic, 66:1199–1205, 2001.

School of Mathematics, Statistics and Operations Research, Victoria University, P.O. Box 600, Wellington, New Zealand

E-mail address:[email protected], [email protected]