Mathematical Logic
Reverse Mathematics
Reverse mathematics answers: what is the minimal set of axioms needed to prove a specific theorem? It turns out that most theorems of analysis and algebra require exactly one of five systems - and this exact boundary can be proved mathematically.
- Proof assistants (Lean, Coq, Isabelle): formalizing mathematics reveals the exact axiomatic strength of each theorem - this is computational reverse mathematics in practice
- Computational complexity: connections between complexity classes (P vs NP) and reverse-mathematics systems are an active research area
- Constructive mathematics: RCA_0 corresponds to constructively provable mathematics, WKL_0 to classical mathematics with limited use of compactness
- Database theory: lower bounds for query-processing problems are connected to undecidability and the axiomatic strength of theorems about finite structures
Five Systems of Reverse Mathematics
Harvey Friedman in 1975 asked: which axioms are necessary for specific theorems of analysis? Stephen Simpson developed this into a systematic program. Most theorems of ordinary mathematics turn out to be equivalent to exactly one of five subsystems of second-order arithmetic over the base system RCA_0.
What does it mean that theorem T is equivalent to system S over RCA_0?
Equivalence of theorem T to system S over RCA_0: S proves T (the axioms of S suffice) and RCA_0 + T proves the axioms of S (they are necessary). This reveals the exact axiomatic strength of the theorem.
Examples of Equivalences and Non-Standard Results
Reverse mathematics reveals the fine structure of mathematics. The intermediate value theorem is provable in RCA_0. The theorem that a continuous function on [0,1] attains its maximum is equivalent to WKL_0. Ramsey's theorem for pairs RT^2_2 is not equivalent to any of the Big Five and lies strictly between WKL_0 and ACA_0.
The reverse mathematics program continues: theorems of combinatorics (Hindman's theorem, Carlson-Simpson theorem) are actively studied for their exact place in the hierarchy. Many turn out to lie strictly between levels of the Big Five, enriching the picture of the axiomatic strength of mathematical theorems.
To which system is the Bolzano-Weierstrass theorem (every bounded sequence in R has a convergent subsequence) equivalent?
Bolzano-Weierstrass is equivalent to ACA_0 over RCA_0. Proof: ACA_0 proves BW (via arithmetical comprehension), and BW over RCA_0 proves the axiom of ACA_0.
Итоги
- Reverse mathematics: for theorem T find system S such that T is equivalent to S over RCA_0
- Five systems: RCA_0 (base), WKL_0 (compactness), ACA_0 (arithmetical comprehension), ATR_0 (transfinite recursion), Pi^1_1-CA_0
- Bolzano-Weierstrass is equivalent to ACA_0; Heine-Borel is equivalent to WKL_0
- RT^2_2 (Ramsey theorem for pairs) violates the Big Five schema: it lies strictly between WKL_0 and ACA_0
- Proof-theoretic ordinals: RCA_0 = omega^omega, ACA_0 = epsilon_0, ATR_0 = Gamma_0
- Reverse mathematics reveals the exact axiomatic structure of mathematics - which axioms are truly necessary