13.9.1 Dimension in h-spaces

Greenberg and Miller [170] generalized many notions we have seen in this chapter to h-spaces. The following is the natural generalization of the notions of weak and strong s-Martin-L¨of randomness to hω.

Definition 13.9.2. Let s [0, 1].

(iii)A hω is weakly s-Martin-L¨of random if A / k Vk for all tests for weak s-Martin-L¨of randomness {Vk}k ω.

(iv)A hω is strongly s-Martin-L¨of random if A / k Vk for all tests for strong s-Martin-L¨of randomness {Vk}k ω.

Many results proved in Section 13.5 still hold for hω, such as Theorem 13.5.13, which says that if t < s and A is weakly s-random, then A is strongly t-random. Thus, for A hω, the supremum of all s for which A is weakly s-random equals the supremum of all s for which A is strongly s-random, and, by analogy with the 2ω case, can be called the e ective (Hausdor ) dimension of A, denoted by dimh(A).

We can also generalize the notion of a Solovay s-test.

Definition 13.9.3. Let s [0, 1]. A Solovay s-test is a c.e. set S h<ω

such that σ S μ( σ )s < ∞. A set A is covered by this test if A σ for infinitely many σ S.

Theorem 13.5.7 still holds: If A is weakly s-random then A is not covered by any Solovay s-test. If A is covered by some Solovay s-test then A is not weakly t-random for any t > s.

We can also define martingales for h-spaces.

Definition 13.9.4. A supermartingale (for h) is a function d : h<ω → R 0 such that for all σ h<ω,

d(σi) h(|σ|)d(σ).8

i<h(|σ|)

If s [0, 1], we say that a supermartingale d s-succeeds on A hω if lim supn d(A n)μ( A n )1−s = ∞.

8Note that this condition is equivalent to d(τ )μ( τ ) d(σ)μ( σ ), where the sum is taken over all immediate successors τ of σ.

collection, if the exponent s is smaller than 1 then the process of replacing large intervals by a collection of smaller ones may increase the s-weighted sum of the lengths of the intervals significantly. We show that if h does not grow too irregularly and we increase the exponent s slightly, then this sum remains finite.

Lemma 13.9.6 (Greenberg and Miller [170]). Suppose that (13.1) holds

which by assumption is finite.

Thus for all X hω, if (13.1) holds for t, s, and h, and dim[0,1](πh(X)) < s, then dimh(X) t. So if (13.1) holds for all t > s 0, then dim[0,1](πh(X)) = dimh(X) for all X hω.

622 13. Algorithmic Dimension

For example, (13.1) holds for all t > s 0 for the constant function h(n) = 2. Thus, as discussed above, dimension in [0, 1] is the same as dimension in 2ω. However, this condition holds for some unbounded functions

has well (for example h(n) = 2n).

The following is a su cient condition for (13.1) to hold for all t > s 0.

which is finite because 2δ < 1 and log g(n) n (since h(n) 2).

The regularity condition of Lemma 13.9.7 is not, strictly speaking, a slowness condition, because, for example, h(n) = 2n2 satisfies this condition, yet there is a monotone function that is dominated by h but does not satisfy the condition. However, the condition does hold for all su ciently slow monotone functions.

Lemma 13.9.8 (Greenberg and Miller [170]). If h is nondecreasing and dominated by 2kn for some k, then

Proof. If h is bounded then it is eventually constant, and the condition is easily verified, so assume that h is unbounded. Fix c > 0. There is an Nc such that log h(n) > c for all n Nc. For n > Nc,

Since c is arbitrary, this limit is 0.

Finally, we get the result we will need to translate between hω and 2ω.

13.9.2Slow-growing DNC functions and sets of high e ective dimension

For natural numbers a > b > 0, let Qba be the collection of functions f such that for all n,

1.f (n) {0, . . . , a − 1},

2.|f (n)| = b, and

3.if Φn(n) ↓ then Φn(n) / f (n).

By standard coding, Qba can be seen as a computably bounded Π01 subclass of ωω. Note that Q1a is essentially the same as DNCa.

To connect these sets for di erent values of a and b, we will use the concept of strong reducibility of mass problems from Definition 8.9.1. Recall that P ωω is strongly reducible to R ωω if there is a Turing functional Ψ such that Ψf P for all f R. If P is a Π01 class, then we may assume that the Ψ in the above definition is total, and hence the reduction is a truth table reduction, since we can always define ΨX (n) = 0 if there is an s such that X / P [s] and ΨX (n)[s] ↑.

Lemma 13.9.10 (Greenberg and Miller [170]). If a > b > 0 then Qba+1+1 s

Qba, uniformly in a and b. (Uniformity here means that an index for the reduction functional Ψ can be obtained e ectively from a and b.)

Proof. From n and y < a we can compute an mn,y such that

1.for all x < a such that x =y, we have Φmn,y (mn,y ) ↓= x iff Φn(n) ↓= x; and

2.Φmn,y (mn,y ) ↓= y iff either Φn(n) ↓= y or Φn(n) ↓= a.

624 13. Algorithmic Dimension

Corollary 13.9.11 (Greenberg and Miller [170]). If a 2 then Qba+1+b s

DNCa, uniformly in a and b.

For a 2 and c > 0, let Pac be the collection of functions f aω such

that for all n and all x < c, if Φ n,x ( n, x ) ↓ then Φ n,x ( n, x ) =f (n). Note that Pa1 ≡s DNCa.

Lemma 13.9.12 (Greenberg and Miller [170]). For all a > b > 0 and c > 0, if c(a − b) < a then Pac s Qba, uniformly in a, b, and c.

Proof. Fix f Qba and n. For all x < c, if Φ n,x ( n, x ) ↓ then

The set on the right has size at most c(a − b), so if c(a − b) < a then we can choose some x < a not in that set and define Ψf (n) = x.

Corollary 13.9.13 (Greenberg and Miller [170]). If a 2 and c > 0 then

Pcac s DNCa, uniformly in a and c.

Greenberg and Miller [170] used the classes Pcac to construct sequences of positive e ective dimension.

Theorem 13.9.14 (Greenberg and Miller [170]). Let a 2 and ε > 0. Every f DNCa computes a set of e ective Hausdor dimension greater than 1 − ε, via a reduction that is uniform in a and ε.9

Proof. Fix c > 1. We work in the space (ca)ω . Let d be the universal c.e. supermartingale for this space. By scaling we may assume that d(λ) < 1.

For σ (ca)<ω , let Sσ be the set of k < c such that d(σk) a|σ|+1. Note that these sets are uniformly c.e. From σ, we can compute an mσ such that

for each x < c, we have Φ mσ ,x ( mσ , x ) ↓= k if k is the xth element to be enumerated into Sσ , and Φ mσ ,x ( mσ , x ) ↑ if |Sσ | < x.

The idea here is that if d(σ) a|σ| then |Sσ| c, by the supermartingale condition, so all elements of Sσ are “captured” by the map e →Φe(e). We can thus use a function g Pcac to avoid all such extensions: given such g, inductively define X (ca)<ω by letting the (n + 1)st digit of X be g(mX n). Then, by induction, d(X n) an for all n.

9That each f DNCa computes such a set is of course not a new fact, since the Turing degree of a bounded DNC function is PA and so computes a 1-random set. The extra information is the uniformity.