Math 2.0

Mathematical logic and foundations Definition

Reverse mathematics

Builds on Second-order arithmetic

Definition

Let 𝖱𝖒𝖠0\mathsf{RCA}_0 be the subsystem of second-order arithmetic with the basic axioms, induction for Ξ£10\Sigma^0_1 formulas, and comprehension for Ξ”10\Delta^0_1 formulas. A sentence Ο„\tau of second-order arithmetic is equivalent over 𝖱𝖒𝖠0\mathsf{RCA}_0 to a subsystem SS if:

  1. SS proves Ο„\tau;
  2. 𝖱𝖒𝖠0+Ο„\mathsf{RCA}_0 + \tau proves every axiom of SS.

Reverse mathematics is the study of which theorems of ordinary mathematics are provable in which subsystems of second-order arithmetic. In particular, it studies equivalences over 𝖱𝖒𝖠0\mathsf{RCA}_0.

Remarks

The big five subsystems are 𝖱𝖒𝖠0\mathsf{RCA}_0, 𝖢π–ͺ𝖫0\mathsf{WKL}_0 (adds weak KΓΆnig's lemma), 𝖠𝖒𝖠0\mathsf{ACA}_0 (arithmetical comprehension), 𝖠𝖳𝖱0\mathsf{ATR}_0 (arithmetical transfinite recursion) and Ξ 11-𝖒𝖠0\Pi^1_1\text{-}\mathsf{CA}_0 (Ξ 11\Pi^1_1 comprehension), each stronger than the one before.

Example: the Bolzano–Weierstrass theorem for sequences in [0,1][0,1] is equivalent to 𝖠𝖒𝖠0\mathsf{ACA}_0 over 𝖱𝖒𝖠0\mathsf{RCA}_0. The Heine–Borel theorem for countable covers of [0,1][0,1] by open intervals is equivalent to 𝖢π–ͺ𝖫0\mathsf{WKL}_0 over 𝖱𝖒𝖠0\mathsf{RCA}_0.

Non-example: weak KΓΆnig's lemma is provable in 𝖠𝖒𝖠0\mathsf{ACA}_0 but not equivalent to 𝖠𝖒𝖠0\mathsf{ACA}_0 over 𝖱𝖒𝖠0\mathsf{RCA}_0. Clause 2 fails, because 𝖢π–ͺ𝖫0\mathsf{WKL}_0 does not prove arithmetical comprehension.

The models of 𝖱𝖒𝖠0\mathsf{RCA}_0 with the standard natural numbers include the one whose sets are the computable sets, so 𝖱𝖒𝖠0\mathsf{RCA}_0 corresponds to computable mathematics.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Second-order arithmetic concept
  2. Reverse mathematics definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Reverse_mathematics
About this page
TagTQTDKMBJ0F
URIm2://TQTDKMBJ0F
Kinddefinition
WritingW0 stub
MSC03B30, 03F35
DefinesReverse mathematics
UsesSecond-order arithmetic
Changed2 November 2026

Markdown Β· JSON Β· Edit on GitHub

What this page needs for W1

  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.