Propagation of partial randomness

Kojiro Higuchi

Department of Mathematics and Informatics Faculty of Science, Chiba University 1-33 Yayoi-cho, Inage, Chiba, JAPAN khiguchi@g.math.s.chiba-u.ac.jp

W. M. Phillip Hudelson

One Oxford Center, Suite 2600 301 Grant Street Pittsburgh, PA 15219, USA phil.hudelson@gmail.com

Stephen G. Simpson

Department of Mathematics Pennsylvania State University University Park, PA 16802, USA http://www.personal.psu.edu/t20 t20@psu.edu

Keita Yokoyama

School of Information Science Japan Advanced Institute of Science and Technology 1-1 Asahidai, Nomi, Ishikawa, 923-1292, JAPAN y-keita@jaist.ac.jp

First draft: April 21, 2011 This draft: May 21, 2014

Abstract Let f be a computable function from finite sequences of 0’s and 1’s to real numbers. We prove that strong f-randomness implies strong frandomness relative to a PA-degree. We also prove: if X is strongly f-random and Turing reducible to Y where Y is Martin-Löf random relative to Z, then X is strongly f-random relative to Z. In addition, we prove analogous propagation results for other notions of partial randomness, including non-K-triviality and autocomplexity. We prove that frandomness relative to a PA-degree implies strong f-randomness, hence f-randomness does not imply f-randomness relative to a PA-degree.

Keywords: partial randomness, effective Hausdorff dimension, Martin-Löf randomness, Kolmogorov complexity, models of arithmetic. 2010 Mathematics Subject Classification: Primary 03D32, Secondary 03D28, 68Q30, 03H15, 03C62, 03F30.

A version of this paper has been published in Annals of Pure and Applied Logic, 165(2):742–758, 2014.

Contents

Abstract  1
1 Introduction  2
2 f-randomness and strong f-randomness  4
3 g-randomness implies strong f-randomness  7
4 Propagation of strong f-randomness  8
5 Propagation of non-K-triviality  11
6 Propagation of diagonal nonrecursiveness  12
7 Propagation of autocomplexity  15
8 Vehement f-randomness  18
9 Propagation of vehement f-randomness  21
10 Other characterizations of strong f-randomness  22
11 Non-propagation of f-randomness  24
References  24

1 Introduction

We begin by recalling two known results concerning Martin-Löf randomness relative to a Turing oracle. Let ℕ denote the set of positive integers. Let \{0, 1\}^{ℕ} denote the \underline{Cantor space}, i.e., the set of infinite sequences of 0’s and 1’s.

Theorem 1.1. Let X ∈ {0, 1}^{ℕ} be Martin-Löf random. Suppose X is Turing reducible to Y where Y is Martin-Löf random relative to Z. Then X is Martin-Löf random relative to Z.

Theorem 1.2. Let Q be a nonempty Π_{1}^{0} subset of {0, 1}^{ℕ}. If X ∈ {0, 1}^{ℕ} is Martin-Löf random, then X is Martin-Löf random relative to some Z ∈ Q.

Recall from [18] that a \underline{PA-degree} is defined to be the Turing degree of a complete consistent theory extending first-order Peano arithmetic. It is well known that, via Gödel numbering, the set of complete consistent theories extending first-order Peano arithmetic may be viewed as a Π_{1}^{0} subset of {0, 1}^{ℕ}. Moreover [18, 29, 32, 33], this particular Π_{1}^{0} subset of {0, 1}^{ℕ} is universal in the following sense: a Turing oracle Z is of PA-degree if and only if every nonempty Π_{1}^{0} subset of {0, 1}^{ℕ} contains an element which is Turing reducible to Z. Consequently, Theorem 1.2 may be restated as follows:

Theorem 1.3. If X ∈ {0, 1}^{ℕ} is Martin-Löf random, then X is Martin-Löf random relative to some PA-degree.

Theorem 1.1, which we call the XYZ Theorem, is due to Miller/Yu [22, Theorem 4.3]. Theorems 1.2 and 1.3 are due independently to several groups of researchers: Downey et al [10, Proposition 7.4], Reimann/Slaman [27, Theorem 4.5] (also cited in [10]), and Simpson/Yokoyama [37, Lemma 3.3].

Theorems 1.2 and 1.3 have been very useful in the study of randomness. Reimann/Slaman [27] used Theorem 1.2 to prove that any noncomputable X ∈ {0, 1}^{ℕ} is nonatomically random with respect to some probability measure on {0, 1}^{ℕ}. Simpson/Yokoyama [37] used a generalization of Theorem 1.2 to study the reverse mathematics of Loeb measure. Recently Brattka/Miller/Nies [5] used Theorem 1.2 to prove that x ∈ [0, 1] is random if and only if every computable continuous function of bounded variation is differentiable at x.

The theme of Theorems 1.1–1.3 is what might be called “propagation of Martin-Löf randomness.” Namely, all of these theorems assert that if X is Martin-Löf random then X is Martin-Löf random relative to certain Turing oracles.

The purpose of this paper is to present some new results which are generalizations of Theorems 1.1–1.3. The theme of our new results might be called “propagation of partial randomness.” Here “partial randomness” refers to certain properties which are in the same vein as Martin-Löf randomness. Recent studies of partial randomness include [6, 16, 19, 21, 25, 28, 39]. Our main new results involve a specific notion of partial randomness known as strong frandomness where f is an arbitrary computable function from finite sequences of 0’s and 1’s to real numbers. Along the way we present some old and new characterizations of strong f-randomness. We also consider other notions of partial randomness including complexity [4, 15, 19], autocomplexity [19], and non-K-triviality [11, 23].

The plan of this paper is as follows. In §2 we define f-randomness and strong f-randomness and characterize these notions in terms of Kolmogorov complexity. In §3 we prove that (f + 2 log_{2} f)-randomness implies strong f-randomness. Note that §2 and §3 and §8 are largely expository. In §4 we present our main results concerning propagation of strong f-randomness. Namely, we prove appropriate generalizations of Theorems 1.1–1.3 with Martin-Löf randomness replaced by strong f-randomness. In §5 and §6 we prove analogous results concerning propagation of non-K-triviality and propagation of diagonal nonrecursiveness, respectively. In §7 we prove analogous results concerning propagation of autocomplexity, and we characterize autocomplexity in terms of f-randomness and strong f-randomness. In §8 we define vehement f-randomness and prove that it is equivalent to strong f-randomness, provided f is convex. In §9 we prove a version of Theorem 1.2 with Martin-Löf randomness replaced by vehement f-randomness. In §10 we present two new characterizations of strong f-randomness. In §11 we show that our results concerning propagation of strong f-randomness fail for f-randomness.

2 f-randomness and strong f-randomness

Let f : {0, 1}^{∗} → [−∞, ∞] be an arbitrary computable function from finite sequences of 0’s and 1’s to the extended^{1} real numbers. In this section we define what it means for X ∈ {0, 1}^{ℕ} to be f-random, strongly f-random, f-complex, and strongly f-complex.

Recall that according to Schnorr’s Theorem (see [11, Theorem 6.2.3] or [23, Theorem 3.2.9] or [34, Theorem 10.7]), X is Martin-Löf random if and only if for all n the prefix-free Kolmogorov complexity of the first n bits of X is at least n modulo an additive constant. In this section we prove generalizations of Schnorr’s Theorem, replacing Martin-Löf randomness by f-randomness and strong f-randomness. Our proofs are modeled on one of the standard proofs [34, Theorem 10.7] of Schnorr’s Theorem.

This section is mostly expository. For the history of the concepts and results in this section, see Calude/Staiger/Terwijn [6] and Tadaki [39].

Definition 2.1. For X ∈ {0, 1}^{ℕ} and n ∈ ℕ we write X↾n = X↾{1, …, n} = the first n bits of X. Given f : \{0, 1\}^{∗} → [−∞, ∞] we define X to be \underline{f-complex} or \underline{strongly f-complex} if

∃c ∀n (KP(X↾n) ≥ f(X↾n) − c)

or

∃c ∀n (KA(X↾n) ≥ f(X↾n) − c)

respectively. Here KP and KA denote \underline{prefix-free complexity} (see [11, §3.5] or [23, §2.2] or [34, §10]) and \underline{a priori complexity} (see [11, §3.16] or [40]) respectively.

Definition 2.2. Given f : \{0, 1\}^{∗} → [−∞, ∞], the \underline{f-weight} of σ ∈ \{0, 1\}^{∗} is defined as wt_{f}(σ) = 2^{−f(σ)}. The \underline{direct f-weight} of A ⊆ \{0, 1\}^{∗} is defined as dwt_{f}(A) = ∑_{σ∈A} wt_{f}(σ). A set P ⊆ \{0, 1\}^{∗} is said to be \underline{prefix-free} if no element of P is a proper initial segment of an element of P. The \underline{prefix-free f-weight} of A is defined as

pwt_{f}(A) = sup{dwt_{f}(P) | P ⊆ A is prefix-free}.

Definition 2.3. For σ ∈ {0, 1}^{∗} we write ⟦σ⟧ = {X ∈ {0, 1}^{ℕ} | σ ⊂ X}. For A ⊆ {0, 1}^{∗} we write ⟦A⟧ = ⋃_{σ∈A}⟦σ⟧ and

Â = {σ ∈ A | ∄ρ (ρ ⊂ σ and ρ ∈ A)} = the set of minimal elements of A.

Note that Â is prefix-free and ⟦Â⟧ = ⟦A⟧.

We write \underline{r.e.} as an abbreviation for recursively enumerable. A sequence of sets A_{i} ⊆ \{0, 1\}^{∗}, i ∈ ℕ is said to be \underline{uniformly r.e.} if \{(σ, i) | σ ∈ A_{i}\} is r.e.

1We define f : {0, 1}^{∗} → [−∞, ∞] to be computable if f/(|f| + 1) : {0, 1}^{∗} → [−1, 1] is computable.

Definition 2.4. Assume that f : {0, 1}^{∗} → [−∞, ∞] is computable. We define X ∈ \{0, 1\}^{ℕ} to be \underline{f-random} or \underline{strongly f-random} if X ∉ ⋂_{i}⟦A_{i}⟧ whenever A_{i} is uniformly r.e. with dwt_{f}(A_{i}) ≤ 2^{−i} or pwt_{f}(A_{i}) ≤ 2^{−i} respectively.

Remark 2.5. Since pwt_{f}(A) ≤ dwt_{f}(A) for all A, it is clear that strong frandomness implies f-randomness. Similarly, since ∃c ∀τ (KA(τ) ≤ KP(τ) + c), it is clear that strong f-complexity implies f-complexity. Note also that wt_{f} is a premeasure in the sense of [26, Definition 1].

The next theorem is a straightforward generalization of Tadaki [39, Theorem 3.1].

Theorem 2.6. Let f : {0, 1}^{∗} → [−∞, ∞] be computable. Then f-randomness is equivalent to f-complexity.

Proof. Suppose X is f-random. Let S_{i} = {τ | KP(τ) < f(τ) − i}. Clearly S_{i} is uniformly r.e., and by Kraft’s Inequality [34, Theorem 10.3] we have

dwt_{f}(S_{i}) = ∑_{τ∈S_{i}} 2^{−f(τ)} ≤ ∑_{τ∈S_{i}} 2^{−KP(τ)−i} = 2^{−i} ∑_{τ∈S_{i}} 2^{−KP(τ)} < 2^{−i}

so S_{i} is a test for f-randomness. Since X is f-random it follows that X ∉ ⋂_{i}⟦S_{i}⟧, i.e., ∃i ∀n (KP(X↾n) ≥ f(X↾n) − i), i.e., X is f-complex.

Now suppose X is not f-random, say X ∈ ⋂_{i}⟦A_{i}⟧ where A_{i} is uniformly r.e. and dwt_{f}(A_{i}) ≤ 2^{−i}. Then

∑_{i} ∑_{τ∈A_{2i}} 2^{−f(τ)+i} = ∑_{i} 2^{i}dwt_{f}(A_{2i}) ≤ ∑_{i} 2^{i}2^{−2i} = ∑_{i} 2^{−i} = 1

so by the Kraft/Chaitin Lemma (see [34, Corollary 10.6]) we have

∃c ∀i ∀τ (τ ∈ A_{2i} ⇒ KP(τ) ≤ f(τ) − i + c).

Since X ∈ ⋂_{i}⟦A_{2i}⟧ it follows that ∃c ∀i ∃n (KP(X↾n) ≤ f(X↾n) − i + c). In other words, X is not f-complex. This completes the proof.

Corollary 2.7. The sets S_{i} = {τ | KP(τ) < f(τ) − i} form a universal test for f-randomness.

Proof. Paraphrasing Theorem 2.6 we see that X is f-random if and only if X ∉ ⋂_{i}⟦S_{i}⟧. It remains to prove that dwt_{f}(S_{i}) ≤ 2^{−i}, but we have already seen this as part of the proof of Theorem 2.6.

The next theorem is a straightforward generalization of Calude/Staiger/Terwijn [6, Corollary 4.10].

Theorem 2.8. Let f : {0, 1}^{∗} → [−∞, ∞] be computable. Then strong frandomness is equivalent to strong f-complexity.

Proof. Recall that KA(τ) = − log_{2} m(τ) where m : {0, 1}^{∗} → [0, 1] is a universal left-r.e. semimeasure. See for instance [11, §3.16] or [40].

Suppose X is strongly f-random. Let S_{i} = {τ | KA(τ) < f(τ) − i}. Clearly S_{i} is uniformly r.e. We claim that pwt_{f}(S_{i}) ≤ 2^{−i}. To see this, let P ⊆ S_{i} be prefix-free. Then

dwt_{f}(P) = ∑_{τ∈P} 2^{−f(τ)} ≤ ∑_{τ∈P} 2^{−i−KA(τ)} = 2^{−i} ∑_{τ∈P} m(τ) ≤ 2^{−i}

since m is a semimeasure. This proves our claim. Thus S_{i} is a test for strong f-randomness. Since X is strongly f-random, we have X ∉ ⋂_{i}⟦S_{i}⟧, i.e., ∃i ∀n (KA(X↾n) ≥ f(X↾n) − i), i.e., X is strongly f-complex.

Now suppose X is not strongly f-random, say X ∈ ⋂_{i}⟦A_{i}⟧ where A_{i} is uniformly r.e. and pwt_{f}(A_{i}) ≤ 2^{−i}. For each i let m_{i} be the uniformly leftr.e. semimeasure given by m_{i}(σ) = pwt_{f}({τ ∈ A_{i} | τ ⊇ σ}). Note that m_{i}(τ) ≥ wt_{f}(τ) whenever τ ∈ A_{i}. For each i we have m_{i}(⟨⟩) = pwt_{f}(A_{i}) ≤ 2^{−i}, hence 2^{i}m_{2i}(⟨⟩) ≤ 2^{i}2^{−2i} = 2^{−i}, so consider the left-r.e. semimeasure \overline{m}(σ) = ∑_{i} 2^{i}m_{2i}(σ). Since m is a universal left-r.e. semimeasure, let c be such that \overline{m}(σ) ≤ 2^{c}m(σ) for all σ. Then for all τ ∈ A_{2i} we have 2^{i−f(τ)} = 2^{i}wt_{f}(τ) ≤ 2^{i}m_{2i}(τ) ≤ \overline{m}(τ) ≤ 2^{c}m(τ) = 2^{c−KA(τ)}, hence KA(τ) ≤ f(τ) − i + c. Since X ∈ ⋂_{i}⟦A_{2i}⟧ it follows that ∀i ∃n (KA(X↾n) ≤ f(X↾n) − i + c). In other words, X is not strongly f-complex. This completes the proof.

Corollary 2.9. The sets S_{i} = {τ | KA(τ) < f(τ) − i} form a universal test for strong f-randomness.

Proof. Paraphrasing Theorem 2.8 we see that X is strongly f-random if and only if X ∉ ⋂_{i}⟦S_{i}⟧. It remains to prove that pwt_{f}(S_{i}) ≤ 2^{−i}, but we have already seen this as part of the proof of Theorem 2.8.

Remark 2.10. As a special case, consider the functions f_{s} : {0, 1}^{∗} → [0, ∞) given by f_{s}(σ) = s|σ| where s is rational and 0 < s ≤ 1. Here we are writing |σ| = the length of σ. Define X ∈ \{0, 1\}^{ℕ} to be \underline{s-random} if it is f_{s}- random, and \underline{strongly s-random} if it is strongly f_{s}-random. Note that Martin-Löf randomness is equivalent to 1-randomness and to strong 1-randomness. The \underline{effective Hausdorff dimension} of X is

effdim(X) = sup{s | X is s-random} = sup{s | X is strongly s-random}

and this notion has been studied in [21, 25, 39] and many other publications.

Remark 2.11. Given a computable function f : {0, 1}^{∗} → [−∞, ∞], it is easy to see that {X | X is f-random} and {X | X is strongly f-random} are Σ_{2}^{0} subsets of {0, 1}^{ℕ}. Conversely, given a Σ_{2}^{0} set S ⊆ {0, 1}^{ℕ}, we can easily construct a computable function f : {0, 1}^{∗} → ℕ such that

S = {X | X is f-random} = {X | X is strongly f-random}.

Namely, if S = ⋃_{i}{paths through T_{i}} where T_{i} ⊆ {0, 1}^{∗}, i ∈ ℕ is a computable sequence of computable trees, let

f(τ) = \{ \begin{matrix}1 & if h(τ↾(|τ| − 1)) = h(τ), \\ 2|τ| & otherwise, \end{matrix}

where h(τ) = the least i such that i = |τ| or τ ∈ T_{i}. We mention these examples in order to suggest how our concepts of f-randomness and strong f-randomness may apply to a wide variety of situations. See also Theorem 7.3 below.

3 g-randomness implies strong f-randomness

Suppose we have two computable functions f, g : {0, 1}^{∗} → [−∞, ∞]. Clearly g-randomness implies f-randomness provided ∀σ (f(σ) ≤ g(σ)). We now prove that g-randomness implies strong f-randomness provided g grows significantly faster than f. Our result here is a slight refinement of known results due to Calude/Staiger/Terwijn [6] and Reimann/Stephan [28]. See also Uspensky/Shen [40, §4.2].

Definition 3.1. The \underline{increasing set} of f : \{0, 1\}^{∗} → [−∞, ∞] is

I(f) = {σ | (∀ρ ⊂ σ) (f(ρ) < f(σ))}.

Lemma 3.2. Given a computable function f : {0, 1}^{∗} → [−∞, ∞], we can effectively find a computable function \overline{f} : \{0, 1\}^{∗} → ℕ such that for all σ,

f_{0}(σ) < \overline{f}(σ) < f_{0}(σ) + 2  (1)

where f_{0}(σ) = min(max(f(σ), 0), 2|σ|). It then follows that f-randomness is equivalent to \overline{f}-randomness, and strong f-randomness is equivalent to strong \overline{f}-randomness.

Proof. Given σ ∈ \{0, 1\}^{∗} we can effectively approximate f_{0}(σ) to find \overline{f}(σ) ∈ ℕ such that (1) holds. In this way we obtain a computable function \overline{f} : \{0, 1\}^{∗} → ℕ. Using the fact that ∃c ∀σ (0 < KP(σ) < 2|σ|+c and 0 < KA(σ) < 2|σ|+c), we can easily see that (strong) f-complexity is equivalent to (strong) \overline{f}-complexity. The desired conclusions then follow in view of Theorems 2.6 and 2.8.

Lemma 3.3. Let f : {0, 1}^{∗} → ℕ be computable. Given an r.e. set A ⊆ {0, 1}^{∗} we can effectively find an r.e. set \overline{A} ⊆ I(f) such that ⟦A⟧ ⊆ ⟦\overline{A}⟧ and dwt_{f}(\overline{A}) ≤ dwt_{f}(A) and pwt_{f}(\overline{A}) ≤ pwt_{f}(A).

Proof. Let \overline{A} = \{\overline{σ} | σ ∈ A\} where \overline{σ} = min\{ρ ⊆ σ | f(ρ) ≥ f(σ)\}. It is straightforward to verify that this \overline{A} has the desired properties.

Remark 3.4. Because of Lemmas 3.2 and 3.3, we are often safe in assuming that f : {0, 1}^{∗} → ℕ and that A ⊆ I(f).

Theorem 3.5. Let f, g : {0, 1}^{∗} → [−∞, ∞] be computable with g of the form g(σ) = f(σ) + h(f(σ)) where h is nondecreasing and ∑_{n=1}^{∞} 2^{−h(n)} < ∞. If X is g-random, then X is strongly f-random.

Proof. Because h is nondecreasing, we may safely apply Lemma 3.2 to assume that f : {0, 1}^{∗} → ℕ. Fix c such that ∑_{n} 2^{−h(n)} ≤ 2^{c} < ∞. Suppose X is not strongly f-random, say X ∈ ⋂_{i}⟦A_{i}⟧ where A_{i} is uniformly r.e. and pwt_{f}(A_{i}) ≤ 2^{−i}. By Lemma 3.3 we may safely assume that A_{i} ⊆ I(f) for all i. Let P_{in} = {σ ∈ A_{i} | f(σ) = n}. Clearly A_{i} = ⋃_{n} P_{in} and P_{in} is prefix-free. Thus dwt_{f}(P_{in}) ≤ pwt_{f}(A_{i}) and

dwt_{g}(A_{i}) = ∑_{σ∈A_{i}} 2^{−g(σ)}
= ∑_{σ∈A_{i}} 2^{−h(f(σ))}2^{−f(σ)}
= ∑_{n} ∑_{σ∈P_{in}} 2^{−h(n)}2^{−f(σ)}
= ∑_{n} 2^{−h(n)} ∑_{σ∈P_{in}} 2^{−f(σ)}
= ∑_{n} 2^{−h(n)}dwt_{f}(P_{in})
≤ 2^{c}pwt_{f}(A_{i})
≤ 2^{c−i}.

Since X ∈ ⋂_{i}⟦A_{i}⟧ it follows that X is not g-random, Q.E.D.

Theorem 3.6. Let f : {0, 1}^{∗} → (0, ∞] be computable. Suppose X is (f + (1 + ϵ) log_{2} f)-random for some ϵ > 0. Then X is strongly f-random.

Proof. We may safely assume that ϵ is rational. In this case it suffices to apply Theorem 3.5 with h(x) = (1 + ϵ) log_{2} x.

Remark 3.7. Consider the computable function f = f_{s} where s = 1/2, i.e., f(σ) = |σ|/2 for all σ. (More generally, let f be computable and satisfy certain other conditions which we shall not specify here.) Reimann/Stephan [28] have constructed an X which is f-random but not strongly f-random. Hudelson [16] has constructed an X which is strongly f-random but such that no Y Turing reducible to X is (f + (1 + ϵ) log_{2} f)-random for any ϵ > 0. We conjecture that there exists an X which is f-random but such that no Y Turing reducible to X is strongly f-random.

Remark 3.8. In Theorem 3.6 and Remark 3.7 we may replace f +(1+ϵ) log_{2} f by f + log_{2} f + (1 + ϵ) log_{2} log_{2} f, etc., as in [40, §4.2].

4 Propagation of strong f-randomness

The purpose of this section is to prove generalizations of Theorems 1.1–1.3 in which Martin-Löf randomness is replaced by strong f-randomness. These generalizations are perhaps the most important new results of this paper. Let μ be the \underline{fair-coin probability measure} on \{0, 1\}^{ℕ} given by μ(⟦σ⟧) = 2^{−|σ|}.

Definition 4.1. A \underline{Levin system} is an indexed family of sets V_{σ} ⊆ \{0, 1\}^{ℕ}, σ ∈ {0, 1}^{∗}, such that

1. V_{σ} is Σ_{1}^{0} uniformly in σ,

2. V_{σ} ⊇ V_{σ^{⌢}⟨0⟩} ∪ V_{σ^{⌢}⟨1⟩} for all σ,

3. V_{σ^{⌢}⟨0⟩} ∩ V_{σ^{⌢}⟨1⟩} = ∅ for all σ. These properties easily imply

4. V_{ρ} ⊇ V_{σ} whenever ρ ⊆ σ,

5. V_{σ} ∩ V_{τ} = ∅ whenever σ and τ are incompatible. Lemma 4.2. Let V_{σ} be a Levin system, and let f be computable. If X is strongly f-random, then ∃c ∀n (μ(V_{X↾n}) ≤ 2^{c−f(X↾n)}). Proof. Let A_{i} = {σ | μ(V_{σ}) > 2^{i−f(σ)}}. Clearly A_{i} is uniformly r.e. We claim that pwt_{f}(A_{i}) ≤ 2^{−i}. To see this, let P ⊆ A_{i} be prefix-free. By part 5 of Definition 4.1 we have 1 ≥ μ(⋃_{σ∈P} V_{σ}) = ∑_{σ∈P} μ(V_{σ}) ≥ ∑_{σ∈P} 2^{i−f(σ)} = 2^{i}dwt_{f}(P), so dwt_{f}(P) ≤ 2^{−i}. This proves our claim. Thus A_{i} is a test for strong f-randomness. Since X is strongly f-random, it follows that X ∉ ⟦A_{i}⟧ for some i. In other words, μ(V_{X↾n}) ≤ 2^{i−f(X↾n)} for all n, Q.E.D. Remark 4.3. Our idea of using strong f-randomness in Lemma 4.2 was inspired by Reimann’s use of strong f-randomness in [26, Theorem 14]. Lemma 4.4. Let r_{σ}, σ ∈ {0, 1}^{∗}, be a uniformly left-r.e. system of real numbers. Given a Levin system V_{σ}, we can effectively find a Levin system Ṽ_{σ} such that

1. Ṽ_{σ} ⊆ V_{σ} for all σ,

2. μ(Ṽ_{σ}) ≤ r_{σ} for all σ,

3. Ṽ_{σ} = V_{σ} whenever σ is such that μ(V_{ρ}) < r_{ρ} for all ρ ⊆ σ. Proof. The proof is awkward but straightforward. Theorem 4.5. Let f : {0, 1}^{∗} → [−∞, ∞] be computable. Suppose X is strongly f-random and Turing reducible to Y where Y is Martin-Löf random relative to Z. Then X is strongly f-random relative to Z. Proof. Let Φ be a partial recursive functional such that X = Φ^{Y}. Consider the Levin system V_{σ} = \{\overline{Y} | Φ\overline{Y} ⊇ σ\}. By Lemma 4.2 let c be such that μ(V_{X↾n}) < 2^{c−f(X↾n)} for all n. Applying Lemma 4.4 with r_{σ} = 2^{c−f(σ)} we obtain a Levin system Ṽ_{σ} such that μ(Ṽ_{σ}) ≤ 2^{c−f(σ)} for all σ, and Y ∈ V_{X↾n} = Ṽ_{X↾n} for all n. Now suppose X is not strongly f-random relative to Z, say X ∈ ⋂_{i}⟦A_{i}^{Z}⟧ where A_{i}^{Z} is uniformly Z-r.e. and pwt_{f}(A_{i}^{Z}) ≤ 2^{−i}. Let W_{i}^{Z} = ⋃_{σ∈A_{i}^{Z}} Ṽ_{σ}. Clearly W_{i}^{Z} is uniformly Σ_{1}^{0,Z}. Because X ∈ ⋂_{i}⟦A_{i}^{Z}⟧ and Y ∈ ⋂_{n} V_{X↾n} = ⋂_{n} Ṽ_{X↾n}, we have Y ∈ ⋂_{i} W_{i}^{Z}. Let P_{i} = Â_{i}^{Z} = {minimal elements of A_{i}^{Z}}. Because Ṽ_{σ} is a Levin system, we have W_{i}^{Z} = ⋃_{σ∈P_{i}} Ṽ_{σ} and hence

μ(W_{i}^{Z}) = ∑_{σ∈P_{i}} μ(Ṽ_{σ}) ≤ ∑_{σ∈P_{i}} 2^{c−f(σ)} = 2^{c}dwt_{f}(P_{i}) ≤ 2^{c}pwt_{f}(A_{i}^{Z}) ≤ 2^{c−i}

since P_{i} is a prefix-free subset of A_{i}^{Z}. Thus Y is not Martin-Löf random relative to Z, Q.E.D.

Remark 4.6. In Theorem 4.5 the assumption “Y is Martin-Löf random relative to Z” cannot be weakened to “Y is strongly f-random relative to Z.” For example, define Z(n) = Y (2n) where Y is Martin-Löf random. Then Z is strongly 1/2-random (indeed Martin-Löf random) and Turing reducible to Y, and Y is strongly 1/2-random relative to Z, but of course Z is not strongly 1/2-random relative to Z.

Theorem 4.7. For each i ∈ ℕ let f_{i} : {0, 1}^{∗} → [−∞, ∞] be computable and let X_{i} ∈ {0, 1}^{ℕ}. Suppose ∀i (X_{i} is strongly f_{i}-random). Then, we can find Z of PA-degree such that ∀i (X_{i} is strongly f_{i}-random relative to Z).

Proof. By the Kučera/Gács Theorem (see [11, Theorem 8.3.2] or [23, §3.3] or [34, Theorem 3.8]), let Y be Martin-Löf random such that ∀i (X_{i} is Turing reducible to Y). By Theorem 1.3 let Z be of PA-degree such that Y is Martin-Löf random relative to Z. If ∀i (X_{i} is strongly f_{i}-random), it follows by Theorem 4.5 that ∀i (X_{i} is strongly f_{i}-random relative to Z).

Corollary 4.8. Let f : {0, 1}^{∗} → [−∞, ∞] be computable. If X is strongly f-random, then X is strongly f-random relative to some PA-degree.

Proof. Apply Theorem 4.7 with X_{i} = X and f_{i} = f for all i.

Even the following corollary appears to be new.

Corollary 4.9. Suppose (∀i ∈ ℕ) (X_{i} is Martin-Löf random). Then, we can find Z of PA-degree such that (∀i ∈ ℕ) (X_{i} is Martin-Löf random relative to Z).

Proof. Consider f : {0, 1}^{∗} → [0, ∞) where f(σ) = |σ| for all σ. By Remark 2.10 X_{i} is Martin-Löf random if and only if X_{i} is strongly f-random, and similarly X_{i} is Martin-Löf random relative to Z if and only if X_{i} is strongly f-random relative to Z. Apply Theorem 4.7 with f_{i} = f for all i.

We end this section by presenting a kind of Borel/Cantelli Lemma for strong f-randomness. Let us say that X is \underline{strongly BC-f-random} if \{i | X ∈ ⟦A_{i}⟧\} is finite whenever A_{i} is uniformly r.e. and ∑_{i} pwt_{f}(A_{i}) < ∞. This notion resembles a generalization of Tadaki’s earlier notion of Solovay D-randomness [39, Definition 3.8].

Theorem 4.10. Let f : {0, 1}^{∗} → [−∞, ∞] be computable. Suppose X is strongly f-random and Turing reducible to Y where Y is Martin-Löf random relative to Z. Then X is strongly BC-f-random relative to Z.

Proof. Suppose X is not strongly BC-f-random relative to Z. Let A_{i}^{Z} be uniformly Z-r.e. such that ∑_{i} pwt_{f}(A_{i}^{Z}) < ∞ and X ∈ ⟦A_{i}^{Z}⟧ for infinitely many i. Let V_{σ}, c, Ṽ_{σ}, W_{i}^{Z}, P_{i} be as in the proof of Theorem 4.5. For all i we have μ(W_{i}^{Z}) ≤ 2^{c}pwt_{f}(A_{i}^{Z}), hence ∑_{i} μ(W_{i}^{Z}) ≤ 2^{c} ∑_{i} pwt_{f}(A_{i}^{Z}) < ∞. On the other hand, for all i such that X ∈ ⟦A_{i}^{Z}⟧ we have Y ∈ W_{i}^{Z}, so Y ∈ W_{i}^{Z} for infinitely many i. Relativizing Solovay’s Lemma [34, Lemma 3.5] to Z, we see that Y is not Martin-Löf random relative to Z, Q.E.D.

Theorem 4.11. Let f : {0, 1}^{∗} → [−∞, ∞] be computable. If X is strongly f-random, then X is strongly BC-f-random relative to some PA-degree.

Proof. By the Kučera/Gács Theorem, let Y be Martin-Löf random such that X is Turing reducible to Y. By Theorem 1.3 let Z be of PA-degree such that Y is Martin-Löf random relative to Z. If X is strongly f-random, Theorem 4.10 tells us that X is strongly BC-f-random relative to Z, Q.E.D.

Corollary 4.12. Let f : {0, 1}^{∗} → [−∞, ∞] be computable. Then strong f-randomness is equivalent to strong BC-f-randomness.

Proof. Trivially strong BC-f-randomness implies strong f-randomness. The converse is immediate from Theorem 4.11.

Remark 4.13. It is possible to give a direct proof of Corollary 4.12 resembling the standard proof of Solovay’s Lemma [34, Lemma 3.5].

5 Propagation of non-K-triviality

Recall from [11, 23] that X is \underline{LR-reducible} to Z, abbreviated X ≤_{LR} Z, if ∀Y ((Y Martin-Löf random relative to Z) ⇒ (Y Martin-Löf random relative to X)). The concept of LR-reducibility has been very useful [20, 34, 35] in the reverse mathematics of measure-theoretic regularity. It is also known (see [11, Chapter 11] or [23, Chapter 5]) that LR-reducibility can be used to characterize \underline{K-triviality}. Namely, X is K-trivial if and only if X ≤_{LR} 0.

From our point of view in this paper, it seems reasonable to view non-K-triviality as a kind of partial randomness notion. Accordingly, we now present appropriate analogs of our main propagation results, Theorems 4.5 and 4.7. Our results in this section are easy consequences of previously known characterizations of K-triviality.

Theorem 5.1. Suppose X is Turing reducible to Y where Y is Martin-Löf random relative to Z. Then X ≰_{LR} 0 implies X ≰_{LR} Z.

Proof. Since X ≰_{LR} 0, it follows by [11, Chapter 11] or [23, Chapter 5] that X is not a base for Martin-Löf randomness. In particular, since X is Turing reducible to Y, Y is not Martin-Löf random relative to X. But then, since Y is Martin-Löf random relative to Z, we have X ≰_{LR} Z, Q.E.D.

Theorem 5.2. Suppose X_{i} ≰_{LR} 0 for all i ∈ ℕ. Then, we can find Z of PA-degree such that X_{i} ≰_{LR} Z for all i ∈ ℕ.

Proof. For each i let Y_{i} be Martin-Löf random but not Martin-Löf random relative to X_{i}. By Corollary 4.9 let Z be of PA-degree such that ∀i (Y_{i} is Martin-Löf random relative to Z). It follows that ∀i (X_{i} ≰_{LR} Z), Q.E.D.

Remark 5.3. In Theorems 5.1 and 5.2, the conclusion X ≰_{LR} Z implies that X ⊕ Z ≰_{LR} Z, i.e., X is not K-trivial relative to Z. On the other hand, results such as Theorems 1.3 and 4.7 and 5.2 bear an obvious resemblance to the well known GKT Theorem (see Gandy/Kreisel/Tait [13] or [18, Theorem 2.5] or [31, Theorem VIII.2.24]). Indeed, Theorem 5.2 is just the GKT Theorem with Turing reducibility replaced by LR-reducibility.

6 Propagation of diagonal nonrecursiveness

Let {n} denote the partial recursive functional with index n. Let DNR be the set of functions f : ℕ → ℕ which are \underline{diagonally nonrecursive}, i.e., f(n) ≠ \{n\}(n) for all n. Known results concerning diagonal nonrecursiveness may be found in [1, 17, 19, 32]. We also consider \underline{relative DNR-ness}: DNR^{Z} = \{f ∈ ℕ^{ℕ} | ∀n (f(n) ≠ {n}^{Z}(n))}. The purpose of this section is to obtain propagation results for diagonal nonrecursiveness.

Theorem 6.1. Suppose there exists a DNR function which is Turing reducible to X. Suppose also that X is Turing reducible to Y where Y is Martin-Löf random relative to Z. Then there exists a DNR^{Z} function which is Turing reducible to X.

In order to prove Theorem 6.1 we need the following lemma, which is a variant of the Parametrized Recursion Theorem. In stating and proving our lemma, we shall use standard recursion-theoretic notation. In particular, for any expression E we write E↓ to mean that E is defined, and E↑ to mean that E is undefined. We also write E_{1} ≃ E_{2} to mean that either (E_{1}↓ and E_{2}↓ and E_{1} = E_{2}) or (E_{1}↑ and E_{2}↑). Via Gödel numbering, we identify finite sequences of positive integers with positive integers. We write f ≤_{T} X to mean that f is Turing reducible to X.

Lemma 6.2. Let Θ(n, j, σ, −) be a partial recursive functional. Then, we can find a primitive recursive function p(n, j) such that

{p(n, j)}(−) ≃ Θ(n, j, ⟨p(n, i) | i ≤ j⟩, −)

for all n, j, −.

Proof. By the Parametrized Recursion Theorem, let q be a primitive recursive function such that {q(n, j, σ)}(−) ≃ Θ(n, j, σ^{⌢}⟨q(n, j, σ)⟩, −) for all n, j, σ, −.

Define p primitive recursively by letting p(n, j) = q(n, i, ⟨p(n, i) | i < j⟩) for all n, j. We then have

{p(n, j)}(−) ≃ {q(n, j, ⟨p(n, i) | i < j⟩)}(−)
≃ Θ(n, j, ⟨p(n, i) | i < j⟩^{⌢}⟨q(n, j, ⟨p(n, i) | i < j⟩)⟩, −)
≃ Θ(n, j, ⟨p(n, i) | i < j⟩^{⌢}⟨p(n, j)⟩, −)
≃ Θ(n, j, ⟨p(n, i) | i ≤ j⟩, −)

and this proves our lemma.

We now prove Theorem 6.1.

Proof of Theorem 6.1. Let f ∈ ℕ^{ℕ} be DNR and ≤_{T} X. Then f ≤_{T} Y so let Φ be a partial recursive functional such that f = Φ^{Y}, i.e., f(n) = Φ(Y, n) for all n. As in §4 let μ be the fair-coin probability measure on {0, 1}^{ℕ}. Define a partial recursive function θ(n, j, σ) ≃ some m such that μ(\{\overline{Y} | Φ\overline{Y} (σ(j))↓ = m and (∀i < j) (Φ\overline{Y} (σ(i))↓ ≠ \{σ(i)\}(σ(i))↓)\}) > 2^{−n}. Apply Lemma 6.2 to obtain a primitive recursive function p(n, j) such that {p(n, j)}(p(n, j)) ≃ some m such that μ(V_{n,j,m}) > 2^{−n} where V_{n,j,m} = \{\overline{Y} | Φ\overline{Y} (p(n, j))↓ = m and (∀i < j) (Φ\overline{Y} (p(n, i))↓ ≠ \{p(n, i)\}(p(n, i))↓)\}. Thus \{p(n, j)\}(p(n, j))↓ implies μ(V_{n,j}) > 2^{−n} where V_{n,j} = V_{n,j,{p(n,j)}(p(n,j))}. On the other hand, i ≠ j implies V_{n,i} ∩ V_{n,j} = ∅ so for each n there is at least one j ≤ 2^{n} such that {p(n, j)}(p(n, j))↑.

Let Ψ be a partial recursive functional defined by

Ψ\overline{Y} (n) ≃ ⟨Φ\overline{Y} (p(n, i)) | i ≤ 2^{n}⟩

for all n. In particular we have g ∈ ℕ^{ℕ} defined by

g(n) = Ψ^{Y} (n) = ⟨f(p(n, i)) | i ≤ 2^{n}⟩

for all n. Clearly g ≤_{T} f ≤_{T} X, so it will suffice to prove that g(n) ≠ {n}^{Z}(n) for all but finitely many n.

Let U_{n}^{Z} = \{\overline{Y} | Ψ\overline{Y} (n)↓ = \{n\}^{Z}(n)↓\}. Clearly U_{n}^{Z} is uniformly Σ_{1}^{0,Z}. Given a rational number r, let U_{n}^{Z}[r] be U_{n}^{Z} enumerated so long as its μ-measure is ≤ r. Thus U_{n}^{Z}[r] is uniformly Σ_{1}^{0,Z} and μ(U_{n}^{Z}[r]) ≤ r. Moreover, U_{n}^{Z}[r] = U_{n}^{Z} if and only if μ(U_{n}^{Z}) ≤ r. Since Y is Martin-Löf random, it follows by Solovay’s Lemma [34, Lemma 3.5] that Y ∉ U_{n}^{Z}[2^{−n}] for all but finitely many n. Therefore, it will suffice to prove g(n) ≠ {n}^{Z}(n) for all such n.

Supposing otherwise, we would have Ψ^{Y} (n) = g(n) = {n}^{Z}(n), hence Y ∈ U_{n}^{Z}, hence μ(U_{n}^{Z}) > 2^{−n}. Moreover, for all \overline{Y} ∈ U_{n}^{Z} we would have Ψ\overline{Y} (n) = \{n\}^{Z}(n) = g(n), hence Φ\overline{Y} (p(n, i)) = f(p(n, i)) ≠ \{p(n, i)\}(p(n, i)) for all i ≤ 2^{n}. Let j ≤ 2^{n} be such that (∀i < j) ({p(n, i)}(p(n, i))↓). Then U_{n}^{Z} ⊆ V_{n,j,f(p(n,j))}, hence μ(V_{n,j,f(p(n,j))}) ≥ μ(U_{n}^{Z}) > 2^{−n}, hence {p(n, j)}(p(n, j))↓, so by induction on j we see that {p(n, j)}(p(n, j))↓ holds for all j ≤ 2^{n}. This contradiction completes the proof.

Theorem 6.3. Let Q be a nonempty Π_{1}^{0} subset of {0, 1}^{ℕ}. If (∀i ∈ ℕ) (∃f ∈ DNR) (f ≤_{T} X_{i}), then (∃Z ∈ Q) (∀i ∈ ℕ) (∃g ∈ DNR^{Z}) (g ≤_{T} X_{i}).

Proof. By the Kučera/Gács Theorem (see [11, Theorem 8.3.2] or [23, §3.3] or [34, Theorem 3.8]), let Y be Martin-Löf random such that ∀i (X_{i} ≤_{T} Y). By Theorem 1.2 let Z ∈ Q be such that Y is Martin-Löf random relative to Z. If ∀i ∃f (f ∈ DNR and f ≤_{T} X_{i}), it follows by Theorem 6.1 that ∀i ∃g (g ∈ DNR^{Z} and g ≤_{T} X_{i}).

Corollary 6.4. Let Q be a nonempty Π_{1}^{0} subset of {0, 1}^{ℕ}. If there exists a DNR function which is Turing reducible to X, then for some Z ∈ Q there exists a DNR^{Z} function which is Turing reducible to X.

Proof. This is the special case of Theorem 6.3 with X_{i} = X for all i ∈ ℕ.

Theorem 6.5. Suppose (∀i ∈ ℕ) (∃f ∈ DNR) (f ≤_{T} X_{i}). Then, there exists Z of PA-degree such that (∀i ∈ ℕ) (∃g ∈ DNR^{Z}) (g ≤_{T} X_{i}).

Proof. In Theorem 6.3 let Q be the Π_{1}^{0} set consisting of all completions of firstorder Peano arithmetic.

Corollary 6.6. If there exists a DNR function which is Turing reducible to X, then for some Z of PA-degree there exists a DNR^{Z} function which is Turing reducible to X.

Proof. In Corollary 6.4 let Q be the Π_{1}^{0} set consisting of all completions of first-order Peano arithmetic.

Remark 6.7. As in [32, §10] and [36, §2.2], let C be a “nice” class of recursive functions. For example, C could be the class of all recursive functions, or the class of primitive recursive functions, or the class of recursive functions up to level α of the transfinite Ackermann hierarchy for some limit ordinal α ≤ ε_{0}. A function f : ℕ → ℕ is said to be \underline{C-bounded} if (∃F ∈ C) ∀n (f(n) < F (n)). In particular, f is \underline{recursively bounded} if it is C-bounded where C = the class of all recursive functions. Our proofs above show that Theorems 6.1 and 6.3 and 6.5 and Corollaries 6.4 and 6.6 also hold with “DNR” replaced by “C-bounded DNR.” It suffices to note that, in our proof of Theorem 6.1, if f is C-bounded then so is g. See also the refinements mentioned in Remarks 7.8 and 7.9 below.

We end this section by presenting an alternative proof of Corollary 6.4.

Alternative proof of Corollary 6.4. Let ℕ^{∗} be the set of finite sequences of positive integers. For each σ ∈ ℕ^{∗} let

Q_{σ} = {Z ∈ Q | (∀n < |σ|) (σ(n) ≠ {n}^{Z}(n))}

where |σ| = the length of σ. Clearly σ ⊆ τ implies Q_{σ} ⊇ Q_{τ}. By the Parametrization or S-m-n Theorem, let p(n, σ) be a primitive recursive function such that for all m, {p(n, σ)}(p(n, σ)) = m if and only if {n}^{Z}(n) = m for all Z ∈ Q_{σ}. Let f ≤_{T} X be a DNR function. Define g ≤_{T} X recursively by letting g(n) = f(p(n, ⟨g(i) | i < n⟩)) for all n. We are going to show that g is DNR relative to some Z ∈ Q.

We claim that Q_{⟨g(i)|i<n⟩} ≠ ∅ for all n. To begin with, we have Q_{⟨⟩} = Q ≠ ∅. Assume inductively that Q_{⟨g(i)|i<n⟩} ≠ ∅. We shall prove that Q_{⟨g(i)|i≤n⟩} ≠ ∅. There are two cases. If {p(n, ⟨g(i) | i < n⟩)}(p(n, ⟨g(i) | i < n⟩)) = m, we have {n}^{Z}(n) = m for all Z ∈ Q_{⟨g(i)|i<n⟩}, but g(n) = f(p(n, ⟨g(i) | i < n⟩)) ≠ m since f is DNR. Thus Q_{⟨g(i)|i≤n⟩} = Q_{⟨g(i)|i<n⟩} ≠ ∅. If {p(n, ⟨g(i) | i < n⟩)}(p(n, ⟨g(i) | i < n⟩)) is undefined, there exists Z ∈ Q_{⟨g(i)|i<n⟩} such that {n}^{Z}(n) ≠ g(n), and then Z belongs to Q_{⟨g(i)|i≤n⟩}. This proves our claim.

By compactness, our claim implies that ⋂_{n=0}^{∞} Q_{⟨g(i)|i<n⟩} ≠ ∅. Moreover, from the definition of Q_{⟨g(i)|i<n⟩} we see that g is DNR relative to any Z ∈ ⋂_{n=0}^{∞} Q_{⟨g(i)|i<n⟩}. This completes the proof.

Remark 6.8. Our alternative proof of Corollary 6.4 is more constructive than the previous proof via Theorem 6.1 and the Kučera/Gács Theorem. In particular, the alternative proof can be formalized in WKL_{0} (see [31]) while the previous proof cannot.

There are some issues here which are interesting from the viewpoint of reverse mathematics [31]. For example, consider the following statement.

Let Q be a nonempty Π_{1}^{0} subset of {0, 1}^{ℕ}. If X_{1} and X_{2} are Martin-Löf random, there exists Z ∈ Q such that X_{1} and X_{2} are Martin-Löf random relative to Z.

By Corollary 4.9 this statement is true, and from the truth of the statement it follows easily that the statement is true in all ω-models of WKL_{0}. Moreover, we conjecture that the statement is provable in WKL_{0}. On the other hand, by [2, Theorem 2.1] together with [38], the following special case of the Kučera/Gács Theorem is false in all ω-models of WKL_{0} except those which contain 0^{(1)} = the Turing jump of 0.

If X_{1} and X_{2} are Martin-Löf random, there exists a Martin-Löf random Y such that X_{1} ≤_{T} Y and X_{2} ≤_{T} Y.

7 Propagation of autocomplexity

In this section we prove propagation results for autocomplexity and complexity. We also obtain a characterization of autocomplexity in terms of f-randomness and strong f-randomness. With this characterization plus [19, Theorem 2.3], we see considerable overlap between the propagation results of this section and those of §4 and §6.

Definition 7.1.

1. Following [19] we define X ∈ \{0, 1\}^{ℕ} to be \underline{autocomplex} if there exists an unbounded function h : ℕ → ℕ such that h ≤_{T} X and h(n) ≤ KS(X↾n) for all n. Here KS denotes \underline{simple Kolmogorov complexity} [40], also known as \underline{plain complexity} [11, 23].

2. Following [4] and [15] and [19], we define X ∈ \{0, 1\}^{ℕ} to be \underline{complex} if there exists an unbounded computable function h : ℕ → ℕ such that h(n) ≤ KS(X↾n) for all n.

Remark 7.2. By [40, §4.3.1] there exist constants c_{1} and c_{2} such that KS(σ) ≤ KP(σ) + c_{1} ≤ KS(σ) + 3 log_{2} |σ| + c_{2} and KA(σ) ≤ KP(σ) + c_{1} ≤ KA(σ) + 3 log_{2} |σ| + c_{2} for all σ ∈ {0, 1}^{∗}. These inequalities imply that the distinctions among KS and KP and KA are immaterial for some purposes. In particular, we can replace KS in Definition 7.1 by KP or KA.

We begin with autocomplexity.

Theorem 7.3. The following are pairwise equivalent.

1. X is autocomplex.

2. X is f-random for some computable f : {0, 1}^{∗} → ℕ such that {f(X↾n) | n ∈ ℕ} is unbounded.

3. X is strongly f-random for some computable f : {0, 1}^{∗} → ℕ such that {f(X↾n) | n ∈ ℕ} is unbounded.

Proof. The equivalence 2 ⇔ 3 is clear in view of Remark 7.2.

To prove 2 ⇒ 1, suppose 2 holds via f. By Theorem 2.6 X is f-complex, so let c ∈ ℕ be such that KP(X↾n) ≥ f(X↾n) − c for all n. Then for all n we have KP(X↾n) ≥ h(n) where h(n) = max(1, f(X↾n) − c). Clearly h ≤_{T} X (in fact h is Lipschitz computable from X) and h is unbounded, so it follows by Remark 7.2 that X is autocomplex, i.e., 1 holds.

It remains to prove 1 ⇒ 2. Suppose X is autocomplex. By Remark 7.2 let h : ℕ → ℕ be unbounded such that h ≤_{T} X and h(n) ≤ KP(X↾n) for all n. Let Φ be a partial recursive functional such that h = Φ^{X}. Consider the primitive recursive function f : {0, 1}^{∗} → ℕ defined by f(σ) = max{p(σ, n) | n ≤ |σ|} where p(σ, n) = Φ_{|σ|}^{σ}(n) if Φ_{|σ|}^{σ}(n)↓, otherwise p(σ, n) = 1. Then for all n and all sufficiently large m ≥ n we have h(n) = p(X↾m, n) ≤ f(X↾m). Since {h(n) | n ∈ ℕ} is unbounded, it follows that {f(X↾m) | m ∈ ℕ} is unbounded. Consider the primitive recursive function q(σ) = the least n ≤ |σ| such that f(σ) = p(σ, n). Let c be a constant such that KP(σ↾q(σ)) ≤ KP(σ) + c for all σ. Then for all m we have KP(X↾m) + c ≥ KP(X↾q(X↾m)) ≥ h(X↾q(X↾m)) ≥ p(X↾m, q(X↾m)) = f(X↾m) so X is f-complex. It follows by Theorem 2.6 that X is f-random. This completes the proof.

Theorem 7.4.

1. If X is autocomplex and ≤_{T} Y where Y is Martin-Löf random relative to Z, then X is autocomplex relative to Z.

2. If (∀i ∈ ℕ) (X_{i} is autocomplex), there exists Z of PA-degree such that (∀i ∈ ℕ) (X_{i} is autocomplex relative to Z).

First proof. Part 1 is immediate from Theorems 4.5 and 7.3. Part 2 is immediate from Theorems 4.7 and 7.3.

Second proof. By Kjos-Hanssen/Merkle/Stephan [19, Theorem 2.3] we know that X is autocomplex if and only if there exists a DNR function which is Turing reducible to X. Modulo this result, parts 1 and 2 are equivalent to Theorems 6.1 and 6.5 respectively.

Remark 7.5. Yet another proof of Theorem 7.4 was obtained independently by Bienvenu [3] who had seen it conjectured in an earlier draft of the present paper. The earlier draft included Theorems 4.5 and 4.7, as well as Corollary 6.4 with our alternative proof, but it did not include Theorem 6.1 or 6.5 or 7.3.

We now turn to propagation results for complexity. Let us define f : \{0, 1\}^{∗} → [−∞, ∞] to be \underline{length-invariant} if ∀σ ∀τ (|σ| = |τ| ⇒ f(σ) = f(τ)).

Theorem 7.6. The following are pairwise equivalent.

1. X is complex.

2. X is f-random for some computable f : {0, 1}^{∗} → ℕ which is unbounded and length-invariant.

3. X is strongly f-random for some computable f : {0, 1}^{∗} → ℕ which is unbounded and length-invariant.

Proof. This is immediate from Theorems 2.6 and 2.8 and Remark 7.2.

Theorem 7.7.

1. If X is complex and ≤_{T} Y where Y is Martin-Löf random relative to Z, then X is complex relative to Z.

2. If (∀i ∈ ℕ) (X_{i} is complex), there exists Z of PA-degree such that (∀i ∈ ℕ) (X_{i} is complex relative to Z).

Proof. Part 1 is immediate from Theorems 4.5 and 7.6. Part 2 is immediate from Theorems 4.7 and 7.6.

Remark 7.8. By [19, Theorem 2.3] we know that X is complex if and only if some DNR function is truth-table reducible to X. Consequently, the Turing degrees of complex X’s are the same as the Turing degrees of recursively bounded DNR functions. And of course, the Turing degrees of autocomplex X’s are the same as the Turing degrees of DNR functions. Thus Theorems 4.5 and 4.7 may be viewed as far-reaching refinements not only of Theorems 7.4 and 7.7 but also of Theorems 6.1–6.5 and Remark 6.7.

Remark 7.9. By [1, Theorem 1.8] there exists an autocomplex X such that no complex Y is Turing reducible to X. Within the class of complex X’s, much more refined results of the same kind have been obtained by Hudelson [16] generalizing the main result of Miller [21, Theorem 4.1]. See also Remarks 3.7 and 3.8 above, as well as [36, §§2.1–2.3, Figure 1].

8 Vehement f-randomness

In this section we define vehement f-randomness and discuss its relationship with strong f-randomness. The notion of vehement f-randomness was originally introduced by Kjos-Hanssen (unpublished, but see [26]). We prove that, under a convexity hypothesis on f, vehement f-randomness is equivalent to strong f-randomness. Our result is a generalization of known results due to Reimann [26, Corollary 21] and Miller [21, Lemma 3.3].

Definition 8.1. Given f : \{0, 1\}^{∗} → [−∞, ∞], the \underline{vehement f-weight} of A ⊆ {0, 1}^{∗} is defined as vwt_{f}(A) = inf{dwt_{f}(S) | ⟦A⟧ ⊆ ⟦S⟧}.

Remark 8.2. Note that ⟦A⟧ ⊆ ⟦B⟧ implies vwt_{f}(A) ≤ vwt_{f}(B). In particular, vwt_{f}(A) depends only on ⟦A⟧.

Lemma 8.3. For all A we have vwt_{f}(A) ≤ dwt_{f}(Â) ≤ pwt_{f}(A).

Proof. The first inequality holds because ⟦A⟧ ⊆ ⟦Â⟧. The second inequality holds because Â is a prefix-free subset of A.

Definition 8.4. Fix f : \{0, 1\}^{∗} → [−∞, ∞]. A \underline{good cover} of A is a set B such that ⟦A⟧ ⊆ ⟦B⟧ and pwt_{f}(B) ≤ vwt_{f}(A). It follows by Remark 8.2 and Lemma 8.3 that vwt_{f}(A) = vwt_{f}(B) = dwt_{f}(B̂) = pwt_{f}(B).

Lemma 8.5. Suppose B is a good cover of A. Given F ⊆ B̂ let us write A_{F} = {σ ∈ A | ⟦F ⟧ ⊇ ⟦σ⟧} and B_{F} = {τ ∈ B | ⟦F ⟧ ⊇ ⟦τ⟧}. Then B_{F} is a good cover of A_{F}.

Proof. Clearly B̂_{F} = F, hence ⟦A_{F} ⟧ ⊆ ⟦F ⟧ = ⟦B̂_{F} ⟧ = ⟦B_{F} ⟧. In order to show that B_{F} is a good cover of A_{F}, it remains to show that dwt_{f}(P) ≤ dwt_{f}(S) whenever P ⊆ B_{F} is prefix-free and ⟦A_{F} ⟧ ⊆ ⟦S⟧. Letting G = B̂ \ F we see that P ∩ G = ∅ and P ∪ G is a prefix-free subset of B and ⟦A⟧ = ⟦A_{F} ⟧ ∪ ⟦A_{G}⟧ ⊆ ⟦S⟧ ∪ ⟦G⟧ = ⟦S ∪ G⟧. Thus dwt_{f}(P) + dwt_{f}(G) = dwt_{f}(P ∪ G) ≤ pwt_{f}(B) ≤ vwt_{f}(A) ≤ dwt_{f}(S ∪ G) ≤ dwt_{f}(S) + dwt_{f}(G), hence dwt_{f}(P) ≤ dwt_{f}(S), Q.E.D.

Remark 8.6. Let B be a good cover of A, and suppose τ is such that ⟦B⟧ ⊉ ⟦τ⟧. Then obviously no initial segment of τ belongs to B. In other words, τ ∈ { \atop B ∪ \{τ\}}. Letting F = { \atop B ∪ \{τ\}} \ \{τ\} and applying Lemma 8.5, we see that B̂_{F} = F and B_{F} is a good cover of A_{F}.

Definition 8.7. We define f : \{0, 1\}^{∗} → [−∞, ∞] to be \underline{convex} if wt_{f}(σ) ≤ wt_{f}(σ^{⌢}⟨0⟩) + wt_{f}(σ^{⌢}⟨1⟩) for all σ ∈ {0, 1}^{∗}. Equivalently, wt_{f}(σ) ≤ dwt_{f}(S) for all σ ∈ {0, 1}^{∗} and all S ⊆ {0, 1}^{∗} such that ⟦S⟧ = ⟦σ⟧.

Lemma 8.8. Assume that f is convex. Suppose B is a good cover of A but not of A′ = A ∪ \{σ\}. Choose τ ⊆ σ so as to minimize dwt_{f}({ \atop B ∪ \{τ\}}). Then B′ = B ∪ {τ} is a good cover of A′.

Proof. Obviously ⟦B′⟧ ⊇ ⟦A′⟧ so it remains to prove that dwt_{f}(P′) ≤ dwt_{f}(S′) whenever P′ ⊆ B′ is prefix-free and ⟦A′⟧ ⊆ ⟦S′⟧.

Since ⟦σ⟧ ⊆ ⟦A′⟧ ⊆ ⟦S′⟧, let τ^{∗} ⊆ σ be as short as possible such that ⟦τ^{∗}⟧ ⊆ ⟦S′⟧. Obviously S′ contains no proper initial segment of τ^{∗}. Hence ⟦τ^{∗}⟧ = ⟦S^{∗}⟧ for some S^{∗} ⊆ S′. It follows by Definition 8.7 that wt_{f}(τ^{∗}) ≤ dwt_{f}(S^{∗}). Therefore, replacing S′ by (S′ \ S^{∗}) ∪ {τ^{∗}}, we may safely assume that τ^{∗} ∈ S′.

Since ⟦σ⟧ ⊈ ⟦B⟧ and τ ⊆ σ and τ^{∗} ⊆ σ, we obviously have ⟦τ⟧ ⊈ ⟦B⟧ and ⟦τ^{∗}⟧ ⊈ ⟦B⟧. Applying Remark 8.6 to τ and to τ^{∗}, we obtain sets F =

{ \atop B ∪ \{τ\}} \ \{τ\} and F^{∗} = { \atop B ∪ \{τ^{∗}\}} \ \{τ^{∗}\}. In particular, since ⟦A⟧ ⊆ ⟦S′⟧ we

have ⟦A_{F^{∗}}⟧ = ⟦A⟧ \ ⟦τ^{∗}⟧ ⊆ ⟦S′⟧ \ ⟦τ^{∗}⟧ ⊆ ⟦S′ \ {τ^{∗}}⟧. Moreover, by our choice of τ we have dwt_{f}({ \atop B ∪ \{τ\}}) ≤ dwt_{f}({ \atop B ∪ \{τ^{∗}\}}).

We are now ready to complete the proof of Lemma 8.8. If τ ∉ P′ we have P′ = P ⊆ B, hence dwt_{f}(P) ≤ pwt_{f}(B) ≤ vwt_{f}(A) ≤ dwt_{f}(S′) and we are done. Suppose now that τ ∈ P′. Then P′ = P ∪ {τ} where P ⊆ B_{F}. Thus we have

dwt_{f}(P′) = dwt_{f}(P) + wt_{f}(τ)
≤ pwt_{f}(B_{F}) + wt_{f}(τ)
= dwt_{f}(F) + wt_{f}(τ)
= dwt_{f}({ \atop B ∪ \{τ\}})
≤ dwt_{f}({ \atop B ∪ \{τ^{∗}\}})
= dwt_{f}(F^{∗}) + wt_{f}(τ^{∗})
= vwt_{f}(A_{F^{∗}}) + wt_{f}(τ^{∗})
≤ dwt_{f}(S′ \ {τ^{∗}}) + wt_{f}(τ^{∗})
= dwt_{f}(S′)

and again we are done.

Definition 8.9. Given f : {0, 1}^{∗} → [−∞, ∞] define

L_{f} : {(P_{1}, P_{2}) | P_{1}, P_{2} are finite and prefix-free} → {0, 1}

by

L_{f}(P_{1}, P_{2}) = \{ \begin{matrix}1 & if dwt_{f}(P_{1}) < dwt_{f}(P_{2}), \\ 0 & otherwise. \end{matrix}

We say that f is \underline{strongly computable} if both f and L_{f} are computable. This is often the case, e.g., if f is computable and integer-valued as in Lemma 3.2. Note also that Lemma 3.3 depends only on strong computability.

Lemma 8.10. Let f be strongly computable and convex. If A is r.e., we can effectively find an r.e. set B such that B is a good cover of A.

Proof. For n = 0, 1, 2, … let A_{n} consist of the first n elements in some fixed recursive enumeration of A. Assume inductively that we have found a finite set B_{n} which is a good cover of A_{n}. Let A_{n+1} = A_{n} ∪ {σ_{n}}. If ⟦σ_{n}⟧ ⊆ ⟦B_{n}⟧ let B_{n+1} = B_{n}. Otherwise, use strong computability to effectively choose τ_{n} ⊆ σ_{n} which minimizes dwt_{f}({ \atop B_{n} ∪ \{τ_{n}\}}). Lemma 8.8 then implies that B_{n+1} = B_{n} ∪ {τ_{n}} is a good cover of A_{n+1}. Finally let B = ⋃_{n=1}^{∞} B_{n}. Clearly B is r.e. and ⟦A⟧ ⊆ ⟦B⟧, so it remains to prove that dwt_{f}(P) ≤ vwt_{f}(A) for all prefix-free sets P ⊆ B. But clearly dwt_{f}(P) = sup{dwt_{f}(P_{0}) | P_{0} is a finite subset of P }, so it suffices to consider finite prefix-free sets. If P ⊆ B is finite and prefix-free, let n be such that P ⊆ B_{n}. Then dwt_{f}(P) ≤ pwt_{f}(B_{n}) ≤ vwt_{f}(A_{n}) ≤ vwt_{f}(A), Q.E.D.

Lemma 8.11. Let f be strongly computable and convex. If A is r.e., we can effecively find an r.e. set B such that ⟦A⟧ ⊆ ⟦B⟧ and pwt_{f}(B) ≤ vwt_{f}(A).

Proof. This is a restatement of Lemma 8.10.

Definition 8.12. Assume that f : {0, 1}^{∗} → [−∞, ∞] is computable. We define X ∈ \{0, 1\}^{∗} to be \underline{vehemently f-random} if X ∉ ⋂_{i}⟦A_{i}⟧ whenever A_{i} is uniformly r.e. such that vwt_{f}(A_{i}) ≤ 2^{−i}.

Theorem 8.13. Let f : {0, 1}^{∗} → [−∞, ∞] be strongly computable and convex. Then vehement f-randomness is equivalent to strong f-randomness.

Proof. Suppose X is not strongly f-random, say X ∈ ⋂_{i}⟦A_{i}⟧ where A_{i} is uniformly r.e. and pwt_{f}(A_{i}) ≤ 2^{−i}. By Lemma 8.3 we have vwt_{f}(A_{i}) ≤ pwt_{f}(A_{i}) ≤ 2^{−i} so X is not vehemently f-random.

Now suppose X is not vehemently f-random, say X ∈ ⋂_{i}⟦A_{i}⟧ where A_{i} is uniformly r.e. and vwt_{f}(A_{i}) ≤ 2^{−i}. By Lemma 8.11 we can find uniformly r.e. B_{i} such that ⟦A_{i}⟧ ⊆ ⟦B_{i}⟧ and pwt_{f}(B_{i}) ≤ vwt_{f}(A_{i}) ≤ 2^{−i}. Clearly X ∈ ⋂_{i}⟦B_{i}⟧, so X is not strongly f-random.

We now sketch how to replace “strongly computable” by “computable.”

Lemma 8.14. Let f be computable and convex. Given ϵ > 0 we can effectively find an \overline{f} which is strongly computable and convex and such that f(σ) < \overline{f}(σ) < f(σ) + ϵ for all σ.

Proof. Let ℚ be the set of rational numbers. By a straightforward but awkward construction, we can find \overline{f} : \{0, 1\}^{∗} → ℚ which is computable and convex and such that f(σ) < \overline{f}(σ) < f(σ) + ϵ for all σ. From the ℚ-valuedness of \overline{f} it follows easily that \overline{f} is strongly computable.

Lemma 8.15. Let f be computable and convex. Given δ > 0 and an r.e. set A, we can effectively find an r.e. set B such that ⟦A⟧ ⊆ ⟦B⟧ and pwt_{f}(B) ≤ (1 + δ) · vwt_{f}(A).

Proof. Let \overline{f} be as in Lemma 8.14 with ϵ = log_{2}(1 + δ). If A is r.e., apply Lemma 8.11 to find an r.e. set B such that ⟦A⟧ ⊆ ⟦B⟧ and pwt\overline{f}(B) ≤ vwt\overline{f}(A). It is then easy to check that pwt_{f}(B) ≤ (1 + δ) · vwt_{f}(A).

Theorem 8.16. Let f : {0, 1}^{∗} → [−∞, ∞] be computable and convex. Then vehement f-randomness is equivalent to strong f-randomness.

Proof. Proceed as in the proof of Theorem 8.13 but instead of Lemma 8.11 use Lemma 8.15 with δ = 1.

9 Propagation of vehement f-randomness

In this section we present an alternative proof of one of our main results concerning propagation of strong f-randomness, Corollary 4.8. Our alternative proof proceeds via vehement f-randomness and depends heavily on Remark 8.2. Our alternative proof has the advantage of being a direct generalization of one of the known proofs (see [10, Proposition 7.4]) of the corresponding result for Martin-Löf randomness, Theorem 1.2.

Theorem 9.1. Let f : {0, 1}^{∗} → [−∞, ∞] be computable and convex. Let Q be a nonempty Π_{1}^{0} subset of {0, 1}^{ℕ}. If X is strongly f-random, then X is strongly f-random relative to some Z ∈ Q.

Proof. Relativizing Corollary 2.9 let S_{i}^{Z} be a universal test for strong f-randomness relative to Z. In other words, S_{i}^{Z} is uniformly r.e. relative to Z and pwt_{f}(S_{i}^{Z}) ≤ 2^{−i} and ∀X ∀Z (X ∉ ⋂_{i}⟦S_{i}^{Z}⟧ ⇔ X is strongly f-random relative to Z). By Lemma 8.3 we have vwt_{f}(S_{i}^{Z}) ≤ pwt_{f}(S_{i}^{Z}) ≤ 2^{−i} so by Theorem 8.16 S_{i}^{Z} is also a universal test for vehement f-randomness relative to Z. Thus, letting U_{i}^{Z} = ⟦S_{i}^{Z}⟧, we have

∀X ∀Z (X ∉ ⋂_{i} U_{i}^{Z} ⇔ X is vehemently f-random relative to Z)

and U_{i}^{Z} is uniformly Σ_{1}^{0} relative to Z.

Let Ũ_{i} = ⋂_{Z∈Q} U_{i}^{Z}. Since Q is Π_{1}^{0}, it follows by compactness that Ũ_{i} is uniformly Σ_{1}^{0}. Therefore, let S̃_{i} be uniformly r.e. such that ⟦S̃_{i}⟧ = Ũ_{i}. For any Z ∈ Q we have Ũ_{i} ⊆ U_{i}^{Z}, i.e., ⟦S̃_{i}⟧ ⊆ ⟦S_{i}^{Z}⟧, so vwt_{f}(S̃_{i}) ≤ vwt_{f}(S_{i}^{Z}) ≤ 2^{−i} by Remark 8.2. Thus S̃_{i} is a test for vehement f-randomness. In particular we have ∀X (X vehemently f-random ⇒ X ∉ ⋂_{i} Ũ_{i}).

Suppose now that X is strongly f-random. By Theorem 8.16 X is vehemently f-random, so

X ∉ ⋂_{i} Ũ_{i} = ⋂_{i} ⋂_{Z∈Q} U_{i}^{Z} = ⋂_{Z∈Q} ⋂_{i} U_{i}^{Z}.

Let Z ∈ Q be such that X ∉ ⋂_{i} U_{i}^{Z}. Then X is vehemently f-random relative to Z, so by Theorem 8.16 X is strongly f-random relative to Z, Q.E.D.

Theorem 9.2. Let f : {0, 1}^{∗} → [−∞, ∞] be computable and convex. Let Q be a nonempty Π_{1}^{0} subset of {0, 1}^{ℕ}. If X is vehemently f-random, then X is vehemently f-random relative to some Z ∈ Q.

Proof. This is immediate from Theorems 8.16 and 9.1.

10 Other characterizations of strong f-randomness

In this section we present two new characterizations of strong f-randomness. One of our new characterizations is in terms of f-randomness relative to a PAdegree. The other is in terms of what we call provable noncomplexity.

Theorem 10.1. Let f : {0, 1}^{∗} → [−∞, ∞] be computable. The following are pairwise equivalent.

1. X is strongly f-random.

2. X is strongly f-random relative to some PA-degree.

3. X is f-random relative to some PA-degree.

Proof. The implication 1 ⇒ 2 follows from Theorem 4.7. The implication 2 ⇒ 3 is trivial. It remains to prove 3 ⇒ 1. Assume that 1 fails, i.e., X is not strongly f-random. Let A_{i}, i ∈ ℕ be uniformly r.e. such that pwt_{f}(A_{i}) ≤ 2^{−i} and X ∈ ⋂_{i}⟦A_{i}⟧. For each i let Â_{i} be the set of minimal elements of A_{i}. Let Q be the set of sequences Z_{i}, i ∈ ℕ such that Z_{i} ⊆ {0, 1}^{∗} and dwt_{f}(Z_{i}) ≤ 2^{−i} and ∀σ (σ ∈ A_{i} ⇒ ∃ρ (ρ ⊆ σ and ρ ∈ Z_{i})). The sequence Â_{i}, i ∈ ℕ belongs to Q, so Q is nonempty. Moreover, Q may be viewed as a Π_{1}^{0} set in the Cantor space. Therefore, given Z of PA-degree, we can find a sequence B_{i}, i ∈ ℕ which is Turing reducible to Z and belongs to Q. From the definition of Q it follows that dwt_{f}(B_{i}) ≤ 2^{−i} and X ∈ ⋂_{i}⟦B_{i}⟧. Thus X is not f-random relative to Z. This holds for all PA-degrees, so 3 fails, Q.E.D.

For our second characterization, let PA denote first-order Peano arithmetic. Within PA we define prefix-free complexity KP : {0, 1}^{∗} → ℕ and a priori complexity KA : {0, 1}^{∗} → (0, ∞) as usual. Also within PA we define KP^{(j)} = prefix-free complexity relative to 0^{(j)}, and KA^{(j)} = a priori complexity relative to 0^{(j)}, where 0^{(j)} = the jth Turing jump of 0. Let f : {0, 1}^{∗} → ℕ and X ∈ {0, 1}^{ℕ} be arbitrary.

Definition 10.2. Let K stand for KP or KA, and let Z be a Turing oracle. We define X to be \underline{K^{Z}-f-complex} if ∃c ∀n (K^{Z}(X↾n) > f(X↾n) − c)).

Definition 10.3. Let M be a nonstandard model of PA. We define X to be \underline{M-f-complex} if ∀r ∃c ∀n (KP_{r}(X↾n) > f(X↾n)−c). Here r ranges over M-finite functions r with prefix-free domain, and KP_{r}(τ) = min{|σ| | r(σ) = τ}.

Definition 10.4. Let K stand for KP or KA or KP^{(j)} or KA^{(j)}. Let T be a consistent theory extending PA. We define X to be \underline{provably K-f-noncomplex in T} if ∀c ∃n (T ⊢ (∃m < n) (K(X↾m) < f(X↾m) − c)).

Theorem 10.5. Let K stand for KP or KA. Let T be a recursively axiomatizable, consistent theory extending PA. Let f : {0, 1}^{∗} → ℕ and X ∈ {0, 1}^{ℕ} be arbitrary. For each j ∈ ℕ the following are pairwise equivalent.

1. X is not K^{Z}-f-complex for any Z of PA-degree.

2. X is not M-f-complex for any nonstandard M ⊧ T.

3. X is provably K-f-noncomplex in some recursively axiomatizable, consistent theory extending T.

4. X is provably K^{(j)}-f-noncomplex in some recursively axiomatizable, consistent theory extending T.

Proof. This is a special case of [41, Theorems 4.1 and 4.4].

Theorem 10.6. Let f : {0, 1}^{∗} → ℕ be computable. Let T be a recursively axiomatizable, consistent theory extending PA. For all X ∈ {0, 1}^{ℕ} the following are pairwise equivalent.

1. X is strongly f-random.

2. X is M-f-complex for some nonstandard M ⊧ T.

3. X is not provably KP-f-noncomplex in any recursively axiomatizable, consistent theory extending T.

Proof. By Theorems 2.8 and 10.1 X is strongly-f-random if and only if X is KA^{Z}-f-complex for all Z of PA-degree. The equivalences 1 ⇔ 2 and 1 ⇔ 3 then follow by Theorem 10.5.

Define K^{Z}-length-complexity to mean K^{Z}-f-complexity where f(σ) = the length of σ, and similarly for M-length-complexity and provable KP-length-noncomplexity.

Theorem 10.7. Let T be a recursively axiomatizable, consistent theory extending PA. For all X ∈ {0, 1}^{ℕ} the following are pairwise equivalent.

1. X is Martin-Löf random.

2. X is M-length-complex for some nonstandard M ⊧ T.

3. X is not provably KP-length-noncomplex in any recursively axiomatizable, consistent theory extending T.

Proof. This is the special case of Theorem 10.6 with f(σ) = |σ| for all σ.

Remark 10.8. By Theorem 10.5 our notion of provable length-noncomplexity is stable under relativation to a strong oracle. Thus, letting X be Martin-Löf random and Turing reducible to 0^{(1)}, we see that X is not KP^{(1)}-length-complex but not provably KP^{(1)}-noncomplex in any recursively axiomatizable, consistent extension T of PA. It follows that for any such T there exist τ ∈ {0, 1}^{∗} and n ∈ ℕ such that KP^{(1)}(τ) < n but T ⊬ KP^{(1)}(τ) < n. Comparing this to the celebrated Chaitin Incompleteness Theorem [7, 24], we now have a somewhat different example of a statement which is true but not provable in T.

11 Non-propagation of f-randomness

In this section we show that Theorems 4.5 and 4.7 and 10.6 fail if strong frandomness is replaced by f-randomness.

Theorem 11.1. For many f’s, e.g., f(σ) = |σ|/2, we can find an X which is f-random but not f-random relative to any PA-degree.

Proof. By Reimann/Stephan [28] let X be f-random but not strongly f-random. By Theorem 10.1 X is not f-random relative to any PA-degree.

Corollary 11.2. For many f’s, e.g., f(σ) = |σ|/2, we can find an X which is f-random but provably KP-f-noncomplex in some recursively axiomatizable, consistent extension of PA. Indeed, X is provably KP-f-noncomplex in some recursively axiomatizable, consistent extension of any recursively axiomatizable, consistent extension of PA.

Proof. By Theorem 11.1 let X be f-random but not f-random relative to any PA-degree. The desired conclusion follows by Theorem 10.5.

References

[1] Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp, and Theodore A. Slaman. Comparing DNR and WWKL. Journal of Symbolic Logic, 69:1089– 1104, 2004. 12, 17

[2] George Barmpalias, Andrew E. M. Lewis, and Keng Meng Ng. The importance of Π_{1}^{0} classes in effective randomness. Journal of Symbolic Logic, 75(1):387–400, 2010. 15

[3] Laurent Bienvenu. Personal communication. June 14, 2012. 17

[4] Stephen Binns. Π_{1}^{0} classes with complex elements. Journal of Symbolic Logic, 73:1341–1353, 2008. 3, 16

[5] Vasco Brattka, Joseph S. Miller, and André Nies. Randomness and differentiability. Transactions of the American Mathematical Society, 2014 (estimated). Preprint, http://arxiv.org/abs/1104.4465v4, 39 pages; to appear in TAMS pending acceptance of revised version. 3

[6] Cristian Calude, Ludwig Staiger, and Sebastiaan A. Terwijn. On partial randomness. Annals of Pure and Applied Logic, 138:20–30, 2006. 3, 4, 5, 7

[7] Gregory J. Chaitin. Information-theoretic limitations of formal systems. Journal of the ACM, 21(3):403–424, 1974. 23 [8] Z. Chatzidakis, P. Koepke, and W. Pohlers, editors. Logic Colloquium ’02:

Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic and the Colloquium Logicum, held in Münster, Germany, August 3–11, 2002. Number 27 in Lecture Notes in Logic. Association for Symbolic Logic, 2006. VIII + 359 pages. 27

[9] J. C. E. Dekker, editor. Recursive Function Theory. Proceedings of Symposia in Pure Mathematics. American Mathematical Society, 1962. VII + 247 pages. 26

[10] Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller, and André Nies. Relativizing Chaitin’s halting probability. Jounal of Mathematical Logic, 5:167– 192, 2005. 3, 21

[11] Rodney G. Downey and Denis R. Hirschfeldt. Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer, 2010. XXVIII + 855 pages. 3, 4, 6, 10, 11, 14, 15

[12] J.-E. Fenstad, I. T. Frolov, and R. Hilpinen, editors. Logic, Methodology and Philosophy of Science VIII. Number 126 in Studies in Logic and the Foundations of Mathematics. North-Holland, 1989. XVII + 702 pages. 25

[13] Robin O. Gandy, Georg Kreisel, and William W. Tait. Set existence. Bulletin de l’Académie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques, 8:577–582, 1960. 12

[14] S. S. Goncharov, R. Downey, and H. Ono, editors. Mathematical Logic in Asia: Proceedings of the 9th Asian Logic Conference, Novosibirsk. World Scientific Publishing Company, Ltd., 2006. VIII + 328 pages. 26

[15] Kojiro Higuchi and Takayuki Kihara. Effective strong nullness and effectively closed sets. In S. B. Cooper, A. Dawar, and B. Löwe, editors, CiE 2012, number 7318 in Lecture Notes in Computer Science, pages 303–312. Springer-Verlag, 2012. 3, 16

[16] W. M. Phillip Hudelson. Mass problems and initial segment complexity. Journal of Symbolic Logic, 79(1):20–44, 2014. 3, 8, 17

[17] Carl G. Jockusch, Jr. Degrees of functions with no fixed points. In [12], pages 191–201, 1989. 12

[18] Carl G. Jockusch, Jr. and Robert I. Soare. Π_{1}^{0} classes and degrees of theories. Transactions of the American Mathematical Society, 173:35–56, 1972. 2, 12

[19] Bjørn Kjos-Hanssen, Wolfgang Merkle, and Frank Stephan. Kolmogorov complexity and the recursion theorem. Transactions of the American Mathematical Society, 363:5465–5480, 2011. 3, 12, 15, 16, 17 [20] Bjørn Kjos-Hanssen, Joseph S. Miller, and David Reed Solomon. Lowness

notions, measure and domination. Proceedings of the London Mathematical Society, 85(3):869–888, 2012. 11

[21] Joseph S. Miller. Extracting information is hard: a Turing degree of nonintegral effective Hausdorff dimension. Advances in Mathematics, 226:373– 384, 2011. 3, 6, 17, 18

[22] Joseph S. Miller and Liang Yu. On initial segment complexity and degrees of randomness. Transactions of the American Mathematical Society, 360:3193–3210, 2008. 3

[23] André Nies. Computability and Randomness. Oxford University Press, 2009. XV + 433 pages. 3, 4, 10, 11, 14, 15

[24] Panu Raatikainen. On interpreting Chaitin’s Incompleteness Theorem. Journal of Philosophical Logic, 27(6):569–586, 1998. 23

[25] Jan Reimann. Computability and Fractal Dimension. PhD thesis, University of Heidelberg, 2004. XI + 130 pages. 3, 6

[26] Jan Reimann. Effectively closed sets of measures and randomness. Annals of Pure and Applied Logic, 156:170–182, 2008. 5, 9, 18

[27] Jan Reimann and Theodore A. Slaman. Measures and their random reals. Transactions of the American Mathematical Society, 2014 (estimated). Preprint, http://arxiv.org/abs/0802.2705v2, 17 pages. 3

[28] Jan Reimann and Frank Stephan. On hierarchies of randomness tests. In [14], pages 215–232, 2006. 3, 7, 8, 24

[29] Dana S. Scott. Algebras of sets binumerable in complete extensions of arithmetic. In [9], pages 117–121, 1962. 2

[30] S. G. Simpson, editor. Reverse Mathematics 2001. Number 21 in Lecture Notes in Logic. Association for Symbolic Logic, 2005. X + 401 pages. 26

[31] Stephen G. Simpson. Subsystems of Second Order Arithmetic. Perspectives in Mathematical Logic. Springer-Verlag, 1999. XIV + 445 pages; Second Edition, Perspectives in Logic, Association for Symbolic Logic, Cambridge University Press, 2009, XVI+ 444 pages. 12, 15

[32] Stephen G. Simpson. Mass problems and randomness. Bulletin of Symbolic Logic, 11:1–27, 2005. 2, 12, 14

[33] Stephen G. Simpson. Π_{1}^{0} sets and models of WKL_{0}. In [30], pages 352–378, 2005. 2

[34] Stephen G. Simpson. Almost everywhere domination and superhighness. Mathematical Logic Quarterly, 53:462–482, 2007. 4, 5, 10, 11, 13, 14 [35] Stephen G. Simpson. Mass problems and measure-theoretic regularity. Bul-

letin of Symbolic Logic, 15:385–409, 2009. 11

[36] Stephen G. Simpson. Mass problems associated with effectively closed sets. Tohoku Mathematical Journal, 63(4):489–517, 2011. 14, 17

[37] Stephen G. Simpson and Keita Yokoyama. A nonstandard counterpart of WWKL. Notre Dame Journal of Formal Logic, 52:229–243, 2011. 3

[38] Frank Stephan. Martin-Löf random and PA-complete sets. In [8], pages 341–347, 2006. 15

[39] Kohtaro Tadaki. A generalization of Chaitin’s halting probability Ω and halting self-similar sets. Hokkaido Mathematical Journal, 31:219–253, 2002. 3, 4, 5, 6, 10

[40] V. A. Uspensky and A. Shen. Relations between varieties of Kolmogorov complexity. Mathematical Systems Theory, 29:271–292, 1996. 4, 6, 7, 8, 15, 16

[41] Keita Yokoyama. A generalization of Levin-Schnorr’s theorem. October 2013. 11 pages, http://arxiv.org/abs/1310.3091. 23