Medvedev and Muchnik Degrees of Nonempty Π_{1}^{0} Subsets of 2^{ω}

Stephen G. Simpson Department of Mathematics Pennsylvania State University

          http://www.math.psu.edu/simpson/

Draft: April 18, 2001

This research was partially supported by NSF grant DMS-0070718. Subject Classification: 03D30, 03D65.

This is a report for my presentation at the upcoming meeting on Berechenbarkeitstheorie (“Computability Theory”), Oberwolfach, January 21–27, 2001.

We use 2^{ω} to denote the space of infinite sequences of 0’s and 1’s. For X, Y ∈ 2^{ω}, X ≤_{T} Y means that X is Turing reducible to Y. For P, Q ⊆ 2^{ω} we say that P is Muchnik reducible to Q, abbreviated P ≤_{w} Q, if for all Y ∈ Q there exists X ∈ P such that X ≤_{T} Y. We say that P is Medvedev reducible to Q, abbreviated P ≤_{M} Q, if there exists a recursive functional Φ : Q → P. Note that P ≤_{M} Q implies P ≤_{w} Q, but not conversely.

Sorbi [13] gives a useful survey of Medvedev and Muchnik degrees of arbitrary subsets of 2^{ω}. Here we initiate a study of Medvedev and Muchnik degrees of nonempty Π_{1}^{0} subsets of 2^{ω}. Theorems 1 and 2 below have been proved in collaboration with my Ph. D. student Stephen Binns.

Let P be the set of nonempty Π_{1}^{0} subsets of 2^{ω}. Let P_{M} (respectively P_{w}) be the set of Medvedev (respectively Muchnik) degrees of members of P, ordered by Medvedev (respectively Muchnik) reducibility. We say that P ∈ P is Medvedev complete (respectively Muchnik complete) if P ≥_{M} Q (respectively P ≥_{w} Q) for all Q ∈ P. For example, the set of complete extensions of Peano Arithmetic is Medvedev complete. Clearly every Medvedev complete set is Muchnik complete, but not conversely. P_{M} and P_{w} are countable distributive lattices with a bottom element, 0, the degree of 2^{ω}, and a top element, 1, the degree of any Medvedev complete set. The lattice operations are given by P × Q = {X ⊕ Y : X ∈ P and Y ∈ Q} and P + Q = {⟨0⟩^{⌢}X : X ∈ P } ∪ {⟨1⟩^{⌢}Y : Y ∈ Q}. Here P × Q (respectively P + Q) is the join (respectively meet) of P and Q.

In both P_{M} and P_{w}, it is easy to see that P, Q > 0 implies P + Q > 0, but we do not know whether P, Q < 1 implies P × Q < 1. In addition, there are many other open problems. For example, we do not know whether the Sacks Density Theorem holds for P_{M} or for P_{w}. This subject appears to be a rich source of problems for recursion theorists.

Theorem 1 In P_{w}, for every P > 0, every countable distributive lattice is lattice embeddable below P.

Proof (sketch). We begin by defining infinitary “almost lattice” operations in such a way that, given a recursive sequence ⟨P_{i} : i ∈ ω⟩ of members of P, ∏_{i∈ω} P_{i} and ∑_{i∈ω} P_{i} are again members of P. We define the infinite product in the obvious way, ∏_{i∈ω} P_{i} = {X ∈ 2^{ω} : (X)_{i} ∈ P_{i} for all i ∈ ω}, where (X)_{i}(n) = X((n, i)) for all n ∈ ω. To define the infinite sum, let ⟨T_{i} : i ∈ ω⟩ be a recursive sequence of recursive subtrees of 2^{<ω} such that, for each i, P_{i} is the set of paths through T_{i}. Let R be a fixed, Medvedev complete member of P. Let T be a recursive subtree of 2^{<ω} such that R is the set of paths through T. Put T̃ = {τ^{⌢}⟨k⟩ : τ ∈ T, k ∈ {0, 1}, τ^{⌢}⟨k⟩ ∉ T }. Let ⟨σ_{i} : i ∈ ω⟩ be a recursive enumeration of T̃ without repetition. We define the infinite sum ∑_{i∈ω} P_{i} to be the set of paths through T^{∗} = T ∪ {σ_{i}^{⌢}τ : i ∈ ω, τ ∈ T_{i}}.

To prove the theorem, construct a recursive sequence ⟨Q_{i} : i ∈ ω⟩ of members of P such that X ≰_{T} Y for all X ∈ Q_{i}, Y ∈ Q_{j}, i ≠ j. This is a finite injury priority construction, similar to that of Jockusch/Soare [6, Theorem 4.7]. For i ∈ ω define Q̂_{i} = ∑_{j≠i} Q_{j}. For recursive A ⊆ ω define Q̂(A) = ∏_{i∈A} Q̂_{i}. We have Q̂(A) ∈ P and Q̂(A ∪ B) ≡_{w} Q̂(A) × Q̂(B) and Q̂(A ∩ B) ≡_{w} Q̂(A) + Q̂(B). Moreover A ≠ B implies Q̂(A) ≢_{w} Q̂(B). Thus A ↦ Q̂(A) is a lattice embedding of the lattice of recursive subsets of ω into P_{w}. Note also that every countable distributive lattice is lattice embeddable into the lattice of recursive subsets of ω. To push the embedding below P, assume in addition that X ≰_{T} Y for all X ∈ P, Y ∈ Q_{i}, i ∈ ω. This property can be obtained by a Sacks preservation strategy. Our lattice embedding below P is given by A ↦ Q̂(A) + P. □

It seems likely that Theorem 1 holds with P_{w} replaced by P_{M}. In this direction we have the following partial result.

Theorem 2 In P_{M}, for every P > 0, the free countable distributive lattice is lattice embeddable below P, as are the lattice of finite subsets of ω, the lattice of cofinite subsets of ω, and all finite distributive lattices.

Proof (sketch). With notation as before, we have Q̂(A∪B) ≡_{M} Q̂(A)×Q̂(B) and Q̂(A ∩ B) ≡_{M} Q̂(A) + Q̂(B), provided A, B ⊆ ω are finite. Thus A ↦ Q̂(A) + P is the desired lattice embedding of the lattice of finite subsets of ω into P_{M} below P. Note also that every finite distributive lattice is lattice embeddable into the lattice of finite subsets of ω.

Now assume that ⟨Q_{i} : i ∈ ω⟩ has the following stronger properties:

(1) X_{i} ≰_{T} Y for all X_{i} ∈ Q_{i}, Y ∈ ∏_{j≠i} Q_{j}, (2) X ≰_{T} Y for all X ∈ P, Y ∈ ∏_{i∈ω} Q_{i}. As before, these properties can be obtained by a finite injury priority argument and a preservation strategy. For i ∈ ω define Q̌_{i} = ∏_{j≠i} Q_{i}. For recursive A ⊆ ω define Q̌(A) = ∑_{i∈A} Q̌_{i}. Note that the definition of Q̌(A) is dual to that of Q̂(A). We have Q̌(A) ∈ P and Q̌(A ∩ B) ≡_{w} Q̌(A) × Q̌(B) and Q̌(A ∪ B) ≡_{w} Q̌(A) + Q̌(B). For finite A, B ⊆ ω we have Q̌(A ∩ B) ≡_{M} Q̌(A) × Q̌(B) and Q̌(A ∪ B) ≡_{M} Q̌(A) + Q̌(B). Thus ω \ A ↦ Q̌(A) + P is the desired lattice embedding of the lattice of cofinite subsets of ω into P_{M} below P.

Finally, with Q_{i}, i ∈ ω as above, the Medvedev degrees of Q_{i} + P, i ∈ ω freely generate a free distributive sublattice of P_{M} below P. □

Remark The study of the distributive lattices P_{M} and P_{w} is in some ways parallel to the study of R_{T}, the upper semilattice of Turing degrees of recursively enumerable subsets of ω. (For background on this topic, see Soare [12].) However, as is well known, there are no specific examples of recursively enumerable degrees ≠ 0, 0′. (See the FOM discussion with Soare [4, July 1999].) In this respect, P_{M} and P_{w} are much better, as shown by the following two theorems, due to Kučera [7] and Jockusch [5] respectively.

Theorem 3 Among all Muchnik degrees of Π_{1}^{0} subsets of 2^{ω} of positive measure, there is a unique largest one. This particular element of P_{w} is ≠ 0, 1.

Theorem 4 For k ≥ 2 let DNR_{k} be the Π_{1}^{0} set of k-valued DNR functions. In the Medvedev degrees P_{M} we have 1 ≡_{M} DNR_{2} >_{M} DNR_{3} >_{M} ⋯ >_{M} DNR_{k} >_{M} ⋯ >_{M} 0. All of these Medvedev degrees are Muchnik complete.

Simpson [11, Theorem 3.20] proves the following analog of Myhill’s Theorem on creative sets (see Rogers [9]). This is closely related to a result of Pour-El/Kripke [8].

Theorem 5 If P, Q ∈ P are Medvedev complete, then P and Q are recursively homeomorphic.

Proof (sketch). First we define what it means for P ∈ P to be productive. Then we use the Recursion Theorem to prove the following two results: (1) P is productive if and only if P is Medvedev complete. (2) Any two productive sets P, Q ∈ P are recursively homeomorphic. The details are in Simpson [11, Section 3]. □

Simpson [11, Theorem 6.9] applies Theorem 5 plus Jockusch/Soare forcing [6, Theorem 2.4] to prove the following result concerning subsystems of second order arithmetic. (For background on this topic, see Simpson [10].)

Theorem 6 There is a countable ω-model S of WKL_{0} with the following property. For all X, Y ∈ S, X is definable from Y over S if and only if X ≤_{T} Y.

References

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

[2] H.-D. Ebbinghaus, G.H. Müller, and G.E. Sacks, editors. Recursion Theory Week. Number 1141 in Lecture Notes in Mathematics. Springer-Verlag, 1985. IX + 418 pages.

[3] 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. Elsevier, 1989. XVII + 702 pages.

 [4] FOM e-mail list. http://www.math.psu.edu/simpson/fom/, Septem-

ber 1997 to the present.

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

[6] Carl G. Jockusch, Jr. and Robert I. Soare. Π_{1}^{0} classes and degrees of theories. Transactions of the American Mathematical Society, 173:35– 56, 1972.

[7] Antonín Kučera. Measure, Π_{1}^{0} classes and complete extensions of PA. In [2], pages 245–259, 1985.

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

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

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

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

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

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