Reverse Mathematics:

An Overview

Stephen G. Simpson

Pennsylvania State University

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

ASL Annual Meeting Association for Symbolic Logic Philadelphia, March 10–13, 2001

Special Session on Reverse Mathematics Outline of this talk:

1. subsystems of Z_{2} and SOSOA

2. f.o.m. and FOM

3. the Gödel hierarchy

4. r.m. as a classification program

5. r.m. and traditional foundational schemes (constructivism, predicativism, reductionist programs)

6. philosophical significance of r.m.

7. mathematical significance of r.m.

8. significance of r.m. for mathematical logic History of reverse mathematics:

Kreisel in the 1960’s introduced numerous subsystems of Z_{2} including Δ_{1}^{1}-CA, Σ_{1}^{1}-AC, Σ_{1}^{1}- DC

Friedman 1967 introduced a system equivalent to ATR to show that Σ_{1}^{1}-AC ≠ Σ_{1}^{1}-DC.

Simpson 1973 lectured at Berkeley on subsystems of Z_{2} and their role in f.o.m. Lecture notes are available.

Steel 1973 showed that ATR ↔ comparability of countable well orderings, over Δ_{1}^{1}-CA. This and other r.m. results appeared in Steel’s Ph.D. thesis, supervised by me.

Friedman in his 1974 ICM lecture stated the theme of reverse mathematics. In JSL abstracts he introduced systems with restricted induction.

History of r.m. (continued):

Simpson in a lecture at a 1982 recursion theory meeting (Cornell) isolated the “big five”: RCA_{0}, WKL_{0}, ACA_{0}, ATR_{0}, Π_{1}^{1}-CA_{0}.

Papers by Simpson and Friedman/Simpson/Smith.

Simpson supervises Ph.D. theses at Penn State: Smith, Brackin, Ferreira, Hirst, Brown, Yu, Marcone, Humphreys, Giusto, …, + numerous papers …. (1979–1998)

Simpson 1998 finally finishes his book on subsystems of Z_{2} and reverse mathematics. (Sorry for the delay!)

Simpson 1999 begins assembling the volume Reverse Mathematics 2001.

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

Unfortunately the book is no longer available from Springer, but there is hope that the ASL will reprint it soon.

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/

An upcoming reverse mathematics event:

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 here in Philadelphia who have contributed to reverse mathematics:

Avigad, Cenzer, Feng, Friedman, Girard, Hirschfeldt, Hirst, Jockusch, Lempp, Schmerl, Simpson, Shore, Slaman, Solomon Foundations of mathematics (f.o.m.):

Foundations of mathematics 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 4800 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.

Background of reverse mathematics:

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.

Themes of r.m. (continued):

We develop a table indicating which mathematical theorems can be proved in which subsystems of Z_{2}.

RCA_{0} WKL_{0} ACA_{0} ATR_{0} Π_{1}^{1}-CA_{0}

analysis (separable):

differential equations X X
continuous functions  X, X X, X X
completeness, etc.  X  X  X
Banach spaces  X  X, X  X
open and closed sets  X  X  X, X X
Borel and analytic sets  X  X, X X, X

algebra (countable):

countable fields  X  X, X X
commutative rings  X  X  X
vector spaces  X  X
Abelian groups  X  X  X  X

miscellaneous:

mathematical logic  X  X
countable ordinals  X  X  X, X
infinite matchings  X  X  X
the Ramsey property  X  X  X
infinite games  X  X  X

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 ⋮

Foundational consequences of r.m.:

1. We precisely classify mathematical theorems, according to which subsystems of Z_{2} they are provable in.

2. We identify certain subsystems of Z_{2} as being mathematically natural. The naturalness is rigorously demonstrated.

3. We work out the consequences of particular foundational doctrines:

• recursive analysis (Pour-El/Richards)

• constructivism (Bishop)

• finitistic reductionism (Hilbert)

• predicativism (Weyl)

• predicative reductionism (Feferman/Friedman/Simpson)

• impredicative analysis (Takeuti/Schütte/Pohlers)

Foundational consequences (continued):

By means of reverse mathematics, we identify five particular subsystems of Z_{2} as being mathematically natural. We correlate these systems to traditional f.o.m. programs.

RCA_{0}  constructivism  Bishop
WKL_{0}  finitistic reductionism  Hilbert
ACA_{0}  predicativism  Weyl, Feferman
ATR_{0}  predicative reductionism  Friedman, Simpson
Π_{1}^{1}-CA_{0} impredicativity  Feferman et al.

We analyze these foundational proposals in terms of their consequences for mathematical practice. Specifically, under the various proposals, which mathematical theorems are “lost”? Reverse mathematics provides precise answers to such questions.

Significance of r.m. for mathematical logic:

1. recursion theory • reversals use coding arguments

• ω-models of subsystems of Z_{2}

• Turing ideals (RCA_{0})

• Turing jump ideals (ACA_{0})

• Π_{1}^{0} subsets of 2^{ω} (WKL_{0})

• hyperarithmetic theory (ATR_{0}, Π_{1}^{1}-CA_{0})

• basis and anti-basis theorems

• Medvedev and Muchnik degrees

2. model theory • models of subsystems of Z_{2}

• ω-models and non-ω-models

• nonstandard models of arithmetic

• model-theoretic conservation results 3. set theory

• r.m. highlights the foundational significance of set theory

• ZFC is usually too strong for math, but r.m. highlights the rare cases when strong axioms are actually needed

• set-theoretic methods are used to build models of subsystems of Z_{2} (constructible sets, forcing, etc)

4. proof theory • subsystems of Z_{2} studied in proof theory • r.m. brings out their f.o.m. significance • Gentzen-style ordinal analysis

• proof-theoretic conservation results My recent papers:

1. Simpson/Tanaka/Yamazaki (35 pages, 2000, submitted) contains many conservation results for WKL_{0} over RCA_{0}.

2. Simpson (26 pages, 2000, to appear in Reverse Mathematics 2001) constructs models of WKL_{0} where relative definability equals Turing reducibility.

3. Simpson (8 pages, 2000) constructs βmodels where relative definability equals relative hyperarithmeticity.

4. Binns/Simpson (20 pages, 2001, under revision) obtain lattice embedding results for P_{M} and P_{w}, the lattices of Medvedev and Muchnik degrees of nonempty Π_{1}^{0} subsets of 2^{ω}.

5. Simpson (2001, in preparation) studies interesting subsets of P_{M} and P_{w}.