Cone avoidance and randomness preservation

Stephen G. Simpson Department of Mathematics Pennsylvania State University University Park, PA 16802, USA http://www.math.psu.edu/simpson simpson@math.psu.edu

Frank Stephan Department of Mathematics National University of Singapore Block S17, 10 Lower Kent Ridge Road Singapore 119076 http://www.comp.nus.edu.sg/∼fstephan fstephan@comp.nus.edu.sg

First draft: August 27, 2012 This draft: April 21, 2015

Abstract

Let X be an infinite sequence of 0’s and 1’s. Let f be a computable function. Recall that X is strongly f-random if and only if the a priori Kolmogorov complexity of each finite initial segment τ of X is bounded below by f(τ) minus a constant. We study the problem of finding a PAcomplete Turing oracle which preserves the strong f-randomness of X while avoiding a Turing cone. In the context of this problem, we prove that the cones which cannot always be avoided are precisely the K-trivial ones. We also prove: (1) If f is convex and X is strongly f-random and Y is Martin-Löf random relative to X, then X is strongly f-random relative to Y. (2) X is complex relative to some oracle if and only if X is random with respect to some continuous probability measure.

A version of this paper is in Annals of Pure and Applied Logic, 166(3):713–728, 2015. Simpson’s research was partially supported by a Simons Foundation Collaboration Grant. Stephan’s research was partially supported by NUS grant R252-000-420-112. Keywords: algorithmic randomness, Kolmogorov complexity, basis theorems, PAcompleteness, Turing degrees, K-triviality, partial randomness. 2010 MSC: Primary 03D32, Secondary 68Q30, 03D28, 03F30.

Contents

Abstract  1
1 Introduction  2
1.1 Basis theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Combining basis theorems . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Partial randomness relative to a Turing oracle . . . . . . . . . . . 4
2 Combining two basis theorems  6
3 Low-for-Ω PA-completeness  7
4 An approach to μ-randomness  10
5 A product theorem for strong f-randomness  13
6 Complexity relative to a Turing oracle  16
References  19

1 Introduction

In this paper we prove several new results concerning Martin-Löf randomness and partial randomness. A theme of our results is randomness preservation, i.e., the phenomenon that if X is (partially) random then X is (partially) random relative to certain Turing oracles.

The purpose of this introductory section is to provide some additional context and motivation for our results. In §1.1 we review basis theorems in general and the Randomness Preservation Basis Theorem in particular. In §1.2 we discuss the problem of combining two or more basis theorems into one basis theorem. We present a new result to the effect that K-triviality is the only obstacle to combining the Randomness Preservation Basis Theorem with the Cone Avoidance Basis Theorem. In §1.3 we present some other new results concerning partial randomness relative to a Turing oracle. Among the partial randomness notions which we consider are μ-randomness, strong f-randomness, autocomplexity, and complexity.

1.1 Basis theorems

Remark 1.1. A \underline{basis theorem} is a theorem of the following form:

Let P be a nonempty, effectively closed set in Euclidean space. Then, at least one point of P is “close to being computable.”

Or, instead of assuming that P is an effectively closed set in Euclidean space, it suffices to assume that P is an effectively closed set in an effectively compact metric space. See Definition 4.2 below.

Remark 1.2. It is well known that basis theorems play an important role in the foundations of mathematics. The foundational idea underlying these applications is that, even though it is not always possible to find a computable point with a desired property, it is nevertheless often possible to find a point which is “close to being computable,” in various senses.

Remark 1.3. Several well known basis theorems may be summarized as follows. Let P be a nonempty, effectively closed set in Euclidean space. Then, for each of the following properties, there exists Z ∈ P such that the property holds.

1. Z is \underline{low}, i.e., Z′ ≤_{T} 0′. This is the Low Basis Theorem, 1972 [16].

2. Z is of recursively enumerable Turing degree. This is the R.E. Basis Theorem, 1972 [15].

3. Z is \underline{hyperimmune-free}, i.e., (∀f ≤_{T} Z) (∃g ≤_{T} 0) ∀n (f(n) < g(n)). This is the Hyperimmune-Free Basis Theorem, 1972 [16].

4. X ≰_{T} Z, where X ≰_{T} 0 is given. This is the Cone Avoidance Basis Theorem, 1960 [12].

5. Y ∈ MLR^{Z}, where Y ∈ MLR is given. This is the Randomness Preservation Basis Theorem, 2005 [9, 26].

Here ≤_{T} denotes Turing reducibility,′ denotes the Turing jump operator, MLR = {Y | Y is Martin-Löf random}, and MLR^{Z} = {Y | Y is Martin-Löf random relative to Z}.

Remark 1.4. The Cone Avoidance Basis Theorem is so named because Z avoids the Turing cone above X. This theorem has been applied in foundational studies touching on set existence [12], Turing degrees of complete theories [16, 27, 28], nonstandard models of arithmetic [17], Scott sets [1, Chapter XIX], and models of WKL_{0} (see [30, §§VIII.2,IX.2] and [32, §§9,10]).

Remark 1.5. The Randomness Preservation Basis Theorem is so named because Z preserves the randomness of Y. This theorem has been applied to prove several interesting results in the foundations of probability theory [3, 26, 36]. There is also a recent, less well known, basis theorem concerning preservation of strong f-randomness [13, Theorem 4.6].

1.2 Combining basis theorems

Remark 1.6. The question arises:

Which basis theorems can be combined with each other?

Regarding this question, a large amount of information is known.

For instance, it is known that the Low Basis Theorem and the R.E. Basis Theorem are incompatible in the sense that they cannot be combined into one basis theorem. In other words, we can find P as above such that no point of P is both low and of recursively enumerable Turing degree. (In fact, we can find P as above such that every point of P which is of recursively enumerable Turing degree is Turing complete, i.e., ≥_{T} 0′ where 0′ = the halting problem. This is a consequence of the Arslanov Completeness Criterion [37, Theorem V.5.1].)

Similarly, it is known that the Hyperimmune-Free Basis Theorem is incompatible with the Low Basis Theorem and with the R.E. Basis Theorem. (In fact, any hyperimmune-free Z which is ≤_{T} 0′ is ≤_{T} 0, hence ∉ P for a suitably chosen P as above.) Also, the Cone Avoidance Basis Theorem is compatible with the Low Basis Theorem, and with the Hyperimmune-Free Basis Theorem, but not with the R.E. Basis Theorem. (See for instance [10, §2.19.3].)

In addition, the Randomness Preservation Basis Theorem is incompatible with the Hyperimmune-Free Basis Theorem, and with the Low Basis Theorem, and with the R.E. Basis Theorem. To see this, let Y ∈ MLR be such that Y ≥_{T} 0′. (The existence of such Y ’s is a consequence of a famous theorem known as the Kučera/Gács Theorem; see [10, Theorems 8.3.2 and 8.5.1] or [22, 3.3.2] or [33, Theorem 3.8].) Then, any hyperimmune-free Z such that Y ∈ MLR^{Z} is ≤_{T} 0 (see [22, Theorem 8.1.18]). And, any Z ≤_{T} 0′ such that Y ∈ MLR^{Z} is K-trivial (see [10, Chapter 11] or [22, Chapter 5]), hence again ∉ P for a suitably chosen P as above.

Summarizing these known results, we have Table 1. In this table, 0 denotes incompatibility and 1 denotes compatibility.

Basis Theorems  Low R.E. H.I.F. C.A. R.P.
Low  1  0  0  1  0
Recursively Enumerable  0  1  0  0  0
Hyperimmune-Free  0  0  1  1  0
Cone Avoidance  1  0  1  1  ???
Randomness Preservation  0  0  0  ???  1

Table 1: Combining basis theorems

Remark 1.7. Note that Table 1 has two missing entries. One of our accomplishments in this paper is to fill in the missing entries. We prove that, although the Randomness Preservation Basis Theorem is incompatible with the Cone Avoidance Basis Theorem, the only Turing cones which cannot be avoided in this context are the K-trivial ones. In other words, X is K-trivial if and only if there exist P as above and Y ∈ MLR such that (∀Z ∈ P) (Y ∈ MLR^{Z} ⇒ X ≤_{T} Z). Indeed, we find a fixed P which works for all K-trivial X and all Y ∈ MLR such that Y ≥_{T} 0′. See Theorems 2.3 and 3.13 below.

1.3 Partial randomness relative to a Turing oracle

In addition to our new results mentioned in Remark 1.7, we also prove some other new results concerning partial randomness relative to a Turing oracle.

The following definition from [13, §2] plays a key role.

Definition 1.8. We write {0, 1}^{∗} = ⋃_{n=0}^{∞}{0, 1}^{n} = the set of finite sequences of 0’s and 1’s. Let f : {0, 1}^{∗} → (−∞, ∞) be a computable function. For S ⊆ {0, 1}^{∗} we write pwt_{f}(S) = sup {∑_{τ∈F} 2^{−f(τ)} | F ⊆ S prefix-free} and ⟦S⟧ = \{X ∈ \{0, 1\}^{ℕ} | ∃n (X↾n ∈ S)\}. We say that X is \underline{strongly f-random} if X ∉ ⋂_{i}⟦S_{i}⟧ for all uniformly recursively enumerable sequences S_{i} ⊆ {0, 1}^{∗}, i = 1, 2, … such that ∀i (pwt_{f}(S_{i}) ≤ 2^{−i}).

Remark 1.9. Let KA denote a priori Kolmogorov complexity (see [10, §3.16] or [38]). The following characterization from [13, §2] is a straightforward generalization of [4, Corollary 4.10]:

X is strongly f-random if and only if ∃c ∀n (KA(X↾n) ≥ f(X↾n) − c).

Remark 1.10. \underline{Martin-Löf randomness} is just strong f-randomness with f(τ) = |τ| = the length of τ. In this case we have pwt_{f}(A) = λ(⟦A⟧) where λ is the \underline{fair coin probability measure} on \{0, 1\}^{ℕ}, also known as the \underline{uniform measure} or \underline{Lebesgue measure}, given by λ(⟦τ⟧) = 2^{−|τ|} for all τ ∈ \{0, 1\}^{∗}. The corresponding special case of Remark 1.9 is a famous theorem known as Schnorr’s Theorem or the Schnorr/Levin Theorem. See [10, Theorem 6.2.3] or [22, page 105] or [33, Theorem 10.7].

Remark 1.11. A famous theorem known as Van Lambalgen’s Theorem (see [10, §6.9] or [22, Theorem 3.4.6] or [33, Theorem 3.6]) implies the following.

If X is Martin-Löf random, and if Y is Martin-Löf random relative to X, then X is Martin-Löf random relative to Y.

One of our new results in this paper is a generalization of this, replacing Martin-Löf randomness by strong f-randomness. Namely, under a convexity assumption on f, we prove the following.

If X is strongly f-random, and if Y is Martin-Löf random relative to X, then X is strongly f-random relative to Y.

See Theorem 5.8 below. This result appears to be new, even in well studied special cases such as f(τ) = |τ|/2.

Remark 1.12. Recall from [6, 7, 25, 26] the notion of \underline{μ-randomness} where μ is a Borel probability measure. Namely, X is said to be \underline{μ-random} if X ∉ ⋂_{i} U_{i} whenever U_{i} is uniformly Σ_{1}^{0} relative to μ and μ(U_{i}) ≤ 2^{−i} for all i. (For a fuller explanation, see §4 below.) Recall also that μ is said to be \underline{continuous} if μ({X}) = 0 for all X. Note that λ is continuous, and λ-randomness is the same as Martin-Löf randomness. One of our new results in this paper is a codingfree version of Schnorr’s Theorem for μ-randomness. See Theorem 4.10 below. We also obtain a version of Van Lambalgen’s Theorem for μ-randomness. See Theorem 4.14 below.

Remark 1.13. Recall from [18] the notions of \underline{autocomplexity} and \underline{complexity} for X ∈ {0, 1}^{ℕ}. By [13, §7] we have the following characterizations in terms of strong f-randomness.

1. X is autocomplex if and only if X is strongly f-random for some computable f such that {f(X↾n) | n ∈ ℕ} is unbounded.

2. X is complex if and only if X is strongly f-random for some computable, length-invariant f such that {f(X↾n) | n ∈ ℕ} is unbounded.

Here f is said to be \underline{length-invariant} if ∀σ ∀τ (|σ| = |τ| ⇒ f(σ) = f(τ)).

Remark 1.14. One may also consider autocomplexity and complexity relative to Turing oracles. By [18, 24, 26] (see also Theorem 6.4 below) we have:

X is autocomplex relative to some Turing oracle if and only if X is μ-random for some μ with μ({X}) = 0, if and only if X ≰_{T} 0.

One of our new results in this paper is as follows.

X is complex relative to some Turing oracle if and only if X is μrandom for some continuous μ.

See Theorem 6.6 below. The class {X | X is μ-random for some continuous μ} has been studied extensively [26].

2 Combining two basis theorems

In this section we prove that, except for K-triviality, the Cone Avoidance Basis Theorem and the Randomness Preservation Basis Theorem are compatible. See Theorem 2.3 below.

Remark 2.1. The concept of K-triviality will be defined and used later, in §3. Our results in this section are more conveniently formulated in terms of a related concept, \underline{LR-reducibility}. Recall from [10, 22, 33, 34] that, by definition, X ≤_{LR} Z if and only if MLR^{Z} ⊆ MLR^{X}. Obviously X ≤_{LR} Z if X ≤_{T} Z, but the converse is known to fail. (In fact, there are recursively enumerable sets A ≤_{LR} 0 such that A ≰_{T} 0.) Two major theorems concerning K-triviality (see [10, Chapter 11] or [22, Chapter 5]) are as follows.

1. X is K-trivial if and only if X ≤_{LR} 0.

2. X is K-trivial if and only if X ≤_{T} Z for some Z ∈ MLR^{X}.

It is also known that X ≤_{LR} 0 implies X′ ≤_{T} 0′.

The following theorem implies that, given countably many non-K-trivial instances of our two basis theorems, we can simultaneously satisfy all of them. Note that part 2 of the theorem was already implicit in [13].

Theorem 2.2. Let P be a nonempty effectively closed set in Euclidean space.

1. Assume that (∀i ∈ ℕ) (X_{i} ≰_{LR} 0 or X_{i} ≰_{T} Y) where Y ∈ MLR. Then, there exists Z ∈ P such that ∀i (X_{i} ≰_{T} Z) and Y ∈ MLR^{Z}.

2. Assume that (∀i ∈ ℕ) (X_{i} has one of the following properties):

(a) X_{i} is Martin-Löf random.

(b) X_{i} is strongly f_{i}-random, where f_{i} : {0, 1}^{∗} → (−∞, ∞) is a specific computable function.

(c) X_{i} is autocomplex.

(d) X_{i} is complex.

(e) X_{i} ≰_{LR} 0.

Then ∃Z (Z ∈ P and ∀i (X_{i} has the same property relative to Z)).

Proof. To prove 1, let Q = {Z ∈ P | Y ∈ MLR^{Z}}. By the Randomness Preservation Basis Theorem, Q is nonempty. Since Q is Σ_{2}^{0,Y}, we may apply the relativization to Y of a variant of the Cone Avoidance Basis Theorem (see for instance [16, Theorem 2.5]) to find Z ∈ Q such that ∀i (X_{i} ≰_{T} Y ⇒ X_{i} ≰_{T} Z). On the other hand, for all i such that X_{i} ≤_{T} Y, we have X_{i} ≰_{LR} 0, hence Y ∉ MLR^{X_{i}} by Remark 2.1, hence X_{i} ≰_{LR} Z, hence again X_{i} ≰_{T} Z.

To prove 2, apply the Kučera/Gács Theorem to find Y ∈ MLR such that ∀i (X_{i} ≤_{T} Y). By the Randomness Preservation Basis Theorem, let Z ∈ P be such that Y ∈ MLR^{Z}. Our conclusion is now immediate by [13, Theorems 1.1, 4.4, 5.1, 7.5.1, 7.5.2].

Theorem 2.3. Let P be a nonempty effectively closed set in Euclidean space. If X is non-K-trivial and Y is Martin-Löf random, there exists Z ∈ P such that X ≰_{T} Z and Y ∈ MLR^{Z}.

Proof. This is immediate from Theorem 2.2 and Remark 2.1.

3 Low-for-Ω PA-completeness

In this section we prove that the results of the previous section are sharp. In particular, by Theorem 3.13 below, K-triviality is indeed an obstacle to combining the Cone Avoidance Basis Theorem with the Randomness Preservation Basis Theorem.

Definition 3.1. Recall from [10, Chapter 11] or [22, Chapter 5] that X ∈ \{0, 1\}^{ℕ} is said to be \underline{K-trivial} if KP(X↾n) ≤^{+} KP(n) for all n. Here KP denotes prefix-free Kolmogorov complexity, and ≤^{+} denotes ≤ modulo an additive constant.

Definition 3.2. Recall from [10, 22] that Chaitin’s Ω is ≡_{T} 0′ and Martin-Löf random. A Turing oracle Z is said to be \underline{low-for-Ω} (see [10, Chapter 15] or [22, §8.1]) if Ω is Martin-Löf random relative to Z. An equivalent condition is that some Y ≡_{T} 0′ is Martin-Löf random relative to Z. Another equivalent condition is that every Martin-Löf random Y ≤_{T} 0′ is Martin-Löf random relative to Z. (These equivalences follow from [21, Theorem 4.3], a.k.a., the XYZ Theorem [13, Theorem 1.1].) It is also known [2] that Z is low-for-Ω if and only if {X | X ≤_{LR} Z} is countable.

Definition 3.3. A Turing oracle Z is said to be \underline{PA-complete} if it is Turing equivalent to some complete, consistent extension of Peano Arithmetic. Equivalently, every nonempty effectively closed set P in Euclidean space contains at least one point which is Turing reducible to Z. (See [16] or [31, §6].)

Remark 3.4. The Randomness Preservation Basis Theorem may be restated as follows: (∀Y ∈ MLR) ∃Z (Y ∈ MLR^{Z} and Z is PA-complete). The special case Y = Ω is known as the Low-for-Ω Basis Theorem (see [10, Chapter 15] or [22, §8.1]). In other words, ∃Z (Z is low-for-Ω and PA-complete). We are going to prove ∀X (X K-trivial ⇒ X ≤_{T} Z) for all such Z. See Theorem 3.11 below.

Lemma 3.5. If Z is low-for-Ω, then KP(n) ≤^{+} KP^{Z}(n) for infinitely many n.

Proof. This result is due to Miller [20, Theorem 3.3]. See also [10, Theorem 15.6.2] or [22, Theorem 8.1.9].

Lemma 3.6. If Z is PA-complete, there is a Z-recursive function K̃P: ℕ → ℕ such that KP^{Z}(n) ≤^{+} K̃P(n) ≤ KP(n) for all n.

Proof. Let U: ⊆ {0, 1}^{∗} → ℕ be a prefix-free partial recursive function such that KP(n) = KP_{U}(n) = min{|σ| | U(σ) = n} for all n. Let G_{U} be the set of characteristic functions of graphs of prefix-free partial functions from {0, 1}^{∗} to ℕ which extend U. Clearly G_{U} is a nonempty effectively closed subset of {f | f : {0, 1}^{∗}×ℕ → {0, 1}} so let g ∈ G_{U} be such that g ≤_{T} Z. Let K̃P = KPŨ where g is the characteristic function of the graph of Ũ. For all n we have K̃P(n) ≤ KP(n) because Ũ extends U, and KP^{Z}(n) ≤^{+} K̃P(n) because Ũ is prefix-free and partial Z-recursive. It remains to show that K̃P ≤_{T} Z, but this is clear because K̃P(n) = |σ| for the least σ such that g(σ, n) = 1.

Lemma 3.7. If Z is low-for-Ω and PA-complete, there is an infinite Z-recursive set A such that K̃P(n) ≤ KP(n) ≤^{+} K̃P(n) for all n ∈ A.

Proof. By Lemma 3.6 we have K̃P(n) ≤ KP(n) for all n. By Lemmas 3.5 and 3.6 let a be a constant such that KP(n) ≤ K̃P(n) + a for infinitely many n. Since K̃P is Z-recursive, the set S = {n | KP(n) ≤ K̃P(n) + a} is Z-recursively enumerable. Let A be an infinite Z-recursive subset of S.

The next two lemmas are essentially due to Chaitin [5].

Lemma 3.8. ∀c ∃d ∀n (|{τ ∈ {0, 1}^{n} | KP(τ) ≤ KP(n) + c}| ≤ d).

Proof. See [10, Theorem 11.1.3] or [22, Theorem 2.2.26(ii)].

Definition 3.9. A \underline{tree} is a set T ⊆ \{0, 1\}^{∗} which is closed under initial segments, i.e., (∀τ ∈ T) (∀n < |τ|) (τ↾n ∈ T). We write [T] = {X ∈ {0, 1}^{ℕ} | ∀n (X↾n ∈ T)} = {paths through T }.

Lemma 3.10. Let T be a recursively enumerable tree such that ∃d ∀n (n ∈ A ⇒ |T ∩ {0, 1}^{n}| ≤ d) for some infinite recursively enumerable set A. Then [T] is finite and ∀X (X ∈ [T] ⇒ X is recursive).

Proof. Clearly |[T]| ≤ d. Let e ≤ d be as large as possible such that |T ∩ {0, 1}^{n}| = e for infinitely many n ∈ A. Let m be such that |T ∩ {0, 1}^{n}| ≤ e for all n > m such that n ∈ A. Let B = {n > m | n ∈ A and |T ∩ {0, 1}^{n}| = e}. Clearly B is infinite and recursively enumerable and the function n ↦ T ∩{0, 1}^{n} for n ∈ B is partial recursive. Let P = {X ∈ {0, 1}^{ℕ} | ∀n (n ∈ B ⇒ X↾n ∈ T ∩ {0, 1}^{n})}. Clearly P = [T] and P is a Π_{1}^{0} subset of {0, 1}^{ℕ}. Thus [T] is a finite Π_{1}^{0} subset of {0, 1}^{ℕ}. It follows that every path through T is recursive.

Theorem 3.11. If Z is low-for-Ω and PA-complete, then ∀X (X K-trivial ⇒ X ≤_{T} Z).

Proof. Let K̃P and A be as in Lemmas 3.6 and 3.7. Let a be a constant such that KP(n) ≤ K̃P(n) + a for all n ∈ A. Suppose X is K-trivial. Let b be a constant such that KP(X↾n) ≤ KP(n) + b for all n. Let

T = {τ ∈ {0, 1}^{∗} | (∀n ≤ |τ|) (n ∈ A ⇒ KP(τ↾n) ≤ K̃P(n) + a + b)}.

Clearly T is a tree. Since KP(n) ≤ K̃P(n) + a for all n ∈ A, we have X ∈ [T]. Since K̃P and A are Z-recursive, T is Z-recursively enumerable. Since K̃P(n) ≤ KP(n) for all n, we may apply Lemma 3.8 with a + b = c to obtain a constant d such that |T ∩ {0, 1}^{n}| ≤ d for all n ∈ A. Since A is infinite and Z-recursive, we may apply the Z-relativization of Lemma 3.10 to conclude that ∀X (X ∈ [T] ⇒ X ≤_{T} Z). This completes the proof.

Theorem 3.12.

1. If Z is low-for-Ω and PA-complete, then ∀X (X is K-trivial ⇔ (X ≤_{T} Z and X ≤_{T} 0′)).

2. ∀X (X is K-trivial ⇔ ∀Z ((Z is low-for-Ω and PA-complete) ⇒ X ≤_{T} Z)).

Proof. Combine Theorems 2.3 and 3.11.

The next result is a strong converse to Theorem 2.3.

Theorem 3.13. We can find Y ∈ MLR and P a nonempty effectively closed set in Euclidean space such that the following holds. For all Z ∈ P and all K-trivial X, Y ∈ MLR^{Z} implies X ≤_{T} Z.

Proof. Let Y = Ω and let P = the set of complete, consistent extensions of Peano Arithmetic. Our conclusion is then a restatement of Theorem 3.11.

We end this section with a counterpoint to Theorems 3.11 and 3.12.

Theorem 3.14. If Z is low-for-Ω and PA-complete, then ∀A (A recursively enumerable ⇒ (A ≤_{T} Z or Z′ ≤_{T} A ⊕ Z)).

Proof. Let A be recursively enumerable such that A ≰_{T} Z. Since Z is PAcomplete, we have 0′ ≤_{T} A ⊕ Z by Day/Reimann [7, Corollary 2.1]. Since Z is low-for-Ω, we have Z′ ≤_{T} Z ⊕ 0′ by Nies [22, Fact 3.6.19(ii)]. Combining these two observations, we have Z′ ≤_{T} A ⊕ Z.

4 An approach to μ-randomness

Let μ be a Borel probability measure on {0, 1}^{ℕ}. We present a coding-free approach to μ-randomness. In this context we prove generalizations of Schnorr’s Theorem and Van Lambalgen’s Theorem. See Theorems 4.10 and 4.14 below.

Remark 4.1. Our approach is derived from the one in [7, 26] augmented by ideas from [23, §3.3]. A more elaborate and general coding-free approach may be found in [11].

Definition 4.2. An \underline{effectively presented complete separable metric space} consists of a complete separable metric space D with metric ρ together with a sequence a of points a_{n} ∈ D, n ∈ ℕ such that {a_{n} | n ∈ ℕ} is dense in D and the function (m, n) ↦ ρ(a_{m}, a_{n}) : ℕ × ℕ → [0, ∞) is computable. An \underline{effectively compact metric space} is an effectively presented complete separable metric space D, ρ, a such that (∀z ∈ D) ∀i (∃n < c_{i}) (ρ(z, a_{n}) < 2^{−i}) for some computable function c : ℕ → ℕ. In this situation, a \underline{code for z} is defined to be a function f ∈ ∏_{i}{n | n < c_{i}} such that ∀i (ρ(z, a_{f(i)}) ≤ 2^{−i}). Note that ∏_{i}{n | n < c_{i}} is effectively homeomorphic to {0, 1}^{ℕ}, so we may identify codes as points in {0, 1}^{ℕ}. It is then straightforward to show that C_{z} = {Z ∈ {0, 1}^{ℕ} | Z is a code for z} is uniformly Π_{1}^{0} relative to any Z ∈ C_{z}.

Remark 4.3. The concepts in the previous definition are well known. See for instance [30, Definitions II.5.1 and III.2.3].

Remark 4.4. Let z be a point in an effectively compact metric space. From [6, 19] we know that z is not always equivalent to a Turing oracle. Nevertheless, using the ideas of [23, §3.3], it is possible to relativize many familiar recursiontheoretic concepts to z, just as if z were a Turing oracle. This theme is illustrated in the following definition and lemma.

Definition 4.5. Let z be a point in an effectively compact metric space. We define m : \{0, 1\}^{∗} → [0, ∞) to be \underline{left-r.e. relative to z} if m(τ) is left-r.e. relative to Z uniformly for all Z ∈ C_{z} and all τ ∈ {0, 1}^{∗}. A semimeasure m which is left-r.e. relative to z is said to be \underline{universal} if for all such semimeasures \overline{m} we have ∃c ∀τ (\overline{m}(τ) ≤ 2^{c}m(τ)). A sequence of sets U_{i} ⊆ \{0, 1\}^{ℕ}, i = 1, 2, … is said to be \underline{uniformly Σ_{1}^{0} relative to z} if \{(X, i) | X ∈ U_{i}\} ⊆ \{0, 1\}^{ℕ} × ℕ is uniformly Σ_{1}^{0} relative to any Z ∈ C_{z}. Equivalently, U_{i} = ⋂_{Z∈C_{z}} U_{i}^{Z} where U_{i}^{Z} is Σ_{1}^{0} relative to Z uniformly for all Z ∈ C_{z} and all i. We define KA^{z}(τ) = sup{KA^{Z}(τ) | Z ∈ C_{z}}.

Lemma 4.6. Let z be a point in an effectively compact metric space. Then KA^{z} = − log_{2} m^{z} where m^{z} is a universal left-r.e. semimeasure relative to z.

Proof. For all Z ∈ {0, 1}^{ℕ} let m^{Z} = ∑_{i} 2^{−i}m_{i}^{Z} where m_{i}^{Z}, i = 1, 2, … is a uniform enumeration of all left r.e. semimeasures relative to Z. Clearly m^{Z} is a universal left-r.e. semimeasure relative to Z, so we may safely assume that KA^{Z} = − log_{2} m^{Z}. Define m^{z} = inf{m^{Z} | Z ∈ C_{z}} and m_{i}^{z} = inf{m_{i}^{Z} | Z ∈ C_{z}}. Clearly KA^{z} = − log_{2} m^{z}. Using compactness of C_{z}, it is straightforward to show that m^{z} and m_{i}^{z} are left-r.e. semimeasures relative to z. Note that m_{i}^{z}, i = 1, 2, … is a uniform enumeration of all left-r.e. semimeasures relative to z, hence \overline{m}^{z} = ∑_{i} 2^{−i}m_{i}^{z} is a universal left-r.e. semimeasure relative to z. Moreover, we clearly have m^{z} ≥ \overline{m}^{z}, hence m^{z} is likewise universal.

Definition 4.7. As is well known, the set of Borel probability measures on {0, 1}^{ℕ} with the Prokhorov metric is an effectively compact metric space. (See for instance [23, Lemma 3.3.8] or [26, §2.4].) Let μ be such a measure, and let z be a point in an effectively compact metric space. Then, the ordered pair μ, z is again a point in such a space. A \underline{test for μ-randomness relative to z} is sequence of sets U_{i} ⊆ {0, 1}^{ℕ}, i = 1, 2, … which is uniformly Σ_{1}^{0} relative to the pair μ, z and such that μ(U_{i}) ≤ 2^{−i} for all i. We define X ∈ {0, 1}^{ℕ} to be \underline{μ-random relative to z} if X ∉ ⋂_{i} U_{i} for all such tests.

Theorem 4.8. Let z be a point in an effectively compact metric space. Let μ be a Borel probability measure on {0, 1}^{ℕ}. Then X ∈ {0, 1}^{ℕ} is μ-random relative to z if and only if X is μ-random relative to some Z ∈ C_{z}.

Proof. We follow the idea of [23, Lemma 3.3.31, Theorem 3.3.33]. Let U_{i}^{M,Z}, i = 1, 2, … be a universal test for μ-randomness relative to M ⊕ Z uniformly for all M ∈ C_{μ} and Z ∈ {0, 1}^{ℕ}. Then U_{i}^{μ,Z} = ⋂_{M∈C_{μ}} U_{i}^{M,Z}, i = 1, 2, … is a universal test for μ-randomness relative to Z uniformly for all Z ∈ {0, 1}^{ℕ}. And in turn, U_{i}^{μ,z} = ⋂_{Z∈C_{z}} U_{i}^{μ,Z}, i = 1, 2, … is a universal test for μ-randomness relative to z. The latter statement easily implies our theorem.

Corollary 4.9. Let μ be a Borel probability measure on {0, 1}^{ℕ}. Then X is μ-random if and only if X is μ-random relative to M for some code M of μ.

Proof. As a special case of Theorem 4.8 we have: X is μ-random relative to μ if and only if X is μ-random relative to M for some M ∈ C_{μ}. This statement is equivalent to our corollary.

Theorem 4.10. Let z be a point in an effectively compact metric space. Let μ be a Borel probability measure on {0, 1}^{ℕ}. Then X ∈ {0, 1}^{ℕ} is μ-random relative to z if and only if ∃c ∀n (KA^{μ,z}(X↾n) ≥ − log_{2} μ(⟦X↾n⟧) − c).

Proof. For the “if” direction, suppose X is not μ-random relative to z, say X ∈ ⋂_{i} U_{i} where U_{i} is a test for μ-randomness relative to z. Define \overline{m}^{μ,z}(τ) = ∑_{i} 2^{i}μ(U_{2i} ∩ ⟦τ⟧) and note that \overline{m}^{μ,z} is a left-r.e. semimeasure relative to the pair μ, z. By Lemma 4.6 with the pair μ, z in place of z, let m^{μ,z} be a universal left-r.e. semimeasure relative to μ, z. Let c be a constant such that ∀τ (\overline{m}^{μ,z}(τ) ≤ 2^{c}m^{μ,z}(τ)). It follows that ∀i ∀τ (2^{i}μ(U_{2i} ∩ ⟦τ⟧) ≤ 2^{c}m^{μ,z}(τ)). But X ∈ ⋂_{i} U_{2i}, hence ∀i ∃n (⟦X↾n⟧ ⊆ U_{2i}), hence ∀i ∃n (2^{i}μ(⟦X↾n⟧) ≤ 2^{c}m^{μ,z}(X↾n)), hence ∀i ∃n (KA^{μ,z}(X↾n) ≤ − log_{2} μ(⟦X↾n⟧) + c − i).

For the “only if” direction, suppose X is μ-random relative to z. For each i let S_{i} = {τ | KA^{μ,z}(τ) < − log_{2} μ(⟦τ⟧) − i}. Clearly S_{i} is uniformly μrecursively enumerable relative to μ, z. As in [13, Definition 2.3] let Ŝ_{i} be the set of minimal elements of S_{i}. Since ⟦S_{i}⟧ = ⟦Ŝ_{i}⟧ and Ŝ_{i} is prefix-free, we have μ(⟦S_{i}⟧) = μ(⟦Ŝ_{i}⟧) = ∑_{τ∈Ŝ_{i}} μ(⟦τ⟧) = ∑_{τ∈Ŝ_{i}} 2^{log_{2} μ(⟦τ⟧)} ≤ ∑_{τ∈Ŝ_{i}} 2^{−KA^{μ,z}(τ)−i} ≤ 2^{−i}. Since X is μ-random relative to z, it follows that X ∉ ⋂_{i}⟦S_{i}⟧, hence ∃i ∀n (KA^{μ,z}(X↾n) ≥ − log_{2} μ(⟦X↾n⟧) − i).

Remark 4.11. Theorem 4.10 may be viewed as a coding-free variant of [14, Theorem 6.2.1]. Note that Theorem 4.10 involves a priori complexity, KA, rather than prefix-free complexity, KP. We do not know whether Theorem 4.10 holds for KP instead of KA. The original, non-coding-free theorem in [14, §6.2] was stated for KP and it also holds for KA.

In order to prove a version of Van Lambalgen’s Theorem for μ-randomness, we first generalize a well known lemma concerning Σ_{1}^{0} subsets of {0, 1}^{ℕ}.

Lemma 4.12. Let z be a point in an effectively compact metric space. Let U ⊆ {0, 1}^{ℕ} be Σ_{1}^{0} relative to z. Given a Borel probability measure μ on {0, 1}^{ℕ} and a real number r, we can effectively find a set U[μ, r] ⊆ {0, 1}^{ℕ} with the following properties.

1. U[μ, r] ⊆ U and μ(U[μ, r]) ≤ r.

2. U[μ, r] = U provided μ(U) < r.

3. U[μ, r] is uniformly Σ_{1}^{0} relative to z, μ, r.

Proof. By Definition 4.5 we have U = ⋂_{Z∈C_{z}} U^{Z} where U^{Z} is Σ_{1}^{0} relative to Z uniformly for all Z ∈ {0, 1}^{ℕ}. For each s ∈ ℕ let U_{s}^{Z} be the part of U^{Z} which is enumerated prior to stage s. Let U^{Z}[μ, r] be the union of U_{s}^{Z} for all s such that μ(U_{s}^{Z}) < r. Clearly U^{Z}[μ, r] ⊆ U^{Z}, and μ(U^{Z}[μ, r]) ≤ r, and U^{Z}[μ, r] = U^{Z} provided μ(U^{Z}) < r, and U^{Z}[μ, r] is uniformly Σ_{1}^{0} relative to Z, μ, r. It follows that U[μ, r] = ⋂_{Z∈C_{z}} U^{Z}[μ, r] has the desired properties.

Definition 4.13. If μ and ν are Borel probability measures on {0, 1}^{ℕ}, let μ×ν be the product measure on {0, 1}^{ℕ} × {0, 1}^{ℕ}. We identify {0, 1}^{ℕ} × {0, 1}^{ℕ} with {0, 1}^{ℕ} via the standard pairing function (X, Y) ↦ X ⊕Y where (X ⊕Y)(2n) = X(n) and (X ⊕ Y)(2n + 1) = Y (n) for all n ∈ ℕ. Thus μ × ν is again a Borel probability measure on {0, 1}^{ℕ}.

Theorem 4.14. Let μ and ν be Borel probability measures on {0, 1}^{ℕ}. For X, Y ∈ {0, 1}^{ℕ} the following are equivalent.

1. X ⊕ Y is μ × ν-random.

2. X is μ-random relative to ν and Y is ν-random relative to the pair μ, X.

Proof. We imitate the standard proof of Van Lambalgen’s Theorem. See for instance [33, Theorem 3.6]. To prove 1 ⇒ 2, suppose Y is not ν-random relative to the pair μ, X, say Y ∈ ⋂_{i} V_{i} where ν(V_{i}) < 2^{−i} and V_{i} is uniformly Σ_{1}^{0} relative to μ, X. Using the notation of Lemma 4.12, let W_{i} = \{\overline{X} ⊕ \overline{Y} | \overline{Y} ∈ V_{i}[ν, 2^{−i}]\}. Then X ⊕ Y ∈ ⋂_{i} W_{i} and (μ × ν)(W_{i}) ≤ 2^{−i} and W_{i} is uniformly Σ_{1}^{0} relative to μ × ν, contradicting 1. To prove 2 ⇒ 1, suppose X ⊕ Y is not μ × ν-random, say X ⊕ Y ∈ ⋂_{i} W_{i} where (μ × ν)(W_{i}) ≤ 2^{−i} and W_{i} is uniformly Σ_{1}^{0} relative to

μ×ν. Let U_{i} = \{\overline{X} | ν(V \overline{X} ; i) > 2^{−i}\} where V \overline{X} ; i = \{\overline{Y} | \overline{X} ⊕\overline{Y} ∈ W_{2i}\}. Note that

U_{i} is uniformly Σ_{1}^{0} relative to μ, ν. Moreover μ(U_{i}) ≤ 2^{−i}, because otherwise we would have (μ × ν)(W_{2i}) ≥ μ(U_{i}) · 2^{−i} > 2^{−i} · 2^{−i} = 2^{−2i}, a contradiction. Let Ũ_{j} = ⋃_{i=j}^{∞} U_{i} and note that μ(Ũ_{j}) ≤ 2^{−j−1} and Ũ_{j} is again uniformly Σ_{1}^{0} relative to μ, ν. Hence X ∉ ⋂_{j} Ũ_{j}, so for all but finitely many i we have X ∉ U_{i}, i.e., ν(V_{i}^{X}) ≤ 2^{−i}. Moreover Y ∈ ⋂_{i} V_{i}^{X} and V_{i}^{X} is uniformly Σ_{1}^{0} relative to the triple X, μ, ν, contradicting 2. This completes the proof.

Corollary 4.15. Let μ and ν be Borel probability measures on {0, 1}^{ℕ}. Suppose X is μ-random relative to ν and Y is ν-random relative to the pair μ, X. Then X is μ-random relative to the pair ν, Y.

Proof. Apply Theorem 4.14 twice.

Remark 4.16. Theorem 4.14 seems to be “folklore,” i.e., well known but not in the literature. The special case μ = ν has appeared as [7, Theorem 1.7].

5 A product theorem for strong f-randomness

The purpose of this section is to prove a product theorem for strong f-randomness. See Theorem 5.8 below. We first prove a generalization of the Effective Capacitability Theorem from [25].

Definition 5.1 (compare [25, §3.3]). For f : {0, 1}^{∗} → (−∞, ∞) we say that X ∈ \{0, 1\}^{ℕ} is \underline{effectively f-capacitable} if X is μ-random for some Borel probability measure μ on {0, 1}^{ℕ} such that ∃c ∀τ (μ(⟦τ⟧) ≤ 2^{c−f(τ)}).

Definition 5.2 ([13, §8], compare [25, §2.3]). For f : {0, 1}^{∗} → (−∞, ∞) we say that f is \underline{convex} if wt_{f}(τ) ≤ wt_{f}(τ^{⌢}⟨0⟩) + wt_{f}(τ^{⌢}⟨1⟩) for all τ ∈ \{0, 1\}^{∗}. Here we are writing wt_{f}(τ) = 2^{−f(τ)}.

Theorem 5.3 (Effective Capacitability Theorem, compare [25, Theorem 14, Corollary 23]). Let f : {0, 1}^{∗} → (−∞, ∞) be computable and convex. For X ∈ {0, 1}^{ℕ} the following are equivalent.

1. X is strongly f-random.

2. X is effectively f-capacitable.

In order to prove Theorem 5.3, we use the following definitions and lemma.

Definition 5.4. Recall from [25, §3.3] that a \underline{semimeasure} is a function m : {0, 1}^{∗} → [0, 1] such that m(τ) ≥ m(τ^{⌢}⟨0⟩) + m(τ^{⌢}⟨1⟩) for all τ ∈ {0, 1}^{∗}. Dually, we define a \underline{submeasure} to be a function m : \{0, 1\}^{∗} → [0, ∞] such that m(τ) ≤ m(τ^{⌢}⟨0⟩) + m(τ^{⌢}⟨1⟩) for all τ ∈ {0, 1}^{∗}. Note that f is convex if and only if wt_{f} is a submeasure.

Definition 5.5. A function m : \{0, 1\}^{∗} → [0, ∞) is said to be \underline{left-r.e.} (respectively \underline{right-r.e.}) if the real numbers m(τ) are uniformly left recursively enumerable (respectively right recursively enumerable) for all τ ∈ {0, 1}^{∗}.

Lemma 5.6. Let m_{1} be a semimeasure and let m_{2} be a submeasure.

1. If m_{1}(⟨⟩) ≤ 1 ≤ m_{2}(⟨⟩) and ∀τ (m_{1}(τ) ≤ m_{2}(τ)), then we can find a Borel probability measure μ on {0, 1}^{ℕ} such that ∀τ (m_{1}(τ) ≤ μ(⟦τ⟧) ≤ m_{2}(τ)).

2. If m_{1} is left-r.e. and m_{2} is right-r.e., then the set of all such Borel probability measures is effectively closed.

Proof. The proof of part 1 is based on the following observation:

Given a_{0} + a_{1} ≤ b ≤ c_{0} + c_{1} where a_{0} ≤ c_{0} and a_{1} ≤ c_{1}, we can find

b_{0} and b_{1} such that b = b_{0} + b_{1} and a_{0} ≤ b_{0} ≤ c_{0} and a_{1} ≤ b_{1} ≤ c_{1}. (1)

To prove (1), define h(t) = a_{0} + t(c_{0} − a_{0}) + a_{1} + t(c_{1} − a_{1}) and note that h(0) = a_{0} + a_{1} and h(1) = c_{0} + c_{1}. By the Intermediate Value Theorem, there exists t such that 0 ≤ t ≤ 1 and h(t) = b. Then b_{0} = a_{0} + t(c_{0} − a_{0}) and b_{1} = a_{1} + t(c_{1} − a_{1}) are as desired.

To prove part 1, define μ(⟦τ⟧) by induction on the length of τ beginning with μ(⟦⟨⟩⟧) = 1. Assume inductively that μ(⟦τ⟧) has been defined such that m_{1}(τ) ≤ μ(⟦τ⟧) ≤ m_{2}(τ). Then

m_{1}(τ^{⌢}⟨0⟩) + m_{1}(τ^{⌢}⟨1⟩) ≤ μ(⟦τ⟧) ≤ m_{2}(τ^{⌢}⟨0⟩) + m_{2}(τ^{⌢}⟨1⟩)

so by (1) we can find μ(⟦τ^{⌢}⟨0⟩⟧) and μ(⟦τ^{⌢}⟨1⟩⟧) such that

μ(⟦τ⟧) = μ(⟦τ^{⌢}⟨0⟩⟧) + μ(⟦τ^{⌢}⟨1⟩⟧)
and m_{1}(τ^{⌢}⟨0⟩) ≤ μ(⟦τ^{⌢}⟨0⟩⟧) ≤ m_{2}(τ^{⌢}⟨0⟩)
and m_{1}(τ^{⌢}⟨1⟩) ≤ μ(⟦τ^{⌢}⟨1⟩⟧) ≤ m_{2}(τ^{⌢}⟨1⟩).

This proves part 1 of our lemma, and part 2 is obvious.

We are now ready to prove Theorem 5.3.

Proof of Theorem 5.3. To prove 1 ⇒ 2, assume that X is strongly f-random. By the Kučera/Gács Theorem, let Y be Martin-Löf random such that X ≤_{T} Y. Let Φ be a partial recursive functional such that X = Φ^{Y}. For each τ ∈ {0, 1}^{∗} let V_{τ} = \{\overline{Y} | τ ⊂ Φ\overline{Y} \}. Note that the indexed family V_{τ}, τ ∈ \{0, 1\}^{∗} is a Levin system in the sense of [13, Definition 4.1]. By [13, Lemma 4.2] let c be a rational number such that ∀n (λ(V_{X↾n}) < 2^{c−f(X↾n)}). By [13, Lemma 4.3] let Ṽ_{τ} ⊆ V_{τ}, τ ∈ {0, 1}^{∗} be a Levin system such that ∀τ (λ(Ṽ_{τ}) ≤ 2^{c−f(τ)}) and ∀n (Ṽ_{X↾n} = V_{X↾n}). Note that λ(Ṽ_{⟨⟩}) = 1 and τ ↦ λ(Ṽ_{τ}) is a left-r.e. semimeasure, and by convexity τ ↦ 2^{c−f(τ)} is a right-r.e. submeasure. Let P be the set of Borel probability measures μ such that λ(Ṽ_{τ}) ≤ μ(⟦τ⟧) ≤ 2^{c−f(τ)} for all τ. By Lemma 5.6 P is nonempty and effectively closed, so by the Randomness Preservation Basis Theorem plus Corollary 4.9, let μ ∈ P be such that Y is Martin-Löf random relative to μ, i.e., λ-random relative to μ. We claim that X is μ-random. Otherwise, suppose X ∈ ⋂_{i} U_{i} where U_{i} is uniformly Σ_{1}^{0} relative to μ and μ(U_{i}) ≤ 2^{−i} for all i. Let W_{i} = ⋃_{τ∈S_{i}} Ṽ_{τ} where S_{i} = {τ | ⟦τ⟧ ⊆ U_{i}}. As in [13, Definition 2.3] let Ŝ_{i} be the set of minimal elements of S_{i} and note that Ŝ_{i} is prefix-free and ⟦Ŝ_{i}⟧ = ⟦S_{i}⟧ = U_{i}. Note also that S_{i} and consequently W_{i} are uniformly Σ_{1}^{0} relative to μ. For each i we have ∃n (X↾n ∈ S_{i}) and for this n we have Y ∈ V_{X↾n} = Ṽ_{X↾n}, hence Y ∈ W_{i}, so Y ∈ ⋂_{i} W_{i}. But for each i we also have λ(W_{i}) = ∑_{τ∈Ŝ_{i}} λ(Ṽ_{τ}) ≤ ∑_{τ∈Ŝ_{i}} μ(⟦τ⟧) = μ(U_{i}) ≤ 2^{−i} contradicting the fact that Y is λ-random relative to μ. This proves our claim. Our claim implies that X is effectively f-capacitable, and this proves 1 ⇒ 2.

To prove 2 ⇒ 1, assume that X is not strongly f-random. By [13, Theorem 8.16] it follows that X is not vehemently f-random, say X ∈ ⋂_{i} U_{i} where U_{i} is uniformly Σ_{1}^{0} and vwt_{f}(U_{i}) ≤ 2^{−i} for all i. By [13, Lemma 8.15] let S_{i} ⊆ {0, 1}^{∗} be uniformly r.e. such that U_{i} ⊆ ⟦S_{i}⟧ and pwt_{f}(S_{i}) ≤ 2^{−i+1} for all i. To show that X is not effectively f-capacitable, let μ be a Borel probability measure on {0, 1}^{ℕ} such that ∃c ∀τ (μ(⟦τ⟧) ≤ 2^{c−f(τ)}). Then for all i we have μ(U_{i}) ≤ μ(⟦S_{i}⟧) = μ(⟦Ŝ_{i}⟧) = ∑_{τ∈Ŝ_{i}} μ(⟦τ⟧) ≤ ∑_{τ∈Ŝ_{i}} 2^{c−f(τ)} ≤ 2^{c}pwt_{f}(S_{i}) ≤ 2^{c−i+1} so X is not μ-random. This proves 2 ⇒ 1 and thus Theorem 5.3.

Remark 5.7. The length-invariant case of Theorem 5.3 is due to Reimann and Kjos-Hanssen (see [25, Theorem 14, Corollary 23]). Our proof of Theorem 5.3 is similar to Reimann’s proof [25] of the length-invariant case.

Our new result is as follows.

Theorem 5.8. Let f : {0, 1}^{∗} → (−∞, ∞) be computable and convex. If X is strongly f-random, and if Y is Martin-Löf random relative to X, then X is strongly f-random relative to Y.

Proof. Let Q be the set of Borel probability measures μ on {0, 1}^{ℕ} such that X is μ-random and ∃c ∀τ (μ(⟦τ⟧) ≤ 2^{c−f(τ)}). By Theorem 5.3 Q is nonempty. Clearly Q is Σ_{2}^{0} relative to X, so by the Randomness Preservation Basis Theorem relative to X, let μ ∈ Q be such that Y is Martin-Löf random relative to μ, X. Since λ is computable, it follows that Y is λ-random relative to μ, X. But then, by Corollary 4.15, X is μ-random relative to Y. Hence, by Theorem 5.3 relativized to Y, X is strongly f-random relative to Y.

Remark 5.9 (compare [13, Remark 4.5]). In Theorem 5.8 the assumption “Y is Martin-Löf random” cannot be weakened to “Y is strongly f-random.” For example, define X(n) = Y (2n) where Y is Martin-Löf random. Then X is strongly 1/2-random (indeed Martin-Löf random), and Y is strongly 1/2-random relative to X, but of course X is not strongly 1/2-random relative to Y.

Corollary 5.10 (compare [33, Corollary 3.9]). Let f : {0, 1}^{∗} → (−∞, ∞) be computable and convex. Assume that X is strongly f-random and X ≤_{T} Y and Y is Martin-Löf random relative to Z and Z ≥_{T} 0′. Then X is strongly f-random relative to Z.

Proof. Since Z ≥_{T} 0′, we may assume by the Kučera/Gács Theorem that Z is Martin-Löf random. Since Y is Martin-Löf random relative to Z, it follows by Van Lambalgen’s Theorem that Z is Martin-Löf random relative to Y. Since X ≤_{T} Y, it follows that Z is Martin-Löf random relative to X. It then follows by Theorem 5.8 that X is strongly f-random relative to Z.

Remark 5.11. It is known [13, Theorem 4.4] that Corollary 5.10 holds even if we drop two of the assumptions, namely, Turing completeness of Z and convexity of f. We conjecture that Theorem 5.8 holds without the convexity assumption.

6 Complexity relative to a Turing oracle

In this section we obtain a new characterization of complexity relative to a Turing oracle. We also obtain a new proof of some known characterizations of autocomplexity relative to a Turing oracle. See Theorems 6.4 and 6.6 below.

Before proving Theorems 6.4 and 6.6, we note the following alternative characterizations.

Theorem 6.1. Let Z be a Turing oracle, and suppose X ∈ {0, 1}^{ℕ}.

1. The following are equivalent.

(a) X is autocomplex relative to Z.

(b) There exists g ∈ DNR^{Z} such that g ≤_{T}^{Z} X, i.e., g ≤_{T} X ⊕ Z.

2. The following are pairwise equivalent.

(a) X is complex relative to Z.

(b) There exists g ∈ DNR^{Z} such that g ≤_{tt}^{Z} X, i.e., g = Φ^{Z}(X) for some total Z-recursive functional Φ^{Z} : {0, 1}^{ℕ} → ℕ^{ℕ}.

(c) There exists g ∈ DNR^{Z} such that g ≤_{wtt}^{Z} X, i.e., g ≤_{T} X ⊕ Z with Z-recursively bounded use of X.

Here DNR^{Z} = {g ∈ ℕ^{ℕ} | g is diagonally nonrecursive relative to Z}.

Proof. This is just [18, Theorem 2.3] relativized to Z.

We now begin the proofs of Theorems 6.4 and 6.6.

Definition 6.2. A function f : \{0, 1\}^{∗} → (−∞, ∞) is said to be \underline{monotone} if ∀σ ∀τ (σ ⊂ τ ⇒ f(σ) ≤ f(τ)). Note that KA is monotone.

Lemma 6.3. Given a computable function f : {0, 1}^{∗} → (−∞, ∞), we can find a computable, convex, monotone function f̃ : {0, 1}^{∗} → (−∞, ∞) such that the following holds. For all X ∈ {0, 1}^{ℕ}, if X is strongly f-random and {f(X↾n) | n ∈ ℕ} is unbounded, then the same holds with f̃ instead of f. Moreover, if f is length-invariant, then so is f̃.

Proof. Let F be the smallest monotone function which majorizes f, i.e., F (τ) = max{f(σ) | σ ⊆ τ}. Define f̃(τ) by recursion on |τ| as follows: f̃(⟨⟩) = F (⟨⟩), f̃(τ^{⌢}⟨i⟩) = min(F (τ^{⌢}⟨i⟩), f̃(τ) + 1) for i = 0, 1. Obviously f̃ is computable and monotone and f̃(τ) ≤ F (τ) for all τ. Also, f̃ is convex, because f̃(τ^{⌢}⟨i⟩) ≤ f̃(τ) + 1 for i = 0, 1. If f is length-invariant then so is F, hence so is f̃. Suppose now that X is strongly f-random. Recall from [13, §2] that strong frandomness is equivalent to strong f-complexity. Thus X is strongly f-complex, i.e., KA(X↾n) ≥^{+} f(X↾n) for all n. Since KA is monotone, it follows by the definition of F that X is strongly F -complex, hence strongly f̃-complex, hence strongly f̃-random. If {f(X↾n) | n ∈ ℕ} is unbounded, so is {F (X↾n) | n ∈ ℕ}, and this together with the monotonicity of F implies that {f̃(X↾n) | n ∈ ℕ} is unbounded. This completes the proof.

Theorem 6.4. For X ∈ {0, 1}^{ℕ} the following are pairwise equivalent.

1. X is autocomplex relative to some oracle Z.

2. X is autocomplex relative to some PA-complete oracle Z.

3. X is μ-random for some Borel probability measure μ on {0, 1}^{ℕ} such that μ({X}) = 0.

4. X is noncomputable.

Proof. The equivalence 1 ⇔ 2 is obtained by relativizing [13, Theorem 7.5.3] to Z. To prove 1 ⇒ 3, assume that X is autocomplex relative to Z. By Remark 1.13 and Lemma 6.3 relativized to Z, X is strongly f-random relative to Z for some convex f ≤_{T} Z such that {f(X↾n) | n ∈ ℕ} is unbounded. But then, by Theorem 5.3 relative to Z, X is μ-random relative to Z for some Borel probability measure μ such that ∃c ∀τ (μ(⟦τ⟧) ≤ 2^{c−f(τ)}). For this c we have ∀n (μ(⟦X↾n⟧) ≤ 2^{c−f(X↾n)}), hence μ({X}) = 0, thus proving 1 ⇒ 3. The implication 3 ⇒ 4 is trivial because X ∈ ⋂_{n}⟦X↾n⟧. To prove 4 ⇒ 1, assume that X is noncomputable. By a famous theorem known as the Posner/Robinson Theorem (see [24] or [35, Lemma 3.4.1]), let Z be an oracle such that X ⊕ Z ≡_{T} Z′. In particular X is autocomplex relative to Z.

Lemma 6.5. Let μ be a Borel probability measure μ on {0, 1}^{ℕ}. Suppose X is μ-random and μ({X}) = 0. Then, we can find a μ-computable, convex, monotone function f : {0, 1}^{∗} → [0, ∞] such that {f(X↾n) | n ∈ ℕ} is unbounded and X is strongly f-random relative to (some code for) μ. If μ is continuous, we can choose f to be length-invariant.

Proof. By Corollary 4.9 let M ∈ {0, 1}^{ℕ} be a code for μ such that X is μ-random relative to M. Let f(τ) = − log_{2} μ(⟦τ⟧). Clearly f is μ-computable, convex, and monotone. Since μ({X}) = 0 we have lim_{n} μ(⟦X↾n⟧) = 0, hence {f(X↾n) | n ∈ ℕ} is unbounded. By Theorem 4.10 we have KA^{M}(X↾n) ≥^{+} − log_{2} μ(⟦X↾n⟧) for all n, i.e., X is strongly f-complex relative to M, hence by [13, §2] X is strongly f-random relative to M. If μ is continuous, we can repeat the above argument with a length-invariant f, namely f(τ) = min{− log_{2} μ(⟦σ⟧) | |σ| = |τ|}.

Theorem 6.6. For X ∈ {0, 1}^{ℕ} the following are pairwise equivalent.

1. X is complex relative to some oracle Z.

2. X is complex relative to some PA-complete oracle Z.

3. X is μ-random for some continuous Borel probability measure μ on {0, 1}^{ℕ}.

Proof. The equivalence 1 ⇔ 2 is obtained by relativizating [13, Theorem 7.5.4] to Z. To prove 1 ⇒ 3, assume that X is complex relative to Z. By Remark 1.13 and Lemma 6.3 relative to Z, X is strongly f-random relative to Z for some length-invariant, convex, unbounded f ≤_{T} Z. But then, by Theorem 5.3 relative to Z, X is μ-random relative to Z for some Borel probability measure μ such that ∃c ∀τ (μ(⟦τ⟧) ≤ 2^{c−f(τ)}). Since f is length-invariant and unbounded, μ is continuous, thus proving 1 ⇒ 3. To prove 3 ⇒ 1, assume that X is μ-random for some continuous μ. By Lemma 6.5 there is an oracle Z such that X is strongly f-random relative to Z for some length-invariant, unbounded f ≤_{T} Z. Hence, by Remark 1.13 relative to Z, X is complex relative to Z.

Remark 6.7. Theorem 6.4 was essentially already known, being a combination of known results from [13, 18, 26]. However, Theorem 6.6 appears to be new. In connection with Theorem 6.6, note that the class {X ∈ {0, 1}^{ℕ} | X is μ-random for some continuous Borel probability measure μ on {0, 1}^{ℕ}} has been studied extensively in [26].

We finish by presenting another product theorem.

Theorem 6.8. Suppose X, Y ∈ {0, 1}^{ℕ}.

1. If X is autocomplex, and if Y is Martin-Löf random relative to X, then X is autocomplex relative to Y.

2. If X is complex, and if Y is Martin-Löf random relative to X, then X is complex relative to Y.

Proof. If X is autocomplex, it follows by Remark 1.13 that X is strongly frandom for some computable f such that {f(X↾n) | n ∈ ℕ} is unbounded. By Lemma 6.3 we may safely assume that f is convex. But then, if Y is Martin-Löf random relative to X, Theorem 5.8 implies that X is strongly f-random relative to Y, hence by Remark 1.13 X is autocomplex relative to Y. This proves part 1 of our theorem. The proof of part 2 is similar.

Remark 6.9. Theorem 6.8 and similar results such as [13, Theorems 7.5.1, 7.5.2] are of a different flavor than other randomness preservation results. This is because complexity relative to an oracle does not necessarily imply complexity or even autocomplexity. For example, let X be nonrecursive such that no g ∈ DNR is ≤_{T} X. By Theorem 6.1 X is neither complex nor autocomplex, but by Theorem 6.4 X is autocomplex relative to some oracle. If X is in addition nonhyperarithmetical, it follows by Theorem 6.6 and [26, Theorem 5.9] that X is complex relative to some oracle.

References

[1] Christopher J. Ash and Julia F. Knight. Computable Structures and the Hyperarithmetical Hierarchy. Number 144 in Studies in Logic and the Foundations of Mathematics. North-Holland, 2000. XV + 346 pages. 3

[2] George Barmpalias and Andrew E. M. Lewis. Chaitin’s halting probability and the compression of strings using oracles. Proceedings of The Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences, 467:2912–2926, 2011. http://dx.doi.org/10.1098/rspa.2011.0031. 8

[3] 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

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

[5] Gregory J. Chaitin. Information-theoretical characterizations of recursive infinite strings. Theoretical Computer Science, 2:45–48, 1976. 8

[6] Adam R. Day and Joseph S. Miller. Randomness for non-computable measures. Transactions of the American Mathematical Society, 365(7):3575– 3591, 2013. 5, 10

[7] Adam R. Day and Jan Reimann. Independence, relative randomness, and PA degrees. Notre Dame Journal of Formal Logic, 55(1):1–10, 2014. 5, 10, 13 [8] J. C. E. Dekker, editor. Recursive Function Theory. Proceedings of Sym-

posia in Pure Mathematics. American Mathematical Society, 1962. VII + 247 pages. 21

[9] 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

[10] Rodney G. Downey and Denis R. Hirschfeldt. Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer, 2010. XXVIII + 855 pages. 4, 5, 6, 7, 8, 9

[11] Peter Gács. Uniform test of algorithmic randomness over a general space. Theoretical Computer Science, 341:91–137, 2005. 10

[12] 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. 3

[13] Kojiro Higuchi, W. M. Phillip Hudelson, Stephen G. Simpson, and Keita Yokoyama. Propagation of partial randomness. Annals of Pure and Applied Logic, 165(2):742–758, 2014. http://dx.doi.org/10.1016/j.apal.2013.10.006. 3, 5, 6, 7, 8, 12, 13, 15, 16, 17, 18, 19

[14] W. M. Phillip Hudelson. Partial Randomness and Kolmogorov Complexity. PhD thesis, Pennsylvania State University, April 2013. VII + 107 pages, http://etda.libraries.psu.edu/paper/17456/. 12

[15] Carl G. Jockusch, Jr. and Robert I. Soare. Degrees of members of Π_{1}^{0} classes. Pacific Journal of Mathematics, 40:605–616, 1972. 3

[16] 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. 3, 7, 8

[17] Richard Kaye. Models of Peano Arithmetic. Oxford University Press, 1991. X + 292 pages. 3

[18] 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. 6, 17, 18

[19] Joseph S. Miller. Degrees of unsolvability of continuous functions. Journal of Symbolic Logic, 69:555–584, 2004. 10

[20] Joseph S. Miller. The K-degrees, low for K degrees, and weakly low for K sets. Notre Dame Journal of Formal Logic, 50(4):381–391, 2010. 8

[21] Joseph S. Miller and Liang Yu. On initial segment complexity and degrees of randomness. Transactions of the American Mathematical Society, 360:3193–3210, 2008. 8 [22] André Nies. Computability and Randomness. Oxford University Press,

2009. XV + 433 pages. 4, 5, 6, 7, 8, 9, 10

[23] Noopur Pathak. Computable Aspects of Measure Theory. PhD thesis, Pennsylvania State University, June 2013. V + 63 pages, http://etda.libraries.psu.edu/paper/18698/. 10, 11

[24] David B. Posner and Robert W. Robinson. Degrees joining to 0′. Journal of Symbolic Logic, 46:714–722, 1981. 6, 17

[25] Jan Reimann. Effectively closed sets of measures and randomness. Annals of Pure and Applied Logic, 156:170–182, 2008. 5, 13, 14, 15

[26] 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, 5, 6, 10, 11, 18, 19

[27] Dana S. Scott. Algebras of sets binumerable in complete extensions of arithmetic. In [8], pages 117–121, 1962. 3

[28] Dana S. Scott and Stanley Tennenbaum. On the degrees of complete extensions of arithmetic (abstract). Notices of the American Mathematical Society, 7:242–243, 1960. 3

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

[30] 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. 3, 10

[31] Stephen G. Simpson. Mass problems and randomness. Bulletin of Symbolic Logic, 11:1–27, 2005. 8

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

[33] Stephen G. Simpson. Almost everywhere domination and superhighness. Mathematical Logic Quarterly, 53:462–482, 2007. 4, 5, 6, 13, 16

[34] Stephen G. Simpson. Mass problems and measure-theoretic regularity. Bulletin of Symbolic Logic, 15:385–409, 2009. 6

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

[36] Stephen G. Simpson and Keita Yokoyama. A nonstandard counterpart of WWKL. Notre Dame Journal of Formal Logic, 52:229–243, 2011. 3 [37] Robert I. Soare. Recursively Enumerable Sets and Degrees. Perspectives in

Mathematical Logic. Springer-Verlag, 1987. XVIII + 437 pages. 4

[38] V. A. Uspensky and A. Shen. Relations between varieties of Kolmogorov complexity. Mathematical Systems Theory, 29:271–292, 1996. 5