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