[FOM] Importance of Reverse Mathematics
Dmytro Taranovsky
dmytro at mit.edu
Wed Jul 7 20:01:23 EDT 2004
Reverse mathematics is important because it allows us to see the
interrelationships between mathematical results. In a strong axiomatic system,
almost all mathematical results are trivially equivalent because they are
provable. In a weak base system, most important mathematical facts are not
provable. Instead, the facts separate into groups, with statements in a single
group provably equivalent to each other and (in most cases) to a set existence
axiom. By showing equivalence of diverse mathematical facts, one gains a
better understanding of them. Over RCA0 (theory of integers and sets of
integers consisting of basic arithmetic, Sigma-0-1 induction, induction for
sets of numbers, and recursive comprehension; most of mathematics is
expressible in the language of RCA0), much of mathematical knowledge separates
into five groups linearly ordered by the corresponding set existence axioms:
RCA0, WKL0, ACA0, ATR0, and Pi-1-1-CA0. "Subsystems of Second Order
Arithmetic" by Stephen Simpson describes this in detail.
An important side benefit of reverse mathematics is that by proving a result in
a weak system one often proves more than that the result is true. For example,
because existence of a 2-coloring for bipartite graphs is provable in WKL0,
every countable bipartite graph G has a 2-coloring that is almost recursive and
low in G. Because over RCA0, existence of a 2-coloring for every bipartite
graph implies WKL0, there is a recursive bipartite graph without a recursive
2-coloring.
The choice of base theory for reverse mathematics strongly depends on the area
examined. For reverse arithmetic, polynomial function arithmetic is a good
choice. For much of reverse mathematical analysis, RCA0 is ordinarily chosen.
The study of projective sets in ZFC has the flavor of reverse mathematics,
although it has not been traditionally considered as such. In ZFC, one
examines the binary relation of provable implication between various facts
about projective sets. (Although second order arithmetic is a more natural
choice as a base theory, ZFC is ordinarily chosen for convenience; in most
aspects, ZFC is not too strong to act as a weak base theory for reverse
mathematics of projective sets.) One deduces equivalence of two apparently
unrelated forms of set existence axioms, say boldface Sigma-1-1 determinacy and
closure of the set of real numbers under sharps. Much rather like one studies
"recursive counterexamples" to facts in analysis--such as a recursive bounded
increasing sequence of real numbers without a recursive least upper bound--one
studies "constructible counterexamples" to, for example, the fact that every
projection of a coanalytic set is measurable. However, because of the greater
ability (in the absence of strong set existence axioms) to change the theory
through forcing, the relation of provable implication is much less linear for
general study of projective sets than for ordinary mathematical analysis.
This comes to my last point about importance of reverse mathematics: Reverse
mathematics can be used to evaluate proposed axioms. On the one hand, the
study can help establish the truthfulness of a proposed axiom beyond a
reasonable doubt. On the other hand, those who, perhaps out of an abundance of
caution (after all, an inconsistency in mathematics would be disastrous),
choose not to accept the proposed axiom, can still use the results proven in
the base theory or with such additional axioms that they accept, and ponder the
relationships between the undecidable propositions.
Dmytro Taranovsky
More information about the FOM
mailing list