A World Where Relative Definability

Coincides With Relative Recursiveness (i.e., Turing Reducibility)

Stephen G. Simpson

Pennsylvania State University

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

Philosophy of Mathematics Workshop

Carnegie-Mellon University December 9–10, 2000 Outline of talk:

1. Reverse mathematics, SOSOA, FOM.

2. ω-models of WKL_{0}.

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

4. Symmetric models of WKL_{0}.

5. Foundational significance.

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

7. Hyperarithmetical analogs.

8. References.

Background:

Second order arithmetic 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.

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

Book on Reverse Mathematics:

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

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

Order: 1-800-SPRINGER

List price: $60

Discount: 30 percent for ASL members, mention promotion code S206 The FOM mailing list:

FOM is an automated e-mail list for discussing foundations of mathematics. There are currently almost 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

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

The purpose of FOM is to promote the idea that 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.

Main results of this talk:

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}].

Corollary (Friedman 1974, unpublished, by a different method). There is 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.

Note: Friedman’s 1974 manuscript contains another result which contradicts my theorem above, concerning relative definability. 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, with the following properties:

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.

Foundational significance:

Foundations of mathematics (f.o.m.) is the study of the most basic concepts and logical structure of mathematics, with an eye to the unity of human knowledge.

General background in f.o.m.: the van Heijenoort volume; Gödel’s Collected Works; the Friedman volume.

Specific background: recursive mathematics, i.e., the development of mathematics in the computable world, REC = {X : X is recursive}. See Aberth, Pour-El/Richards, ….

Foundational significance (continued):

Regrettably, the assumption “all real numbers are computable” conflicts with many basic theorems of real analysis. E.g., the maximum principle for continuous real-valued functions on [0, 1].

On the other hand, many such theorems are provable in WKL_{0}. This is a by-product of Reverse Mathematics.

To strike a balance, we can work in an ω-model of WKL_{0} where all definable real numbers are computable. Thus many non-constructive theorems hold, yet REC is the “definable core”.

Foundational significance (continued):

More generally, consider the scheme

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

in the language of second order arithmetic.

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.

Often in mathematics, under some assumptions on a real parameter X, there exists a unique real Y having some property stated in terms of X. In this situation, (*) implies that Y is Turing reducible to X.

Two new structures in recursion theory:

P_{w} (P_{M}) consists of the Muchnik (Medvedev) degrees of nonempty Π_{1}^{0} subsets of 2^{ω}, 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.

Results and problems:

P_{w} and P_{M} are countable distributive lattices with a top and bottom element, call them 1 and 0. In P_{w} and P_{M}, it is trivial that P, Q > 0 implies inf (P, Q) > 0, but we do not know whether P, Q < 1 implies sup (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.

This is joint work with my Ph. D. student Stephen Binns (2000).

An invidious comparison:

The study of P_{w} and P_{M}, the Muchnik and Medvedev degrees of nonempty Π_{1}^{0} subsets of 2^{ω}, is in some ways parallel to the study of R_{T}, the Turing degrees of recursively enumerable subsets of ω.

Analogy:

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

As is well known, there are no specific examples of recursively enumerable Turing degrees ≠ 1, 0. (See the FOM discussion with Soare, July 1999.) In this respect, P_{w} and P_{M} are much better.

For example, the set of Muchnik degrees of Π_{1}^{0} subsets of 2^{ω} of positive Lebesgue measure contains a maximum degree, which is ≠ 1, 0.

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.

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/.

These transparencies are available at

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