Almost Everywhere Domination

Natasha L. Dobrinen^{∗} Stephen G. Simpson^{†}

Department of Mathematics Pennsylvania State University

May 18, 2004

to appear in the Journal of Symbolic Logic originally submitted March 17, 2004

Abstract

A Turing degree a is said to be almost everywhere dominating if, for almost all X ∈ 2^{ω} with respect to the “fair coin” probability measure on 2^{ω}, and for all g : ω → ω Turing reducible to X, there exists f : ω → ω of Turing degree a which dominates g. We study the problem of characterizing the almost everywhere dominating Turing degrees and other, similarly defined classes of Turing degrees. We relate this problem to some questions in the reverse mathematics of measure theory.

1 Introduction

In this paper ω denotes the set of natural numbers, 2^{ω} denotes the set of total functions from ω to {0, 1}, and ω^{ω} denotes the set of total functions from ω to ω. The “fair coin” probability measure μ on 2^{ω} is given by

μ({X ∈ 2^{ω} | X(n) = i}) = 1/2

for all n ∈ ω and i ∈ {0, 1}. A property P is said to hold almost everywhere (abbreviated a.e.) or for almost all X ∈ 2^{ω} (abbreviated a.a.) if

μ({X ∈ 2^{ω} | X has property P }) = 1.

For f, g ∈ ω^{ω} we say that f dominates g if

∗http://www.math.psu.edu/dobrinen/. Dobrinen’s research was partially supported by NSF VIGRE Grant DMS-9810759.

†http://www.math.psu.edu/simpson/. Simpson’s research was partially supported by NSF Grant DMS-0070718.

∃m ∀n (n ≥ m ⇒ f(n) > g(n)).

A well known theorem of axiomatic set theory reads as follows.

Theorem 1.1. Let M be a countable transitive model of ZFC. Then for almost all X ∈ 2^{ω} we have

(∀g ∈ M[X] ∩ ω^{ω}) (∃f ∈ M ∩ ω^{ω}) (f dominates g) .

Here M[X] denotes the set of all sets constructible from finitely many elements of M ∪ {X} by ordinals belonging to M. It is known that, for almost all X ∈ 2^{ω}, M[X] is a model of ZFC. This leads to a forcing-free proof of the independence of the Continuum Hypothesis. See the exposition of Sacks [8].

The purpose of this paper is to investigate recursion-theoretic analogs of Theorem 1.1, replacing the set-theoretic ground model M by the recursiontheoretic ground model

REC = {f ∈ ω^{ω} | f is recursive},

and replacing M[X] by

REC[X] = {g ∈ ω^{ω} | g ≤_{T} X}.

Here ≤_{T} denotes Turing reducibility, i.e., Turing computability relative to an oracle. Thus g ≤_{T} X if and only if g is recursive in X, i.e., g is Turing computable using an oracle for X.

In analogy with Theorem 1.1, it would be natural to conjecture that for almost all X ∈ 2^{ω} and all g ∈ REC[X] there exists f ∈ REC such that f dominates g. However, this is not the case, as shown by the following result of Martin [7]. Since the proof of Theorem 1.2 has not been published, we present it below.

Theorem 1.2 (Martin [7]). For almost all X ∈ 2^{ω} there exists g ∈ REC[X] such that g is not dominated by any f ∈ REC.

Proof. We present Martin’s unpublished proof from [7].

Fix a positive integer p. We shall define a recursive relation R ⊆ 2^{ω} × ω × ω called the chasing relation. We shall read R(X, e, n) as “X chases e at n”. Also, “X chases e” will mean that X chases e at n for some n.

In order to define “chasing e”, we proceed as follows. Given e, put k = k_{e} = 2^{e+p+1}, and partition 2^{ω} into k pairwise disjoint clopen sets C_{1}^{e}, …, C_{k}^{e} each of measure 1/k. Define s_{1}, …, s_{k} by

s_{1} = e ,
s_{2} ≃ least s > s_{1} such that {e}_{s}(s_{1}) ↓ ,
⋮
s_{i+1} ≃ least s > s_{i} such that {e}_{s}(s_{i}) ↓ ,
⋮
s_{k} ≃ least s > s_{k−1} such that {e}_{s}(s_{k−1}) ↓ .

Note that e = s_{1} < ⋯ < s_{k}. Also, writing s_{i}^{e} = s_{i}, the relation

{(e, n, i) | n = s_{i}^{e}} ⊆ ω × ω × ω

is recursive. We define X to chase e at n if and only if X ∈ C_{i}^{e} and n = s_{i}^{e} for some i = 1, …, k.

Note that the relation “X chases e at n” is recursive, and if X chases e at n then e ≤ n. Thus we can define a partial recursive functional Φ from 2^{ω} into ω^{ω} by

Φ^{X}(n) ≃ max {{e}(n) + 1 | X chases e at n} .

Obviously, if Φ^{X} is not total, then Φ^{X}(n) is undefined for some n, and this is so because of chasing e for some e. Furthermore, if Φ^{X}(n) is undefined because of chasing e, then this means that X chases e at n and {e}(n) is undefined, hence n = s_{i}^{e} for the unique largest i such that s_{i}^{e} is defined. The set of all such X’s is therefore just C_{i}^{e}, and the measure of C_{i}^{e} is 1/k_{e}, i.e., 1/2^{e+p+1}. Thus we have

μ (\{X | Φ^{X} is not total\}) ≤ ∑_{e=0}^{∞} \frac{1}{2^{e+p+1}} = \frac{1}{2^{p}} ,

hence

μ (\{X | Φ^{X} is total\}) ≥ 1 − \frac{1}{2^{p}} .

Furthermore, if {e} and Φ^{X} are both total, then Φ^{X}(n) ≥ {e}(n) + 1 where n = the unique s_{i}^{e} such that X ∈ C_{i}^{e}. It follows that, if Φ^{X} is total, then Φ^{X} is not dominated by any recursive function.

Letting p go to infinity, we have shown that for almost all X ∈ 2^{ω} there exists g ∈ REC[X] such that g is not dominated by any f ∈ REC. This gives Theorem 1.2.

2 Almost everywhere domination

Motivated by Theorem 1.2, we make the following definition.

Definition 2.1. We say that A ∈ 2^{ω} is almost everywhere dominating if for almost all X ∈ 2^{ω} and all g ∈ REC[X] there exists f ∈ REC[A] such that f dominates g.

Note that this property of A depends only on the Turing degree of A. In these terms, Theorem 1.2 says that 0, the Turing degree of recursive functions, is not almost everywhere dominating. In this paper we raise the problem of characterizing the Turing degrees which are almost everywhere dominating.

The following theorem of Kurtz [5] implies that 0′, the Turing degree of the Halting Problem, is almost everywhere dominating. We consider an apparently more restrictive property.

Definition 2.2. We say that A ∈ 2^{ω} is almost everywhere uniformly dominating if for almost all X ∈ 2^{ω} there exists f ∈ REC[A] such that for all g ∈ REC[X], f dominates g.

Again, this property of A depends only on the Turing degree of A. Note also that, if A is almost everywhere uniformly dominating, then A is uniformly almost everywhere dominating, i.e., there exists a fixed function f ∈ REC[A] such that for almost all X ∈ 2^{ω} and all g ∈ REC[X], f dominates g. This additional uniformity follows from the Zero-One Law of probability theory, plus countability of REC[A].

Theorem 2.3 (Kurtz [5, Theorem 4.3]). The Turing degree 0′ is uniformly almost everywhere dominating. In other words, we can find a fixed function f ∈ ω^{ω} recursive in the Halting Problem, such that f dominates all g ∈ ω^{ω} recursive in X for almost all X ∈ 2^{ω}.

It follows from Theorem 2.3 that all Turing degrees ≥ 0′ are uniformly almost everywhere dominating. We make the following conjecture.

Conjecture 2.4. Let a be a Turing degree. The following are pairwise equivalent.

1. a is almost everywhere dominating.

2. a is uniformly almost everywhere dominating.

3. a ≥ 0′.

Conjecture 2.4 is perhaps too good to be true. However, we have the following result, Theorem 2.6, which improves Theorem 2.3 and provides a kind of converse to it. Let ψ be a partial function from ω to ω. We write ψ(n) ↓ to mean that ψ(n) is defined, i.e., n ∈ domain of ψ. Let us say that f ∈ ω^{ω} dominates ψ if

∃m ∀n ((n ≥ m ∧ ψ(n) ↓) ⇒ f(n) > ψ(n)) .

Definition 2.5. We say that A ∈ 2^{ω} is almost everywhere strongly dominating if for almost all X ∈ 2^{ω} and all ψ partial recursive in X there exists f recursive in A such that f dominates ψ. We say that A ∈ 2^{ω} is almost everywhere uniformly strongly dominating if for almost all X ∈ 2^{ω} there exists f recursive in A such that, for all ψ partial recursive in X, f dominates ψ.

Again, if A is almost everywhere uniformly strongly dominating, then A is uniformly almost everywhere strongly dominating, and all of these notions depend only on the Turing degree of A. We have the following new result.

Theorem 2.6. Let a be a Turing degree. The following are pairwise equivalent.

1. a is almost everywhere strongly dominating.

2. a is uniformly almost everywhere strongly dominating.

3. a ≥ 0′.

Proof. We first show that 0′ is uniformly almost everywhere strongly dominating.

For e, i ∈ ω define ρ(e, i) = μ({X ∈ 2^{ω} | {e}^{X}(i) ↓}). Note that the recursive sequence of rational numbers

r(e, i, n) = \frac{|\{σ ∈ 2^{n} | \{e\}_{n}^{σ}(i) ↓\}|}{2^{n}}, n = 0, 1, 2, …,

is nondecreasing and converges to ρ(e, i). Thus ρ ≤_{T} 0′. Put h(e, i) = the least n such that

r(e, i, n) ≥ ρ(e, i) − \frac{1}{2^{i+1}} .

Clearly h ≤_{T} 0′. Put

f(e, i) = max {{e}_{h(e,i)}^{σ}(i) | σ ∈ 2^{h(e,i)} and {e}_{h(e,i)}^{σ}(i) ↓} .

Then f ≤_{T} h ≤_{T} 0′. Moreover, for all e, i ∈ ω we have

μ(\{X ∈ 2^{ω} | \{e\}^{X}(i) ↓ > f(e, i)\}) < \frac{1}{2^{i+1}} .

Put

U_{e,n} = {X ∈ 2^{ω} | ∃i ≥ n {e}^{X}(i) ↓ > f(e, i)} .

Clearly the U_{e,n}’s are uniformly Σ_{1}^{0,f}, hence uniformly Σ_{1}^{0,0′}. Moreover

μ(U_{e,n}) ≤ ∑_{i=n}^{∞} μ(\{X ∈ 2^{ω} | \{e\}^{X}(i) ↓ > f(e, i)\}) < ∑_{i=n}^{∞} \frac{1}{2^{i+1}} = \frac{1}{2^{n}} .

Thus S_{e} = ⋂_{n=0}^{∞} U_{e,n} is of measure 0, and X ∉ S_{e} implies X ∉ U_{e,n} for some n, hence {e}^{X}(i) ≤ f(e, i) for all i ≥ n such that {e}^{X}(i) ↓. Now define g ∈ ω^{ω} by g(i) = max{f(e, i) + 1 | e ≤ i}. Then g ≤_{T} 0′ and g dominates {e}^{X} for all e ∈ ω and X ∈ 2^{ω} \S_{e}. In particular 0′ is uniformly almost everywhere strongly dominating.

It remains to show that if a is almost everywhere strongly dominating then a ≥ 0′. In fact, a better result is known. Say that A is strongly dominating if every partial recursive function from ω to ω is dominated by some function in REC[A]. Again, this is a property of the Turing degree of A. The following theorem is well known.

Theorem 2.7. A Turing degree a is strongly dominating if and only if a ≥ 0′.

Proof. That 0′ is strongly dominating follows from what we have already proved, by ignoring the oracle X. For the converse, consider the partial recursive function η given by η(e) ≃ the least s such that {e}_{s}(0) ↓. If f dominates η, then the Halting Problem H = {e ∈ ω | {e}(0) ↓} is computable from f, hence 0′ ≤_{T} f. This proves Theorem 2.7.

We now note that if a is almost everywhere strongly dominating then it is strongly dominating, hence ≥ 0′. The proof of Theorem 2.6 is now complete.

Remark 2.8. Our proof of Theorem 2.6 actually gives a more precise result. Following Kautz [4, Definition II.1.2], let us say that X ∈ 2^{ω} is 2-random if X is not Σ_{2}^{0}-approximable, i.e., if there is no uniformly Σ_{2}^{0} sequence of sets V_{n} ⊆ 2^{ω}, n ∈ ω, such that μ(V_{n}) < 1/2^{n} and X ∈ V_{n} for all n. Note that X is 2-random for almost all X. Our proof of Theorem 2.6 actually gives a fixed g ≤_{T} 0′ which dominates all functions partial recursive in X for all 2-random X. (This is because the sets U_{e,n} are uniformly Σ_{1}^{0,0′}, hence uniformly Σ_{2}^{0}.) Similarly, the proof of Martin’s Theorem 1.2 shows that for all 2-random X there exists a total function recursive in X which is not dominated by any recursive function. (See also Kautz [4, Theorem IV.2.4, part (iv)].)

On the other hand, let us say that X ∈ 2^{ω} is weakly 2-random [4, Definition II.3.1] if X ∈ V for all Σ_{2}^{0} sets V ⊆ 2^{ω} with μ(V) = 1. We do not know whether there exists a function recursive in some weakly 2-random X which is not dominated by any function recursive in 0′.

An alternative to Conjecture 2.4 is the following, where a′ denotes the Turing jump of a.

Conjecture 2.9. Let a be a Turing degree. The following are pairwise equivalent.

1. a is almost everywhere dominating.

2. a is uniformly almost everywhere dominating.

3. a′ ≥ 0′′.

Toward Conjecture 2.9, the following theorem of Martin [6] is well known. Say that A is uniformly dominating if there exists f ∈ REC[A] such that f dominates every g ∈ REC. Again, this is a property of the Turing degree of A.

Theorem 2.10 (Martin [6]). A Turing degree a is uniformly dominating if and only if a′ ≥ 0′′.

Proof. The proof is in [6]. See also Soare [13, pages 208–209].

Corollary 2.11. If a is almost everywhere uniformly dominating, then a′ ≥ 0′′.

3 Connection to reverse mathematics

In this section we exhibit a relationship between almost everywhere domination and the reverse mathematics of measure theory.

Reverse mathematics is a well known program of determining the weakest set existence axioms needed to prove specific mathematical theorems. This is carried out in the context of subsystems of second order arithmetic. For general background, see Simpson [12]. Other results on the reverse mathematics of measure theory are in the papers of Yu [14, 15, 16, 17, 18], Yu/Simpson [19], and Brown/Giusto/Simpson [1].

A well known result in measure theory asserts that the fair coin measure μ is regular. This means that measurable sets are approximable from within by F_{σ} sets and from without by G_{δ} sets. Recall that an F_{σ} is the union of countably many closed sets, and a G_{δ} is the intersection of countably many open sets. Regularity of μ means: For every measurable set Q ⊆ 2^{ω} there exist an F_{σ} set S and a G_{δ} set P such that S ⊆ Q ⊆ P and μ(S) = μ(Q) = μ(P). See for example the classic textbook of Halmos [2].

Attempting to reverse this measure-theoretic result, we encounter the difficulty that arbitrary measurable sets cannot be discussed in the language of second order arithmetic. However, we can discuss sets defined by arithmetical formulas, including F_{σ} and G_{δ} sets. We make the following conjecture.

Conjecture 3.1. The following are pairwise equivalent over RCA_{0}.

1. ACA_{0}.

2. Given a G_{δ} set Q ⊆ 2^{ω}, we can find an F_{σ} set S ⊆ Q such that μ(S) = μ(Q).

3. Given a G_{δ} set Q ⊆ 2^{ω}, and given ϵ > 0, we can find a closed set F ⊆ Q such that μ(F) ≥ μ(Q) − ϵ.

4. Given a G_{δ} set Q ⊆ 2^{ω} with μ(Q) > 0, we can find a closed set F ⊆ Q such that μ(F) > 0.

Toward Conjecture 3.1, it is already known that ACA_{0} implies statement 2. See for example Hinman [3, Lemma III.4.20] and Kautz [4, Lemma II.1.4]. And clearly 2 implies 3, which implies 4. Thus, we would like to prove that any or all of statements 2, 3, 4 imply ACA_{0} over RCA_{0}.

In this direction we have the following results.

Theorem 3.2. For A ∈ 2^{ω} the following are equivalent.

1. A is uniformly almost everywhere dominating.

2. Given a Π_{2}^{0} set Q ⊆ 2^{ω}, we can find a Σ_{2}^{0,A} set S ⊆ Q such that μ(S) = μ(Q).

Proof. Assume that A is uniformly almost everywhere dominating. Fix f ∈ REC[A] such that f dominates all g ∈ REC[X] for almost all X. Given a Π_{2}^{0} set Q ⊆ 2^{ω}, it is well known that there exists e = e_{Q} ∈ ω such that

Q = {X ∈ 2^{ω} | ∀n {e}^{X}(n) ↓}.

Fix such an e. Then for all X ∈ Q we have that g^{X} ∈ ω^{ω} given by

g^{X}(n) = least s such that {e}_{s}^{X}(n) ↓

belongs to REC[X]. It follows that f dominates g^{X} for almost all X ∈ Q. Thus

S = {X ∈ 2^{ω} | ∃k ∀n {e}_{f(n)+k}^{X}(n) ↓}

is a Σ_{2}^{0,A} subset of Q with μ(S) = μ(Q). This proves statement 2.

Conversely, assume that A is as in statement 2. Applying this to the Π_{2}^{0} set

Q^{∗} = \{⟨\underbrace{0, …, 0}_{e}, 1⟩^{⌢}X | e ∈ ω, X ∈ 2^{ω}, ∀n \{e\}^{X}(n) ↓\},

we obtain a Σ_{2}^{0,A} set S^{∗} ⊆ Q^{∗} such that μ(S^{∗}) = μ(Q^{∗}). Let us write

S^{∗} = {Y | ∃i P (Y, i)}

where P ⊆ 2^{ω} × ω is a Π_{1}^{0,A} predicate. We have

∀e ∀X ∀i (P (⟨\underbrace{0, …, 0}_{e}, 1⟩^{⌢}X, i) ⇒ ∀n \{e\}^{X}(n) ↓).

Furthermore, for each e and i,

P_{e,i} = \{X | P (⟨\underbrace{0, …, 0}_{e}, 1⟩^{⌢}X, i)\}

is a closed subset of 2^{ω}, hence for each n,

{{e}^{X}(n) | X ∈ P_{e,i}}

is finite, by compactness of 2^{ω}. Thus we have

∀e ∀i ∀n ∃m ∀X (P (⟨\underbrace{0, …, 0}_{e}, 1⟩^{⌢}X, i) ⇒ \{e\}^{X}(n) ≤ m).

Now, by Lemma 3.5 of Simpson [11] relativized to A, the predicate

∀X (P (⟨\underbrace{0, …, 0}_{e}, 1⟩^{⌢}X, i) ⇒ \{e\}^{X}(n) ≤ m)

is Σ_{1}^{0,A}. Hence by Σ_{1}^{0,A} uniformization we find g : ω × ω × ω → ω recursive in A such that

∀e ∀X ∀i (P (⟨\underbrace{0, …, 0}_{e}, 1⟩^{⌢}X, i) ⇒ ∀n \{e\}^{X}(n) ≤ g(e, i, n)).

Thus f ∈ REC[A] given by

f(n) = max{g(e, i, n) + 1 | e, i ≤ n}

dominates {e}^{X} for all X ∈ P_{e,i} for all i. Since μ(S^{∗}) = μ(Q^{∗}), it follows that f dominates {e}^{X} for almost all X such that {e}^{X} is total, for all e. Thus A is uniformly almost everywhere dominating.

Theorem 3.3. For A ∈ 2^{ω} the following are equivalent.

1. A is almost everywhere dominating.

2. Given a Π_{2}^{0} set Q ⊆ 2^{ω}, and given ϵ > 0, we can find a Π_{1}^{0,A} set F ⊆ Q such that μ(F) ≥ μ(Q) − ϵ.

Proof. Assume that A is almost everywhere dominating. It follows that A is almost everywhere majorizing, i.e., for almost all X ∈ 2^{ω} and all g ∈ REC[X] there exists f ∈ REC[A] such that f majorizes g, i.e., ∀n (f(n) > g(n)). Given a Π_{2}^{0} set Q ⊆ 2^{ω}, let e = e_{Q} and g^{X} be as in the proof of Theorem 3.2. Then for almost all X ∈ Q there exists f ∈ REC[A] such that f majorizes g^{X}. Now let ϵ > 0 be given. Since REC[A] is countable, there exist f_{1}, …, f_{k} ∈ REC[A] such that

μ (⋃_{i=1}^{k} {X ∈ Q | f_{i} majorizes g^{X}}) ≥ μ(Q) − ϵ.

Putting f(n) = max{f_{1}(n), …, f_{k}(n)}, we have f ∈ REC[A] and

μ ({X ∈ Q | f majorizes g^{X}}) ≥ μ(Q) − ϵ.

Thus

F = {X ∈ 2^{ω} | ∀n {e}_{f(n)}^{X}(n) ↓}

is a Π_{1}^{0,A} subset of Q with μ(F) ≥ μ(Q) − ϵ. This proves statement 2. Conversely, assume that A is as in statement 2. Fix e ∈ ω and ϵ > 0. Put

Q_{e} = {X | ∀n {e}^{X}(n) ↓} .

Then Q_{e} is Π_{2}^{0}, so by assumption there exists a Π_{1}^{0,A} set F ⊆ Q such that μ(F) ≥ μ(Q) − ϵ. For each n we have

∀X (X ∈ F ⇒ {e}^{X}(n) ↓)

and F is a closed subset of 2^{ω}, hence by compactness of 2^{ω} {{e}^{X}(n) | X ∈ F } is finite. Thus we have

∀n ∃m ∀X (X ∈ F ⇒ {e}^{X}(n) < m) .

By Lemma 3.5 of Simpson [11] relativized to A, the predicate

∀X (X ∈ F ⇒ {e}^{X}(n) < m)

is Σ_{1}^{0,A}. Hence by Σ_{1}^{0,A} uniformization we find f ∈ REC[A] such that

∀n ∀X (X ∈ F ⇒ {e}^{X}(n) < f(n)) .

Now letting ϵ go to 0, we see that for almost all X ∈ Q_{e} there exists f ∈ REC[A] such that f majorizes {e}^{X}. Since this holds for all e, we see that A is almost everywhere majorizing, hence almost everywhere dominating.

Remark 3.4. Recall that Π_{2}^{0} and Π_{1}^{0} sets are recursion-theoretic analogs of G_{δ} sets and closed sets, respectively. See for example Hinman [3, Theorem III.1.16]. From this viewpoint, the properties mentioned in Theorems 3.2 and 3.3 are analogous to statements 2 and 3 in Conjecture 3.1, respectively. Thus, it seems reasonable to think that progress on Conjecture 2.4 in recursion theory may lead to progress on Conjecture 3.1 in reverse mathematics.

Remark 3.5. In particular, let (⋆) be statement 2 of Conjecture 3.1. By relativizing and formalizing the proofs of Corollary 2.11 and Theorem 3.2, we can show that any ω-model M of WKL_{0}+(⋆) has (∀X∈M)(∃Y ∈M)(Y′ ≥_{T} X′′). It follows by [12, Corollary VIII.2.18] (a consequence of the Low Basis Theorem) that there exists an ω-model of WKL_{0} in which (⋆) fails. We thank the referee for suggesting this observation. Furthermore, using Theorem III.2.1 of Kautz [4], we can build an ω-model M of WKL_{0} such that (∀X∈M)(∃Y ∈M)(Y is ωrandom relative to X), and (∀X∈M)(∃Y ∈M)(Y is ω-generic relative to X), yet (∀Y ∈M)(Y′ ≱_{T} 0′′), hence (⋆) fails in M.

References

[1] Douglas K. Brown, Mariagnese Giusto, and Stephen G. Simpson. Vitali’s theorem and WWKL. Archive for Mathematical Logic, 41:191–206, 2002.

[2] Paul R. Halmos. Measure Theory. Van Nostrand, 1950. XI + 304 pages.

[3] Peter G. Hinman. Recursion-Theoretic Hierarchies. Perspectives in Mathematical Logic. Springer-Verlag, 1978. XII + 480 pages.

[4] Steven M. Kautz. Degrees of Random Sets. PhD thesis, Cornell University, 1991. X + 89 pages.

[5] Stuart A. Kurtz. Randomness and Genericity in the Degrees of Unsolvability. PhD thesis, University of Illinois at Urbana-Champaign, 1981. VII + 131 pages.

[6] Donald A. Martin. Classes of recursively enumerable sets and degrees of unsolvability. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 12:295–310, 1966.

[7] Donald A. Martin. Measure, category, and degrees of unsolvability. Unpublished, typewritten, 16 pages, 1967.

[8] Gerald E. Sacks. Measure-theoretic uniformity in recursion theory and set theory. Transactions of the American Mathematical Society, 142:381–420, 1969.

[9] W. Sieg, editor. Logic and Computation. Contemporary Mathematics. American Mathematical Society, 1990. XIV + 297 pages.

[10] S. G. Simpson, editor. Reverse Mathematics 2001. Lecture Notes in Logic. Association for Symbolic Logic, 2004. To appear.

[11] Stephen G. Simpson. Π_{1}^{0} sets and models of WKL_{0}. In [10]. Preprint, April 2000, 29 pages, to appear.

[12] Stephen G. Simpson. Subsystems of Second Order Arithmetic. Perspectives in Mathematical Logic. Springer-Verlag, 1999. XIV + 445 pages.

[13] Robert I. Soare. Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer-Verlag, 1987. XVIII + 437 pages.

[14] Xiaokang Yu. Measure Theory in Weak Subsystems of Second Order Arithmetic. PhD thesis, Pennsylvania State University, 1987. VII + 73 pages.

[15] Xiaokang Yu. Radon-Nikodym theorem is equivalent to arithmetical comprehension. In [9], pages 289–297, 1990.

[16] Xiaokang Yu. Riesz representation theorem, Borel measures, and subsystems of second order arithmetic. Annals of Pure and Applied Logic, 59:65– 78, 1993.

[17] Xiaokang Yu. Lebesgue convergence theorems and reverse mathematics. Mathematical Logic Quarterly, 40:1–13, 1994.

[18] Xiaokang Yu. A study of singular points and supports of measures in reverse mathematics. Annals of Pure and Applied Logic, 79:211–219, 1996.

[19] Xiaokang Yu and Stephen G. Simpson. Measure theory and weak König’s lemma. Archive for Mathematical Logic, 30:171–180, 1990.