Π_{1}^{0} Sets and Models of WKL_{0}

Stephen G. Simpson Department of Mathematics Pennsylvania State University

           www.math.psu.edu/simpson/

First draft: April 10, 2000 This draft: September 6, 2013

Abstract

We show that any two Medvedev complete Π_{1}^{0} subsets of 2^{ω} are recursively homeomorphic. We obtain a Π_{1}^{0} set Q̂′ of countable coded ωmodels of WKL_{0} with a strong homogeneity property. We show that if G is a generic element of Q̂′, then the ω-model of WKL_{0} coded by G satisfies ∀X ∀Y (if X is definable from Y, then X is Turing reducible to Y). We use a result of Kučera to refute some plausible conjectures concerning ω-models of WKL_{0}. We generalize our results to non-ω-models of WKL_{0}. We discuss the significance of our results for foundations of mathematics.

This research was partially supported by NSF grant DMS-0070718. For helpful discussions and correspondence, I thank F. Ferreira, A. M. Fernandes, K. Tanaka, and T. Yamazaki.

AMS Subject Classifications: 03F35, 03D30, 03D80, 03B30.

A version of this paper has appeared in Reverse Mathematics 2001, edited by S. G. Simpson, Lecture Notes in Logic, Volume 21, Association for Symbolic Logic, 2005, pp. 352–378.

Contents

Abstract 1

Contents 2

1 Introduction 2

2 Foundational Significance 4

3 Medvedev Degrees of Π_{1}^{0} Subsets of 2^{ω} 5

4 Relativization, Iteration, ω-Models 11

5 Jockusch/Soare Genericity 14

6 Relative Genericity and Definability 17

7 Generalization to Non-ω-Models 19

8 A Result of Kučera 21

9 An Application to ω-Models 23

10 Applications to Non-ω-Models 24

References 26

1 Introduction

In this paper we apply recursion-theoretic methods to the study of ω-models of subsystems of second order arithmetic. Specifically, we present some results concerning Π_{1}^{0} subsets of 2^{ω}, along with applications to countable ω-models of WKL_{0}. These results and applications may be regarded as an addendum or supplement to Simpson [31, §VIII.2]. We also present generalizations to countable non-ω-models of WKL_{0}. These generalizations may be regarded as an addendum to Simpson [31, §IX.2].

For background on subsystems of second order arithmetic, see Simpson [31]. We recall here that RCA_{0} is the subsystem consisting of Δ_{1}^{0} comprehension and Σ_{1}^{0} induction, and WKL_{0} is the subsystem consisting of RCA_{0} plus Weak König’s Lemma, i.e., the statement that every infinite tree of finite sequences of 0’s and 1’s has a path. These two systems play an important role in Reverse Mathematics [31]. Their ω-models are easy to understand in recursion-theoretic terms. An ω-model of RCA_{0} is a set S ⊆ P (ω) such that (i) S ≠ ∅, (ii) X⊕Y ∈ S for all X, Y ∈ S, and (iii) if X ∈ S and Y ≤_{T} X then Y ∈ S. An ω-model of WKL_{0} has the additional property that if T ∈ S and T is an infinite tree of finite sequences of 0’s and 1’s, then T has a path in S.

There is a large recursion-theoretic literature on Π_{1}^{0} subsets of 2^{ω} and degrees of elements of such sets. An important paper in this area is Jockusch/Soare [17]. An extensive recent survey is Cenzer/Remmel [3]. This topic is well known to be closely related to ω-models of WKL_{0}. The connection is as follows: P ⊆ 2^{ω} is Π_{1}^{0} if and only if there exists a recursive tree T of finite sequences of 0’s and 1’s such that P = {X ∈ 2^{ω} : X is a path through T }.

In the model-theoretic literature, ω-models of WKL_{0} are known as Scott systems, after Scott [26], who proved that S ⊆ P (ω) is a countable ω-model of WKL_{0} if and only if S is the set of sets representable in some complete extension of Peano arithmetic. This idea is important in the study of models of arithmetic. See also Kaye [18].

Here is an outline of the rest of this paper.

In §2 we discuss the significance of some of our results, in terms of foundations of mathematics.

In §3 we study and characterize the nonempty Π_{1}^{0} subsets of 2^{ω} which are Medvedev complete. We prove that any two such sets are recursively homeomorphic (Theorem 3.21). This is related to a result of Pour-El/Kripke [23] concerning effectively inseparable theories.

In §4 we relativize and iterate the result of §3 to obtain a nonempty Π_{1}^{0} set Q̂′ of codes for countable ω-models of WKL_{0}, with a strong homogeneity property: any two nonempty Π_{1}^{0} subsets of Q̂′ are recursively homeomorphic, via a homeomorphism which preserves the ω-models (Theorem 4.11).

In §5 we combine the results of §§3,4 with Jockusch/Soare forcing, to obtain a countable ω-model of WKL_{0} in which all definable elements are recursive (Theorem 5.11). This result is originally due to Friedman [11, unpublished]. In §6 we improve this result, to obtain a countable ω-model of WKL_{0} satisfying ∀X ∀Y (if X is definable from Y then X ≤_{T} Y) (Theorem 6.9).

In §7 we generalize the results of §§3,4,5,6 to non-ω-models. In this way we obtain a conservation result, showing that WKL_{0} plus a strong relative nondefinability scheme is conservative over Σ_{1}^{0}-PA (Corollary 7.9).

In §8 we prove a recursion-theoretic result of Kučera [20]: There is a disjoint pair of recursively inseparable, recursively enumerable sets, such that any two separating sets which differ infinitely compute the complete recursively enumerable set (Theorem 8.3). In §9 we apply Kučera’s result to the study of ω-models of WKL_{0}. It is well known that the intersection of all such models consists of the recursive sets. We now show that the intersection of all such models which are submodels of a given one may contain nonrecursive sets (Theorem 9.1).

In §10 we generalize Kučera’s result, and we apply the generalization to the study of non-ω-models of WKL_{0}. We refute several plausible conjectures concerning the relationship between WKL_{0} and RCA_{0}. See Remarks 10.4, 10.8, 10.9.

Throughout this paper, we use recursion-theoretic concepts and notation from Rogers [25] and Soare [34]. We use ω = {0, 1, 2, …} to denote the set of natural numbers. We identify points X ∈ 2^{ω} with functions X : ω → {0, 1}. For e, n, s, k ∈ ω and X ∈ 2^{ω}, we write {e}_{s}^{X}(n) = k to mean that the Turing machine with Gödel number e and oracle X and input n halts in ≤ s steps with output k. For e, n, k ∈ ω and X ∈ 2^{ω}, we write {e}^{X}(n) = k to mean that ∃s ({e}_{s}^{X}(n) = k). Furthermore, {e}^{X}(n) ↓ means that {e}^{X}(n) is defined, i.e., ∃k ({e}^{X}(n) = k), and {e}^{X}(n) ↑ means that {e}^{X}(n) is undefined, i.e., ¬ ∃k ({e}^{X}(n) = k). For X, Y ∈ 2^{ω}, X ≤_{T} Y means that X is Turing reducible to Y, i.e., ∃e ∀n (X(n) = {e}^{Y} (n)). The Turing degree of X, written deg_{T} (X), is the set of all Y such that X ≡_{T} Y, i.e., X ≤_{T} Y and Y ≤_{T} X. A predicate R ⊆ 2^{ω} × ω is said to be recursive if ∃e ∀X ∀n ({e}^{X}(n) = 1 if R(X, n), and {e}^{X}(n) = 0 if ¬ R(X, n)). A set P ⊆ 2^{ω} is said to be Π_{1}^{0} if there exists a recursive predicate R such that P = {X ∈ 2^{ω} : ∀n R(X, n)}. For Π_{1}^{0} sets P ⊆ 2^{ω}, we shall consider recursive functionals Φ : P → 2^{ω} given by Φ(X)(n) = {e}^{X}(n) for some e ∈ ω and all X ∈ P, n ∈ ω.

2 Foundational Significance

In this section we explore the foundational significance of some of our results.

Foundations of mathematics is the study of the most basic concepts and logical structure of mathematics, with an eye to the unity of human knowledge. For general background in this area, the reader may turn to the van Heijenoort volume [38], where some of the most important modern papers have been carefully translated and reprinted. See also Gödel’s collected works [8] and the Friedman volume [13].

As background for our work here, consider the well known foundational program of computable analysis, i.e., the development of mathematics in the computable world, REC = {X : X is recursive}. See Aberth [1] and Pour-El/Richards [24]. This program is obviously attractive from the viewpoint of Turing’s analysis of computability. However, it is also known that the assumption “all real numbers are computable” conflicts with many basic, well known theorems of real analysis. For example, it is in conflict with the maximum principle for continuous real-valued functions on a closed bounded interval.

Clearly it would be desirable to strike a balance between these conflicting requirements. A fairly successful attempt in this direction is Theorem 5.11, below. In non-technical terms, the theorem asserts the existence of a world where the main theorems of real analysis hold, and the natural numbers are standard, yet each definable real number is computable. In technical terms, one obtains an ω-model S of WKL_{0} in which all definable reals are recursive. The identification of the recursive reals with the computable reals is an outcome of Turing’s foundational work on computable functions. Thus the computable reals play a large and important role in S, forming so to speak the “definable core” of S. On the other hand, from recent foundational work in Reverse Mathematics, we know that WKL_{0} is just strong enough to prove many basic theorems of real analysis. See Simpson [31, Chapter IV]. Thus S contains just enough noncomputable reals in order to satisfy the demands of real analysis.

Furthermore, in Theorem 6.9 below, we show that the same ω-model S satisfies a more general scheme:

For all reals X and Y, if Y is definable from X, then Y is Turing reducible to X, i.e., computable using X as an oracle.

We also show that WKL_{0} plus the above scheme has the same first order part as WKL_{0} alone. See Corollary 7.9, below.

The above scheme is foundationally interesting, for the following reason. Often in mathematics one has the situation that, under some assumptions on a real parameter X, there exists a unique real Y having some property which is stated in terms of X. In this kind of situation, our scheme allows us to conclude that Y is Turing reducible to X.

3 Medvedev Degrees of Π_{1}^{0} Subsets of 2^{ω}

In this section we exposit the lattice of Medvedev degrees of nonempty Π_{1}^{0} subsets of 2^{ω}. We prove an important result concerning nonempty Π_{1}^{0} subsets of 2^{ω} which are Medvedev complete.

For background on Medvedev degrees of subsets of the Baire space, ω^{ω}, see Rogers [25, §13.7] and Sorbi [35]. For background on Π_{1}^{0} subsets of the Cantor space, 2^{ω}, and of the Baire space, see the survey by Cenzer/Remmel [3].

Definition 3.1. Let P and Q be nonempty Π_{1}^{0} subsets of 2^{ω}. We say that P is Medvedev reducible to Q, written P ≤_{M} Q, if there exists a recursive functional Φ : Q → P. We say that Q is Medvedev complete if P ≤_{M} Q for all nonempty Π_{1}^{0} subsets P of 2^{ω}. We say that P and Q are Medvedev equivalent, written P ≡_{M} Q, if P ≤_{M} Q and Q ≤_{M} P. The Medvedev degree of P, written deg_{M}(P), is the set of all Q such that P ≡_{M} Q. The Medvedev degrees are partially ordered by writing deg_{M}(P) ≤ deg_{M}(Q) if and only if P ≤_{M} Q. We write deg_{M}(P) < deg_{M}(Q) if and only if P <_{M} Q, i.e., P ≤_{M} Q and Q ≰_{M} P.

Theorem 3.2. The Medvedev degrees of nonempty Π_{1}^{0} subsets of 2^{ω} form a distributive lattice P_{M} with a bottom and a top element. The top element of P_{M} consists of the nonempty Π_{1}^{0} subsets of 2^{ω} which are Medvedev complete.

Proof. In this proof and throughout this paper, we use the following notation. For X, Y ∈ 2^{ω} we have X⊕Y ∈ 2^{ω} where (X⊕Y)(2n) = X(n) and (X⊕Y)(2n+ 1) = Y (n). We use 2^{<ω} to denote the set of strings, i.e., finite sequences of 0’s and 1’s. The length of σ ∈ 2^{<ω} is denoted lh(σ). For X ∈ 2^{ω} and n ∈ ω, we have X[n] = ⟨X(0), …, X(n − 1)⟩ ∈ 2^{<ω} and lh(X[n]) = n. For σ ∈ 2^{<ω} and X ∈ 2^{ω}, we have σ^{⌢}X ∈ 2^{ω} given by

(σ^{⌢}X)(n) = \{ \begin{matrix}σ(n) & if n < lh(σ), \\ X(n − lh(σ)) & if n ≥ lh(σ). \end{matrix}

We fix a primitive recursive, one-to-one, onto function (·, ·) : ω × ω → ω. For Y ∈ 2^{ω} and m ∈ ω, we have (Y)_{m} ∈ 2^{ω} where (Y)_{m}(n) = Y ((m, n)).

To prove our theorem, let P and Q be nonempty Π_{1}^{0} subsets of 2^{ω}. The supremum or least upper bound of deg_{M}(P) and deg_{M}(Q) is deg_{M}(P × Q) where P × Q = {X ⊕ Y : X ∈ P and Y ∈ Q}. The infimum or greatest lower bound of deg_{M}(P) and deg_{M}(Q) is deg_{M}(P + Q) where

P + Q = {⟨0⟩^{⌢}X : X ∈ P } ∪ {⟨1⟩^{⌢}Y : Y ∈ Q}.

The distributive laws P × (Q + R) ≡_{M} (P × Q) + (P × R) and P + (Q × R) ≡_{M} (P + Q) × (P + R) are easily verified. The bottom element of our lattice P_{M} is deg_{M}(2^{ω}), or equivalently deg_{M}(P) where P is any Π_{1}^{0} subset of 2^{ω} with a recursive element. The top element of P_{M} is deg_{M}(Q) where Q is any nonempty Π_{1}^{0} subset of 2^{ω} which is Medvedev complete. See Lemma 3.3 and Remark 3.4 below. □

Lemma 3.3. There exists a nonempty Π_{1}^{0} subset Q of 2^{ω} which is Medvedev complete.

Proof. Let {P_{e} : e ∈ ω} be a standard, recursive enumeration of the Π_{1}^{0} subsets of 2^{ω}. (See Remark 3.9 below.) In particular, the predicate U(e, X) ≡ (X ∈ P_{e}) is Π_{1}^{0}. By the Normal Form Theorem for Π_{1}^{0} predicates, we have U(e, X) ≡ ∀n U_{1}(e, X[n]) where U_{1} ⊆ ω × 2^{<ω} is primitive recursive. As in Simpson [31, Lemmas VIII.2.5 and VIII.2.9], put U^{+}(e, X) ≡

∀n (∀σ of length n) (if (∀m ≤ n) U_{1}(e, σ[m]) then U_{1}(e, X[n])).

Note that U^{+}(e, X) is again Π_{1}^{0}. Now for all e such that P_{e} is nonempty, we have P_{e} = P_{e}^{+} = {X : U^{+}(e, X)}. On the other hand, for all e, P_{e}^{+} is nonempty, by compactness of 2^{ω}. Put

Q = ∏_{e} P_{e}^{+} = {Y : ∀e U^{+}(e, (Y)_{e})}.

Obviously Q is a nonempty Π_{1}^{0} subset of 2^{ω}. For all e such that P_{e} is nonempty, we have P_{e} ≤_{M} Q via the recursive functional Y ↦ (Y)_{e}. Thus Q is Medvedev complete. □

Remark 3.4. Another construction of a Medvedev complete set is as follows. Let Q be the Π_{1}^{0} set of complete extensions of Peano arithmetic. It can be shown that Q is Medvedev complete; see Scott/Tennenbaum [27] and Jockusch/Soare [17]. Instead of Peano arithmetic, we may use any effectively inseparable theory; see Pour-El/Kripke [23]. Or, we may use any effectively essentially incomplete theory; see Remark 3.18 below. Yet another construction of a Medvedev complete set may be obtained from Lemmas 3.14 and 3.16 below.

We are going to show that any two Medvedev complete Π_{1}^{0} subsets of 2^{ω} are recursively homeomorphic (Theorem 3.21). In order to prove this, we shall first consider the nature of Medvedev reducibility in more detail.

Lemma 3.5. Let R ⊆ ω × 2^{ω} × 2^{ω}. If the predicate R(k, X, Y) is Π_{1}^{0}, then the predicate S(k, X) ≡ ∃Y R(k, X, Y) is also Π_{1}^{0}.

Proof. By the Normal Form Theorem for Π_{1}^{0} predicates, we have

R(k, X, Y) ≡ ∀n R_{1}(k, X[n], Y [n])

where R_{1}(k, σ, τ) is primitive recursive. Thus S(k, X) holds if and only if ∃Y ∀n R_{1}(k, X[n], Y [n]). By compactness of 2^{ω}, this is equivalent to ∀n (∃τ of length n) (∀m ≤ n) R_{1}(k, X[m], τ[m]), which is explicitly Π_{1}^{0}. □

Lemma 3.6. Let Q be a Π_{1}^{0} subset of 2^{ω}, and let Φ : Q → 2^{ω} be a recursive functional.

1. The image Φ(Q) is a Π_{1}^{0} subset of 2^{ω}.

2. For any Π_{1}^{0} subset P of 2^{ω}, the inverse image Φ^{−1}(P) is a Π_{1}^{0} subset of 2^{ω}.

Proof. To prove part 1, note that for all X ∈ 2^{ω} we have X ∈ Φ(Q) if and only if ∃Y (Y ∈ Q and Φ(X) = Y). By Lemma 3.5, this is Π_{1}^{0}. For part 2 we have Φ^{−1}(P) = {Y : Y ∈ Q and Φ(Y) ∈ P } and this is obviously Π_{1}^{0}. □

Definition 3.7. We use B to denote the free Boolean algebra on a countable set of generators {a_{n} : n ∈ ω}. There is a well known isomorphism b ↦ [b] of B onto the Boolean algebra of clopen subsets of 2^{ω}, given by [a_{n}] = {X : X(n) = 1}, [b · c] = [b] ∩ [c], [b + c] = [b] ∪ [c], [−b] = 2^{ω} \ [b], [0] = ∅, [1] = 2^{ω}. For T ⊆ B we write [T] = ⋂{[b] : b ∈ T }.

Remark 3.8. The mapping b ↦ [b] is essentially just the usual semantics for propositional calculus. The Compactness Theorem for propositional calculus says: For all T ⊆ B, [T] = ∅ if and only if [T_{0}] = ∅ for some finite T_{0} ⊆ T. This is a consequence of the fact that 2^{ω} is compact as a topological space.

Remark 3.9. If T ⊆ B is recursively enumerable, then [T] ⊆ 2^{ω} is Π_{1}^{0}. Conversely, if P ⊆ 2^{ω} is Π_{1}^{0}, then P = [T_{P}] where T_{P} = {b ∈ B : P ⊆ [b]}. Note that T_{P} is recursively enumerable. A standard, recursive enumeration {P_{e} : e ∈ ω} of the Π_{1}^{0} subsets of 2^{ω} may be obtained by setting P_{e} = [T_{e}], where {T_{e} : e ∈ ω} is a standard, recursive enumeration of the recursively enumerable subsets of B.

Remark 3.10. The mapping b ↦ [b] gives a one-to-one correspondence between nonempty Π_{1}^{0} subsets of 2^{ω} and Stone spaces of Boolean algebras of the form B/I where I is a recursively enumerable ideal. These are the so-called “recursively enumerable Boolean algebras” of Cenzer/Remmel [3, §5]. Recursively presented homomorphisms on the Boolean algebras correspond to recursive functionals on the Stone spaces.

Lemma 3.11. Let Q be a Π_{1}^{0} subset of 2^{ω}, and let Φ : Q → 2^{ω} be a recursive functional. Then there is a recursive function f : B → B such that Φ^{−1}[b] = [f(b)] ∩ Q for all b ∈ B.

Proof. The predicate (Y ∈ Q and Φ(Y) ∈ [b]) is Π_{1}^{0}, so by the Normal Form Theorem, let R(τ, b) be a primitive recursive predicate such that

(Y ∈ Q and Φ(Y) ∈ [b]) ≡ ∀n R(Y [n], b).

Trivially we have

(∀b ∈ B) (∀Y ∈ 2^{ω}) (Φ(Y) ∉ [b] or Φ(Y) ∉ [−b] or Y ∉ Q),

or in other words,

(∀b ∈ B) (∀Y ∈ 2^{ω}) ∃n (not R(Y [n], b) or not R(Y [n], −b) or not R(Y [n], 1)).

By compactness of 2^{ω}, it follows that (∀b ∈ B) ∃n (∀τ of length n) (∃m ≤ n) (not R(τ[m], b) or not R(τ[m], −b) or not R(τ[m], 1)). For b ∈ B let n(b) be the least such n, and form f(b) ∈ B such that

[f(b)] = {Y ∈ 2^{ω} : (∀m ≤ n(b)) R(Y [m], b)}.

Clearly n : B → ω and f : B → B are recursive, and Φ^{−1}[b] = [f(b)] ∩ Q. □

Remark 3.12. In Lemma 3.11, we may replace f by the unique recursive homomorphism \overline{f} : B → B given by \overline{f}(a_{n}) = f(a_{n}) for all n. For X ∈ Q and b ∈ B, we have Φ(X) ∈ [b] if and only if X ∈ [f(b)]. Thus Φ is a truth-table reducibility operator. This is closely related to results of Nerode as presented in Rogers [25, pages 143 and 154].

We now introduce a property of nonempty Π_{1}^{0} subsets of 2^{ω}, called productiveness, which will turn out to be equivalent to Medvedev completeness (Lemma 3.20).

Definition 3.13. Let P be a nonempty Π_{1}^{0} subset of 2^{ω}. A splitting function for P is a recursive function g : ω → B such that for all e, if P_{e} ⊆ P and P_{e} is nonempty, then P_{e} ∩ [g(e)] and P_{e} ∩ [−g(e)] are nonempty. P is said to be productive if there exists a splitting function for P.

Lemma 3.14. There exists a nonempty Π_{1}^{0} set P ⊆ 2^{ω} such that P is productive.

Proof. Put P = {X ∈ 2^{ω} : ∀n (X(n) ≠ {n}(n))}. Clearly P is nonempty and Π_{1}^{0}. By Lemma 3.5, the predicate

S(e, n, k) ≡ ∀X (if X ∈ P_{e} then X(n) = k)

is Σ_{1}^{0}. By the Σ_{1}^{0} Uniformization Principle and the S-m-n Theorem, let h be a primitive recursive function such that, for all e and n, {h(e)}(n) = some k such that S(e, n, k) holds, if such a k exists. Define g : ω → B by g(e) = a_{h(e)}. We claim that g is a splitting function for P. To see this, suppose P_{e} ⊆ P and P_{e} ≠ ∅. If P_{e} ∩ [a_{h(e)}] = ∅, then ∀X (if X ∈ P_{e} then X(h(e)) = 0), hence {h(e)}(h(e)) = 0, a contradiction. If P_{e} ∩ [−a_{h(e)}] = ∅, then ∀X (if X ∈ P_{e} then X(h(e)) = 1), hence {h(e)}(h(e)) = 1, a contradiction. □

Lemma 3.15. Let P and Q be nonempty Π_{1}^{0} subsets of 2^{ω}. Given a, b, a′ ∈ B such that a ≠ a · b = b ≠ 0 and a′ ≠ 0, and given a splitting function for P, we can effectively find b′ ∈ B with the following properties: a′ ≠ a′ · b′ = b′ ≠ 0, and if Q ∩ [a] ≠ ∅ and P ∩ [a′] ≠ ∅ then 1. Q ∩ [a] ∩ [b] = ∅ if and only if P ∩ [a′] ∩ [b′] = ∅,

2. Q ∩ [a] ∩ [−b] = ∅ if and only if P ∩ [a′] ∩ [−b′] = ∅.

Proof. Because P is productive, P is nowhere dense in 2^{ω}, so given a′ ≠ 0 we can effectively find a′_{0}, a′_{1}, a′_{2} ∈ B such that a′ = a′_{0}+a′_{1}+a′_{2} and a′_{0}·a′_{1} = a′_{0}·a′_{2} = a′_{1} · a′_{2} = 0 and a′_{0} ≠ 0 and a′_{1} ≠ 0 and a′_{2} ≠ 0 and P ∩ [a′_{0}] = P ∩ [a′_{1}] = ∅. Thus P ∩ [a′] = P ∩ [a′_{2}]. Now let g be a splitting function for P. By the Recursion Theorem, we can effectively find e ∈ ω such that

P_{e} = \{ \begin{matrix}P ∩ [a′_{2}] & if Q ∩ [a] ∩ [b] ≠ ∅ and Q ∩ [a] ∩ [−b] ≠ ∅, \\ P ∩ [a′_{2}] ∩ [g(e)] & if Q ∩ [a] ∩ [b] = ∅ and Q ∩ [a] ∩ [−b] ≠ ∅, \\ P ∩ [a′_{2}] ∩ [−g(e)] & if Q ∩ [a] ∩ [b] ≠ ∅ and Q ∩ [a] ∩ [−b] = ∅, \\ ∅ & if Q ∩ [a] ∩ [b] = ∅ and Q ∩ [a] ∩ [−b] = ∅. \end{matrix}

Put b′ = a′_{1} + a′_{2} · g(e). Clearly a′ ≠ a′ · b′ = b′ ≠ 0. Now assume Q ∩ [a] ≠ ∅ and P ∩ [a′] ≠ ∅. If Q ∩ [a] ∩ [b] = ∅, then we have P_{e} = P ∩ [a′_{2}] ∩ [g(e)], hence P_{e} ∩ [−g(e)] = ∅, hence P_{e} = ∅ (because g is a splitting function for P), hence P ∩ [a′] ∩ [b′] = P ∩ [a′_{2}] ∩ [g(e)] = P_{e} = ∅. Similarly, if Q ∩ [a] ∩ [−b] = ∅, then P ∩ [a′] ∩ [−b′] = ∅. On the other hand, if Q ∩ [a] ∩ [b] ≠ ∅ and Q ∩ [a] ∩ [−b] ≠ ∅, then we have P_{e} = P ∩ [a′_{2}] = P ∩ [a′] ≠ ∅, hence P ∩ [a′] ∩ [b′] = P_{e} ∩ [g(e)] ≠ ∅ and P ∩ [a′] ∩ [−b′] = P_{e} ∩ [−g(e)] ≠ ∅. This completes the proof. □

Lemma 3.16. Let P and Q be nonempty Π_{1}^{0} subsets of 2^{ω}.

1. If P is productive, then there exists a recursive functional from P onto Q.

2. If P and Q are productive, then P and Q are recursively homeomorphic, i.e., there exists a recursive functional from P one-to-one onto Q.

Proof. Let P and Q be as in the hypothesis of our lemma. If B^{∗} is a subalgebra of B and if f^{∗} : B^{∗} → B is a monomorphism, let us call f^{∗} good if, for all b ∈ B^{∗}, Q ∩ [b] = ∅ if and only if P ∩ [f^{∗}(b)] = ∅.

For part 1, to find a recursive functional Φ from P onto Q, it suffices to find a good recursive monomorphism f : B → B. Assume inductively that we have already found a good finite monomorphism f_{n} : B_{n} → B, where B_{n} is a finite subalgebra of B. (We start with B_{0} = {0, 1}.) Let b be the nth element of B with respect to some fixed recursive enumeration of B. Let B_{n+1} be the finite subalgebra of B generated by B_{n} ∪{b}. We effectively extend f_{n} to a good finite monomorphism f_{n+1} : B_{n+1} → B, as follows. For each atom a of B_{n}, if a · b = a or a · b = 0 put f_{n+1}(a · b) = f_{n}(a · b), otherwise use Lemma 3.15 and a splitting function for P to effectively find f_{n+1}(a · b) = b′ ∈ B such that f_{n}(a) ≠ f_{n}(a)·b′ = b′ ≠ ∅, and Q∩[a]∩[b] = ∅ if and only if P ∩[f_{n}(a)]∩[b′] = ∅, and Q ∩ [a] ∩ [−b] = ∅ if and only if P ∩ [f_{n}(a)] ∩ [−b′] = ∅. Finally we obtain a good recursive monomorphism f = ⋃_{n} f_{n} : B → B, and part 1 is proved.

For part 2 we proceed as above, except that we use a back-and-forth argument involving splitting functions for both P and Q. The inductive hypothesis is that we have a good finite isomorphism f_{2n} : B_{2n} ≅ B′_{2n}, where B_{2n} and B′_{2n} are finite subalgebras of B. Let b be the nth element of B with respect to some fixed recursive enumeration of B. Let B_{2n+1} be the finite subalgebra of B generated by B_{2n} ∪ {b}. Use Lemma 3.15 and a splitting function for P to effectively extend f_{2n} to a good finite isomorphism f_{2n+1} : B_{2n+1} ≅ B′_{2n+1}. Then let B′_{2n+2} be the finite subalgebra of B generated by B′_{2n+1} ∪ {b}. Use Lemma 3.15 and a splitting function for Q to effectively extend f_{2n+1} to a good finite isomorphism f_{2n+2} : B_{2n+2} ≅ B′_{2n+2}. Finally we obtain a good recursive automorphism f = ⋃_{n} f_{n} : B → B, and part 2 is proved. □

Remark 3.17. The ideas used in the proofs of Lemmas 3.15 and 3.16 can be traced to Myhill [21], Smullyan [33], and Pour-El/Kripke [23].

Remark 3.18. Pour-El and Kripke [23] have obtained some interesting results concerning deduction-preserving isomorphisms of theories. In the Pour-El/Kripke terminology, some of our results in this section can be reformulated as follows. Let T, T′, T_{1}, T_{2} denote consistent, recursively axiomatized theories in the predicate calculus, or in the propositional calculus. Note that the Lindenbaum sentence algebras of such theories correspond precisely to nonempty Π_{1}^{0} subsets of 2^{ω}, via Stone duality. Let us say that T is effectively essentially incomplete if, given T′ extending T, we can effectively find a sentence σ in the language of T such that both T′ ∪ {σ} and T′ ∪ {¬σ} are consistent. Note that T is effectively essentially incomplete if and only if the nonempty Π_{1}^{0} subset of 2^{ω} corresponding to T is productive, in the sense of Definition 3.13. Thus by Lemma 3.16 we have: (1) If T_{2} is effectively essentially incomplete, then for all T_{1} there exists a deduction-preserving recursive monomorphism of T_{1} into T_{2}. (2) If T_{1} and T_{2} are effectively essentially incomplete, then there exists a deduction-preserving recursive isomorphism of T_{1} onto T_{2}. Pour-El/Kripke [23] obtain similar results under the stronger hypothesis that T_{2} is effectively inseparable. Our results (1) and (2) are best possible, in the sense that effective essential incompleteness is a necessary as well as sufficient condition for them to hold.

Lemma 3.19. Let P and Q be nonempty Π_{1}^{0} subsets of 2^{ω}. If P ≤_{M} Q and P is productive, then Q is productive.

Proof. Since P ≤_{M} Q, there is a recursive functional Φ : Q → P. By Lemma 3.11, let f : B → B be recursive such that Φ^{−1}[b] = [f(b)] ∩ Q for all b ∈ B. Let g : ω → B be a splitting function for P. The predicate S(e, X) ≡ (X ∈ Φ(P_{e} ∩ Q)) is Π_{1}^{0} (see the proof of part 1 of Lemma 3.6), so by the S-m-n Theorem, let h : ω → ω be primitive recursive such that P_{h(e)} = Φ(P_{e} ∩ Q) for all e. Now if P_{e} ⊆ Q and P_{e} ≠ ∅, we have P_{h(e)} = Φ(P_{e}) ⊆ P and P_{h(e)} ≠ ∅, hence P_{h(e)} ∩ [gh(e)] ≠ ∅ and P_{h(e)} ∩ [−gh(e)] ≠ ∅, hence P_{e} ∩ [fgh(e)] ≠ ∅ and P_{e} ∩ [−fgh(e)] ≠ ∅. Thus fgh : ω → B is a splitting function for Q. □

Lemma 3.20. Let P be a nonempty Π_{1}^{0} subset of 2^{ω}. P is productive if and only if P is Medvedev complete.

Proof. By Lemma 3.19, Medvedev completeness implies productiveness. By part 1 of Lemma 3.16, productiveness implies Medvedev completeness. □

Theorem 3.21. Let P and Q be nonempty Π_{1}^{0} subsets of 2^{ω}.

1. If P is Medvedev complete, then there exists a recursive functional from P onto Q.

2. If P and Q are Medvedev complete, then P and Q are recursively homeomorphic, i.e., there exists a recursive functional from P one-to-one onto Q.

Proof. This is immediate from Lemmas 3.16 and 3.20. □

Remark 3.22. Let P_{M} be the lattice of Medvedev degrees of nonempty Π_{1}^{0} subsets of 2^{ω}, as in Theorem 3.2. There are many obvious structural questions to ask about P_{M}. One may ask about embeddability, initial segments, final segments, definability, automorphisms, etc. There is reason to believe that a study of structural aspects of the distributive lattice P_{M} could be more rewarding than the ongoing study of the structural aspects of R_{T}, the upper semilattice of Turing degrees of recursively enumerable subsets of ω, as pursued for instance in Soare [34]. For one thing, there is a well known lack of natural examples of elements of R_{T}, but there are some interesting natural examples of elements of P_{M}. In particular, putting

DNR_{k} = {X ∈ k^{ω} : ∀n (X(n) ≠ {n}(n))},

Jockusch [16] has shown that

DNR_{2} >_{M} DNR_{3} >_{M} ⋯ >_{M} DNR_{k} >_{M} ⋯, 2 ≤ k ∈ ω,

and of course DNR_{2} is Medvedev complete (see the proof of Lemma 3.14). See also Simpson [29, 30] and other FOM postings in the same thread.

4 Relativization, Iteration, ω-Models

In this section we relativize and iterate the results of §3. Our construction is inspired by the idea of iterated forcing in set theory, as exposited in Jech [15, page 458] and Kunen [19, page 273]. We show that our construction gives rise to a Π_{1}^{0} set of countable ω-models of WKL_{0} with a strong homogeneity property (Theorem 4.11).

Definition 4.1. All of the concepts and results of §3 can be uniformly relativized (Rogers [25, pages 128–137]) to an arbitrary X ∈ 2^{ω}. Say that P^{X} ⊆ 2^{ω} is Π_{1}^{0,X} if P^{X} = {Y ∈ 2^{ω} : ∀n R(X, Y, n)} for some recursive predicate R ⊆ 2^{ω} × 2^{ω} × ω. We employ a uniform, standard, recursive enumeration {P_{e}^{X} : e ∈ ω} of the Π_{1}^{0,X} subsets of 2^{ω}. A nonempty Π_{1}^{0,X} set P^{X} ⊆ 2^{ω} is said to be X-productive if there exists an X-recursive splitting function, i.e., an X-recursive function g : ω → B such that for all e, if ∅ ≠ P_{e}^{X} ⊆ P^{X} then P_{e}^{X} ∩ [g(e)] ≠ ∅ ≠ P_{e}^{X} ∩ [−g(e)].

Recall that for Y ∈ 2^{ω} and e ∈ ω we have (Y)_{e} ∈ 2^{ω} where (Y)_{e}(n) = Y ((e, n)). (See the proofs of Theorem 3.2 and Lemma 3.3.) For Q ⊆ 2^{ω} put (Q)_{e} = {(Y)_{e} : Y ∈ Q}.

Lemma 4.2. There is a Π_{1}^{0} predicate P̂ ⊆ 2^{ω} × 2^{ω} such that

∀X ∀e (if P_{e}^{X} ≠ ∅ then P_{e}^{X} = (P̂^{X})_{e})

where P̂^{X} = {Y : P̂(X, Y)}.

Proof. This comes from a uniform relativization of the proof of Lemma 3.3. The predicate U(e, X, Z) ≡ (Z ∈ P_{e}^{X}) is Π_{1}^{0}, so by the Normal Form Theorem for Π_{1}^{0} predicates, let U_{1} ⊆ ω × 2^{<ω} × 2^{<ω} be primitive recursive such that U(e, X, Z) ≡ ∀n U_{1}(e, X[n], Z[n]). Put P̂(X, Y) ≡ ∀e U^{+}(e, X, (Y)_{e}), where U^{+}(e, X, Z) ≡

∀n (∀τ of length n) (if (∀m ≤ n) U_{1}(e, X[m], τ[m]) then U_{1}(e, X[n], Z[n])).

It is straightforward to verify that P̂ has the desired property. The details are as in the proof of Lemma 3.3. □

Lemma 4.3. With notation as in Lemma 4.2, for all X ∈ 2^{ω}, P̂^{X} is Xproductive with a fixed primitive recursive splitting function g : ω → B.

Proof. This comes from a uniform relativization of Lemmas 3.14 and 3.19. Let e_{0} ∈ ω be such that, for all X ∈ 2^{ω}, P_{e_{0}}^{X} = {Y ∈ 2^{ω} : ∀n (Y (n) ≠ {n}^{X}(n))}. The argument for Lemma 3.14 gives a primitive recursive function g_{0} : ω → B such that, for all X, P_{e_{0}}^{X} is X-productive with splitting function g_{0}. Note also that (Y)_{e_{0}} ∈ P_{e_{0}}^{X} for all Y ∈ P̂^{X}. Let f_{0} : B → B be primitive recursive such that, for all Y ∈ 2^{ω} and b ∈ B, Y ∈ [f_{0}(b)] if and only if (Y)_{e_{0}} ∈ [b]. Let h_{0} : ω → ω be primitive recursive such that, for all X ∈ 2^{ω} and all e ∈ ω, P_{h_{0}(e)}^{X} = {(Y)_{e_{0}} : Y ∈ P_{e}^{X}}. As in the proof of Lemma 3.19 we have that, for

all X ∈ 2^{ω}, P̂^{X} is X-productive with splitting function g = f_{0}g_{0}h_{0} : ω → B. □

Definition 4.4. Recall that (Y)_{i}(n) = Y ((i, n)). We also put

(Y)^{i}((j, n)) = \{ \begin{matrix}Y ((j, n)) & if j < i, \\ 0 & otherwise. \end{matrix}

(Compare the dependent choice notation of Simpson [31, Definition VII.6.1 and Lemmas VIII.2.5 and VIII.2.9].) From now on, fix P̂ as in Lemma 4.2, and put Q̂ = {Y ∈ 2^{ω} : ∀i P̂((Y)^{i}, (Y)_{i})}. Clearly Q̂ is a nonempty Π_{1}^{0} subset of 2^{ω}.

Lemma 4.5. For all Y ∈ Q̂ we have

{((Y)_{i})_{e} : i, e ∈ ω} = {X ∈ 2^{ω} : ∃i (X ≤_{T} (Y)^{i})}

and this is an ω-model of WKL_{0}.

Proof. If X ≤_{T} (Y)^{i} then clearly {X} = P_{e}^{(Y)^{i}} for an appropriate e, hence X = ((Y)_{i})_{e}. This gives {X : ∃i (X ≤_{T} (Y)^{i})} ⊆ {((Y)_{i})_{e} : i, e ∈ ω}. The converse inclusion follows from ((Y)_{i})_{e} ≤_{T} (Y)_{i} ≤_{T} (Y)^{i+1}. To see that this is an ω-model of WKL_{0}, use Lemma 4.2 plus the following characterization: S ⊆ 2^{ω} is an ω-model of WKL_{0} if and only if (i) S ≠ ∅, (ii) X ⊕ Y ∈ S for all X, Y ∈ S, and (iii) for all X ∈ S and e ∈ ω, if P_{e}^{X} ≠ ∅ then P_{e}^{X} ∩ S ≠ ∅. □

Definition 4.6. Let P and Q be nonempty Π_{1}^{0} subsets of 2^{ω}. Let Φ be a recursive functional from Q onto P. A splitting functional for Φ is a recursive functional g : P × ω → B such that for all X ∈ P, the X-recursive function e ↦ g^{X}(e) is a splitting function for the Π_{1}^{0,X} set Φ^{−1}(X) = {Y ∈ Q : Φ(Y) = X}. We say that Φ is productive if there exists a splitting functional for Φ.

Lemma 4.7. Let P_{1}, P_{2}, Q_{1}, Q_{2} be nonempty Π_{1}^{0} subsets of 2^{ω}. Suppose that Φ_{i} is a recursive functional from Q_{i} onto P_{i}, i = 1, 2. If P_{1} and P_{2} are recursively homeomorphic and Φ_{1} and Φ_{2} are productive, then Q_{1} and Q_{2} are recursively homeomorphic. Indeed, given a recursive homeomorphism Ψ : P_{1} ≅ P_{2} and splitting functionals for Φ_{1} and Φ_{2}, we can effectively find a recursive homeomorphism Ψ′ : Q_{1} ≅ Q_{2} such that Ψ ∘ Φ_{1} = Φ_{2} ∘ Ψ′.

Proof. This is a uniform relativization of part 2 of Lemma 3.16. □

Definition 4.8. For any i ∈ ω and any nonempty Π_{1}^{0} set Q ⊆ 2^{ω}, put (Q)_{i} = {(Y)_{i} : Y ∈ Q} and (Q)^{i} = {(Y)^{i} : Y ∈ Q}. Note that (Q)_{i} and (Q)^{i} are again nonempty Π_{1}^{0} subsets of 2^{ω}. In particular (Q)^{0} is a trivial Π_{1}^{0} set, namely (Q)^{0} = {Z_{0}} where Z_{0} ∈ 2^{ω} is defined by Z_{0}(n) = 0 for all n.

Lemma 4.9. Let P and Q be nonempty Π_{1}^{0} subsets of Q̂. Then there are a recursive homeomorphism Ψ : P ≅ Q and a recursive sequence of recursive homeomorphisms Ψ^{i} : (P)^{i} ≅ (Q)^{i}, i ∈ ω, such that Ψ^{i}((Y)^{i}) = (Ψ(Y))^{i} for all Y ∈ P.

Proof. By Lemma 4.3, the recursive functionals from (Q̂)^{i+1} onto (Q̂)^{i} given by (Y)^{i+1} ↦ (Y)^{i} are uniformly productive. Hence their restrictions, from (P)^{i+1} onto (P)^{i} and from (Q)^{i+1} onto (Q)^{i}, are uniformly productive. Begin with the trivial recursive homeomorphism Ψ^{0} : (P)^{0} ≅ (Q)^{0}. Repeatedly apply Lemma 4.7 to obtain a recursive sequence of recursive homeomorphisms Ψ^{1} : (P)^{1} ≅ (Q)^{1}, Ψ^{2} : (P)^{2} ≅ (Q)^{2}, …, Ψ^{i} : (P)^{i} ≅ (Q)^{i}, …, such that Ψ^{i}((Y)^{i}) = (Ψ^{i+1}((Y)^{i+1}))^{i} for all Y ∈ P. Finally Ψ : P ≅ Q is given by Ψ = lim_{i} Ψ^{i}. □

Lemma 4.10. Let P and Q be nonempty Π_{1}^{0} subsets of Q̂. Then there exists a recursive homeomorphism Ψ : P ≅ Q such that for all Y ∈ P and Z ∈ Q, if Ψ(Y) = Z then {((Y)_{i})_{e} : i, e ∈ ω} = {((Z)_{i})_{e} : i, e ∈ ω}.

Proof. Let Ψ : P ≅ Q be as in Lemma 4.9. Let Y ∈ P and Z ∈ Q be such that Ψ(Y) = Z. By Lemma 4.9 we have Ψ^{i}((Y)^{i}) = (Z)^{i}, hence (Y)^{i} ≡_{T} (Z)^{i} for all i, hence {X : ∃i (X ≤_{T} (Y)^{i})} = {X : ∃i (X ≤_{T} (Z)^{i})}. By Lemma 4.5 it follows that {((Y)_{i})_{e} : i, e ∈ ω} = {((Z)_{i})_{e} : i, e ∈ ω}. □

Theorem 4.11. There is a nonempty Π_{1}^{0} subset of 2^{ω}, Q̂′, with the following properties:

1. For all Y ∈ Q̂′, {(Y)_{m} : m ∈ ω} is an ω-model of WKL_{0}.

2. Any two nonempty Π_{1}^{0} subsets of Q̂′ are recursively homeomorphic.

3. For all nonempty Π_{1}^{0} sets P, Q ⊆ Q̂′, there is a recursive homeomorphism Ψ : P ≅ Q such that for all Y ∈ P and Z ∈ Q, if Ψ(Y) = Z then {(Y)_{m} : m ∈ ω} = {(Z)_{m} : m ∈ ω}.

Proof. This follows from Lemmas 4.5 and 4.10 if we let Q̂′ = {Y′ : Y ∈ Q̂}, where Y′(((i, e), n)) = Y ((i, (e, n))) for all i, e, n ∈ ω. (Note: Y′ is not the Turing jump of Y.) □

5 Jockusch/Soare Genericity

In this section we combine the previous theorem with so-called Jockusch/Soare forcing, to obtain an ω-model of WKL_{0} in which all definable elements are recursive (Theorem 5.11).

Definition 5.1. A relation R ⊆ ω^{k} is said to be arithmetical if it is first order definable over the standard model of arithmetic (ω, +, ·, 0, 1, <, =). We write REC = {A ∈ 2^{ω} : A is recursive}, and ARITH = {A ∈ 2^{ω} : A is arithmetical}.

Definition 5.2. Let P be the set of all nonempty Π_{1}^{0} subsets of 2^{ω}. D ⊆ P is said to be arithmetical if {e ∈ ω : P_{e} ∈ D} is arithmetical. D is said to be dense if for all P ∈ P there exists Q ∈ D such that Q ⊆ P. G ∈ 2^{ω} is said to meet D if there exists Q ∈ D such that G ∈ Q. G is said to be Jockusch/Soare generic (cf. Jockusch/Soare [17, proof of Theorem 2.4]), or simply, generic, if G meets every dense arithmetical D ⊆ P.

Lemma 5.3. Given P ∈ P, there exists G ∈ P such that G is generic.

Proof. Let D_{n}, n ∈ ω be an enumeration of the dense arithmetical subsets of P. Construct a sequence P_{0} ⊇ P_{1} ⊇ … P_{n} ⊇ … in P as follows. Begin with P_{0} = P. Given P_{n}, let P_{n+1} ⊆ P_{n} be such that P_{n+1} ∈ D_{n}. Finally let G be the unique element of ⋂_{n} P_{n}. Clearly G ∈ P and G meets each D_{n}, hence G is generic. □

Lemma 5.4. Let A_{i}, i ∈ ω be a sequence of nonrecursive elements of 2^{ω}. Given P ∈ P, there exists G ∈ P such that G is generic and ∀i (A_{i} ≰_{T} G).

Proof. For all Y ∈ 2^{ω} we have A_{i} ≤_{T} Y if and only if ∃e ∀n ({e}^{Y} (n) = A_{i}(n)). For e, i ∈ ω, put D_{e,i} = {Q ∈ P : ∃n (∀Y ∈ Q) ({e}^{Y} (n) ≠ A_{i}(n))}. We claim that D_{e,i} is dense in P. To see this, let P ∈ P be given. If ∀n (∀Y ∈ P) ({e}^{Y} (n) = A_{i}(n)), then by Lemma 3.5 A_{i} is recursive, contrary to assumption. So we have ∃n (∃Y ∈ P) ({e}^{Y} (n) ≠ A_{i}(n)). Fix such an n and put Q = {Y ∈ P : {e}^{Y} (n) ≠ A_{i}(n)}. Clearly Q ∈ P and Q ⊆ P and Q ∈ D_{e,i}. This proves our claim. Now let D_{n}, n ∈ ω be an enumeration of the dense arithmetical subsets of P. As in the proof of Lemma 5.3, given P ∈ P there exists G ∈ P such that G meets D_{n} for all n, and G meets D_{e,i} for all e, i. This proves our lemma. □

Lemma 5.5. Let G, H ∈ 2^{ω}. Suppose H ≤_{T} G and G is generic. Then H is generic, and H is truth-table reducible to G.

Proof. We are assuming H ≤_{T} G, so let e ∈ ω be such that ∀n (H(n) = {e}^{G}(n)). Put D′_{e} = {Q ∈ P : either ∃n (∀Y ∈ Q) ({e}^{Y} (n) is undefined) or ∀n (∀Y ∈ Q) ({e}^{Y} (n) is defined)}. We claim that D′_{e} is dense in P. To see this, given P ∈ P \ D′_{e}, we have ∃n (∃Y ∈ P) ({e}^{Y} (n) is undefined), so fix such an n and put Q = {Y ∈ P : {e}^{Y} (n) is undefined}. Then clearly Q ⊆ P and Q ∈ D′_{e}. This proves our claim. Since D′_{e} is dense arithmetical, let Q ∈ D′_{e} be such that G ∈ Q. It follows that ∀n (∀Y ∈ Q) ({e}^{Y} (n) is defined), so we have a recursive functional Φ : Q → 2^{ω} given by Φ(Y)(n) = {e}^{Y} (n), and H = Φ(G). Hence by Lemma 3.11 and Remark 3.12, H is truth-table reducible to G. To show that H is generic, let D ⊆ P be dense arithmetical. Put D^{∗} = {Q^{∗} ∈ P : Q^{∗} ∩ Q = ∅ or Φ(Q^{∗} ∩ Q) ∈ D}. By Lemma 3.6, D^{∗} is dense arithmetical. Let Q^{∗} ∈ D^{∗} be such that G ∈ Q^{∗}. Then G ∈ Q^{∗} ∩ Q, so H = Φ(G) ∈ Φ(Q^{∗} ∩ Q) ∈ D. This completes the proof. □

Definition 5.6. Let L_{1}(Y) be the language of first order arithmetic with an extra function symbol Y denoting an element of 2^{ω}, i.e., a function Y : ω → {0, 1}. Let φ(Y) be an L_{1}(Y)-sentence. Let P ∈ P. We say that P forces φ(Y) if φ(G) holds for all generic G such that G ∈ P.

Lemma 5.7.

1. Let φ(Y) be an L_{1}(Y)-sentence. If G is generic, then φ(G) holds if and only if there exists P ∈ P such that G ∈ P and P forces φ(Y).

2. Let φ(Y, n_{1}, …, n_{k}) be an L_{1}(Y)-formula with free variables n_{1}, …, n_{k}. Then

{(e, n_{1}, …, n_{k}) : P_{e} ∈ P and P_{e} forces φ(Y, n_{1}, …, n_{k})}

is arithmetical.

Proof. Parts 1 and 2 are proved together by a straightforward induction on the complexity of φ(Y). If φ(Y) is atomic, then for all P ∈ P we have that P forces φ(Y) if and only if φ(Y) holds for all Y ∈ P, because {Y ∈ P : φ(Y)} and {Y ∈ P : ¬ φ(Y)} are elements of P. For arbitrary φ(Y) and ψ(Y) of L_{1}(Y), we have that P ∈ P forces φ(Y) ∨ ψ(Y) if and only if (∀P′ ∈ P) (if P′ ⊆ P then (∃P′′ ∈ P) (P′′ ⊆ P′ and either P′′ forces φ(Y) or P′′ forces ψ(Y))). For arbitrary φ(Y, n) of L_{1}(Y), we have that P ∈ P forces ∃n φ(Y, n) if and only if (∀P′ ∈ P) (if P′ ⊆ P then (∃P′′ ∈ P) (∃n ∈ ω) (P′′ ⊆ P′ and P′′ forces φ(Y, n))). For arbitrary φ(Y) of L_{1}(Y), we have that P ∈ P forces φ(Y) if and only if (∀P′ ∈ P) (if P′ ⊆ P then P′ does not force φ(Y)). □

Lemma 5.8. Let L_{2} be the language of second order arithmetic. Given an L_{2}- sentence σ, we can find an L_{1}(Y)-sentence σ̃(Y) such that for all Y ∈ 2^{ω}, σ̃(Y) holds if and only if the ω-model {(Y)_{m} : m ∈ ω} satisfies σ.

Proof. The proof is straightforward. Set quantifiers in σ are translated as number quantifiers in σ̃(Y). □

Lemma 5.9. With Q̂′ as in Theorem 4.11, let G, H ∈ Q̂′ be generic. Then the ω-models {(G)_{m} : m ∈ ω} and {(H)_{m} : m ∈ ω} satisfy the same L_{2}-sentences.

Proof. Suppose {(G)_{m} : m ∈ ω} and {(H)_{m} : m ∈ ω} satisfy σ and ¬ σ respectively. Then σ̃(G) and ¬ σ̃(H) hold. By part 1 of Lemma 5.7, there exist P, Q ∈ P such that G ∈ P and H ∈ Q and P forces σ̃(Y) and Q forces ¬ σ̃(Y). Since G, H ∈ Q̂′, we may safely assume that P, Q ⊆ Q̂′. Let Ψ : P ≅ Q be a recursive homeomorphism as in part 3 of Theorem 4.11. By Lemma 5.5 we have that G^{∗} = Ψ(G) ∈ Q is generic. Since Q forces ¬ σ̃(Y), it follows that ¬ σ̃(G^{∗}) holds, i.e., {(G^{∗})_{m} : m ∈ ω} ⊧ ¬ σ. But, by part 3 of Theorem 4.11, we have that {(G)_{m} : m ∈ ω} = {(G^{∗})_{m} : m ∈ ω}. This contradiction proves our lemma. □

Lemma 5.10. Consider an ω-model S = {(G)_{m} : m ∈ ω} where G ∈ Q̂′ and G is generic.

1. For L_{2}-sentences σ, we have that S ⊧ σ if and only if Q̂′ forces σ̃(Y).

2. For relations R ⊆ ω^{k}, we have that R is definable over S without parameters if and only if R is arithmetical.

3. For A ∈ S, we have that A is definable over S (without parameters) if and only if A is recursive.

Proof. Parts 1 and 2 are immediate from Lemmas 5.7 and 5.9. For part 3, suppose that A ∈ S and A is definable without parameters over S. Let φ(Z) be an L_{2}-formula with one free set variable, Z, such that A is the unique Z ∈ S such that S ⊧ φ(Z). Letting σ be the L_{2}-sentence (∃ unique Z) φ(Z), we have that S ⊧ σ. By part 1 we have that Q̂′ forces σ̃(Y). By Lemma 5.4, let H ∈ Q̂′ be generic such that (∀Z ∈ S) (if Z ∉ REC then Z ≰_{T} H). Consider the ωmodel T = {(H)_{m} : m ∈ ω}. Then S ∩ T = REC. Since H ∈ Q̂′ and H is generic and Q̂′ forces σ̃(Y), we have that σ̃(H) holds, i.e., T ⊧ σ. Let B be the unique Z ∈ T such that T ⊧ φ(Z). We claim that A = B. This is clear from Lemma 5.9, because for all n ∈ ω and k = 0, 1, we have A(n) = k if and only if S ⊧ ∃Z (φ(Z) and Z(n) = k), if and only if T ⊧ ∃Z (φ(Z) and Z(n) = k), if and only if B(n) = k. Since A = B, it follows that A ∈ REC. □

Theorem 5.11. There is a countable ω-model S of WKL_{0} such that every definable element of S is recursive.

Proof. This follows immediately from Theorem 4.11 and Lemma 5.3 and part 3 of Lemma 5.10. □

Remark 5.12. Theorem 5.11 is due to Friedman [11, unpublished, Theorem 1.10], announced in [12, Theorem 1.6]. Our proof here is different from Friedman’s proof in [11].

6 Relative Genericity and Definability

In this section we prove a key lemma concerning relativized Jockusch/Soare genericity (Lemma 6.2). We then use our lemma to obtain an improvement of Theorem 5.11, involving relative definability and relative recursiveness, i.e., Turing reducibility (Theorem 6.9).

Definition 6.1. All of the concepts and results of §5 can be straightforwardly relativized to an arbitrary X ∈ 2^{ω}. We use P^{X} to denote the set of nonempty Π_{1}^{0,X} subsets of 2^{ω}. (See Definition 4.1.) D^{X} ⊆ P^{X} is said to be arithmetical in X if {e : P_{e}^{X} ∈ D^{X}} is arithmetical in X, i.e., definable over (ω, +, ·, 0, 1, <, =, X) by a formula of L_{1}(X). G ∈ 2^{ω} is said to be Jockusch/Soare generic over X, or simply, generic over X, if G meets every dense subset of P^{X} which is arithmetical in X.

Lemma 6.2. Let G, X ∈ 2^{ω}. Suppose X ≤_{T} G and G is generic. Then G is generic over X.

Proof. Let D^{X} ⊆ P^{X} be given such that D^{X} is dense in P^{X} and arithmetical in X. We need to show that G meets D^{X}. By Lemma 5.5, there are a Π_{1}^{0} set Q ⊆ 2^{ω} and a recursive functional Φ : Q → 2^{ω} such that Φ(G) = X. It suffices to show that Q forces (if D^{Φ(Y)} is dense in P^{Φ(Y)} then Y meets D^{Φ(Y)}). Equivalently, we shall show (∀Q′ ∈ P) (if Q′ ⊆ Q and Q′ forces (D^{Φ(Y)} is dense in P^{Φ(Y)}), then (∃Q′′ ∈ P) (Q′′ ⊆ Q′ and Q′′ forces (Y meets D^{Φ(Y)}))). To see this, let Q′ ∈ P be given such that Q′ ⊆ Q and Q′ forces (D^{Φ(Y)} is dense in P^{Φ(Y)}). Put P′ = Φ(Q′). Using L_{1}(X) as our forcing language, we have that P′ forces (D^{X} is dense in P^{X}). In particular, since P′ forces Q′ ∩ Φ^{−1}(X) ∈ P^{X}, it follows that P′ forces ∃e (P_{e}^{X} ∈ D^{X} and P_{e}^{X} ⊆ Q′ ∩ Φ^{−1}(X)). Let e ∈ ω and P′′ ∈ P be such that P′′ ⊆ P′ and P′′ forces (P_{e}^{X} ∈ D^{X} and P_{e}^{X} ⊆ Q′ ∩ Φ^{−1}(X)). Put Q′′ = {Y ∈ Q′ : Φ(Y) ∈ P′′ and Y ∈ P_{e}^{Φ(Y)}}. Then Q′′ ∈ P, Q′′ ⊆ Q′, and Q′′ forces (Y ∈ P_{e}^{Φ(Y)} and P_{e}^{Φ(Y)} ∈ D^{Φ(Y)}), i.e., Q′′ forces (Y meets D^{Φ(Y)}). This proves our lemma. □

Lemma 6.3. Let X ∈ 2^{ω} be given. Suppose P^{X}, Q^{X} ∈ P^{X}, and suppose Φ^{X} : P^{X} ≅ Q^{X} is an X-recursive homeomorphism of P^{X} onto Q^{X}. If G ∈ P^{X} is generic over X, then Φ^{X}(G) ∈ Q^{X} is generic over X.

Proof. This follows from a straightforward relativization to X of Lemma 5.5. □

Definition 6.4. Let P̂ be as in Lemma 4.2. Relativizing Definition 4.4, put

Q̂^{X} = {Y ∈ 2^{ω} : ∀i P̂(X ⊕ (Y)^{i}, (Y)_{i})}

for all X ∈ 2^{ω}. Clearly Q̂^{X} ∈ P^{X}.

Lemma 6.5. Let X ∈ 2^{ω} be given. For all Y ∈ Q̂^{X} we have

{((Y)_{i})_{e} : i, e ∈ ω} = {W ∈ 2^{ω} : ∃i (W ≤_{T} (Y)^{i})}

and this is an ω-model of WKL_{0} containing X.

Proof. A straightforward relativization to X of Lemma 4.5 shows that, for all Y ∈ Q̂^{X}, {((Y)_{i})_{e} : i, e ∈ ω} = {W ∈ 2^{ω} : W ≤_{T} (Y)^{i}} and this is an ω-model of WKL_{0}. Clearly {X} is Π_{1}^{0,X}, hence {X} = P_{e}^{X⊕(Y)^{0}} for an appropriate e, hence X = ((Y)_{1})_{e}. □

Lemma 6.6. Consider an ω-model S = {((G)_{i})_{e} : i, e ∈ ω} where G ∈ Q̂ and G is generic. For all A ∈ S, if A is definable over S, then A is recursive.

Proof. The proof of Theorem 4.11 shows that Q̂ ≅ Q̂′ via a recursive homeomorphism Y ↦ Y′ such that, for all Y ∈ Q̂, {((Y)_{i})_{e} : i, e ∈ ω} = {(Y′)_{m} : m ∈ ω}. In particular, S = {(G′)_{m} : m ∈ ω} where G′ ∈ Q̂′. Furthermore, by Lemma 5.5, G′ is generic. Part 3 of Lemma 5.10 now gives the desired conclusion. □

Lemma 6.7. Let X ∈ 2^{ω} be given. Consider an ω-model S = {((G)_{i})_{e} : i, e ∈ ω} where G ∈ Q̂^{X} and G is generic over X. For all A ∈ S, if A is definable over S from X, then A ≤_{T} X.

Proof. This is a straightforward relativization to X of Lemma 6.6. □

Lemma 6.8. Let X ∈ 2^{ω} and i^{∗}, e^{∗} ∈ ω be given. Put

Q̂_{∗}^{X} = {Y ∈ Q̂ : ((Y)_{i^{∗}})_{e^{∗}} = X}.

If Q̂_{∗}^{X} is nonempty, then there exists an X-recursive homeomorphism Ψ_{∗}^{X} : Q̂_{∗}^{X} ≅ Q̂^{X} such that for all Y ∈ Q̂_{∗}^{X}, putting Y_{∗} = Ψ_{∗}^{X}(Y), we have {((Y)_{i})_{e} : i, e ∈ ω} = {((Y_{∗})_{i})_{e} : i, e ∈ ω}.

Proof. As in the proof of Lemma 4.9, construct a recursive sequence of Xrecursive homeomorphisms Ψ_{∗}^{X,i} : (Q̂_{∗}^{X})^{i^{∗}+i+2} ≅ (Q̂^{X})^{i+1}, i ∈ ω, such that Ψ_{∗}^{X,i}((Y)^{i^{∗}+i+2}) = (Ψ_{∗}^{X,i+1}((Y)^{i^{∗}+i+3}))^{i+1} for all Y ∈ Q̂_{∗}^{X}. Define Ψ_{∗}^{X} = lim_{i} Ψ_{∗}^{X,i}. Then Ψ_{∗}^{X} : Q̂_{∗}^{X} ≅ Q̂^{X} is an X-recursive homeomorphism. Furthermore, for Y ∈ Q̂_{∗}^{X} and Y_{∗} = Ψ_{∗}^{X}(Y), we have (Y)^{i^{∗}+i+2} ≡_{T} (Y_{∗})^{i+1} for all i ∈ ω. Hence {W : ∃i (W ≤_{T} (Y)^{i})} = {W : ∃i (W ≤_{T} (Y_{∗})^{i})}. By Lemmas 4.5 and 6.5, it follows that {((Y)_{i})_{e} : i, e ∈ ω} = {((Y_{∗})_{i})_{e} : i, e ∈ ω}. □

Theorem 6.9. There is a countable ω-model of WKL_{0} satisfying ∀X ∀Z (if Z is definable from X then Z ≤_{T} X).

Proof. Let G ∈ Q̂ be generic, and put S = {((G)_{i})_{e} : i, e ∈ ω}. By Lemma 4.5, S is an ω-model of WKL_{0}. Fix X ∈ S. Fix i^{∗}, e^{∗} ∈ ω such that X = ((G)_{i^{∗}})_{e^{∗}}. As in Lemma 6.8, put Q̂_{∗}^{X} = {Y ∈ Q̂ : ((Y)_{i^{∗}})_{e^{∗}} = X}, and let Ψ_{∗}^{X} be an X-recursive homeomorphism of Q̂_{∗}^{X} onto Q̂^{X}. We have G ∈ Q̂_{∗}^{X}. Put G_{∗} = Ψ_{∗}^{X}(G) ∈ Q̂^{X}. By Lemma 6.8, S = {((G_{∗})_{i})_{e} : i, e ∈ ω}. By Lemma 6.2, G is generic over X. Hence, by Lemma 6.3, G_{∗} is generic over X. It follows by Lemma 6.7 that, for all A ∈ S, if A is definable over S from X, then A ≤_{T} X. This completes the proof. □

Remark 6.10. Our Theorem 6.9 above contradicts Friedman’s Theorem 1.12 of [11, unpublished].

7 Generalization to Non-ω-Models

In this section we generalize the results of §§3,4,5,6 to countable non-ω-models of WKL_{0}.

As in [31, Remark I.7.6], let Σ_{1}^{0}-PA be first order Peano arithmetic with the induction scheme restricted to Σ_{1}^{0} formulas. The following theorem is well known.

Theorem 7.1. Let N = (|N|, +_{N}, ·_{N}, 0_{N}, 1_{N}, <_{N}, =_{N}) be a countable model of Σ_{1}^{0}-PA. Then there exists a countable S ⊆ P (|N|) such that (N, S) ⊧ WKL_{0}.

Proof. This result is originally due to Harrington (1977, unpublished). The proof is in Simpson [31, §IX.2]. □

Thus any countable model of Σ_{1}^{0}-PA is the first order part of a countable model of WKL_{0}. It follows by the Gödel Completeness Theorem that Σ_{1}^{0}-PA is the first order part of WKL_{0}. (See Simpson [31, §IX.2].) We shall strengthen these results below (Theorems 7.6 and 7.8, Corollary 7.9).

Let N be a countable model of Σ_{1}^{0}-PA. It is well known that the familiar concepts and results of classical recursion theory can be generalized to N-recursion theory. See for instance Mytilinaios [22]. Let Δ_{1}^{0}-Def(N) be the set of all A ⊆ |N| such that A is Δ_{1}^{0} definable over N, i.e., both Σ_{1}^{0} and Π_{1}^{0} definable over N allowing parameters from |N|. We describe sets A ∈ Δ_{1}^{0}-Def(N) as being Nrecursive. It is known from Simpson [31, §IX.1] that Δ_{1}^{0}-Def(N) is the smallest S ⊆ P (|N|) such that (N, S) ⊧ RCA_{0}. Thus Δ_{1}^{0}-Def(N) in N-recursion theory plays the role of REC in classical recursion theory.

A set F ⊆ |N| is said to be N-finite if it is N-recursive and bounded in N, or equivalently, if there exists an N-canonical index of F. By an N-canonical index of F, we mean an n ∈ |N| such that F = F_{n} = {m ∈ |N| : N ⊧ mEn}, where mEn is the usual Σ_{0}^{0} formula asserting that 2^{m} occurs in the binary expansion of n, i.e., (∃x < n) (∃y < 2^{m}) (n = (2x + 1)2^{m} + y). Compare Rogers [25, §5.6]. The N-finite sets play the role of finite sets in classical recursion theory. A set A ⊆ |N| is said to be N-regular if A ∩ F is N-finite for each N-finite F ⊆ |N|. By Bounded Σ_{1}^{0} Comprehension [31, Theorem II.3.9], every N-recursively enumerable set is N-regular. In this paper we shall have no use for sets which are not N-regular. If S ⊆ P (|N|) is such that (N, S) ⊧ RCA_{0}, then every A ∈ S is necessarily N-regular.

We denote by (2^{ω})_{N} the set of all N-regular functions X : |N| → {0, 1}. We denote by (2^{<ω})_{N} the set of N-strings, i.e., (N-canonical indices of) Nfinite sequences of 0’s and 1’s. Clearly (2^{<ω})_{N} and the length function lh_{N} : (2^{<ω})_{N} → |N| are N-recursive. For X ∈ (2^{ω})_{N} and n ∈ |N|, we have an Nstring X[n] = ⟨X(0), …, X(n−1)⟩ ∈ (2^{<ω})_{N} of length n. We denote by P_{N} the set of nonempty sets of the form {X ∈ (2^{ω})_{N} : (∀n ∈ |N|) (X[n] ∈ T)} where T ⊆ (2^{<ω})_{N} is N-recursive. The sets P ∈ P_{N} in N-recursion theory play the role of nonempty Π_{1}^{0} subsets of 2^{ω} in classical recursion theory.

We say that P ∈ P_{N} is complete if for every Q ∈ P_{N} there exists an Nrecursive functional Φ : P → Q. Generalizing Theorem 3.21, we have:

Theorem 7.2. Let N be a countable model of Σ_{1}^{0}-PA, and let P, Q ∈ P_{N}. If P is complete, there exists an N-recursive functional from P onto Q. If P and Q are complete, there exists an N-recursive functional Φ : P ≅ Q.

Proof. This is a straightforward generalization of the arguments of §3. □

Generalizing Theorem 4.11, we have:

Theorem 7.3. Let N be a countable model of Σ_{1}^{0}-PA. We can find (Q̂′)_{N} ∈ P_{N} with the following properties:

1. For all Y ∈ (Q̂′)_{N}, if (N, {(Y)_{n} : n ∈ |N|}) ⊧ RCA_{0} then (N, {(Y)_{n} : n ∈ |N|}) ⊧ WKL_{0}.

2. For all P, Q ∈ P_{N} such that P, Q ⊆ (Q̂′)_{N}, there exists an N-recursive functional Ψ : P ≅ Q such that for all Y ∈ P and Z ∈ Q, if Ψ(Y) = Z then {(Y)_{n} : n ∈ |N|} = {(Z)_{n} : n ∈ |N|}.

Proof. This is a straightforward generalization of the arguments of §4. □

For G ∈ (2^{ω})_{N} the notion of Jockusch/Soare genericity over N is defined in the obvious way, in terms of dense subsets of P_{N} which are definable over N allowing parameters from |N|. This notion is equivalent to genericity over (N, Δ_{1}^{0}-Def(N)) in the sense of Simpson [31, §IX.2]. Generalizing Lemma 5.3, we have:

Lemma 7.4. Let N be a countable model of Σ_{1}^{0}-PA. For any P ∈ P_{N} there exists G ∈ P such that G is Jockusch/Soare generic over N. For any such G we have (N, Δ_{1}^{0}-Def(N, G)) ⊧ RCA_{0}.

Proof. See Simpson [31, §IX.2]. □

Generalizing Lemma 5.4, we have:

Lemma 7.5. Let N be a countable model of Σ_{1}^{0}-PA, and suppose

{A_{i} : i ∈ ω} ∩ Δ_{1}^{0}-Def(N) = ∅.

Then for any P ∈ P_{N} there exists G ∈ P such that

{A_{i} : i ∈ ω} ∩ Δ_{1}^{0}-Def(N, G) = ∅,

and G is Jockusch/Soare generic over N.

Proof. Combine the proof of Lemma 7.4 with a straightforward generalization of the proof of Lemma 5.4. □

Generalizing Theorem 5.11, we have:

Theorem 7.6. Let N be a countable model of Σ_{1}^{0}-PA. Then there exists a countable S ⊆ P (|N|) such that (N, S) ⊧ WKL_{0} and furthermore, every element of S which is definable over (N, S) allowing parameters from |N| is N-recursive.

Proof. This is a straightforward generalization of the arguments of §5. □

Remark 7.7. Theorems 7.2, 7.3 and 7.6 and Lemma 7.5 are originally due to Simpson/Tanaka/Yamazaki [32].

Generalizing Theorem 6.9, we have:

Theorem 7.8. Let N be a countable model of Σ_{1}^{0}-PA. Then there exists a countable S ⊆ P (|N|) such that (N, S) ⊧ WKL_{0} and furthermore, for all X, Z ∈ S, if Z is definable over (N, S) allowing parameters from |N| ∪ {X}, then Z ∈ Δ_{1}^{0}-Def(N, X).

Proof. This is a straightforward generalization of the arguments of §6. □

Corollary 7.9. Σ_{1}^{0}-PA is the first order part of the L_{2}-theory consisting of WKL_{0} plus the following scheme:

∀X (if (∃ exactly one Z) φ(X, Z) then (∃Z) (Z ≤_{T} X and φ(X, Z))),

where φ(X, Z) is any L_{2}-formula with no free set variables other than X, Z.

Proof. This follows from Theorem 7.8 plus Gödel’s Completeness Theorem. □

8 A Result of Kučera

In this section we present a simplified proof of a recursion-theoretic result of Kučera [20]. Our proof is based on two easy, well-known lemmas. We present the proof in detail now, because later we shall need to generalize it to the context of N-recursion theory where N is a model of Σ_{1}^{0}-PA.

Lemma 8.1. There exists a recursively enumerable set A ⊆ ω such that the complement \overline{A} is infinite and, for all x, if \{x\}(x) ↓ then \{x\}_{a_{x}}(x) ↓, where

\overline{A} = \{a_{0} < a_{1} < ⋯ < a_{x} < ⋯\} .

Proof. We use a movable marker argument, as in Rogers [25, pages 235–236]. We shall have a_{x} = lim_{s} a_{x}^{s} where a_{x}^{s} is the position of marker x at stage s. Thus

\overline{A^{s}} = \{a_{0}^{s} < a_{1}^{s} < ⋯ < a_{x}^{s} < ⋯\} .

Stage 0. Begin by defining a_{x}^{0} = x for all x. In other words, A^{0} = ∅.

Stage s + 1. Let x_{s} be the least x such that {x}_{s}(x) ↓ and {x}_{a_{x}^{s}}(x) ↑. If x_{s} is undefined, let A^{s+1} = A^{s}. Thus a_{x}^{s+1} = a_{x}^{s} for all x. If x_{s} is defined, let A^{s+1} = A^{s} ∪ {a_{x}^{s}, …, a_{s−1}^{s}}. Thus

a_{x}^{s+1} = \{ \begin{matrix}a_{x}^{s} & if x < x_{s}, \\ a_{s+x−x_{s}}^{s} & if x ≥ x_{s}. \end{matrix}

and in particular a_{x_{s}}^{s+1} = a_{s}^{s} ≥ s.

Finally put A = ⋃_{s} A^{s}. Clearly A is a recursively enumerable set. Note that x_{s} takes on each possible value at most once. Hence x_{s} → ∞ as s → ∞, and it is clear that the construction works. □

The following lemma is a strengthening due to K. Ohashi of the well-known Splitting Theorem of R. Friedberg. See Rogers [25, Exercise 12.21].

Lemma 8.2. Let A be a nonrecursive, recursively enumerable set. Then there exists a pair of disjoint, recursively inseparable, recursively enumerable sets B_{1}, B_{2} such that A = B_{1} ∪ B_{2}.

Proof. Let f : ω → ω be a one-to-one recursive function such that A is the range of f. Put A^{s} = {f(0), …, f(s)}. Let W_{x} (x ∈ ω) be a standard, recursive enumeration of the recursively enumerable sets. Let W_{x}^{s} be the finite set of elements enumerated into W_{x} prior to stage s + 1.

To construct B_{1}, B_{2} we use a no-injury priority argument. For each i = 1, 2 and x = 0, 1, 2, … there is a requirement R_{2x+i} to the effect that B_{i} ∩ W_{x} ≠ ∅ “if possible”. The ordering of the requirements is R_{1}, R_{2}, …, R_{2x+1}, R_{2x+2}, . . ..

Stage 0. Put B_{1}^{0} = B_{2}^{0} = ∅.

Stage s+1. Let x_{s} be the least x such that f(s) ∈ W_{x}^{s} and either B_{1}^{s}∩W_{x}^{s} = ∅ or B_{2}^{s} ∩ W_{x}^{s} = ∅. If x_{s} does not exist, or if B_{1}^{s} ∩ W_{x}^{s} = ∅, put f(s) into B_{1}, i.e., B_{1}^{s+1} = B_{1}^{s} ∪ {f(s)} and B_{2}^{s+1} = B_{2}^{s}. Otherwise put f(s) into B_{2}, i.e., B_{1}^{s+1} = B_{1}^{s} and B_{2}^{s+1} = B_{2}^{s} ∪ {f(s)}.

Finally put B_{1} = ⋃_{s} B_{1}^{s} and B_{2} = ⋃_{s} B_{2}^{s}. Clearly B_{1} and B_{2} are recursively enumerable sets, and A = B_{1} ∪B_{2}. It is also clear that x_{s} takes on each possible value at most twice, hence x_{s} → ∞ as s → ∞.

We claim that B_{1} and B_{2} are recursively inseparable. Assume for a contradiction that X is a recursive set which separates B_{1} and B_{2}, i.e., B_{1} ⊆ X and B_{2} ∩ X = ∅. Let x and y be such that W_{x} = X and W_{y} = \overline{X}. Then W_{x} ∩ B_{2} = ∅ and W_{y} ∩ B_{1} = ∅. For all sufficiently large s we have x_{s} > x, y, hence f(s) ∉ W_{x}^{s} ∪ W_{y}^{s}. Thus there is a finite set F such that for all a ∈ A \ F there exists s such that a ∈ A^{s} \ (W_{x}^{s} ∪ W_{y}^{s}). On the other hand, we also have that for all a ∈ \overline{A} there exists s such that a ∈ (W_{x}^{s} ∪ W_{y}^{s}) \ A^{s}. It follows that A is recursive, a contradiction. □

The following theorem and its corollaries are due to Kučera [20].

Theorem 8.3. There exists a disjoint, recursively inseparable pair of recursively enumerable sets B_{1}, B_{2} with the following property. If X and Y are separating sets, then for the symmetric difference X △ Y = (X \ Y) ∪ (Y \ X) we have that either X △ Y is finite or K ≤_{T} X △ Y. Here K = {x : {x}(x) ↓}, the complete recursively enumerable set.

Proof. Let A be a recursively enumerable set as in Lemma 8.1. Then clearly K ≤_{T} Z for any infinite set Z ⊆ \overline{A}. By Lemma 8.2 let B_{1}, B_{2} be a disjoint, recursively inseparable pair of recursively enumerable sets such that A = B_{1} ∪ B_{2}. Now let X and Y be separating sets. Then B_{1} ⊆ X∩Y and B_{2}∩(X∪Y) = ∅. Hence X △ Y ⊆ \overline{A} and we have our result. □

The previous theorem is of interest with respect to Π_{1}^{0} subsets of 2^{ω}. An extensive survey of this part of recursion theory is Cenzer/Remmel [3]. It is known that a nonempty Π_{1}^{0} subset of 2^{ω} with no recursive elements necessarily has elements of 2^{ℵ_{0}} distinct Turing degrees, among which are infinitely many pairwise incomparable Turing degrees < 0′. We now get:

Corollary 8.4. There exists a nonempty Π_{1}^{0} set P ⊆ 2^{ω} with no recursive elements, such that if a and b are Turing degrees of elements of P, then either a = b or a ∪ b ≥ 0′.

Proof. Let B_{1}, B_{2} be as in Theorem 8.3. Let P be the Π_{1}^{0} set of (characteristic functions of) separating sets for B_{1}, B_{2}. If a and b are the Turing degrees of X, Y ∈ P respectively, it follows from the conclusion of Theorem 8.3 that either a = b or a ∪ b ≥ 0′. □

If a is a Turing degree, we write a ≫ 0 to mean that every nonempty Π_{1}^{0} subset of 2^{ω} contains at least one element of Turing degree ≤ a. This is equivalent to a being the degree of a complete extension of Peano arithmetic. See also Jockusch/Soare [17] and Simpson [28, §6]. It is known that there exist a ≫ 0 and b ≫ 0 such that a ∩ b = 0. We now get:

Corollary 8.5. If a ≫ 0 and b ≫ 0 and a ∩ b = 0, then a ∪ b ≥ 0′.

9 An Application to ω-Models

In this section we apply Kučera’s result to the study of ω-models of WKL_{0}. For background on this subject, see Simpson [31, §VIII.2].

It is known that minimal ω-models of WKL_{0} do not exist, i.e., every ωmodel of WKL_{0} has a proper ω-submodel of WKL_{0}. It is also known that the intersection of all ω-models of WKL_{0} is REC, the set of recursive sets. We now have:

Theorem 9.1. There exists a countable ω-model S of WKL_{0} such that

⋂{S′ ⊆ S : S′ is an ω-model of WKL_{0}} ≠ REC.

Here REC is the set of recursive sets.

Proof. Let B_{1}, B_{2} be as in Theorem 8.3. Since WKL_{0} proves Σ_{1}^{0} separation [31, Lemma IV.4.4], every ω-model of WKL_{0} contains a separating set for B_{1}, B_{2}. Let S be an ω-model of WKL_{0} such that K ∉ S, where K is the complete recursively enumerable set. Let X ∈ S be a separating set for B_{1}, B_{2}. Obviously X is not recursive. We claim that X ∈ ⋂{S′ ⊆ S : S′ ⊧ WKL_{0}}. Given S′ ⊆ S such that S′ ⊧ WKL_{0}, let Y ∈ S′ be a separating set for B_{1}, B_{2}. Since X, Y ∈ S but K ∉ S, the conclusion of Theorem 8.3 implies that the symmetric difference X △ Y is finite. Since Y ∈ S′, it follows that X ∈ S′. This gives our result. □

Remark 9.2. For any ω-model S of WKL_{0}, it can be shown that ⋂{S′ ⊆ S : S′ is an ω-model of WKL_{0}} = REC if and only if K ∈ S.

The above theorem concerning ω-models of WKL_{0} is in contrast to the following theorem of Simpson [31, Corollary VIII.6.10] concerning β-models of ATR_{0}. This is one instance where the well-known analogy [31, pages 40 and 314] between ω-models of WKL_{0} and β-models of ATR_{0} breaks down.

Theorem 9.3. If S is a β-model of ATR_{0}, then

⋂{S′ ⊆ S : S′ is a β-model of ATR_{0}} = HYP.

Here HYP is the set of hyperarithmetical sets.

Actually Simpson [31, Corollary VIII.6.10] obtains not only Theorem 9.3 for β-models of ATR_{0}, but also an appropriate generalization for arbitrary models of ATR_{0}.

10 Applications to Non-ω-Models

In this section we generalize Kučera’s result and apply the generalization to the study of non-ω-models of WKL_{0}. For background on non-ω-models of WKL_{0}, see Simpson [31, §VIII.2].

Lemma 10.1. There exists a Σ_{1}^{0} formula φ(n, i) with the following properties. Let ψ(X) be the Π_{1}^{0} formula ∀n ((φ(n, 1) → n ∈ X) ∧ (φ(n, 0) → n ∉ X)). Then

1. WKL_{0} proves ∃X ψ(X).

2. RCA_{0} proves ∀X (ψ(X) → X is not recursive).

3. RCA_{0} proves ∀X ∀Y ((ψ(X)∧ψ(Y)) → (X △Y is finite or K ≤_{T} X △Y)).

Here K is the complete recursively enumerable set.

Proof. This follows from a straightforward formalization of our proof of Theorem 8.3 via Lemmas 8.1 and 8.2 above, with φ(n, i) ≡ (n ∈ B_{1} ∧ i = 1) ∨ (n ∈ B_{2} ∧ i = 0). The key point for the success of the priority argument for Lemma 8.2 is that x_{s} → ∞ as s → ∞. This is provable in RCA_{0} because of Bounded Σ_{1}^{0} Comprehension [31, Theorem II.3.9]. □

Remark 10.2. For applications of Bounded Σ_{1}^{0} Comprehension in formalization of more sophisticated priority arguments, see Mytilinaios [22].

Theorem 10.3. Let (N, S) be a model of WKL_{0} + “K does not exist”. Then with the Π_{1}^{0} formula ψ(X) of Lemma 10.1, we have that (N, S) satisfies

1. ∃X ψ(X)

2. ∀X (ψ(X) → X is not recursive)

3. ∀X ∀Y ((ψ(X) ∧ ψ(Y)) → X △ Y is finite).

Furthermore, ⋂{S′ ⊆ S : (N, S′) ⊧ WKL_{0}} ≠ Δ_{1}^{0}-Def(N).

Proof. That (N, S) satisfies 1, 2, 3 is immediate from Lemma 10.1. Let X ∈ S be such that (N, S) ⊧ ψ(X). Then X ∉ Δ_{1}^{0}-Def(N), but for every S′ ⊆ S such that (N, S′) ⊧ WKL_{0} we have X ∈ S′. See also Theorem 9.1 and its proof. □

Remark 10.4. Friedman [12, Theorem 1.7] states the following result: If φ(X) is an arithmetical formula and WKL proves ∃X (φ(X)∧X is not recursive), then WKL proves ∀X ∃Y (φ(Y) ∧ Y is not recursive ∧ ∀n (Y ≠ (X)_{n})). But this is refuted by our Theorem 10.3, taking φ(X) to be the Π_{1}^{0} formula ψ(X).

As in §7, let Σ_{1}^{0}-PA be first order Peano arithmetic with the induction scheme restricted to Σ_{1}^{0} formulas. For k ≥ 1 we define Σ_{k}^{0}-PA similarly, with the induction scheme restricted to Σ_{k}^{0} formulas.

Corollary 10.5. Any countable model of Σ_{1}^{0}-PA is the first order part of a countable model of WKL_{0} with the properties mentioned in Theorem 10.3.

Proof. Let N be a countable model of Σ_{1}^{0}-PA. By [31, Exercise IX.2.8], there exists a countable S ⊆ P (|N|) such that (N, S) is a model of WKL_{0} + “K does not exist”. Our result now follows from Theorem 10.3. □

Corollary 10.6. Let N be a model of Σ_{1}^{0}-PA which is not a model of Σ_{2}^{0}-PA. Then any model of WKL_{0} having N as its first order part has the properties mentioned in Theorem 10.3.

Proof. Any model of WKL_{0} having N as its first order part is of the form (N, S) where S ⊆ P (|N|). We claim that (N, S) necessarily satisfies “K does not exist”. Otherwise, let K ∈ S be such that (N, S) ⊧ “K is the complete recursively enumerable set”. Clearly any Σ_{2}^{0} formula without set parameters is equivalent over (N, S) to a Σ_{1}^{0} formula with parameter K. Since WKL_{0} includes induction for all Σ_{1}^{0} formulas with set parameters, (N, S) satisfies induction for all Σ_{1}^{0} formulas with parameter K. Hence (N, S) satisfies induction for all Σ_{2}^{0} formulas without set parameters. In other words, N ⊧ Σ_{2}^{0}-PA, a contradiction. This proves the claim. Our result now follows from Theorem 10.3. □

Theorem 10.7. There is a Π_{1}^{0} formula ψ̃(X) with no free variables other than X, such that

1. WKL_{0} proves ∃X ψ̃(X).

2. RCA_{0} proves ∀X ∀Y ((ψ̃(X) ∧ ψ̃(Y)) → X △ Y is finite).

3. WKL_{0} does not prove (∃ recursive X) ψ̃(X).

4. RCA_{0} does not prove ∃X ψ̃(X).

Proof. Let ψ(X) be the Π_{1}^{0} formula of Lemma 10.1. Let ∀n θ(n) be a Π_{1}^{0} sentence which is provable in Σ_{2}^{0}-PA but not in Σ_{1}^{0}-PA. (For instance, we may take ∀n θ(n) to be the Π_{1}^{0} sentence expressing consistency of Σ_{1}^{0}-PA.) We may assume that θ(n) is Σ_{0}^{0}. Let ψ̃(X) be the Π_{1}^{0} formula

∀n (if (∀m ≤ n) (m ∉ X) then θ(n)), and
∀n (if n = least element of X then ¬ θ(n) and ψ({k : n+1+k ∈ X})).

Reasoning in RCA_{0}, suppose X is such that ψ̃(X) holds. If X = ∅ then we have ∀n θ(n), hence ∀X (ψ̃(X) → X = ∅). Now suppose X ≠ ∅. Then X = {n_{0}} ∪ {n_{0} + 1 + k : k ∈ X_{0}} where ψ(X_{0}) holds and n_{0} is the least n such that ¬ θ(n). Since ∀n θ(n) fails, Σ_{2}^{0}-PA fails. Hence by Corollary 10.6 we have ∀X_{0} ∀Y_{0} ((ψ(X_{0}) ∧ ψ(Y_{0})) → X_{0} △ Y_{0} is finite). This implies ∀X ∀Y ((ψ̃(X) ∧ ψ̃(Y)) → X △ Y is finite). The rest follows easily from Theorem 10.3. □

Remark 10.8. For Π_{1}^{0} formulas φ(X) with no free set variables other than X, it is known that WKL_{0} proves

(∃ exactly one X) φ(X) → (∃ recursive X) φ(X).

(This follows from [31, Lemma VIII.2.4.2] using Δ_{1}^{0} comprehension.) One might conjecture that this result would continue to hold with “(∃ exactly one X)” weakened to “(∃ countably many X)”. However, such a conjecture is refuted by Theorem 10.7, taking φ(X) to be ψ̃(X).

Remark 10.9. Tanaka [36] conjectured that WKL_{0} is conservative over RCA_{0} for sentences of the form (∃ countably many X) φ(X), where φ(X) is arithmetical with no free set variables other than X. This conjecture is refuted by Theorem 10.7, taking φ(X) to be the Π_{1}^{0} formula ψ̃(X).

References

[1] Oliver Aberth. Computable Analysis. McGraw-Hill, 1980. XI + 187 pages.

[2] J. Barwise, editor. Handbook of Mathematical Logic. Studies in Logic and the Foundations of Mathematics. North-Holland, 1977. XI + 1165 pages.

[3] Douglas Cenzer and Jeffrey B. Remmel. Π_{1}^{0} classes in mathematics. In [7], pages 623–821, 1998.

[4] S. B. Cooper, T. A. Slaman, and S. S. Wainer, editors. Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Number 224 in London Mathematical Society Lecture Note Series. Cambridge University Press, 1996. VII + 347 pages.

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

[6] F. R. Drake and J. K. Truss, editors. Logic Colloquium ’86. Studies in Logic and the Foundations of Mathematics. North-Holland, 1988. X + 342 pages.

[7] Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, editors. Handbook of Recursive Mathematics. Studies in Logic and the Foundations of Mathematics. North-Holland, 1998. Volumes 1 and 2, XLVI + 1372 pages.

[8] S. Feferman, J. Dawson, Jr., et al., editors. Kurt Gödel: Collected Works. Oxford University Press, 1986–1995. Volume I, XVIII + 474 pages, 1986, Volume II, XVI + 407 pages, 1990, Volume III, XX + 532 pages, 1995.

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

[10] FOM e-mail list. http://www.cs.nyu.edu/mailman/listinfo/fom/. September 1997 to the present.

[11] Harvey Friedman. Subsystems of second order arithmetic and their use in the formalization of mathematics. 19 pages, unpublished, March 1974.

[12] Harvey Friedman. Some systems of second order arithmetic and their use. In [14], pages 235–242, 1975.

[13] L. A. Harrington, M. Morley, A. Scedrov, and S. G. Simpson, editors. Harvey Friedman’s Research on the Foundations of Mathematics. Studies in Logic and the Foundations of Mathematics. North-Holland, 1985. XVI + 408 pages.

[14] Ralph D. James, editor. Proceedings of the International Congress of Mathematicians, Vancouver 1974, volume 1. Canadian Mathematical Congress, 1975. XLIX + 552 pages.

[15] Thomas Jech. Set Theory. Academic Press, 1978. XI + 621 pages.

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

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

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

[19] Kenneth Kunen. Set Theory, an Introduction to Independence Proofs. Studies in Logic and the Foundations of Mathematics. North-Holland, 1980. XVI + 313 pages.

[20] Antonín Kučera. On the role of 0′ in recursion theory. In [6], pages 133–141, 1988.

[21] John Myhill. Creative sets. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 1:97–108, 1955.

[22] Michael E. Mytilinaios. Finite injury and Σ_{1} induction. Journal of Symbolic Logic, 54:38–49, 1989.

[23] Marian B. Pour-El and Saul Kripke. Deduction-preserving “recursive isomorphisms” between theories. Fundamenta Mathematicae, 61:141–163, 1967.

[24] Marian B. Pour-El and J. Ian Richards. Computability in Analysis and Physics. Perspectives in Mathematical Logic. Springer-Verlag, 1988. XI + 206 pages.

[25] Hartley Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967. XIX + 482 pages.

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

[27] 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.

[28] Stephen G. Simpson. Degrees of unsolvability: a survey of results. In [2], pages 631–652, 1977.

[29] Stephen G. Simpson. FOM: natural r.e. degrees; Pi01 classes. FOM e-mail list [10], 13 August 1999.

[30] Stephen G. Simpson. FOM: priority arguments; Kleene-r.e. degrees; Pi01 classes. FOM e-mail list [10], 16 August 1999.

[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.

[32] Stephen G. Simpson, Kazuyuki Tanaka, and Takeshi Yamazaki. Some conservation results on weak König’s lemma. Annals of Pure and Applied Logic, 118:87–114, 2002.

[33] Raymond M. Smullyan. Theory of Formal Systems. Annals of Mathematics Studies. Princeton University Press, 1961. XIII + 142 pages.

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

[35] Andrea Sorbi. The Medvedev lattice of degrees of difficulty. In [4], pages 289–312, 1996.

[36] Kazuyuki Tanaka. More on models of WKL_{0} (see also [37]). 4 pages, handwritten, 1995.

[37] Kazuyuki Tanaka. (in Japanese). R.I.M.S. Kokyuroku, 976:77–85, 1997.

[38] J. van Heijenoort, editor. From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931. Harvard University Press, 1971. Second Printing. XII + 660 pages.