An introduction to reverse mathematics
Paul Shafer (University of Leeds)
Reverse mathematics aims to determine precisely which axioms are required to prove which theorems. The name "reverse mathematics" comes from the idea that one shows a strong axiom A is necessary to prove a theorem T by showing that A can be deduced from T over a weak set of basic axioms. The proof of axiom A from theorem T is called a "reversal," which puts the "reverse" in "reverse mathematics." This course gives an overview of the recursion-theoretic approach to reverse mathematics in second-order arithmetic.
Part 1: Proofs and reversals.
We use the classic Tietze extension theorem to introduce the main subsystems of second-order arithmetic, proofs in these systems, and reversals to these systems. The Tietze extension theorem also illustrates that the strength of a "theorem" can vary considerably depending on exactly how the theorem is phrased.
Part 2: Models and separations.
Reverse mathematics is not only about equivalences. It is also about showing when one theorem T does *not* suffice to prove some other theorem S. To do this, one typically shows that there are objects that theorem T asserts to exist which do not compute any of the objects that theorem S asserts to exist, and then one iterates this idea to build a model of T that is not a model of S. We illustrate this process via Dzhafarov and Jockusch's proof of Seetapun's theorem separating Ramsey's theorem for pairs from arithmetical comprehension.
Part 3: Induction (time permitting).
If time permits, we revisit proofs, reversals, models, and separations with an eye toward induction axioms and non-standard models. We discuss a theorem of Rival and Sands that turns out to be equivalent to Sigma_2 induction plus the ascending/descending sequence principle. We also discuss principles concerning so-called "diagonally non-recursive functions" that are equivalent to weak Koenig's lemma in the presence of Sigma_2 induction, but are weaker in the presence of only Sigma_2 bounding.