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, Sn =Wg(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 andhSniis a trace, then we say thathSniis anh-trace (or that hSniis bounded byh) if for alln,|Sn|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 Π04 complete by Ng [19, 20], giving an alternative proof of the proper containment, as the K-trivial c.e. sets form a Σ03 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 Simpson2 [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∅0is 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 ∆02case. 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 ∆02case, 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 ∆02, 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 A6LRB if every B-random set isA-random, or equivalently, if KB 6+KA. 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(An)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→nq is partial computable, as its domain is c.e. (and not computable). Note thatn0= 0.
Fork < ω, let
Qk=
0,2−k,2·2−k,3·2−k, . . . ,2k−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. sequencehTkik>e such that:
(1) everyTk is ak-tree;
(2) for allk > e, if σ∈Tk and|σ| ∈Nk−1 thenσ∈Tk−1; (3) for allk,Tk has at mostkmany nonempty leaves; and (4) for allk, for all n∈Nk,An∈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>eTk. Lemma 2.7. For alln < ω,An∈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σ∈Tk, we letqk(σ) be the leastq∈Qksuch that|σ|=nq. Ifσis nonempty, thenqk(σ)>0, andqk(σ) is the uniqueq∈Qk such that|σ|=q
andnq 6=nq−2−k. For nonemptyσ∈Tk, we let Sk(σ) =n
τ : σn
qk(σ)−2−k ⊂τ ⊆σo
;
note thatσnqk(σ)−2−k isσ’s immediate predecessor onTk. For the empty stringλ we letSk(λ) ={λ}.
For k > e, let Lk be the collection of nonempty leaves σ of Tk such that
|σ| ∈Nk\Nk−1; by property (2),Lk is the set of leavesσofTksuch thatσ /∈Tk−1. We letLe=Te.
Lemma 2.8. Let k > e. For anyσ∈Lk, X
τ∈Sk(σ)
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) : nq−2−k < l6nqo
=c(nq)−c(nq−2−k).
Now by definition, we havec(nq−2−k)>q−2−k. We also assumed thatnq ∈/Nk−1. Hence q /∈ Qk−1. This implies that q+ 2−k ∈ Qk; so either q+ 2−k > q(ω) or nq+2−k > nq. In the former case, we have c(nq) < c(ω) < q + 2−k; in the latter case, we have, by minimality of nq+2−k, c(nq) < q+ 2−k. In either case we see that c(nq) < q + 2−k. Together with c(nq−2−k) > q−2−k we get
c(nq)−c(nq−2−k)<2·2−k as required.
Fork>e, let
Gk = [
σ∈Lk
Sk(σ).
Lemma 2.8 and property (3) imply that fork > e, X
τ∈Gk
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σ∈Tk,Sk(σ)⊂G. The lemma follows, since for allσ andk,σ∈Sk(σ).
Fork=e, we definedLe=Teso for allσ∈Te,Se(σ)⊆Ge.
Letk > e, and letσ∈Tk be nonempty. Letq=qk(σ). There are three cases:
• Ifnq ∈Nk−1, then by property (2),σ∈Tk−1. Certainlyσnq−2−(k−1) ⊆σnq−2−k, soSk(σ)⊆Sk−1(σ). By induction,Sk−1(σ)⊂G, soSk(σ)⊂G.
• Ifnq∈/Nk−1 andσis a leaf ofTk, thenσ∈Lk, in which case by definition ofGk, we haveSk(σ)⊂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 ∈/ Nk−1 we have q /∈Qk−1, so q+ 2−k ∈ Qk−1; since nq+2−k is defined, we have nq+2−k ∈ Nk−1. By property (2), ρ ∈ Tk−1. We have ρnq+2−k−2−(k−1) = ρnq−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(An)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Ψei be an enumeration of all partial computable functionals; recall thatJ is a partial computable functional such that for allX∈2ω,JX 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 forJAwe can obtain, uniformly ine, a (c.e. index for a) c.e.max{e, h}-trace forΨAe.
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 forJA. 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∈Ik,h(z) =k. Thus, for allk>e, for allz∈Ik, we have|Sz|6k.
3.2. The general idea. As in other constructions, we use Ψ and the trace hSzi 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 ofTk, and in that way amplify (or promote) boxes.
3.3. The construction. We let|Ik|= 2k+ 1 + (2k)2k. Forq∈Qk, fix (distinct) z(k, q)∈Ik. We let
Mk(λ) =Ik\ {z(k, q) : q∈Qk};
so |Mk(λ) = (2k)2k. Now we define Mk(ν) for every ν which is a sequence of subsets of {1,2, . . . , k} of length at most 2k. Mk(λ) has just been defined; ifν is a sequence of subsets of{1,2, . . . , k} and|ν|<2k, andMk(ν) is defined, then by induction,
|Mk(ν)|= (2k)2k−|ν|, and we let
Mk(νB) : B ⊆ {1,2, . . . , k}
be a partition ofMk(ν) into 2ksubsets of equal size, namely (2k)2k−|ν|−1= (2k)2k−|νB|. Note that ifν ⊂µthenMk(µ)⊂Mk(ν), but ifν andµare not comparable, then Mk(ν) andMk(µ) are disjoint.
Let
Q¯k =
q∈Qk : q >0, q < c(ω) & nq > nq−2−k . Q¯k is c.e., uniformly ink.
Initial testing. For allk>e, for allq∈Q¯k, we test all binary strings of lengthnq 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 inSz(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 (k0, q0) such that:
• e6k0< k, q0∈Q¯k0, and n0q6nq; or
• k0 =k,q0∈Q¯k, andq0< 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 (k0, q0) ∈P(k, q), nq0 6nq.
We say that a stringσ∈Sz(k,q)is (k, q)-preapproved if for all (k0, q0)∈P(k, q), we haveσnq0 ∈Tk0. 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) =
q0∈Q¯k : q0< q ;
note thatm62kandm>1. We further testσon all the elements of several boxes Mk(ν), whereν is a sequence of subsets of{1,2, . . . , k} of lengthm(k, q). Which such sequences? We testσon the elements ofMk(B1, . . . , Bm(k,q)) if:
(1) i∈Bm(k,q);
(2) For allq0∈Q¯k such thatq0< q, ifσj(k, q0) is an initial segment ofσ, then j /∈Bm(k,q0).
For the second condition, note that sinceσis (k, q) approved and (k, q0)∈P(k, q), and since Sz(k,q0)is an antichain of strings, there is a unique j such thatσj(k, q0) 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σintoTkif for all z on which we testedσwe haves∈Sz, that is, all tests ofσ are successful. Since hSziare 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∈Mk(λ). There areq0, q1∈Q¯k
and indicesi0, i16ksuch that σ0=σi0(k, q0) andσ1=σi1(k, q1); without loss of generality, q0 6q1. There is some ν = (B1, . . . , Bm) of lengthm=m(k, q1) such thatz∈Mk(ν).
Now there are two cases. If q0 =q1, thenσ0, σ1 are both of lengthnq0 and so are incomparable. Otherwise,q0 < q1; letm0=m(k, q0) which is smaller thanm.
There is a unique j such thatσj(k, q0) is an initial segment of σ1, and j /∈Bm0. Nowν0= (B1, . . . , Bm0) is the only sequenceµof subsets of{1,2, . . . , k}of length m0 such thatz ∈ Mk(µ); the fact that σ0 is tested on z means that σ0 is tested onMk(ν0), which in turn implies thati0 ∈ Bm0. Since j /∈Bm0 we have i0 6=j, and so σ0 =σi0(k, q0) is not an initial segment ofσ1. Since|σ0|=nq0 < nq1, we
conclude thatσ0 andσ1are incomparable.
3.4. Verification. We show that the sequencehTkik>e satisfies the properties re- quired by Proposition 2.6.
By construction, the sequencehTkik>e is uniformly c.e., and eachTk consists of strings of lengthnq for someq∈Qk. We first establish properties (1) and (2).
Lemma 3.3. Let σ∈Tk.
(1) Ifn∈Nk andn <|σ|, thenσn ∈Tk. (2) Ifk > eand|σ| ∈Nk−1, then σ∈Tk−1.
Proof. We haveNk={0} ∪ {nq q∈Q¯k}. Letq∈Q¯k such that|σ|=nq. Nowσis (k, q)-preapproved: for all (k0, q0)∈P(k, q) we have σnq0 ∈Tk0.
If n ∈ Nk, n < |σ|, then either n = 0, in which case certainly σn ∈ Tk; or n=nq0 for someq0∈Q¯k smaller thanq. In this case we have (k, q0)∈P(k, q), and soσn∈Tk.
Now suppose thatk > eand|σ|=nq ∈Nk−1. Letq0∈Q¯k−1such thatnq=nq0; then (k−1, q0)∈P(k, q). It follows thatσ=σnq0 ∈Tk−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 Mk(B1, . . . , Bm(k,q)), and so on every input in Mk(ν); and since such σ is actually enumerated into Tk, these tests must be successful. We conclude that for allz∈Mk(ν) 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,An∈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¯ksuch thatn=nq; so we show that for allk>e, for allq∈Q¯k, Anq∈Tk. This is proved by induction onk, and then onq.
Let k > e and q ∈ Q¯k. By induction, for all (k0, q0) ∈ P(k, q), we have Anq0 ∈Tk0. Letσ=Anq. The string σis tested onz(k, q), and sinceσ⊂A we haveσ∈Sz(k,q). Henceσis (k, q)-preapproved. Nowσis tested on the elements o variousMk(ν)’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]
