$\mathbf{\Pi^0_1}$ Sets and Models of $\mathbf{\mathsf{WKL}_0}$

Stephen G. Simpson

Department of Mathematics

Draft: May 8, 2000

Pennsylvania State University

Abstract:

We show that any two Medvedev complete $\Pi ^0_1$ subsets of $2^\omega$ are recursively homeomorphic. We obtain a $\Pi ^0_1$ set $\widehat{Q}'$ of countable coded $\omega$-models of $\mathsf{WKL}_0$ with a strong homogeneity property. We show that if $G$ is a generic element of $\widehat{Q}'$, then the $\omega$-model of $\mathsf{WKL}_0$ coded by $G$ satisfies $\forall X\,\forall Y\,($if $X$ is definable from $Y$, then $X$ is Turing reducible to $Y)$. We use a result of Kucera to refute some plausible conjectures concerning $\omega$-models of $\mathsf{WKL}_0$. We generalize our results to non-$\omega$-models of $\mathsf{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.

This paper has been accepted for publication in Reverse Mathematics 2001, to appear.

Contents

• Introduction
• Foundational Significance
• Medvedev Degrees of $\Pi ^0_1$ Subsets of $2^\omega$
• Relativization, Iteration, $\omega$-Models
• Jockusch/Soare Genericity
• Relative Genericity and Definability
• Generalization to Non-$\omega$-Models
• A Result of Kucera
• An Application to $\omega$-Models
• Applications to Non-$\omega$-Models
• Bibliography

Introduction

In this paper we apply recursion-theoretic methods to the study of $\omega$-models of subsystems of second order arithmetic. Specifically, we present some results concerning $\Pi ^0_1$ subsets of $2^\omega$, along with applications to countable $\omega$-models of $\mathsf{WKL}_0$. These results and applications may be regarded as an addendum or supplement to Simpson [30, §VIII.2]. We also present generalizations to countable non-$\omega$-models of $\mathsf{WKL}_0$. These generalizations may be regarded as an addendum to Simpson [30, §IX.2].

For background on subsystems of second order arithmetic, see Simpson [30]. We recall here that $\mathsf{RCA}_0$ is the subsystem consisting of $\Delta^0_1$ comprehension and $\Sigma^0_1$ induction, and $\mathsf{WKL}_0$ is the subsystem consisting of $\mathsf{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 [30]. Their $\omega$-models are easy to understand in recursion-theoretic terms. An $\omega$-model of $\mathsf{RCA}_0$ is a set $S\subseteq P(\omega)$ such that (i) $S\ne\emptyset$, (ii) $X\oplus Y\in S$ for all $X,Y\in S$, and (iii) if $X\in S$ and $Y\le_TX$ then $Y\in S$. An $\omega$-model of $\mathsf{WKL}_0$ has the additional property that if $T\in 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 $\Pi ^0_1$ subsets of $2^\omega$ and degrees of elements of such sets. An important paper in this area is Jockusch/Soare [16]. An extensive recent survey is Cenzer/Remmel [3]. This topic is well known to be closely related to $\omega$-models of $\mathsf{WKL}_0$. The connection is as follows: $P\subseteq2^\omega$ is $\Pi ^0_1$ if and only if there exists a recursive tree $T$ of finite sequences of $0$'s and $1$'s such that $P=\{X\in2^\omega:X$ is a path through $T\}$.

In the model-theoretic literature, $\omega$-models of $\mathsf{WKL}_0$ are known as Scott systems, after Scott [25], who proved that $S\subseteq P(\omega)$ is a countable $\omega$-model of $\mathsf{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 [17].

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 $\Pi ^0_1$ subsets of $2^\omega$ 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 [22] concerning effectively inseparable theories.

In §4 we relativize and iterate the result of §3 to obtain a nonempty $\Pi ^0_1$ set $\widehat{Q}'$ of codes for countable $\omega$-models of $\mathsf{WKL}_0$, with a strong homogeneity property: any two nonempty $\Pi ^0_1$ subsets of $\widehat{Q}'$ are recursively homeomorphic, via a homeomorphism which preserves the $\omega$-models (Theorem 4.11).

In §5 we combine the results of §§3,4 with Jockusch/Soare forcing, to obtain a countable $\omega$-model of $\mathsf{WKL}_0$ in which all definable elements are recursive (Theorem 5.11). This result is originally due to Friedman [10, unpublished]. In §6 we improve this result, to obtain a countable $\omega$-model of $\mathsf{WKL}_0$ satisfying $\forall X\,\forall Y\,($if $X$ is definable from $Y$ then $X\le_TY)$ (Theorem 6.9).

In §7 we generalize the results of §§3,4,5,6 to non-$\omega$-models. In this way we obtain a conservation result, showing that $\mathsf{WKL}_0$ plus a strong relative non-definability scheme is conservative over $\Sigma^0_1$-$\mathsf{PA}$ (Corollary 7.9).

In §8 we prove a recursion-theoretic result of Kucera [19]: 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 Kucera's result to the study of $\omega$-models of $\mathsf{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 Kucera's result, and we apply the generalization to the study of non-$\omega$-models of $\mathsf{WKL}_0$. We refute several plausible conjectures concerning the relationship between $\mathsf{WKL}_0$ and $\mathsf{RCA}_0$. See Remarks 10.4, 10.8, 10.9.

Throughout this paper, we use recursion-theoretic concepts and notation from Rogers [24] and Soare [33]. We use $\omega=\{0,1,2,\dots\}$ to denote the set of natural numbers. We identify points $X\in2^\omega$ with functions $X:\omega\to\{0,1\}$. For $e,n,s,k\in\omega$ and $X\in2^\omega$, 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 $\le s$ steps with output $k$. For $e,n,k\in\omega$ and $X\in2^\omega$, we write $\{e\}^X(n)=k$ to mean that $\exists s\,(\{e\}_s^X(n)=k)$. Furthermore, $\{e\}^X(n)\downarrow$ means that $\{e\}^X(n)$ is defined, i.e., $\exists k\,(\{e\}^X(n)=k)$, and $\{e\}^X(n)\uparrow$ means that $\{e\}^X(n)$ is undefined, i.e., $\lnot\,\exists k\,(\{e\}^X(n)=k)$. For $X,Y\in2^\omega$, $X\le_TY$ means that $X$ is Turing reducible to $Y$, i.e., $\exists e\,\forall n\,(X(n)=\{e\}^Y(n))$. The Turing degree of $X$, written $\deg_T(X)$, is the set of all $Y$ such that $X\equiv_TY$, i.e., $X\le_TY$ and $Y\le_TX$. A predicate $R\subseteq2^\omega\times\omega$ is said to be recursive if $\exists e\,\forall X\,\forall n\,(\{e\}^X(n)=1$ if $R(X,n)$, and $\{e\}^X(n)=0$ if $\lnot\,R(X,n))$. A set $P\subseteq2^\omega$ is said to be $\Pi ^0_1$ if there exists a recursive predicate $R$ such that $P=\{X\in2^\omega:\forall n\,R(X,n)\}$. For $\Pi ^0_1$ sets $P\subseteq2^\omega$, we shall consider recursive functionals $\Phi:P\to2^\omega$ given by $\Phi(X)(n)=\{e\}^X(n)$ for some $e\in\omega$ and all $X\in P$, $n\in\omega$.

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 [37], where some of the most important modern papers have been carefully translated and reprinted. See also Gödel's collected works [12] 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, $\mathrm{REC}=\{X:X$ is recursive$\}$. See Aberth [1] and Pour-El/Richards [23]. 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 $\omega$-model $S$ of $\mathsf{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 $\mathsf{WKL}_0$ is just strong enough to prove many basic theorems of real analysis. See Simpson [30, Chapter IV]. Thus $S$ contains just enough non-computable reals in order to satisfy the demands of real analysis.

Furthermore, in Theorem 6.9 below, we show that the same $\omega$-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 $\mathsf{WKL}_0$ plus the above scheme has the same first order part as $\mathsf{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$.

Medvedev Degrees of $\Pi ^0_1$ Subsets of $2^\omega$

In this section we exposit the lattice of Medvedev degrees of nonempty $\Pi ^0_1$ subsets of $2^\omega$. We prove an important result concerning nonempty $\Pi ^0_1$ subsets of $2^\omega$ which are Medvedev complete.

For background on Medvedev degrees of subsets of the Baire space, $\omega^\omega$, see Rogers [24, §13.7] and Sorbi [34]. For background on $\Pi ^0_1$ subsets of the Cantor space, $2^\omega$, and of the Baire space, see the survey by Cenzer/Remmel [3].

Definition 3.1   Let $P$ and $Q$ be nonempty $\Pi ^0_1$ subsets of $2^\omega$. We say that $P$ is Medvedev reducible to $Q$, written $P\le_MQ$, if there exists a recursive functional $\Phi:Q\to P$. We say that $Q$ is Medvedev complete if $P\le_MQ$ for all nonempty $\Pi ^0_1$ subsets $P$ of $2^\omega$. We say that $P$ and $Q$ are Medvedev equivalent, written $P\equiv_MQ$, if $P\le_MQ$ and $Q\le_MP$. The Medvedev degree of $P$, written $\deg_M(P)$, is the set of all $Q$ such that $P\equiv_MQ$. The Medvedev degrees are partially ordered by writing $\deg_M(P)\le\deg_M(Q)$ if and only if $P\le_MQ$. We write $\deg_M(P)<\deg_M(Q)$ if and only if $P<_MQ$, i.e., $P\le_MQ$ and $Q\not\le_MP$.

Theorem 3.2   The Medvedev degrees of nonempty $\Pi ^0_1$ subsets of $2^\omega$ form a distributive lattice $\mathcal{P}_M$ with a bottom and a top element. The top element of $\mathcal{P}_M$ consists of the nonempty $\Pi ^0_1$ subsets of $2^\omega$ which are Medvedev complete.

Proof.In this proof and throughout this paper, we use the following notation. For $X,Y\in2^\omega$ we have $X\oplus Y\in2^\omega$ where $(X\oplus Y)(2n)=X(n)$ and $(X\oplus Y)(2n+1)=Y(n)$. We use $2^{<\omega}$ to denote the set of strings, i.e., finite sequences of $0$'s and $1$'s. The length of $\sigma\in2^{<\omega}$ is denoted $\mathrm{lh}(\sigma)$. For $X\in2^\omega$ and $n\in\omega$, we have $X[n]=\langle X(0),\dots,X(n-1)\rangle\in2^{<\omega}$ and $\mathrm{lh}(X[n])=n$. For $\sigma\in2^{<\omega}$ and $X\in2^\omega$, we have $\sigma{{}^\smallfrown}X\in2^\omega$ given by

$$(\sigma{{}^\smallfrown}X)(n)=\left\{ \begin{array}{ll} \sig... ...sigma))&\mbox{ if }n\ge\mathrm{lh}(\sigma). \end{array}\right.$$

We fix a primitive recursive, one-to-one, onto function $(\cdot,\cdot):\omega\times\omega\to\omega$. For $Y\in2^\omega$ and $m\in\omega$, we have $(Y)_m\in2^\omega$ where $(Y)_m(n)=Y((m,n))$.

To prove our theorem, let $P$ and $Q$ be nonempty $\Pi ^0_1$ subsets of $2^\omega$. The supremum or least upper bound of $\deg_M(P)$ and $\deg_M(Q)$ is $\deg_M(P\times Q)$ where $P\times Q=\{X\oplus Y:X\in P$ and $Y\in Q\}$. The infimum or greatest lower bound of $\deg_M(P)$ and $\deg_M(Q)$ is $\deg_M(P+Q)$ where

$$P+Q=\{\langle0\rangle{{}^\smallfrown}X:X\in P\}\cup\{\langle1\rangle{{}^\smallfrown}Y:Y\in Q\}.$$

The distributive laws $P\times(Q+R)\equiv_M(P\times Q)+(P\times R)$ and $P+(Q\times R)\equiv_M(P+Q)\times(P+R)$ are easily verified. The bottom element of our lattice $\mathcal{P}_M$ is $\deg_M(2^\omega)$, or equivalently $\deg_M(P)$ where $P$ is any $\Pi ^0_1$ subset of $2^\omega$ with a recursive element. The top element of $\mathcal{P}_M$ is $\deg_M(Q)$ where $Q$ is any nonempty $\Pi ^0_1$ subset of $2^\omega$ which is Medvedev complete. See Lemma 3.3 and Remark 3.4 below.$\Box$

Lemma 3.3   There exists a nonempty $\Pi ^0_1$ subset $Q$ of $2^\omega$ which is Medvedev complete.

Proof.Let $\{P_e:e\in\omega\}$ be a standard, recursive enumeration of the $\Pi ^0_1$ subsets of $2^\omega$. (See Remark 3.9 below.) In particular, the predicate $U(e,X)\equiv(X\in P_e)$ is $\Pi ^0_1$. By the Normal Form Theorem for $\Pi ^0_1$ predicates, we have $U(e,X)\equiv\forall n\,U_1(e,X[n])$ where $U_1\subseteq\omega\times2^{<\omega}$ is primitive recursive. As in Simpson [30, Lemmas VIII.2.5 and VIII.2.9], put $U^{+}(e,X)\equiv$

$\forall n\,(\forall\sigma$ of length $n)\,($if $(\forall m\le n)\,U_1(e,\sigma[m])$ then $U_1(e,X[n])).$

Note that $U^{+}(e,X)$ is again $\Pi ^0_1$. 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^\omega$. Put

$Q=\prod_eP_e^{+}=\{Y:\forall e\,U^{+}(e,(Y)_e)\}.$

Obviously $Q$ is a nonempty $\Pi ^0_1$ subset of $2^\omega$. For all $e$ such that $P_e$ is nonempty, we have $P_e\le_MQ$ via the recursive functional $Y\mapsto(Y)_e$. Thus $Q$ is Medvedev complete.$\Box$

Remark 3.4   Another construction of a Medvedev complete set is as follows. Let $Q$ be the $\Pi ^0_1$ set of complete extensions of Peano arithmetic. It can be shown that $Q$ is Medvedev complete; see Scott/Tennenbaum [26] and Jockusch/Soare [16]. Instead of Peano arithmetic, we may use any effectively inseparable theory; see Pour-El/Kripke [22]. 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 $\Pi ^0_1$ subsets of $2^\omega$ 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\subseteq\omega\times2^\omega\times2^\omega$. If the predicate $R(k,X,Y)$ is $\Pi ^0_1$, then the predicate $S(k,X)\equiv\exists Y\,R(k,X,Y)$ is also $\Pi ^0_1$.

Proof.By the Normal Form Theorem for $\Pi ^0_1$ predicates, we have

$R(k,X,Y)\equiv\forall n\,R_1(k,X[n],Y[n])$

where $R_1(k,\sigma,\tau)$ is primitive recursive. Thus $S(k,X)$ holds if and only if $\exists Y\,\forall n\,R_1(k,X[n],Y[n])$. By compactness of $2^\omega$, this is equivalent to $\forall n\,(\exists\tau$ of length $n)\,(\forall m\le n)\,R_1(k,X[m],\tau[m])$, which is explicitly $\Pi ^0_1$.$\Box$

Lemma 3.6   Let $Q$ be a $\Pi ^0_1$ subset of $2^\omega$, and let $\Phi:Q\to2^\omega$ be a recursive functional.

1.

The image $\Phi(Q)$ is a $\Pi ^0_1$ subset of $2^\omega$.

2.

For any $\Pi ^0_1$ subset $P$ of $2^\omega$, the inverse image $\Phi^{-1}(P)$ is a $\Pi ^0_1$ subset of $2^\omega$.

Proof.To prove part 1, note that for all $X\in2^\omega$ we have $X\in\Phi(Q)$ if and only if $\exists Y\,(Y\in Q$ and $\Phi(X)=Y)$. By Lemma 3.5, this is $\Pi ^0_1$. For part 2 we have $\Phi^{-1}(P)=\{Y:Y\in Q$ and $\Phi(Y)\in P\}$ and this is obviously $\Pi ^0_1$.$\Box$

Definition 3.7   We use $\mathcal{B}$ to denote the free Boolean algebra on a countable set of generators $\{a_n:n\in\omega\}$. There is a well known isomorphism $b\mapsto[b]$ of $\mathcal{B}$ onto the Boolean algebra of clopen subsets of $2^\omega$, given by $[a_n]=\{X:X(n)=1\}$, $[b\cdot c]=[b]\cap[c]$, $[b+c]=[b]\cup[c]$, $[-b]=2^\omega\setminus[b]$, $[0]=\emptyset$, $[1]=2^\omega$. For $T\subseteq\mathcal{B}$ we write $[T]=\bigcap\{[b]:b\in T\}$.

Remark 3.8   The mapping $b\mapsto[b]$ is essentially just the usual semantics for propositional calculus. The Compactness Theorem for propositional calculus says: For all $T\subseteq\mathcal{B}$, $[T]=\emptyset$ if and only if $[T_0]=\emptyset$ for some finite $T_0\subseteq T$. This is a consequence of the fact that $2^\omega$ is compact as a topological space.

Remark 3.9   If $T\subseteq\mathcal{B}$ is recursively enumerable, then $[T]\subseteq2^\omega$ is $\Pi ^0_1$. Conversely, if $P\subseteq2^\omega$ is $\Pi ^0_1$, then $P=[T_P]$ where $T_P=\{b\in\mathcal{B}:P\subseteq[b]\}$. Note that $T_P$ is recursively enumerable. A standard, recursive enumeration $\{P_e:e\in\omega\}$ of the $\Pi ^0_1$ subsets of $2^\omega$ may be obtained by setting $P_e=[T_e]$, where $\{T_e:e\in\omega\}$ is a standard, recursive enumeration of the recursively enumerable subsets of $\mathcal{B}$.

Remark 3.10   The mapping $b\mapsto[b]$ gives a one-to-one correspondence between nonempty $\Pi ^0_1$ subsets of $2^\omega$ and Stone spaces of Boolean algebras of the form $\mathcal{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 $\Pi ^0_1$ subset of $2^\omega$, and let $\Phi:Q\to2^\omega$ be a recursive functional. Then there is a recursive function $f:\mathcal{B}\to\mathcal{B}$ such that $\Phi^{-1}[b]=[f(b)]\cap Q$ for all $b\in\mathcal{B}$.

Proof.The predicate $(Y\in Q$ and $\Phi(Y)\in[b])$ is $\Pi ^0_1$, so by the Normal Form Theorem, let $R(\tau,b)$ be a primitive recursive predicate such that

$(Y\in Q$ and $\Phi(Y)\in[b])\equiv\forall n\,R(Y[n],b).$

Trivially we have

$(\forall b\in\mathcal{B})\,(\forall Y\in2^\omega)\,(\Phi(Y)\notin[b]$ or $\Phi(Y)\notin[-b]$ or $Y\notin Q),$

or in other words,

$(\forall b\in\mathcal{B})\,(\forall Y\in 2^\omega)\,\exists n\,($not $R(Y[n],b)$ or not $R(Y[n],-b)$ or not $R(Y[n],1)).$

By compactness of $2^\omega$, it follows that $(\forall b\in\mathcal{B})\,\exists n\,(\forall\tau$ of length $n)\,(\exists m\le n)\,($not $R(\tau[m],b)$ or not $R(\tau[m],-b)$ or not $R(\tau[m],1))$. For $b\in\mathcal{B}$ let $n(b)$ be the least such $n$, and form $f(b)\in\mathcal{B}$ such that

$[f(b)]=\{Y\in2^\omega:(\forall m\le n(b))\,R(Y[m],b)\}.$

Clearly $n:\mathcal{B}\to\omega$ and $f:\mathcal{B}\to\mathcal{B}$ are recursive, and $\Phi^{-1}[b]=[f(b)]\cap Q$.$\Box$

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

We now introduce a property of nonempty $\Pi ^0_1$ subsets of $2^\omega$, called productiveness, which will turn out to be equivalent to Medvedev completeness (Lemma 3.20).

Definition 3.13   Let $P$ be a nonempty $\Pi ^0_1$ subset of $2^\omega$. A splitting function for $P$ is a recursive function $g:\omega\to\mathcal{B}$ such that for all $e$, if $P_e\subseteq P$ and $P_e$ is nonempty, then $P_e\cap[g(e)]$ and $P_e\cap[-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 $\Pi ^0_1$ set $P\subseteq2^\omega$ such that $P$ is productive.

Proof.Put $P=\{X\in2^\omega:\forall n\,(X(n)\ne\{n\}(n))\}$. Clearly $P$ is nonempty and $\Pi ^0_1$. By Lemma 3.5, the predicate

$S(e,n,k)\equiv\forall X\,($if $X\in P_e$ then $X(n)=k)$

is $\Sigma^0_1$. By the $\Sigma^0_1$ 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:\omega\to\mathcal{B}$ by $g(e)=a_{h(e)}$. We claim that $g$ is a splitting function for $P$. To see this, suppose $P_e\subseteq P$ and $P_e\ne\emptyset$. If $P_e\cap[a_{h(e)}]=\emptyset$, then $\forall X\,($if $X\in P_e$ then $X(h(e))=0)$, hence $\{h(e)\}(h(e))=0$, a contradiction. If $P_e\cap[-a_{h(e)}]=\emptyset$, then $\forall X\,($if $X\in P_e$ then $X(h(e))=1)$, hence $\{h(e)\}(h(e))=1$, a contradiction.$\Box$

Lemma 3.15   Let $P$ and $Q$ be nonempty $\Pi ^0_1$ subsets of $2^\omega$. Given $a,b,a'\in\mathcal{B}$ such that $a\ne a\cdot b=b\ne0$ and $a'\ne0$, and given a splitting function for $P$, we can effectively find $b'\in\mathcal{B}$ with the following properties: $a'\ne a'\cdot b'=b'\ne0$, and if $Q\cap[a]\ne\emptyset$ and $P\cap[a']\ne\emptyset$ then

1.

$Q\cap[a]\cap[b]=\emptyset$ if and only if $P\cap[a']\cap[b']=\emptyset$,

2.

$Q\cap[a]\cap[-b]=\emptyset$ if and only if $P\cap[a']\cap[-b']=\emptyset$.

Proof.Because $P$ is productive, $P$ is nowhere dense in $2^\omega$, so given $a'\ne0$ we can effectively find $a'_0,a'_1,a'_2\in\mathcal{B}$ such that $a'=a'_0+a'_1+a'_2$ and $a'_0\cdot a'_1=a'_0\cdot a'_2=a'_1\cdot a'_2=0$ and $a'_0\ne0$ and $a'_1\ne0$ and $a'_2\ne0$ and $P\cap[a'_0]=P\cap[a'_1]=\emptyset$. Thus $P\cap[a']=P\cap[a'_2]$. Now let $g$ be a splitting function for $P$. By the Recursion Theorem, we can effectively find $e\in\omega$ such that

$$P_e=\left\{ \begin{array}{ll} P\cap[a'_2]&\mbox{ if }Q\cap[... ...set\mbox{ and }Q\cap[a]\cap[-b]=\emptyset. \end{array}\right.$$

Put $b'=a'_1+a'_2\cdot g(e)$. Clearly $a'\ne a'\cdot b'=b'\ne0$. Now assume $Q\cap[a]\ne\emptyset$ and $P\cap[a']\ne\emptyset$. If $Q\cap[a]\cap[b]=\emptyset$, then we have $P_e=P\cap[a'_2]\cap[g(e)]$, hence $P_e\cap[-g(e)]=\emptyset$, hence $P_e=\emptyset$ (because $g$ is a splitting function for $P$), hence $P\cap[a']\cap[b']=P\cap[a'_2]\cap[g(e)]=P_e=\emptyset$. Similarly, if $Q\cap[a]\cap[-b]=\emptyset$, then $P\cap[a']\cap[-b']=\emptyset$. On the other hand, if $Q\cap[a]\cap[b]\ne\emptyset$ and $Q\cap[a]\cap[-b]\ne\emptyset$, then we have $P_e=P\cap[a'_2]=P\cap[a']\ne\emptyset$, hence $P\cap[a']\cap[b']=P_e\cap[g(e)]\ne\emptyset$ and $P\cap[a']\cap[-b']=P_e\cap[-g(e)]\ne\emptyset$. This completes the proof.$\Box$

Lemma 3.16   Let $P$ and $Q$ be nonempty $\Pi ^0_1$ subsets of $2^\omega$.

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 $\mathcal{B}^{*}$ is a subalgebra of $\mathcal{B}$ and if $f^{*}:\mathcal{B}^{*}\to\mathcal{B}$ is a monomorphism, let us call $f^{*}$ good if, for all $b\in\mathcal{B}^{*}$, $Q\cap[b]=\emptyset$ if and only if $P\cap[f^{*}(b)]=\emptyset$.

For part 1, to find a recursive functional $\Phi$ from $P$ onto $Q$, it suffices to find a good recursive monomorphism $f:\mathcal{B}\to\mathcal{B}$. Assume inductively that we have already found a good finite monomorphism $f_n:\mathcal{B}_n\to\mathcal{B}$, where $\mathcal{B}_n$ is a finite subalgebra of $\mathcal{B}$. (We start with $\mathcal{B}_0=\{0,1\}$.) Let $b$ be the $n$th element of $\mathcal{B}$ with respect to some fixed recursive enumeration of $\mathcal{B}$. Let $\mathcal{B}_{n+1}$ be the finite subalgebra of $\mathcal{B}$ generated by $\mathcal{B}_n\cup\{b\}$. We effectively extend $f_n$ to a good finite monomorphism $f_{n+1}:\mathcal{B}_{n+1}\to\mathcal{B}$, as follows. For each atom $a$ of $\mathcal{B}_n$, if $a\cdot b=a$ or $a\cdot b=0$ put $f_{n+1}(a\cdot b)=f_n(a\cdot b)$, otherwise use Lemma 3.15 and a splitting function for $P$ to effectively find $f_{n+1}(a\cdot b)=b'\in\mathcal{B}$ such that $f_n(a)\ne f_n(a)\cdot b'=b'\ne\emptyset$, and $Q\cap[a]\cap[b]=\emptyset$ if and only if $P\cap[f_n(a)]\cap[b']=\emptyset$, and $Q\cap[a]\cap[-b]=\emptyset$ if and only if $P\cap[f_n(a)]\cap[-b']=\emptyset$. Finally we obtain a good recursive monomorphism $f=\bigcup_nf_n:\mathcal{B}\to\mathcal{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}:\mathcal{B}_{2n}\cong\mathcal{B}'_{2n}$, where $\mathcal{B}_{2n}$ and $\mathcal{B}'_{2n}$ are finite subalgebras of $\mathcal{B}$. Let $b$ be the $n$th element of $\mathcal{B}$ with respect to some fixed recursive enumeration of $\mathcal{B}$. Let $\mathcal{B}_{2n+1}$ be the finite subalgebra of $\mathcal{B}$ generated by $\mathcal{B}_{2n}\cup\{b\}$. Use Lemma 3.15 and a splitting function for $P$ to effectively extend $f_{2n}$ to a good finite isomorphism $f_{2n+1}:\mathcal{B}_{2n+1}\cong\mathcal{B}'_{2n+1}$. Then let $\mathcal{B}'_{2n+2}$ be the finite subalgebra of $\mathcal{B}$ generated by $\mathcal{B}'_{2n+1}\cup\{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}:\mathcal{B}_{2n+2}\cong\mathcal{B}'_{2n+2}$. Finally we obtain a good recursive automorphism $f=\bigcup_nf_n:\mathcal{B}\to\mathcal{B}$, and part 2 is proved.$\Box$

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

Remark 3.18   Pour-El and Kripke [22] 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 $\Pi ^0_1$ subsets of $2^\omega$, via Stone duality. Let us say that $T$ is effectively essentially incomplete if, given $T'$ extending $T$, we can effectively find a sentence $\sigma$ in the language of $T$ such that both $T'\cup\{\sigma\}$ and $T'\cup\{\lnot\sigma\}$ are consistent. Note that $T$ is effectively essentially incomplete if and only if the nonempty $\Pi ^0_1$ subset of $2^\omega$ 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 [22] 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 $\Pi ^0_1$ subsets of $2^\omega$. If $P\le_MQ$ and $P$ is productive, then $Q$ is productive.

Proof.Since $P\le_MQ$, there is a recursive functional $\Phi:Q\to P$. By Lemma 3.11, let $f:\mathcal{B}\to\mathcal{B}$ be recursive such that $\Phi^{-1}[b]=[f(b)]\cap Q$ for all $b\in\mathcal{B}$. Let $g:\omega\to\mathcal{B}$ be a splitting function for $P$. The predicate $S(e,X)\equiv(X\in\Phi(P_e\cap Q))$ is $\Pi ^0_1$ (see the proof of part 1 of Lemma 3.6), so by the S-m-n Theorem, let $h:\omega\to\omega$ be primitive recursive such that $P_{h(e)}=\Phi(P_e\cap Q)$ for all $e$. Now if $P_e\subseteq Q$ and $P_e\ne\emptyset$, we have $P_{h(e)}=\Phi(P_e)\subseteq P$ and $P_{h(e)}\ne\emptyset$, hence $P_{h(e)}\cap[gh(e)]\ne\emptyset$ and $P_{h(e)}\cap[-gh(e)]\ne\emptyset$, hence $P_e\cap[fgh(e)]\ne\emptyset$ and $P_e\cap[-fgh(e)]\ne\emptyset$. Thus $fgh:\omega\to\mathcal{B}$ is a splitting function for $Q$.$\Box$

Lemma 3.20   Let $P$ be a nonempty $\Pi ^0_1$ subset of $2^\omega$. $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.$\Box$

Theorem 3.21   Let $P$ and $Q$ be nonempty $\Pi ^0_1$ subsets of $2^\omega$.

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.$\Box$

Remark 3.22   Let $\mathcal{P}_M$ be the lattice of Medvedev degrees of nonempty $\Pi ^0_1$ subsets of $2^\omega$, as in Theorem 3.2. There are many obvious structural questions to ask about $\mathcal{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 $\mathcal{P}_M$ could be more rewarding than the ongoing study of the structural aspects of $\mathcal{R}_T$, the upper semilattice of Turing degrees of recursively enumerable subsets of $\omega$, as pursued for instance in Soare [33]. For one thing, there is a well known lack of natural examples of elements of $\mathcal{R}_T$, but there are some interesting natural examples of elements of $\mathcal{P}_M$. In particular, putting

$\mathrm{DNR}_k=\{X\in k^\omega:\forall n\,(X(n)\ne\{n\}(n))\}$, Jockusch [15] has shown that

$\mathrm{DNR}_2>_M\mathrm{DNR}_3>_M\cdots>_M\mathrm{DNR}_k>_M\cdots$, $2\le k\in\omega$, and of course $\mathrm{DNR}_2$ is Medvedev complete (see the proof of Lemma 3.14). See also Simpson [28,29] and other FOM postings in the same thread.

Relativization, Iteration, $\omega$-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 [14, page 458] and Kunen [18, page 273]. We show that our construction gives rise to a $\Pi ^0_1$ set of countable $\omega$-models of $\mathsf{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 [24, pages 128-137]) to an arbitrary $X\in2^\omega$. Say that $P^X\subseteq2^\omega$ is $\Pi^{0,X}_1$ if $P^X=\{Y\in2^\omega:\forall n\,R(X,Y,n)\}$ for some recursive predicate $R\subseteq2^\omega\times2^\omega\times\omega$. We employ a uniform, standard, recursive enumeration $\{P_e^X:e\in\omega\}$ of the $\Pi^{0,X}_1$ subsets of $2^\omega$. A nonempty $\Pi^{0,X}_1$ set $P^X\subseteq2^\omega$ is said to be $X$-productive if there exists an $X$-recursive splitting function, i.e., an $X$-recursive function $g:\omega\to\mathcal{B}$ such that for all $e$, if $\emptyset\ne P_e^X\subseteq P^X$ then $P_e^X\cap[g(e)]\ne\emptyset\ne P_e^X\cap[-g(e)]$.

Recall that for $Y\in2^\omega$ and $e\in\omega$ we have $(Y)_e\in2^\omega$ where $(Y)_e(n)=Y((e,n))$. (See the proofs of Theorem 3.2 and Lemma 3.3.) For $Q\subseteq2^\omega$ put $(Q)_e=\{(Y)_e:Y\in Q\}$.

Lemma 4.2   There is a $\Pi ^0_1$ predicate $\widehat{P}\subseteq2^\omega\times2^\omega$ such that

$\forall X\,\forall e\,($if $P^X_e\ne\emptyset$ then $P^X_e=(\widehat{P}^X)_e)$

where $\widehat{P}^X=\{Y:\widehat{P}(X,Y)\}$.

Proof.This comes from a uniform relativization of the proof of Lemma 3.3. The predicate $U(e,X,Z)\equiv(Z\in P_e^X)$ is $\Pi ^0_1$, so by the Normal Form Theorem for $\Pi ^0_1$ predicates, let $U_1\subseteq\omega\times2^{<\omega}\times2^{<\omega}$ be primitive recursive such that $U(e,X,Z)\equiv\forall n\,U_1(e,X[n],Z[n])$. Put $\widehat{P}(X,Y)\equiv \forall e\,U^{+}(e,X,(Y)_e)$, where $U^{+}(e,X,Z)\equiv$

$\forall n\,(\forall\tau$ of length $n)\,($if $(\forall m\le n)\,U_1(e,X[m],\tau[m])$ then $U_1(e,X[n],Z[n]))$.

It is straightforward to verify that $\widehat{P}$ has the desired property. The details are as in the proof of Lemma 3.3.$\Box$

Lemma 4.3   With notation as in Lemma 4.2, for all $X\in2^\omega$, $\widehat{P}^X$ is $X$-productive with a fixed primitive recursive splitting function $g:\omega\to\mathcal{B}$.

Proof.This comes from a uniform relativization of Lemmas 3.14 and 3.19. Let $e_0\in\omega$ be such that, for all $X\in2^\omega$, $P^X_{e_0}=\{Y\in2^\omega:\forall n\,(Y(n)\ne\{n\}^X(n))\}$. The argument for Lemma 3.14 gives a primitive recursive function $g_0:\omega\to\mathcal{B}$ such that, for all $X$, $P^X_{e_0}$ is $X$-productive with splitting function $g_0$. Note also that $(Y)_{e_0}\in P^X_{e_0}$ for all $Y\in\widehat{P}^X$. Let $f_0:\mathcal{B}\to\mathcal{B}$ be primitive recursive such that, for all $Y\in2^\omega$ and $b\in\mathcal{B}$, $Y\in[f_0(b)]$ if and only if $(Y)_{e_0}\in[b]$. Let $h_0:\omega\to\omega$ be primitive recursive such that, for all $X\in2^\omega$ and all $e\in\omega$, $P^X_{h_0(e)}=\{(Y)_{e_0}:Y\in P^X_e\}$. As in the proof of Lemma 3.19 we have that, for all $X\in2^\omega$, $\widehat{P}^X$ is $X$-productive with splitting function $g=f_0g_0h_0:\omega\to\mathcal{B}$.$\Box$

Definition 4.4   Recall that $(Y)_i(n)=Y((i,n))$. We also put

$$(Y)^i((j,n))=\left\{ \begin{array}{ll} Y((j,n))&\mbox{ if }j<i,\\ [3pt] 0&\mbox{ otherwise}. \end{array}\right.$$

(Compare the dependent choice notation of Simpson [30, Definition VII.6.1 and Lemmas VIII.2.5 and VIII.2.9].) From now on, fix $\widehat{P}$ as in Lemma 4.2, and put $\widehat{Q}=\{Y\in2^\omega:\forall i\,\widehat{P}((Y)^i,(Y)_i)\}$. Clearly $\widehat{Q}$ is a nonempty $\Pi ^0_1$ subset of $2^\omega$.

Lemma 4.5   For all $Y\in\widehat{Q}$ we have

$\{((Y)_i)_e:i,e\in\omega\}=\{X\in2^\omega:\exists i\,(X\le_T(Y)^i)\}$

and this is an $\omega$-model of $\mathsf{WKL}_0$.

Proof.If $X\le_T(Y)^i$ then clearly $\{X\}=P_e^{(Y)^i}$ for an appropriate $e$, hence $X=((Y)_i)_e$. This gives $\{X:\exists i\,(X\le_T(Y)^i)\}\subseteq\{((Y)_i)_e:i,e\in\omega\}$. The converse inclusion follows from $((Y)_i)_e\le_T(Y)_i\le_T(Y)^{i+1}$. To see that this is an $\omega$-model of $\mathsf{WKL}_0$, use Lemma 4.2 plus the following characterization: $S\subseteq2^\omega$ is an $\omega$-model of $\mathsf{WKL}_0$ if and only if (i) $S\ne\emptyset$, (ii) $X\oplus Y\in S$ for all $X,Y\in S$, and (iii) for all $X\in S$ and $e\in\omega$, if $P^X_e\ne\emptyset$ then $P^X_e\cap S\ne\emptyset$.$\Box$

Definition 4.6   Let $P$ and $Q$ be nonempty $\Pi ^0_1$ subsets of $2^\omega$. Let $\Phi$ be a recursive functional from $Q$ onto $P$. A splitting functional for $\Phi$ is a recursive functional $g:P\times\omega\to\mathcal{B}$ such that for all $X\in P$, the $X$-recursive function $e\mapsto g^X(e)$ is a splitting function for the $\Pi^{0,X}_1$ set $\Phi^{-1}(X)=\{Y\in Q:\Phi(Y)=X\}$. We say that $\Phi$ is productive if there exists a splitting functional for $\Phi$.

Lemma 4.7   Let $P_1,P_2,Q_1,Q_2$ be nonempty $\Pi ^0_1$ subsets of $2^\omega$. Suppose that $\Phi_i$ is a recursive functional from $Q_i$ onto $P_i$, $i=1,2$. If $P_1$ and $P_2$ are recursively homeomorphic and $\Phi_1$ and $\Phi_2$ are productive, then $Q_1$ and $Q_2$ are recursively homeomorphic. Indeed, given a recursive homeomorphism $\Psi:P_1\cong P_2$ and splitting functionals for $\Phi_1$ and $\Phi_2$, we can effectively find a recursive homeomorphism $\Psi':Q_1\cong Q_2$ such that $\Psi\circ\Phi_1=\Phi_2\circ\Psi'$.

Proof.This is a uniform relativization of part 2 of Lemma 3.16.$\Box$

Definition 4.8   For any $i\in\omega$ and any nonempty $\Pi ^0_1$ set $Q\subseteq2^\omega$, put $(Q)_i=\{(Y)_i:Y\in Q\}$ and $(Q)^i=\{(Y)^i:Y\in Q\}$. Note that $(Q)_i$ and $(Q)^i$ are again nonempty $\Pi ^0_1$ subsets of $2^\omega$. In particular $(Q)^0$ is a trivial $\Pi ^0_1$ set, namely $(Q)^0=\{Z_0\}$ where $Z_0\in2^\omega$ is defined by $Z_0(n)=0$ for all $n$.

Lemma 4.9   Let $P$ and $Q$ be nonempty $\Pi ^0_1$ subsets of $\widehat{Q}$. Then there are a recursive homeomorphism $\Psi:P\cong Q$ and a recursive sequence of recursive homeomorphisms $\Psi^i:(P)^i\cong(Q)^i$, $i\in\omega$, such that $\Psi^i((Y)^i)=(\Psi(Y))^i$ for all $Y\in P$.

Proof.By Lemma 4.3, the recursive functionals from $(\widehat{Q})^{i+1}$ onto $(\widehat{Q})^i$ given by $(Y)^{i+1}\mapsto(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 $\Psi^0:(P)^0\cong(Q)^0$. Repeatedly apply Lemma 4.7 to obtain a recursive sequence of recursive homeomorphisms $\Psi^1:(P)^1\cong(Q)^1$, $\Psi^2:(P)^2\cong(Q)^2$, ..., $\Psi^i:(P)^i\cong(Q)^i$, ..., such that $\Psi^i((Y)^i)=(\Psi^{i+1}((Y)^{i+1}))^i$ for all $Y\in P$. Finally $\Psi:P\cong Q$ is given by $\Psi=\lim_i\Psi^i$.$\Box$

Lemma 4.10   Let $P$ and $Q$ be nonempty $\Pi ^0_1$ subsets of $\widehat{Q}$. Then there exists a recursive homeomorphism $\Psi:P\cong Q$ such that for all $Y\in P$ and $Z\in Q$, if $\Psi(Y)=Z$ then $\{((Y)_i)_e:i,e\in\omega\}=\{((Z)_i)_e:i,e\in\omega\}$.

Proof.Let $\Psi:P\cong Q$ be as in Lemma 4.9. Let $Y\in P$ and $Z\in Q$ be such that $\Psi(Y)=Z$. By Lemma 4.9 we have $\Psi^i((Y)^i)=(Z)^i$, hence $(Y)^i\equiv_T(Z)^i$ for all $i$, hence $\{X:\exists i\,(X\le_T(Y)^i)\}=\{X:\exists i\,(X\le_T(Z)^i)\}$. By Lemma 4.5 it follows that $\{((Y)_i)_e:i,e\in\omega\}=\{((Z)_i)_e:i,e\in\omega\}$.$\Box$

Theorem 4.11   There is a nonempty $\Pi ^0_1$ subset of $2^\omega$, $\widehat{Q}'$, with the following properties:

1.

For all $Y\in\widehat{Q}'$, $\{(Y)_m:m\in\omega\}$ is an $\omega$-model of $\mathsf{WKL}_0$.

2.

Any two nonempty $\Pi ^0_1$ subsets of $\widehat{Q}'$ are recursively homeomorphic.

3.

For all nonempty $\Pi ^0_1$ sets $P,Q\subseteq\widehat{Q}'$, there is a recursive homeomorphism $\Psi:P\cong Q$ such that for all $Y\in P$ and $Z\in Q$, if $\Psi(Y)=Z$ then $\{(Y)_m:m\in\omega\}=\{(Z)_m:m\in\omega\}$.

Proof.This follows from Lemmas 4.5 and 4.10 if we let $\widehat{Q}'=\{Y':Y\in\widehat{Q}\}$, where $Y'(((i,e),n))=Y((i,(e,n)))$ for all $i,e,n\in\omega$. (Note: $Y'$ is not the Turing jump of $Y$.)$\Box$

Jockusch/Soare Genericity

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

Definition 5.1   A relation $R\subseteq\omega^k$ is said to be arithmetical if it is first order definable over the standard model of arithmetic $(\omega,{+},{\cdot},0,1,{<},{=})$. We write $\mathrm{REC}=\{A\in2^\omega:A$ is recursive$\}$, and $\mathrm{ARITH}=\{A\in2^\omega:A$ is arithmetical$\}$.

Definition 5.2   Let $\mathcal{P}$ be the set of all nonempty $\Pi ^0_1$ subsets of $2^\omega$. $\mathcal{D}\subseteq\mathcal{P}$ is said to be arithmetical if $\{e\in\omega:P_e\in\mathcal{D}\}$ is arithmetical. $\mathcal{D}$ is said to be dense if for all $P\in\mathcal{P}$ there exists $Q\in\mathcal{D}$ such that $Q\subseteq P$. $G\in2^\omega$ is said to meet $\mathcal{D}$ if there exists $Q\in\mathcal{D}$ such that $G\in Q$. $G$ is said to be Jockusch/Soare generic (cf. Jockusch/Soare [16, proof of Theorem 2.4]), or simply, generic, if $G$ meets every dense arithmetical $\mathcal{D}\subseteq\mathcal{P}$.

Lemma 5.3   Given $P\in\mathcal{P}$, there exists $G\in P$ such that $G$ is generic.

Proof.Let $\mathcal{D}_n$, $n\in\omega$ be an enumeration of the dense arithmetical subsets of $\mathcal{P}$. Construct a sequence $P_0\supseteq P_1\supseteq\ldots P_n\supseteq\ldots$ in $\mathcal{P}$ as follows. Begin with $P_0=P$. Given $P_n$, let $P_{n+1}\subseteq P_n$ be such that $P_{n+1}\in\mathcal{D}_n$. Finally let $G$ be the unique element of $\bigcap_nP_n$. Clearly $G\in P$ and $G$ meets each $\mathcal{D}_n$, hence $G$ is generic.$\Box$

Lemma 5.4   Let $A_i$, $i\in\omega$ be a sequence of nonrecursive elements of $2^\omega$. Given $P\in\mathcal{P}$, there exists $G\in P$ such that $G$ is generic and $\forall i\,(A_i\not\le_TG)$.

Proof.For all $Y\in2^\omega$ we have $A_i\le_TY$ if and only if $\exists e\,\forall n\,(\{e\}^Y(n)=A_i(n))$. For $e,i\in\omega$, put $\mathcal{D}_{e,i}=\{Q\in\mathcal{P}:\exists n\,(\forall Y\in Q)\,(\{e\}^Y(n)\ne A_i(n))\}$. We claim that $\mathcal{D}_{e,i}$ is dense in $\mathcal{P}$. To see this, let $P\in\mathcal{P}$ be given. If $\forall n\,(\forall Y\in P)\,(\{e\}^Y(n)=A_i(n))$, then by Lemma 3.5 $A_i$ is recursive, contrary to assumption. So we have $\exists n\,(\exists Y\in P)\,(\{e\}^Y(n)\ne A_i(n))$. Fix such an $n$ and put $Q=\{Y\in P:\{e\}^Y(n)\ne A_i(n)\}$. Clearly $Q\in\mathcal{P}$ and $Q\subseteq P$ and $Q\in\mathcal{D}_{e,i}$. This proves our claim. Now let $\mathcal{D}_n$, $n\in\omega$ be an enumeration of the dense arithmetical subsets of $\mathcal{P}$. As in the proof of Lemma 5.3, given $P\in\mathcal{P}$ there exists $G\in P$ such that $G$ meets $\mathcal{D}_n$ for all $n$, and $G$ meets $\mathcal{D}_{e,i}$ for all $e,i$. This proves our lemma.$\Box$

Lemma 5.5   Let $G,H\in2^\omega$. Suppose $H\le_TG$ and $G$ is generic. Then $H$ is generic, and $H$ is truth-table reducible to $G$.

Proof.We are assuming $H\le_TG$, so let $e\in\omega$ be such that $\forall n\,(H(n)=\{e\}^G(n))$. Put $\mathcal{D}'_e=\{Q\in\mathcal{P}:$ either $\exists n\,(\forall Y\in Q)\,(\{e\}^Y(n)$ is undefined$)$ or $\forall n\,(\forall Y\in Q)\,(\{e\}^Y(n)$ is defined$)\}$. We claim that $\mathcal{D}'_e$ is dense in $\mathcal{P}$. To see this, given $P\in\mathcal{P}\setminus\mathcal{D}'_e$, we have $\exists n\,(\exists Y\in P)\,(\{e\}^Y(n)$ is undefined$)$, so fix such an $n$ and put $Q=\{Y\in P:\{e\}^Y(n)$ is undefined$\}$. Then clearly $Q\subseteq P$ and $Q\in\mathcal{D}'_e$. This proves our claim. Since $\mathcal{D}'_e$ is dense arithmetical, let $Q\in\mathcal{D}'_e$ be such that $G\in Q$. It follows that $\forall n\,(\forall Y\in Q)\,(\{e\}^Y(n)$ is defined$)$, so we have a recursive functional $\Phi:Q\to2^\omega$ given by $\Phi(Y)(n)=\{e\}^Y(n)$, and $H=\Phi(G)$. Hence by Lemma 3.11 and Remark 3.12, $H$ is truth-table reducible to $G$. To show that $H$ is generic, let $\mathcal{D}\subseteq\mathcal{P}$ be dense arithmetical. Put $\mathcal{D}^{*}=\{Q^{*}\in\mathcal{P}:Q^{*}\cap Q=\emptyset$ or $\Phi(Q^{*}\cap Q)\in\mathcal{D}\}$. By Lemma 3.6, $\mathcal{D}^{*}$ is dense arithmetical. Let $Q^{*}\in\mathcal{D}^{*}$ be such that $G\in Q^{*}$. Then $G\in Q^{*}\cap Q$, so $H=\Phi(G)\in\Phi(Q^{*}\cap Q)\in\mathcal{D}$. This completes the proof.$\Box$

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^\omega$, i.e., a function $Y:\omega\to\{0,1\}$. Let $\varphi(Y)$ be an $L_1(Y)$-sentence. Let $P\in\mathcal{P}$. We say that $P$ forces $\varphi(Y)$ if $\varphi(G)$ holds for all generic $G$ such that $G\in P$.

Lemma 5.7  

1. Let $\varphi(Y)$ be an $L_1(Y)$-sentence. If $G$ is generic, then $\varphi(G)$ holds if and only if there exists $P\in\mathcal{P}$ such that $G\in P$ and $P$ forces $\varphi(Y)$.
2. Let $\varphi(Y,n_1,\dots,n_k)$ be an $L_1(Y)$-formula with free variables $n_1,\dots,n_k$. Then
   $\{(e,n_1,\dots,n_k):P_e\in\mathcal{P}$ and $P_e$ forces $\varphi(Y,n_1,\dots,n_k)\}$
   is arithmetical.

Proof.Parts 1 and 2 are proved together by a straightforward induction on the complexity of $\varphi(Y)$. If $\varphi(Y)$ is atomic, then for all $P\in\mathcal{P}$ we have that $P$ forces $\varphi(Y)$ if and only if $\varphi(Y)$ holds for all $Y\in P$, because $\{Y\in P:\varphi(Y)\}$ and $\{Y\in P:\lnot\,\varphi(Y)\}$ are elements of $\mathcal{P}$. For arbitrary $\varphi(Y)$ and $\psi(Y)$ of $L_1(Y)$, we have that $P\in\mathcal{P}$ forces $\varphi(Y)\lor\psi(Y)$ if and only if $(\forall P'\in\mathcal{P})\,($if $P'\subseteq P$ then $(\exists P''\in\mathcal{P})\,(P''\subseteq P'$ and either $P''$ forces $\varphi(Y)$ or $P''$ forces $\psi(Y)))$. For arbitrary $\varphi(Y,n)$ of $L_1(Y)$, we have that $P\in\mathcal{P}$ forces $\exists n\,\varphi(Y,n)$ if and only if $(\forall P'\in\mathcal{P})\,($if $P'\subseteq P$ then $(\exists P''\in\mathcal{P})\,(\exists n\in\omega)\,(P''\subseteq P'$ and $P''$ forces $\varphi(Y,n)))$. For arbitrary $\varphi(Y)$ of $L_1(Y)$, we have that $P\in\mathcal{P}$ forces $\varphi(Y)$ if and only if $(\forall P'\in\mathcal{P})\,($if $P'\subseteq P$ then $P'$ does not force $\varphi(Y))$.$\Box$

Lemma 5.8   Let $L_2$ be the language of second order arithmetic. Given an $L_2$-sentence $\sigma$, we can find an $L_1(Y)$-sentence $\widetilde{\sigma}(Y)$ such that for all $Y\in2^\omega$, $\widetilde{\sigma}(Y)$ holds if and only if the $\omega$-model $\{(Y)_m:m\in\omega\}$ satisfies $\sigma$.

Proof.The proof is straightforward. Set quantifiers in $\sigma$ are translated as number quantifiers in $\widetilde{\sigma}(Y)$.$\Box$

Lemma 5.9   With $\widehat{Q}'$ as in Theorem 4.11, let $G,H\in\widehat{Q}'$ be generic. Then the $\omega$-models $\{(G)_m:m\in\omega\}$ and $\{(H)_m:m\in\omega\}$ satisfy the same $L_2$-sentences.

Proof.Suppose $\{(G)_m:m\in\omega\}$ and $\{(H)_m:m\in\omega\}$ satisfy $\sigma$ and $\lnot\,\sigma$ respectively. Then $\widetilde{\sigma}(G)$ and $\lnot\,\widetilde{\sigma}(H)$ hold. By part 1 of Lemma 5.7, there exist $P,Q\in\mathcal{P}$ such that $G\in P$ and $H\in Q$ and $P$ forces $\widetilde{\sigma}(Y)$ and $Q$ forces $\lnot\,\widetilde{\sigma}(Y)$. Since $G,H\in\widehat{Q}'$, we may safely assume that $P,Q\subseteq\widehat{Q}'$. Let $\Psi:P\cong Q$ be a recursive homeomorphism as in part 3 of Theorem 4.11. By Lemma 5.5 we have that $G^{*}=\Psi(G)\in Q$ is generic. Since $Q$ forces $\lnot\,\widetilde{\sigma}(Y)$, it follows that $\lnot\,\widetilde{\sigma}(G^{*})$ holds, i.e., $\{(G^{*})_m:m\in\omega\}\models\lnot\,\sigma$. But, by part 3 of Theorem 4.11, we have that $\{(G)_m:m\in\omega\}=\{(G^{*})_m:m\in\omega\}$. This contradiction proves our lemma.$\Box$

Lemma 5.10   Consider an $\omega$-model $S=\{(G)_m:m\in\omega\}$ where $G\in\widehat{Q}'$ and $G$ is generic.

1. For $L_2$-sentences $\sigma$, we have that $S\models\sigma$ if and only if $\widehat{Q}'$ forces $\widetilde{\sigma}(Y)$.
2. For relations $R\subseteq\omega^k$, we have that $R$ is definable over $S$ without parameters if and only if $R$ is arithmetical.
3. For $A\in 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\in S$ and $A$ is definable without parameters over $S$. Let $\varphi(Z)$ be an $L_2$-formula with one free set variable, $Z$, such that $A$ is the unique $Z\in S$ such that $S\models\varphi(Z)$. Letting $\sigma$ be the $L_2$-sentence $(\exists$ unique $Z)\,\varphi(Z)$, we have that $S\models\sigma$. By part 1 we have that $\widehat{Q}'$ forces $\widetilde{\sigma}(Y)$. By Lemma 5.4, let $H\in\widehat{Q}'$ be generic such that $(\forall Z\in S)\,($if $Z\notin\mathrm{REC}$ then $Z\not\le_TH)$. Consider the $\omega$-model $T=\{(H)_m:m\in\omega\}$. Then $S\cap T=\mathrm{REC}$. Since $H\in\widehat{Q}'$ and $H$ is generic and $\widehat{Q}'$ forces $\widetilde{\sigma}(Y)$, we have that $\widetilde{\sigma}(H)$ holds, i.e., $T\models\sigma$. Let $B$ be the unique $Z\in T$ such that $T\models\varphi(Z)$. We claim that $A=B$. This is clear from Lemma 5.9, because for all $n\in\omega$ and $k=0,1$, we have $A(n)=k$ if and only if $S\models\exists Z\,(\varphi(Z)$ and $Z(n)=k)$, if and only if $T\models\exists Z\,(\varphi(Z)$ and $Z(n)=k)$, if and only if $B(n)=k$. Since $A=B$, it follows that $A\in\mathrm{REC}$.$\Box$

Theorem 5.11   There is a countable $\omega$-model $S$ of $\mathsf{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.$\Box$

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

Relative Genericity and Definability

In this section we prove a key lemma concerning relativized Jockusch/
[0]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\in2^\omega$. We use $\mathcal{P}^X$ to denote the set of nonempty $\Pi^{0,X}_1$ subsets of $2^\omega$. (See Definition 4.1.) $\mathcal{D}^X\subseteq\mathcal{P}^X$ is said to be arithmetical in $X$ if $\{e:P^X_e\in\mathcal{D}^X\}$ is arithmetical in $X$, i.e., definable over $(\omega,{+},{\cdot},0,1,{<},{=},X)$ by a formula of $L_1(X)$. $G\in2^\omega$ is said to be Jockusch/Soare generic over $X$, or simply, generic over $X$, if $G$ meets every dense subset of $\mathcal{P}^X$ which is arithmetical in $X$.

Lemma 6.2   Let $G,X\in2^\omega$. Suppose $X\le_TG$ and $G$ is generic. Then $G$ is generic over $X$.

Proof.Let $\mathcal{D}^X\subseteq\mathcal{P}^X$ be given such that $\mathcal{D}^X$ is dense in $\mathcal{P}^X$ and arithmetical in $X$. We need to show that $G$ meets $\mathcal{D}^X$. By Lemma 5.5, there are a $\Pi ^0_1$ set $Q\subseteq2^\omega$ and a recursive functional $\Phi:Q\to2^\omega$ such that $\Phi(G)=X$. It suffices to show that $Q$ forces $($if $\mathcal{D}^{\Phi(Y)}$ is dense in $\mathcal{P}^{\Phi(Y)}$ then $Y$ meets $\mathcal{D}^{\Phi(Y)})$. Equivalently, we shall show $(\forall Q'\in\mathcal{P})\,($if $Q'\subseteq Q$ and $Q'$ forces $(\mathcal{D}^{\Phi(Y)}$ is dense in $\mathcal{P}^{\Phi(Y)})$, then $(\exists Q''\in\mathcal{P})\,(Q''\subseteq Q'$ and $Q''$ forces $(Y$ meets $\mathcal{D}^{\Phi(Y)})))$. To see this, let $Q'\in\mathcal{P}$ be given such that $Q'\subseteq Q$ and $Q'$ forces $(\mathcal{D}^{\Phi(Y)}$ is dense in $\mathcal{P}^{\Phi(Y)})$. Put $P'=\Phi(Q')$. Using $L_1(X)$ as our forcing language, we have that $P'$ forces $(\mathcal{D}^X$ is dense in $\mathcal{P}^X)$. In particular, since $P'$ forces $Q'\cap\Phi^{-1}(X)\in\mathcal{P}^X$, it follows that $P'$ forces $\exists e\,(P^X_e\in\mathcal{D}^X$ and $P^X_e\subseteq Q'\cap\Phi^{-1}(X))$. Let $e\in\omega$ and $P''\in\mathcal{P}$ be such that $P''\subseteq P'$ and $P''$ forces $(P^X_e\in\mathcal{D}^X$ and $P^X_e\subseteq Q'\cap\Phi^{-1}(X))$. Put $Q''=\{Y\in Q':\Phi(Y)\in P''$ and $Y\in P^{\Phi(Y)}_e\}$. Then $Q''\in\mathcal{P}$, $Q''\subseteq Q'$, and $Q''$ forces $(Y\in P^{\Phi(Y)}_e$ and $P^{\Phi(Y)}_e\in\mathcal{D}^{\Phi(Y)})$, i.e., $Q''$ forces $(Y$ meets $\mathcal{D}^{\Phi(Y)})$. This proves our lemma.$\Box$

Lemma 6.3   Let $X\in2^\omega$ be given. Suppose $P^X,Q^X\in\mathcal{P}^X$, and suppose $\Phi^X:P^X\cong Q^X$ is an $X$-recursive homeomorphism of $P^X$ onto $Q^X$. If $G\in P^X$ is generic over $X$, then $\Phi^X(G)\in Q^X$ is generic over $X$.

Proof.This follows from a straightforward relativization to $X$ of Lemma 5.5.$\Box$

Definition 6.4   Let $\widehat{P}$ be as in Lemma 4.2. Relativizing Definition 4.4, put

$\widehat{Q}^X=\{Y\in2^\omega:\forall i\,\widehat{P}(X\oplus(Y)^i,(Y)_i)\}$ for all $X\in2^\omega$. Clearly $\widehat{Q}^X\in\mathcal{P}^X$.

Lemma 6.5   Let $X\in2^\omega$ be given. For all $Y\in\widehat{Q}^X$ we have

$\{((Y)_i)_e:i,e\in\omega\}=\{W\in2^\omega:\exists i\,(W\le_T(Y)^i)\}$

and this is an $\omega$-model of $\mathsf{WKL}_0$ containing $X$.

Proof.A straightforward relativization to $X$ of Lemma 4.5 shows that, for all $Y\in\widehat{Q}^X$, $\{((Y)_i)_e:i,e\in\omega\}=\{W\in2^\omega:W\le_T(Y)^i\}$ and this is an $\omega$-model of $\mathsf{WKL}_0$. Clearly $\{X\}$ is $\Pi^{0,X}_1$, hence $\{X\}=P^{X\oplus(Y)^0}_e$ for an appropriate $e$, hence $X=((Y)_1)_e$.$\Box$

Lemma 6.6   Consider an $\omega$-model $S=\{((G)_i)_e:i,e\in\omega\}$ where $G\in\widehat{Q}$ and $G$ is generic. For all $A\in S$, if $A$ is definable over $S$, then $A$ is recursive.

Proof.The proof of Theorem 4.11 shows that $\widehat{Q}\cong\widehat{Q}'$ via a recursive homeomorphism $Y\mapsto Y'$ such that, for all $Y\in\widehat{Q}$, $\{((Y)_i)_e:i,e\in\omega\}=\{(Y')_m:m\in\omega\}$. In particular, $S=\{(G')_m:m\in\omega\}$ where $G'\in\widehat{Q}'$. Furthermore, by Lemma 5.5, $G'$ is generic. Part 3 of Lemma 5.10 now gives the desired conclusion.$\Box$

Lemma 6.7   Let $X\in2^\omega$ be given. Consider an $\omega$-model $S=\{((G)_i)_e:i,e\in\omega\}$ where $G\in\widehat{Q}^X$ and $G$ is generic over $X$. For all $A\in S$, if $A$ is definable over $S$ from $X$, then $A\le_TX$.

Proof.This is a straightforward relativization to $X$ of Lemma 6.6.$\Box$

Lemma 6.8   Let $X\in2^\omega$ and $i^{*},e^{*}\in\omega$ be given. Put

$\widehat{Q}^X_{*}=\{Y\in\widehat{Q}:((Y)_{i^{*}})_{e^{*}}=X\}$.

If $\widehat{Q}^X_{*}$ is nonempty, then there exists an $X$-recursive homeomorphism $\Psi^X_{*}:\widehat{Q}^X_{*}\cong\widehat{Q}^X$ such that for all $Y\in\widehat{Q}^X_{*}$, putting $Y_{*}=\Psi^X_{*}(Y)$, we have $\{((Y)_i)_e:i,e\in\omega\}=\{((Y_{*})_i)_e:i,e\in\omega\}$.

Proof.As in the proof of Lemma 4.9, construct a recursive sequence of $X$-recursive homeomorphisms $\Psi^{X,i}_{*}:(\widehat{Q}^X_{*})^{i^{*}+i+2}\cong(\widehat{Q}^X)^{i+1}$, $i\in\omega$, such that $\Psi^{X,i}_{*}((Y)^{i^{*}+i+2})=(\Psi^{X,i+1}_{*}((Y)^{i^{*}+i+3}))^{i+1}$ for all $Y\in\widehat{Q}^X_{*}$. Define $\Psi^X_{*}=\lim_i\Psi^{X,i}_{*}$. Then $\Psi^X_{*}:\widehat{Q}^X_{*}\cong\widehat{Q}^X$ is an $X$-recursive homeomorphism. Furthermore, for $Y\in\widehat{Q}^X_{*}$ and $Y_{*}=\Psi^X_{*}(Y)$, we have $(Y)^{i^{*}+i+2}\equiv_T(Y_{*})^{i+1}$ for all $i\in\omega$. Hence $\{W:\exists i\,(W\le_T(Y)^i)\}=\{W:\exists i\,(W\le_T(Y_{*})^i)\}$. By Lemmas 4.5 and 6.5, it follows that $\{((Y)_i)_e:i,e\in\omega\}=\{((Y_{*})_i)_e:i,e\in\omega\}$.$\Box$

Theorem 6.9   There is a countable $\omega$-model of $\mathsf{WKL}_0$ satisfying $\forall X\,\forall Z\,($if $Z$ is definable from $X$ then $Z\le_TX)$.

Proof.Let $G\in\widehat{Q}$ be generic, and put $S=\{((G)_i)_e:i,e\in\omega\}$. By Lemma 4.5, $S$ is an $\omega$-model of $\mathsf{WKL}_0$. Fix $X\in S$. Fix $i^{*},e^{*}\in\omega$ such that $X=((G)_{i^{*}})_{e^{*}}$. As in Lemma 6.8, put $\widehat{Q}^X_{*}=\{Y\in\widehat{Q}:((Y)_{i^{*}})_{e^{*}}=X\}$, and let $\Psi^X_{*}$ be an $X$-recursive homeomorphism of $\widehat{Q}^X_{*}$ onto $\widehat{Q}^X$. We have $G\in\widehat{Q}^X_{*}$. Put $G_{*}=\Psi^X_{*}(G)\in\widehat{Q}^X$. By Lemma 6.8, $S=\{((G_{*})_i)_e:i,e\in\omega\}$. 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\in S$, if $A$ is definable over $S$ from $X$, then $A\le_TX$. This completes the proof.$\Box$

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

Generalization to Non-$\omega$-Models

In this section we generalize the results of §§3,4,5,6 to countable non-$\omega$-models of $\mathsf{WKL}_0$.

As in [30, Remark I.7.6], let $\Sigma^0_1$-$\mathsf{PA}$ be first order Peano arithmetic with the induction scheme restricted to $\Sigma^0_1$ formulas. The following theorem is well known.

Theorem 7.1   Let $N=(\vert N\vert,{+}_N,{\cdot}_N,0_N,1_N,{<}_N,{=}_N)$ be a countable model of $\Sigma^0_1$-$\mathsf{PA}$. Then there exists a countable $S\subseteq P(\vert N\vert)$ such that $(N,S)\models\mathsf{WKL}_0$.

Proof.This result is originally due to Harrington (1977, unpublished). The proof is in Simpson [30, §IX.2].$\Box$

Thus any countable model of $\Sigma^0_1$-$\mathsf{PA}$ is the first order part of a countable model of $\mathsf{WKL}_0$. It follows by the Gödel Completeness Theorem that $\Sigma^0_1$-$\mathsf{PA}$ is the first order part of $\mathsf{WKL}_0$. (See Simpson [30, §IX.2].) We shall strengthen these results below (Theorems 7.6 and 7.8, Corollary 7.9).

Let $N$ be a countable model of $\Sigma^0_1$-$\mathsf{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 [21]. Let $\Delta^0_1$- $\mathrm{Def}(N)$ be the set of all $A\subseteq\vert N\vert$ such that $A$ is $\Delta^0_1$ definable over $N$, i.e., both $\Sigma^0_1$ and $\Pi ^0_1$ definable over $N$ allowing parameters from $\vert N\vert$. We describe sets $A\in\Delta^0_1$- $\mathrm{Def}(N)$ as being $N$-recursive. It is known from Simpson [30, § IX.1] that $\Delta^0_1$- $\mathrm{Def}(N)$ is the smallest $S\subseteq P(\vert N\vert)$ such that $(N,S)\models\mathsf{RCA}_0$. Thus $\Delta^0_1$- $\mathrm{Def}(N)$ in $N$-recursion theory plays the role of $\mathrm{REC}$ in classical recursion theory.

A set $F\subseteq\vert N\vert$ 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\in\vert N\vert$ such that $F=F_n=\{m\in\vert N\vert:N\models mEn\}$, where $mEn$ is the usual $\Sigma^0_0$ formula asserting that $2^m$ occurs in the binary expansion of $n$, i.e., $(\exists x<n)\,(\exists y<2^m)\,(n=(2x+1)2^m+y)$. Compare Rogers [24, §5.6]. The $N$-finite sets play the role of finite sets in classical recursion theory. A set $A\subseteq\vert N\vert$ is said to be $N$-regular if $A\cap F$ is $N$-finite for each $N$-finite $F\subseteq\vert N\vert$. By Bounded $\Sigma^0_1$ Comprehension [30, 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\subseteq P(\vert N\vert)$ is such that $(N,S)\models\mathsf{RCA}_0$, then every $A\in S$ is necessarily $N$-regular.

We denote by $(2^\omega)_N$ the set of all $N$-regular functions $X:\vert N\vert\to\{0,1\}$. We denote by $(2^{<\omega})_N$ the set of $N$-strings, i.e., ($N$-canonical indices of) $N$-finite sequences of $0$'s and $1$'s. Clearly $(2^{<\omega})_N$ and the length function $\mathrm{lh}_N:(2^{<\omega})_N\to\vert N\vert$ are $N$-recursive. For $X\in(2^\omega)_N$ and $n\in\vert N\vert$, we have an $N$-string $X[n]=\langle X(0),\dots,X(n-1)\rangle\in(2^{<\omega})_N$ of length $n$. We denote by $\mathcal{P}_N$ the set of nonempty sets of the form $\{X\in(2^\omega)_N:(\forall n\in\vert N\vert)\,(X[n]\in T)\}$ where $T\subseteq(2^{<\omega})_N$ is $N$-recursive. The sets $P\in\mathcal{P}_N$ in $N$-recursion theory play the role of nonempty $\Pi ^0_1$ subsets of $2^\omega$ in classical recursion theory.

We say that $P\in\mathcal{P}_N$ is complete if for every $Q\in\mathcal{P}_N$ there exists an $N$-recursive functional $\Phi:P\to Q$. Generalizing Theorem 3.21, we have:

Theorem 7.2   Let $N$ be a countable model of $\Sigma^0_1$-$\mathsf{PA}$, and let $P,Q\in\mathcal{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 $\Phi:P\cong Q$.

Proof.This is a straightforward generalization of the arguments of §3.$\Box$

Generalizing Theorem 4.11, we have:

Theorem 7.3   Let $N$ be a countable model of $\Sigma^0_1$-$\mathsf{PA}$. We can find $(\widehat{Q}')_N\in\mathcal{P}_N$ with the following properties:

1.

For all $Y\in(\widehat{Q}')_N$, if $(N,\{(Y)_n:n\in\vert N\vert\})\models\mathsf{RCA}_0$ then $(N,\{(Y)_n:n\in\vert N\vert\})\models\mathsf{WKL}_0$.

2.

For all $P,Q\in\mathcal{P}_N$ such that $P,Q\subseteq(\widehat{Q}')_N$, there exists an $N$-recursive functional $\Psi:P\cong Q$ such that for all $Y\in P$ and $Z\in Q$, if $\Psi(Y)=Z$ then $\{(Y)_n:n\in\vert N\vert\}=\{(Z)_n:n\in\vert N\vert\}$.

Proof.This is a straightforward generalization of the arguments of §4.$\Box$

For $G\in(2^\omega)_N$ the notion of Jockusch/Soare genericity over $N$ is defined in the obvious way, in terms of dense subsets of $\mathcal{P}_N$ which are definable over $N$ allowing parameters from $\vert N\vert$. This notion is equivalent to genericity over $(N,\Delta^0_1$- $\mathrm{Def}(N))$ in the sense of Simpson [30, § IX.2]. Generalizing Lemma 5.3, we have:

Lemma 7.4   Let $N$ be a countable model of $\Sigma^0_1$-$\mathsf{PA}$. For any $P\in\mathcal{P}_N$ there exists $G\in P$ such that $G$ is Jockusch/Soare generic over $N$. For any such $G$ we have $(N,\Delta^0_1$- $\mathrm{Def}(N,G))\models\mathsf{RCA}_0$.

Proof.See Simpson [30, §IX.2].$\Box$

Generalizing Lemma 5.4, we have:

Lemma 7.5   Let $N$ be a countable model of $\Sigma^0_1$-$\mathsf{PA}$, and suppose

$\{A_i:i\in\omega\}\cap\Delta^0_1$- $\mathrm{Def}(N)=\emptyset$.

Then for any $P\in\mathcal{P}_N$ there exists $G\in P$ such that

$\{A_i:i\in\omega\}\cap\Delta^0_1$- $\mathrm{Def}(N,G)=\emptyset$,

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.$\Box$

Generalizing Theorem 5.11, we have:

Theorem 7.6   Let $N$ be a countable model of $\Sigma^0_1$-$\mathsf{PA}$. Then there exists a countable $S\subseteq P(\vert N\vert)$ such that $(N,S)\models\mathsf{WKL}_0$ and furthermore, every element of $S$ which is definable over $(N,S)$ allowing parameters from $\vert N\vert$ is $N$-recursive.

Proof.This is a straightforward generalization of the arguments of §5.$\Box$

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

Generalizing Theorem 6.9, we have:

Theorem 7.8   Let $N$ be a countable model of $\Sigma^0_1$-$\mathsf{PA}$. Then there exists a countable $S\subseteq P(\vert N\vert)$ such that $(N,S)\models\mathsf{WKL}_0$ and furthermore, for all $X,Z\in S$, if $Z$ is definable over $(N,S)$ allowing parameters from $\vert N\vert\cup\{X\}$, then $Z\in\Delta^0_1$- $\mathrm{Def}(N,X)$.

Proof.This is a straightforward generalization of the arguments of §6.$\Box$

Corollary 7.9   $\Sigma^0_1$-$\mathsf{PA}$ is the first order part of the $L_2$-theory consisting of $\mathsf{WKL}_0$ plus the following scheme:

$\forall X\,($if $(\exists$ exactly one $Z)\,\varphi(X,Z)$ then $(\exists Z)\,(Z\le_T X$ and $\varphi(X,Z)))$,

where $\varphi(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.$\Box$

A Result of Kucera

In this section we present a simplified proof of a recursion-theoretic result of Kucera [19]. 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 $\Sigma^0_1$-$\mathsf{PA}$.

Lemma 8.1   There exists a recursively enumerable set $A\subseteq\omega$ such that the complement $\overline{A}$ is infinite and, for all $x$, if $\{x\}(x)\downarrow$ then $\{x\}_{a_x}(x)\downarrow$, where

$$\overline{A}=\{a_0<a_1<\cdots<a_x<\cdots\}\,.$$

Proof.We use a movable marker argument, as in Rogers [24, pages 235-236]. We shall have $a_x=\lim_sa_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<\cdots<a_x^s<\cdots\}\,.$$

Stage $0$. Begin by defining $a_x^0=x$ for all $x$. In other words, $A^0=\emptyset$.

Stage $s+1$. Let $x_s$ be the least $x$ such that $\{x\}_s(x)\downarrow$ and $\{x\}_{a_x^s}(x)\uparrow$. 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\cup\{a_x^s,\ldots,a_{s-1}^s\}$. Thus

$$a_x^{s+1}=\left\{ \begin{array}{ll} a_x^s&\mbox{ if }x<x_s,\\ a_{s+x-x_s}^s&\mbox{ if }x\ge x_s. \end{array} \right.$$

and in particular $a_{x_s}^{s+1}=a_s^s\ge s$.

Finally put $A=\bigcup_sA^s$. Clearly $A$ is a recursively enumerable set. Note that $x_s$ takes on each possible value at most once. Hence $x_s\to\infty$ as $s\to\infty$, and it is clear that the construction works.$\Box$

The following lemma is a strengthening due to K. Ohashi of the well-known Splitting Theorem of R. Friedberg. See Rogers [24, 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\cup B_2$.

Proof.Let $f:\omega\to\omega$ be a one-to-one recursive function such that $A$ is the range of $f$. Put $A^s=\{f(0),\ldots,f(s)\}$. Let $W_x$ ($x\in\omega$) 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,\dots$ there is a requirement $R_{2x+i}$ to the effect that $B_i\cap W_x\ne\emptyset$ ``if possible''. The ordering of the requirements is $R_1,R_2,\dots,R_{2x+1},R_{2x+2},\dots$.

Stage $0$. Put $B_1^0=B_2^0=\emptyset$.

Stage $s+1$. Let $x_s$ be the least $x$ such that $f(s)\in W_x^s$ and either $B_1^s\cap W_x^s=\emptyset$ or $B_2^s\cap W_x^s=\emptyset$. If $x_s$ does not exist, or if $B_1^s\cap W_x^s=\emptyset$, put $f(s)$ into $B_1$, i.e., $B_1^{s+1}=B_1^s\cup\{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\cup\{f(s)\}$.

Finally put $B_1=\bigcup_sB_1^s$ and $B_2=\bigcup_sB_2^s$. Clearly $B_1$ and $B_2$ are recursively enumerable sets, and $A=B_1\cup B_2$. It is also clear that $x_s$ takes on each possible value at most twice, hence $x_s\to\infty$ as $s\to\infty$.

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\subseteq X$ and $B_2\cap X=\emptyset$. Let $x$ and $y$ be such that $W_x=X$ and $W_y=\overline{X}$. Then $W_x\cap B_2=\emptyset$ and $W_y\cap B_1=\emptyset$. For all sufficiently large $s$ we have $x_s>x,y$, hence $f(s)\notin W_x^s\cup W_y^s$. Thus there is a finite set $F$ such that for all $a\in A\setminus F$ there exists $s$ such that $a\in A^s\setminus(W_x^s\cup W_y^s)$. On the other hand, we also have that for all $a\in\overline{A}$ there exists $s$ such that $a\in(W_x^s\cup W_y^s)\setminus A^s$. It follows that $A$ is recursive, a contradiction.$\Box$

The following theorem and its corollaries are due to Kucera [19].

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\bigtriangleup Y=(X\setminus Y)\cup(Y\setminus X)$ we have that either $X\bigtriangleup Y$ is finite or $K\le_T X\bigtriangleup Y$. Here $K=\{x:\{x\}(x)\downarrow\}$, the complete recursively enumerable set.

Proof.Let $A$ be a recursively enumerable set as in Lemma 8.1. Then clearly $K\le_TZ$ for any infinite set $Z\subseteq\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\cup B_2$. Now let $X$ and $Y$ be separating sets. Then $B_1\subseteq X\cap Y$ and $B_2\cap(X\cup Y)=\emptyset$. Hence $X\bigtriangleup Y\subseteq\overline{A}$ and we have our result.$\Box$

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

Corollary 8.4   There exists a nonempty $\Pi ^0_1$ set $P\subseteq2^\omega$ with no recursive elements, such that if $\mathbf{a}$ and $\mathbf{b}$ are Turing degrees of elements of $P$, then either $\mathbf{a}=\mathbf{b}$ or $\mathbf{a}\cup\mathbf{b}\ge\mathbf{0'}$.

Proof.Let $B_1,B_2$ be as in Theorem 8.3. Let $P$ be the $\Pi ^0_1$ set of (characteristic functions of) separating sets for $B_1,B_2$. If $\mathbf{a}$ and $\mathbf{b}$ are the Turing degrees of $X,Y\in P$ respectively, it follows from the conclusion of Theorem 8.3 that either $\mathbf{a}=\mathbf{b}$ or $\mathbf{a}\cup\mathbf{b}\ge\mathbf{0'}$.$\Box$

If $\mathbf{a}$ is a Turing degree, we write $\mathbf{a}\gg\mathbf{0}$ to mean that every nonempty $\Pi ^0_1$ subset of $2^\omega$ contains at least one element of Turing degree $\le\mathbf{a}$. This is equivalent to $\mathbf{a}$ being the degree of a complete extension of Peano arithmetic. See also Jockusch/Soare [16] and Simpson [27, §6]. It is known that there exist $\mathbf{a}\gg\mathbf{0}$ and $\mathbf{b}\gg\mathbf{0}$ such that $\mathbf{a}\cap\mathbf{b}=\mathbf{0}$. We now get:

Corollary 8.5   If $\mathbf{a}\gg\mathbf{0}$ and $\mathbf{b}\gg\mathbf{0}$ and $\mathbf{a}\cap\mathbf{b}=\mathbf{0}$, then $\mathbf{a}\cup\mathbf{b}\ge\mathbf{0'}$.

An Application to $\omega$-Models

In this section we apply Kucera's result to the study of $\omega$-models of $\mathsf{WKL}_0$. For background on this subject, see Simpson [30, §VIII.2].

It is known that minimal $\omega$-models of $\mathsf{WKL}_0$ do not exist, i.e., every $\omega$-model of $\mathsf{WKL}_0$ has a proper $\omega$-submodel of $\mathsf{WKL}_0$. It is also known that the intersection of all $\omega$-models of $\mathsf{WKL}_0$ is $\mathrm{REC}$, the set of recursive sets. We now have:

Theorem 9.1   There exists a countable $\omega$-model $S$ of $\mathsf{WKL}_0$ such that

$\bigcap\{S'\subseteq S:S'$ is an $\omega$-model of $\mathsf{WKL}_0\}\ne\mathrm{REC}.$

Here $\mathrm{REC}$ is the set of recursive sets.

Proof.Let $B_1,B_2$ be as in Theorem 8.3. Since $\mathsf{WKL}_0$ proves $\Sigma^0_1$ separation [30, Lemma IV.4.4], every $\omega$-model of $\mathsf{WKL}_0$ contains a separating set for $B_1,B_2$. Let $S$ be an $\omega$-model of $\mathsf{WKL}_0$ such that $K\notin S$, where $K$ is the complete recursively enumerable set. Let $X\in S$ be a separating set for $B_1,B_2$. Obviously $X$ is not recursive. We claim that $X\in \bigcap\{S'\subseteq S:S'\models\mathsf{WKL}_0\}$. Given $S'\subseteq S$ such that $S'\models\mathsf{WKL}_0$, let $Y\in S'$ be a separating set for $B_1,B_2$. Since $X,Y\in S$ but $K\notin S$, the conclusion of Theorem 8.3 implies that the symmetric difference $X\bigtriangleup Y$ is finite. Since $Y\in S'$, it follows that $X\in S'$. This gives our result.$\Box$

Remark 9.2   For any $\omega$-model $S$ of $\mathsf{WKL}_0$, it can be shown that $\bigcap\{S'\subseteq S:S'$ is an $\omega$-model of $\mathsf{WKL}_0\}=\mathrm{REC}$ if and only if $K\in S$.

The above theorem concerning $\omega$-models of $\mathsf{WKL}_0$ is in contrast to the following theorem of Simpson [30, Corollary VIII.6.10] concerning $\beta$-models of $\mathsf{ATR}_0$. This is one instance where the well-known analogy [30, pages 40 and 314] between $\omega$-models of $\mathsf{WKL}_0$ and $\beta$-models of $\mathsf{ATR}_0$ breaks down.

Theorem 9.3   If $S$ is a $\beta$-model of $\mathsf{ATR}_0$, then

$\bigcap\{S'\subseteq S:S'$ is a $\beta$-model of $\mathsf{ATR}_0\}=\mathrm{HYP}.$

Here $\mathrm{HYP}$ is the set of hyperarithmetical sets.

Actually Simpson [30, Corollary VIII.6.10] obtains not only Theorem 9.3 for $\beta$-models of $\mathsf{ATR}_0$, but also an appropriate generalization for arbitrary models of $\mathsf{ATR}_0$.

Applications to Non-$\omega$-Models

In this section we generalize Kucera's result and apply the generalization to the study of non-$\omega$-models of $\mathsf{WKL}_0$. For background on non-$\omega$-models of $\mathsf{WKL}_0$, see Simpson [30, § VIII.2].

Lemma 10.1   There exists a $\Sigma^0_1$ formula $\varphi(n,i)$ with the following properties. Let $\psi(X)$ be the $\Pi ^0_1$ formula $\forall n\,((\varphi(n,1)\rightarrow n\in X)\land(\varphi(n,0)\rightarrow n\notin X))$. Then

1.

$\mathsf{WKL}_0$ proves $\exists X\,\psi(X)$.

2.

$\mathsf{RCA}_0$ proves $\forall X\,(\psi(X)\rightarrow X$ is not recursive$)$.

3.

$\mathsf{RCA}_0$ proves $\forall X\,\forall Y\,((\psi(X)\land\psi(Y))\rightarrow (X\bigtriangleup Y$ is finite or $K\le_TX\bigtriangleup 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 $\varphi(n,i)\equiv(n\in B_1\land i=1)\lor(n\in B_2\land i=0)$. The key point for the success of the priority argument for Lemma 8.2 is that $x_s\to\infty$ as $s\to\infty$. This is provable in $\mathsf{RCA}_0$ because of Bounded $\Sigma^0_1$ Comprehension [30, Theorem II.3.9].$\Box$

Remark 10.2   For applications of Bounded $\Sigma^0_1$ Comprehension in formalization of more sophisticated priority arguments, see Mytilinaios [21].

Theorem 10.3   Let $(N,S)$ be a model of $\mathsf{WKL}_0\,\,+$ ``$K$ does not exist''. Then with the $\Pi ^0_1$ formula $\psi(X)$ of Lemma 10.1, we have that $(N,S)$ satisfies

1.

$\exists X\,\psi(X)$

2.

$\forall X\,(\psi(X)\rightarrow X$ is not recursive$)$

3.

$\forall X\,\forall Y\,((\psi(X)\land\psi(Y))\rightarrow X\bigtriangleup Y$ is finite$)$.

Furthermore, $\bigcap\{S'\subseteq S:(N,S')\models\mathsf{WKL}_0\}\ne\Delta^0_1$- $\mathrm{Def}(N)$.

Proof.That $(N,S)$ satisfies 1, 2, 3 is immediate from Lemma 10.1. Let $X\in S$ be such that $(N,S)\models\psi(X)$. Then $X\notin\Delta^0_1$- $\mathrm{Def}(N)$, but for every $S'\subseteq S$ such that $(N,S')\models\mathsf{WKL}_0$ we have $X\in S'$. See also Theorem 9.1 and its proof.$\Box$

Remark 10.4   Friedman [11, Theorem 1.7] states the following result: If $\varphi(X)$ is an arithmetical formula and $\mathsf{WKL}$ proves $\exists X\,(\varphi(X)\land X$ is not recursive$)$, then $\mathsf{WKL}$ proves $\forall X\,\exists Y\,(\varphi(Y)\land Y$ is not recursive $\land\,\,\forall n\,(Y\ne(X)_n))$. But this is refuted by our Theorem 10.3, taking $\varphi(X)$ to be the $\Pi ^0_1$ formula $\psi(X)$.

As in §7, let $\Sigma^0_1$-$\mathsf{PA}$ be first order Peano arithmetic with the induction scheme restricted to $\Sigma^0_1$ formulas. For $k\ge1$ we define $\Sigma^0_k$-$\mathsf{PA}$ similarly, with the induction scheme restricted to $\Sigma^0_k$ formulas.

Corollary 10.5   Any countable model of $\Sigma^0_1$-$\mathsf{PA}$ is the first order part of a countable model of $\mathsf{WKL}_0$ with the properties mentioned in Theorem 10.3.

Proof.Let $N$ be a countable model of $\Sigma^0_1$-$\mathsf{PA}$. By [30, Exercise IX.2.8], there exists a countable $S\subseteq P(\vert N\vert)$ such that $(N,S)$ is a model of $\mathsf{WKL}_0\,\,+$ ``$K$ does not exist''. Our result now follows from Theorem 10.3.$\Box$

Corollary 10.6   Let $N$ be a model of $\Sigma^0_1$-$\mathsf{PA}$ which is not a model of $\Sigma^0_2$-$\mathsf{PA}$. Then any model of $\mathsf{WKL}_0$ having $N$ as its first order part has the properties mentioned in Theorem 10.3.

Proof.Any model of $\mathsf{WKL}_0$ having $N$ as its first order part is of the form $(N,S)$ where $S\subseteq P(\vert N\vert)$. We claim that $(N,S)$ necessarily satisfies ``$K$ does not exist''. Otherwise, let $K\in S$ be such that $(N,S)\models$ ``$K$ is the complete recursively enumerable set''. Clearly any $\Sigma^0_2$ formula without set parameters is equivalent over $(N,S)$ to a $\Sigma^0_1$ formula with parameter $K$. Since $\mathsf{WKL}_0$ includes induction for all $\Sigma^0_1$ formulas with set parameters, $(N,S)$ satisfies induction for all $\Sigma^0_1$ formulas with parameter $K$. Hence $(N,S)$ satisfies induction for all $\Sigma^0_2$ formulas without set parameters. In other words, $N\models\Sigma^0_2$-$\mathsf{PA}$, a contradiction. This proves the claim. Our result now follows from Theorem 10.3.$\Box$

Theorem 10.7   There is a $\Pi ^0_1$ formula $\widetilde{\psi}(X)$ with no free variables other than $X$, such that

1.

$\mathsf{WKL}_0$ proves $\exists X\,\widetilde\psi(X)$.

2.

$\mathsf{RCA}_0$ proves $\forall X\,\forall Y\,((\widetilde\psi(X)\land\widetilde\psi(Y))\rightarrow X\bigtriangleup Y$ is finite$)$.

3.

$\mathsf{WKL}_0$ does not prove $(\exists$ recursive $X)\,\widetilde\psi(X)$.

4.

$\mathsf{RCA}_0$ does not prove $\exists X\,\widetilde\psi(X)$.

Proof.Let $\psi(X)$ be the $\Pi ^0_1$ formula of Lemma 10.1. Let $\forall n\,\theta(n)$ be a $\Pi ^0_1$ sentence which is provable in $\Sigma^0_2$-$\mathsf{PA}$ but not in $\Sigma^0_1$-$\mathsf{PA}$. (For instance, we may take $\forall n\,\theta(n)$ to be the $\Pi ^0_1$ sentence expressing consistency of $\Sigma^0_1$-$\mathsf{PA}$.) We may assume that $\theta(n)$ is $\Sigma^0_0$. Let $\widetilde\psi(X)$ be the $\Pi ^0_1$ formula

$\forall n\,($if $(\forall m\le n)\,(m\notin X)$ then $\theta(n))$, and
$\forall n\,($if $n=$ least element of $X$ then $\lnot\,\theta(n)$ and $\psi(\{k:n+1+k\in X\}))$.

Reasoning in $\mathsf{RCA}_0$, suppose $X$ is such that $\widetilde\psi(X)$ holds. If $X=\emptyset$ then we have $\forall n\,\theta(n)$, hence $\forall X\,(\widetilde\psi(X)\rightarrow X=\emptyset)$. Now suppose $X\ne\emptyset$. Then $X=\{n_0\}\cup\{n_0+1+k:k\in X_0\}$ where $\psi(X_0)$ holds and $n_0$ is the least $n$ such that $\lnot\,\theta(n)$. Since $\forall n\,\theta(n)$ fails, $\Sigma^0_2$-$\mathsf{PA}$ fails. Hence by Corollary 10.6 we have $\forall X_0\,\forall Y_0\,((\psi(X_0)\land\psi(Y_0))\rightarrow X_0\bigtriangleup Y_0$ is finite$)$. This implies $\forall X\,\forall Y\,((\widetilde\psi(X)\land\widetilde\psi(Y))\rightarrow X\bigtriangleup Y$ is finite$)$. The rest follows easily from Theorem 10.3.$\Box$

Remark 10.8   For $\Pi ^0_1$ formulas $\varphi(X)$ with no free set variables other than $X$, it is known that $\mathsf{WKL}_0$ proves

$(\exists$ exactly one $X)\,\varphi(X)\rightarrow (\exists$ recursive $X)\,\varphi(X)$. (This follows from [30, Lemma VIII.2.4.2] using $\Delta^0_1$ comprehension.) One might conjecture that this result would continue to hold with ``$(\exists$ exactly one $X)$'' weakened to ``$(\exists$ countably many $X)$''. However, such a conjecture is refuted by Theorem 10.7, taking $\varphi(X)$ to be $\widetilde{\psi}(X)$.

Remark 10.9   Tanaka [35] conjectured that $\mathsf{WKL}_0$ is conservative over $\mathsf{RCA}_0$ for sentences of the form $(\exists$ countably many $X)\,\,\varphi(X)$, where $\varphi(X)$ is arithmetical with no free set variables other than $X$. This conjecture is refuted by Theorem 10.7, taking $\varphi(X)$ to be the $\Pi ^0_1$ formula $\widetilde{\psi}(X)$.

Bibliography

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.
$\Pi ^0_1$ 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 Notes. 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

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

9

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

10

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

11

Harvey Friedman.
Some systems of second order arithmetic and their use.
In Proceedings of the International Congress of Mathematicians, Vancouver 1974, volume 1, pages 235-242. Canadian Mathematical Congress, 1975.

12

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.

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

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

15

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

16

Carl G. Jockusch, Jr. and Robert I. Soare.
$\Pi ^0_1$ classes and degrees of theories.
Transactions of the American Mathematical Society, 173:35-56, 1972.

17

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

18

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

19

Antonín Kucera.
On the role of $\mathbf{0'}$ in recursion theory.
In [6], pages 133-141, 1988.

20

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

21

Michael E. Mytilinaios.
Finite injury and $\Sigma_1$ induction.
Journal of Symbolic Logic, 54:38-49, 1989.

22

Marian B. Pour-El and Saul Kripke.
Deduction-preserving ``recursive isomorphisms'' between theories.
Fundamenta Mathematicae, 61:141-163, 1967.

23

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

24

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

25

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

26

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.

27

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

28

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

29

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

30

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

31

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.

32

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

33

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

34

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

35

Kazuyuki Tanaka.
More on models of $\mathsf{WKL}_0$ (see also [36]).
4 pages, handwritten, 1995.

36

Kazuyuki Tanaka.
(in Japanese).
R.I.M.S. Kokyuroku, 976:77-85, 1997.

37

J. van Heijenoort, editor.
From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931.
Harvard University Press, 1967.
XII + 660 pages.

About this document ...

$\mathbf{\Pi^0_1}$ Sets and Models of $\mathbf{\mathsf{WKL}_0}$

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 pizowkl

The translation was initiated by Stephen G Simpson on 2004-11-01