Muchnik and Medvedev

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

Stephen G. Simpson

Pennsylvania State University

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

University of Minnesota May 2, 2001 Outline of talk:

1. The Gödel Hierarchy.

2. Reverse Mathematics and WKL_{0}.

3. Forcing with Π_{1}^{0} subsets of 2^{ω}.

4. A symmetric ω-model of WKL_{0}.

5. A symmetric β-model.

6. Muchnik and Medvedev degrees of Π_{1}^{0} sets.

7. Structural (lattice-theoretic) results.

8. Some specific Muchnik and Medvedev degrees

9. Some classes of Muchnik degrees.

10. References.

The Gödel Hierarchy:

strong { ⋮ supercompact cardinal ⋮ measurable cardinal ⋮ ZFC (ZF set theory with choice) Zermelo set theory simple type theory

medium { Z_{2} (2nd order arithmetic) ⋮ Π_{2}^{1} comprehension Π_{1}^{1} comprehension ATR_{0} (arith. transfinite recursion) ACA_{0} (arithmetical comprehension)

weak { WKL_{0} (weak König’s lemma) RCA_{0} (recursive comprehension) PRA (primitive recursive arithmetic) EFA (elementary arithmetic) bounded arithmetic ⋮

Reverse Mathematics:

Let τ be a mathematical theorem. Let S_{τ} be the weakest natural subsystem of second order arithmetic in which τ is provable.

1. Very often, the principal axiom of S_{τ} is logically equivalent to τ.

2. Furthermore, only a few subsystems of second order arithmetic arise in this way.

This classification program provides an interesting picture of the logical structure of contemporary mathematics.

It is a contribution to foundations of mathematics (f.o.m.).

Books on Reverse Mathematics:

1.

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

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

2.

S. G. Simpson (editor) Reverse Mathematics 2001

A volume of papers by various authors, to appear in 2001, approximately 400 pages.

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

An important system:

One of the most important systems for Reverse Mathematics is WKL_{0}.

WKL_{0} is a subsystem of second order arithmetic.

WKL_{0} includes Δ_{1}^{0} comprehension (i.e., closure under Turing reducibility) and Weak König’s Lemma: (i.e., every infinite subtree of the full binary tree has an infinite path).

Remarks on ω-models of WKL_{0}:

1. The ω-model

REC = {X ⊆ ω : X is recursive }

is not an ω-model of WKL_{0}. (Kleene)

2. However, REC is the intersection of all ω-models of WKL_{0}. (Kreisel, “hard core”)

Remarks on ω-models of WKL_{0} (continued):

3. The ω-models of WKL_{0} are just the Scott systems, i.e., M ⊆ P (ω) such that

(a) M ≠ ∅.

(b) X, Y ∈ M implies X ⊕ Y ∈ M.

(c) X ∈ M, Y ≤_{T} X imply Y ∈ M.

(d) If T ∈ M is an infinite subtree of 2^{<ω}, then there exists X ∈ M such that X is a path through T.

Dana Scott, Algebras of sets binumerable in complete extensions of arithmetic, Recursive Function Theory, AMS, 1962, pages 117–121.

Remarks on ω-models of WKL_{0} (continued):

4. There is a close relationship between

(a) ω-models of WKL_{0}, and

(b) Π_{1}^{0} subsets of 2^{ω}.

The recursion-theoretic literature is extensive, with numerous articles by Jockusch, Kučera, and others. A recent survey is:

Douglas Cenzer and Jeffrey B. Remmel, Π_{1}^{0} classes in mathematics, Handbook of Recursive Mathematics, North-Holland, 1998, pages 623–821.

An interesting ω-model of WKL_{0}:

Let P be the nonempty Π_{1}^{0} subsets of 2^{ω}, ordered by inclusion. Forcing with P is known as Jockusch/Soare forcing.

Lemma (Simpson 2000). Let X be J/S generic. Suppose Y ≤_{T} X. Then (i) Y is J/S generic, and (ii) X is J/S generic relative to Y.

Theorem (Simpson 2000). There is an ωmodel M of WKL_{0} with the following property: For all X, Y ∈ M, X is definable from Y in M if and only if X is Turing reducible to Y.

Proof. M is obtained by iterated J/S forcing. We have

M = REC [X_{1}, X_{2}, …, X_{n}, …]

where, for all n, X_{n+1} is J/S generic over REC [X_{1}, …, X_{n}]. To show that M has the desired property, we use symmetry arguments based on the Recursion Theorem.

Foundational significance of M:

The above ω-model, M, represents a compromise between the conflicting needs of

(a) recursive mathematics (“everything is computable”)

and

(b) classical rigorous mathematics as developed in WKL_{0} (“every continuous real-valued function on [0, 1] attains a maximum”, “every countable commutative ring has a prime ideal”, etc etc).

Namely, M contains enough nonrecursive objects for WKL_{0} to hold, yet the recursive objects form the “definable core” of M.

Foundational significance (continued):

More generally, consider the scheme

(*) For all X and Y, if X is definable from Y then X is recursive in Y

in the language of second order arithmetic.

Often in mathematics, under some assumptions on a given countably coded object X, there exists a unique countably coded object Y having some property stated in terms of X. In this situation, (*) implies that Y is Turing computable from X. This is of obvious f.o.m. significance.

Simpson 2000 shows that, for every countable model of WKL_{0}, there exists a countable model of WKL_{0} + (∗) with the same first order part.

Thus WKL_{0} + (∗) is conservative over WKL_{0} for first order arithmetical sentences.

A Π_{1}^{0} set of ω-models of WKL_{0}:

Theorem (Simpson 2000). There is a nonempty Π_{1}^{0} subset of 2^{ω}, P, such that:

1. For all X ∈ P, {(X)_{n} : n ∈ ω} is a countable ω-model of WKL_{0}, and every countable ωmodel of WKL_{0} occurs in this way.

2. For all nonempty Π_{1}^{0} sets P_{1}, P_{2} ⊆ P we can find a recursive homeomorphism

F : P_{1} ≅ P_{2}

such that for all X ∈ P_{1} and Y ∈ P_{2}, if F (X) = Y then

{(X)_{n} : n ∈ ω} = {(Y)_{n} : n ∈ ω} .

The proof uses an idea of Pour-El/Kripke 1967.

Hyperarithmetical analogs:

Theorem (Simpson 2000). There is a countable β-model M such that, for all X, Y ∈ M, X is definable from Y in M if and only if X is hyperarithmetical in Y.

In the language of second order arithmetic, consider the scheme

(**) for all X, Y, if X is definable from Y, then X is hyperarithmetical in Y.

Theorem (Simpson 2000).

1. ATR_{0} + (∗∗) is conservative over ATR_{0} for Σ_{2}^{1} sentences.

2. Π_{∞}^{1}-TI_{0} + (∗∗) is conservative over Π_{∞}^{1}-TI_{0} for Σ_{2}^{1} sentences.

Two new structures in recursion theory: Recall that P is the set of nonempty Π_{1}^{0} subsets of 2^{ω}. P_{w} (P_{M}) consists of the Muchnik (Medvedev) degrees of members of P, ordered by Muchnik (Medvedev) reducibility. P is Muchnik reducible to Q (P ≤_{w} Q) if for all Y ∈ Q there exists X ∈ P such that X ≤_{T} Y. P is Medvedev reducible to Q (P ≤_{M} Q) if there exists a recursive functional F : Q → P. Note: ≤_{M} is a uniform version of ≤_{w}.

P_{w} and P_{M} are countable distributive lattices with 0 and 1.

The lattice operations are given by

P × Q = {X ⊕ Y : X ∈ P, Y ∈ Q}

(least upper bound)

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

(greatest lower bound).

P ≡ 0 in P_{w} if and only if P ∩ REC ≠ ∅.

P ≡ 0 in P_{M} if and only if P ∩ REC ≠ ∅.

P ≡ 1 in P_{w}, i.e., P is Muchnik complete, if and only if the Turing degrees of members of P are exactly the Turing degrees of complete extensions of PA. (Simpson 2001)

P ≡ 1 in P_{M}, i.e., P is Medvedev complete, if and only if P is recursively homeomorphic to the set of complete extensions of PA. (Simpson 2000)

Connection with Lindenbaum algebras:

Stone duality gives a 1-1 correspondence

P ⟷ B_{P}

between members of P (i.e., nonempty Π_{1}^{0} subsets of 2^{ω}) and Lindenbaum sentence algebras of r.e. theories (i.e., Boolean algebras of the form B/I, where B is the countable free Boolean algebra, and I is an r.e. ideal in B).

Moreover, this correspondence is functorial.

Namely, recursive functionals F : Q → P (i.e., Medvedev reductions) correspond to recursive homomorphisms B_{F} : B_{P} → B_{Q}.

This provides an alternative way to view Medvedev reducibility: P ≤_{M} Q if and only if there exists a recursive homomorphism f : B_{P} → B_{Q}.

Structural (lattice-theoretic) results:

Trivially P, Q > 0 implies P + Q > 0, but we do not know whether P, Q < 1 implies P × Q < 1.

In P_{w}, for every P > 0, every countable distributive lattice is lattice embeddable below P. For P_{M} we have partial results in this direction.

To construct our lattice embeddings, we use infinitary “almost lattice” operations, defined in such a way that, if ⟨P_{i} : i ∈ ω⟩ is a recursive sequence of members of P, then

∞ ; ∏ ; i=0 P_{i}  and  ∞ ; ∑ ; i=0 P_{i}

are again members of P. We also use a finite injury priority argument a la Martin/Pour-El 1970 and Jockusch/Soare 1972. To push the embeddings below P, we use a Sacks preservation strategy.

This is ongoing joint work with my Ph. D. student Stephen Binns.

Structural results (continued):

Corollary. In P_{w}, for all P >_{w} 0 there exists Q such that P >_{w} Q >_{w} 0. (nonexistence of minimal Muchnik degrees)

Corollary. In P_{M}, for all P >_{M} 0 there exists Q such that P >_{M} Q >_{M} 0. (nonexistence of minimal Medvedev degrees)

The last corollary was also obtained by Douglas Cenzer and Peter Hinman, using a different method: index sets.

Problem area:

Study structural properties of the countable distributive lattices P_{w} and P_{M}. Lattice embeddings, extensions of embeddings, quotient lattices, cupping and capping, automorphisms, definability, decidability, etc.

An invidious comparison:

In some ways, the study of P_{w} and P_{M} parallels the study of R_{T}, the Turing degrees of recursively enumerable subsets of ω.

Analogy: \frac{P_{w}}{R_{T}} = WKL_{0} ACA_{0}

A regrettable aspect of R_{T} is that there are no specific known examples of recursively enumerable Turing degrees ≠ 0, 0′. (See the extensive FOM discussion of July 1999, in the aftermath of the Boulder meeting.)

In this respect, P_{w} and P_{M} are much better.

Invidious comparison (continued):

For example, we have:

Theorem. The set of Muchnik degrees of Π_{1}^{0} subsets of 2^{ω} of positive measure contains a maximum degree. This particular Muchnik degree is ≠ 0, 1.

Question. What about Medvedev degrees?

The theorem follows from three known results.

1. {X : X is 1-random} is Σ_{2}^{0} and of measure one. (Martin-Löf 1966)

2. {X : ∃Y ≤_{T} X (Y separates a recursively inseparable pair of r.e. sets)} is of measure zero. (Jockusch/Soare 1972)

3. If P ∈ P is of positive measure, then for all 1-random X there exists k such that X^{(k)} = λn.X(n + k) ∈ P. (Kučera 1985)

A related but apparently new result:

Theorem (Simpson 2000). If X is 1-random and hyperimmune-free, then no Y ≤_{T} X separates a recursively inseparable pair of r.e. sets.

Other related results:

1. If X is 1-random and of r.e. Turing degree, then X is Turing complete. (Kučera 1985)

2. {X : X is hyperimmune-free} is of measure zero. (Martin 1967, unpublished)

Foundational significance:

All of these results are informative with respect to ω-models of WWKL_{0}. WWKL_{0} is a subsystem of second order arithmetic which arises in the Reverse Mathematics of measure theory. (Yu/Simpson 1990)

Some specific Medvedev degrees ≠ 0, 1:

For k ≥ 2 let DNR _{k} be the set of k-valued DNR functions. Each DNR _{k} is recursively homeomorphic to a member of P. DNR _{2} is Medvedev complete. In P_{M} we have

DNR _{2} >_{M} DNR _{3} >_{M} ⋯ >_{M} ∞ ; ∑ ; k=2 DNR _{k} .

All of these Medvedev degrees are Muchnik complete. (Jockusch 1989)

Problem area:

Find additional natural examples of Medvedev and Muchnik degrees ≠ 0, 1.

Experience suggests that natural examples could be of significance for f.o.m.

A related problem of Reverse Mathematics:

Let DNR (k) be the statement that for all X there exists a k-valued DNR function relative to X. It is known that, for each k ≥ 2, DNR (k) is equivalent to Weak König’s Lemma over RCA_{0}. Is ∃k (k ≥ 2 ∧ DNR (k)) equivalent to Weak König’s Lemma over RCA_{0}?

This has a bearing on graph coloring problems in Reverse Mathematics. See two recent papers of James H. Schmerl, to appear in MLQ and Reverse Mathematics 2001.

Another problem area:

One may study properties of interesting subsets of P_{w} and P_{M}. For example, we may consider Muchnik and Medvedev degrees of P ∈ P with the following special properties:

1. P is of positive measure.

2. P is thin, i.e., for all Π_{1}^{0} sets Q ⊆ P there exists a clopen set U ⊆ 2^{ω} such that P ∩U = Q. (See also the recent paper of Cholak/Coles/Downey/Herrmann.)

3. P is separating, i.e.,

P = {X ∈ 2^{ω} : X separates A, B}

where A, B is a disjoint pair of r.e. sets.

These classes of Muchnik and Medvedev degrees are related in interesting ways.

Theorem (Simpson 2001). Let P ⊆ 2^{ω} be Π_{1}^{0} of positive measure of maximum Muchnik degree. Let Q ≢_{w} 0 be a thin Π_{1}^{0} set. Then P and Q are Muchnik incomparable, i.e., P ≰_{w} Q and Q ≰_{w} P.

Also, if P is as above and Q ≢_{w} 0 is separating, then Q ≰_{w} P. (Jockusch/Soare 1972)

Theorem (Simpson 2001). Let P be as above. Then P is non-capping in P_{w}. I.e., there do not exist P_{1}, P_{2} >_{w} P such that P ≡_{w} P_{1} + P_{2}, the infimum of P_{1} and P_{2}.

A lemma used in proving these theorems:

Lemma. If P, Q ∈ P and P ≤_{w} Q, then there exists R ⊆ Q, R ∈ P, such that P ≤_{M} R.

A picture of the Muchnik lattice P_{w}:

26

References:

Stephen G. Simpson, Kazuyuki Tanaka, and Takeshi Yamazaki, Some conservation results on weak König’s lemma, preprint, February 2000, 26 pages, to appear in APAL.

Stephen G. Simpson, Π_{1}^{0} sets and models of WKL_{0}, preprint, April 2000, 28 pages, to appear in Reverse Mathematics 2001.

Stephen G. Simpson, A symmetric β-model, preprint, May 2000, 7 pages, to appear.

Stephen Binns and Stephen G. Simpson, Medvedev and Muchnik degrees of Π_{1}^{0} subsets of 2^{ω}, in preparation.

Stephen G. Simpson, Some examples of Muchnik degrees of Π_{1}^{0} subsets of 2^{ω}, in preparation.

Some of my papers are available at

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

Transparencies for my talks are available at

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

THE END