Medvedev Degrees, Muchnik Degrees, Subsystems of Z_{2}

and

Reverse Mathematics

Stephen G. Simpson

Pennsylvania State University

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

Berechenbarkeitstheorie Oberwolfach, Germany January 21–27, 2001 Outline of talk:

1. Reverse mathematics, SOSOA, FOM.

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

3. Symmetric ω-models of WKL_{0}.

4. Symmetric β-models.

5. Foundational significance.

6. Muchnik and Medvedev degrees of nonempty Π_{1}^{0} subsets of 2^{ω}.

7. Natural examples (an invidious comparison).

8. References.

Background:

Second order arithmetic (Z_{2}) is a two-sorted system.

Number variables m, n, … range over

ω = {0, 1, 2, …} .

Set variables X, Y, … range over subsets of ω.

We have +, ×, = on ω, plus the membership relation

∈ = {(n, X) : n ∈ X} ⊆ ω × P (ω) .

Within subsystems of second order arithmetic, we can formalize rigorous mathematics (analysis, algebra, geometry, …).

Subsystems of second order arithmetic are the basis of our current understanding of the logical structure of contemporary mathematics.

Themes of 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.

For a full exposition, see my book.

Book on reverse mathematics:

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/

Order: 1-800-SPRINGER

List price: $60

Discount: 30 percent for ASL members, mention promotion code S206 Another book on reverse mathematics:

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/

Upcoming reverse mathematics events:

1. ASL Annual Meeting, Philadelphia, March 10–13, 2001. Special Session on Reverse Mathematics, organized by S. Simpson.

2. ASL/APA Meeting, Minneapolis, May 3–5, 2001. Panel Discussion on “Computability Theory and Reverse Mathematics”, organized by M. Detlefsen. Panelists: J. Hirst, S. Simpson, R. Solomon.

People at this meeting who have contributed to reverse mathematics:

Cenzer, Cholak, Chong, Downey, Friedman, Gasarch, Hirschfeldt, Jockusch, Lempp, Mc-Coy, Simpson, Slaman, Solomon, Yang Foundational consequences of reverse mathematics:

1. We demonstrate rigorously that certain particular subsystems of second order arithmetic are mathematically natural.

2. We precisely classify mathematical theorems, according to which subsystems they are provable in.

3. . . . .

4. . . . .

What is foundations of mathematics?

Foundations of mathematics (f.o.m.) is the study of the most basic concepts and logical structure of mathematics as a whole. Among the basic concepts are: number, set, function, algorithm, mathematical proof, mathematical definition, mathematical axiom.

A key f.o.m. question:

What are the appropriate axioms for mathematics?

The FOM mailing list:

FOM is an automated e-mail list for discussing foundations of mathematics. There are currently more than 500 subscribers. There have been more than 4700 postings.

FOM is maintained and moderated by S. Simpson. The FOM Editorial Board consists of M. Davis, H. Friedman, C. Jockusch, D. Marker, S. Simpson, A. Urquhart.

FOM postings and information are available on the web at

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

Friedman and Simpson founded FOM in order to promote a controversial idea: mathematical logic is or ought to be driven by f.o.m. considerations.

f.o.m. = foundations of mathematics.

The hierarchy of consistency strengths:

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 ⋮

An important system: One of the most important subsystems of second order arithmetic is WKL_{0}. WKL_{0} includes Δ_{1}^{0} comprehension (i.e., recursive comprehension) and Weak König’s Lemma: 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.

People at this meeting who have contributed to the study of Π_{1}^{0} subsets of 2^{ω}:

Cenzer, Cholak, Downey, Groszek, Jockusch, Kučera, Nies, Slaman, Simpson, Terwijn 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.

Earlier results of Friedman:

In an unpublished 1974 manuscript, Friedman obtained (by a different method) an ω-model M of WKL_{0} with the following property: For all X ∈ M, X is definable in M if and only if X is recursive.

In the same 1974 manuscript, Friedman proved another result which stands in contradiction to my theorem above, concerning relative definability and relative recursiveness. Friedman’s proof of this other result is erroneous.

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

Φ : P_{1} ≅ P_{2}

such that for all X ∈ P_{1} and Y ∈ P_{2}, if Φ(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 Φ : 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 elements 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)

Lattice embedding 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.

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.

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

1. P is perfect and thin.

2. P is of positive measure.

3. P is separating, i.e., P = {X ∈ 2^{ω} : X separates A, B}, where A, B is a recursively inseparable pair of r.e. sets.

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.

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)

People at this meeting who have contributed to the study of 1-randomness, i.e., Martin-Löf randomness:

Ambos-Spies, Downey, Hirschfeldt, Jockusch, Kučera, LaForte, Nies, Simpson, Slaman, Terwijn, Weihrauch 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.

References:

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

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

These and other papers are available at

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

Transparencies are available at

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

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