nLab
reverse mathematics

Reverse mathematics

Idea

Reverse mathematics refers mainly to a program introduced by Harvey Friedman and Stephen Simpson, which aims to establish for many theorems of classical analysis exactly which set existence principles they rely on. They consider the formalization of analysis based on Polish spaces in the language of second order arithmetic (hence the need to focus on separable spaces). One then tries to show that various theorems are equivalent to a set existence axiom relative to a weak base theory, usually RCA 0\mathrm{RCA}_0 (a finitistically reducible system axiomatizing recursive set comprehension only). The implication from a set existence axiom to a theorem is the usual (forward) direction of mathematics, while the implication from a theorem back to the axiom is reverse direction of reverse mathematics.

There are other uses of the term reverse mathematics, notably constructive reverse mathematics (see below).

The “Big Five” subsystems

Work on reverses mathematics has isolated five subsystems of second order arithmetic that correspond to many classical theorems. For more information see ordinal analysis.

These are in increasing order: RCA 0\mathrm{RCA}_0, WKL 0\mathrm{WKL}_0, ACA 0\mathrm{ACA}_0, ATR 0\mathrm{ATR}_0 and Π 1 1CA 0\Pi^1_1{-}\mathrm{CA}_0. The first two are finitistically reducible, but WKL 0\mathrm{WKL}_0 introduces non-recursive sets. The system ACA 0\mathrm{ACA}_0 has the same strength as first-order Peano arithmetic, PA\mathrm{PA}. The system ATR 0\mathrm{ATR}_0 is predicatively reducible, while the system Π 1 1CA 0\Pi^1_1{-}\mathrm{CA}_0 corresponds to the first-order system ID <ω\mathrm{ID}_{\lt\omega} of finitely many generalized inductive definitions.

Constructive reverse mathematics

Constructive reverse mathematics refers to a similar program initiated by Ishihara which aims to calibrate non-constructive theorems with respect to non-constructive axioms over a constructive base theory. The non-constructive axioms he considers are

  • Omniscience principles, in decreasing strength: LPO (limited principle of omniscience), WLPO (weak LPO), LLPO (lesser LPO).

  • Variations of Markov’s Principles (MP): WMP (Weak MP), MP^{\vee} (disjunctive MP).

  • Principles from Brouwer’s intuitionism: FANΔ_\Delta (detachable fan principle), BD-N (boundedness principle).

References

  • Stephen G. Simpson, Subsystems of Second Order Arithmetic, 2nd edition, Cambridge University Press, 2010.

  • Hajime Ishihara, Reverse Mathematics in Bishop’s Constructive Mathematics, Philosophia Scientiæ, CS 6 (2006). PDF

  • Wikipedia, Reverse mathematics

  • Natural examples of Reverse Mathematics outside classical analysis?, MO discussion

Last revised on January 5, 2018 at 13:05:59. See the history of this page for a list of all contributions to it.