FOM: reverse math/recursion theory

[Harvey Friedman]

The Lempp/Simpson correspondence appeared on the FOM on 6/4/98 5:51PM.

Lempp wrote:

>  From what I have heard lately (and this may be my ignorance, or lack
>  of time to tune in to FOM...), it appears that reverse mathematics
>  studies known mathematical theorems and tries to determine their
>  proof-theoretic strength in terms of axioms used. But there must be
>  more to this than just doing this for theorem after theorem. Somehow I
>  don't get the big picture, what is the eventual goal? Do you have some
>  overall "meta" conjecture about what the end result of all this will
>  be?

Already by the early 1970's I was emphasizing the apparent linear ordering
- perhaps well ordering - of logical strengths of actual mathematical
statements as perhaps the deepest mystery in all of f.o.m. and mathematical
logic. It is generally credited to me that linearity of logical strengths
is false in general, but the counterexamples are obviously ad hoc from
various points of view. The counterexamples will appear shortly in my self
contained postings series. This is a phenomenon that

	a) set theorists know full well and appreciate in the large
cardinal hierarchy and in set theoretic problems in general. Although one
large cardinal hypothesis or set theoretic problem may not imply or be
implied by another over ZF, they are verified to be comparable in
consistency strengths over and over again. It is not yet clear how to
precisely formulate this;
	b) recursion theorists know full well and appreciate in the Turing
degrees. I.e., one can "pick out" only certain specific Turing degrees
naturally. It is not yet clear how to precisely formulate this. The
formulations in terms of Borel functions on Turing degrees, and the partial
results about them, are important steps in this direction (and is of
independent interest). But its not quite the same. Especially, there is the
apparent lack of any natural r.e. degree between 0 and 0'. In fact, any
natural r.e. set seems to be (very) recursive or complete r.e. To me, this
is perhaps the deepest mystery in all of recursion theory.

And I have some time ago proved a number of results stated roughly as
follows: Let S,T be finitely axiomatized theories subject to the Godel
phenomena. Then the consistency strength of S is at most that of T if and
only if S is interpretable (in the sense of model theory going back to
Tarski) into T. This is an indication of how robust the concept of
consistency strength or logical strength is.

Let me relate this to reverse mathematics. Here are two or three "big
picture" conjectures for reverse mathematics:

1) that all of the actual mathematical statements (in the published
literature, or part of the University curriculum) subject to the scope of
reverse mathematics (and there are a great many of these) are in fact
linearly ordered under consistency strength. Or, more or less equivalently,
under interpretability;

2) that all of the actual mathematical statements (in the published
literature, or part of the University curriculum) subject to the scope of
reverse mathematics (and there are a great many of these) represent a very
small number of equivalence classes under outright provable equivalence,
and these equivalence classes are represented by a small number of simple
formal systems. [NOTE: This point goes beyond what Lempp refers to above.]

In 2), we know that the formal systems in question are NOT linearly ordered
in terms of outright provability. E.g., Hilbert's basis theorem for
polynomial rings in finitely many variables over the rationals, and Peano's
existence theorem for differential equations. See Simpson's book. However,

3) that a very large percentage of actual mathematical statements (in the
published literature, or part of the University curriculum) subject to the
scope of reverse mathematics (and there are a great many of these)
represent an even smaller number of equivalence classes under outright
provable equivalence, and these equivalence classes are represented by a
small number of simple formal systems that are linearly ordered under
outright provability.

This is a vast undertaking involving substantial points of contact with
virtually every part of mathematics - some more than others.

In fact, more or less the same mathematics continues to be taught and
required decade after decade in the undergraduate and graduate mathematics
curriculum, much of which is subject to analysis via reverse mathematics.
We continue to teach and require these icons of classical mathematics. I am
referring to such mainstays of the mathematics curriculum as

"every field as a unique algebraic closure," "the Stone-Wierstrass
theorem," "every continuous function on a compact set is uniformly
continuous," "compact = closed and bounded," "the intermediate value
theorem," "the maximum value theorem," "the mean value theorem," "every
monotone function is differentiable almost everywhere," "ordered fields =
real fields", "every real closed field has a unique real closure," "every
real closed field becomes algebraically closed when i is adjoined," "the
Cauchy-Peano theorem for differential equations," "the Hilbert basis
theorem," "the Hahn-Banach theorem," "the Radon-Nikodym theorem," "the
closed graph theorem," the Baire category theorem," "the Lebesgue
convergence theorems," "the Riesz representation theorem," the Riemann
mapping theorem," "Fubini's theorem," "Fourier transform theorems," "power
series development of analytic functions," "Cauchy's integration theorem,"
"zeros of analytic functions and omission of values," "the open mapping
theorem," "the maximum modulus theorem," "analytic continuation theorems",
"the Mittag-Leffler theorem," "the monodromy theorem," "the no-retraction
theorem," "the Picard theorem," theorems of Paley and Weiner," "Mergelyan's
theorem," "the Brouwer fixed point theorem," "the Schoenflies theorem,"
"Sylow theorems," "Ulm's theorem on Abelian p-groups," "decomposition
theorem for Abelian groups," "subgroups of free groups are free," "power
series are Noetherian," "Hilbert's Nullstellensatz," "Sturm's theorem,"
"volumes stretched by absolute value of determinant," "Cayley's theorem,"
"theorem on symmetric polynomials," "fundamental theorem of Galois theory,"
"unsolvability by radicals," "Frobenius and Wedderburn theorems on
associative division algebras," "Zorn's lemma," "the Jordan-Holder
theorem," "the Krull-Schmidt theorem," "invariance of dimensionality," "the
Wedderburn-Artin theorem for simple rings," "density theorems for rings,"
"Artin-Rees and the Krull intersection theorem," "Artin's solution to
Hilbert's seventeenth problem," "metrization theorems," "simplicial
approximation theorem," "Jordan curve theorem," "the Euler-Poincare
formula," "the contraction mapping theorem," "the excision theorem,"
"exactness of Mayer-Vietoris," "Jordan-Brouwer separation theorem,"
"implicit and inverse function theorems," "Tietze's extension theorem,"
"Urysohn's theorem on normality," "Stone-Cech compatification," "Borsuk's
Antipodal theorem," "Borsuk's separation theorem," "Brouwer domain
invariance theorem," "the Hurewicz uniformization theorem," "fundamental
theorem of the local theory of curves," "the isoperimetric inequality,"
"the four-vertex theorem," "the Cauchy-Crofton formula," "Gauss' theorema
egregium," "Gauss-Bonnett theorem," "triangulation theorems," "Poincare's
theorem on indices of a vector field," "the Hopf-Rinow theorem," "the
Hadamard theorems," "Fenchel's theorem," "the Farey-Milnor theorem,"
"Jacobi's theorems on geodesics," "Hilbert's theorem on constant negative
curvature," "Dirichlet's theorem on primes," "the fundamental theorem of
arithmetic," "Minkowski's area theorem," "Chinese remainder theorem,"
"Gauss' law of reciprocity," "Fermat's and Wilson's theorem,"
"transcendence of e and pi, and criteria," "various Diophantine equations,"
"Mobius inversion formula," "the prime number theorem," Lagrange's four
square theorem," "Hilbert's theorem on sums of k-th powers," "Bertrand's
postulate," "Minkowski's theorem," "Kronecker's theorem on approximations,"



where I only quit because I got sick and tired of compiling this. These
approx. 75 theorems are about 5% of what I have in mind for reverse
mathematics.

To carry out this program in full, one develops connections between
recursion theoretic ideas and these huge number of topics in mathematics.
The technical difficulties involved range from the straigthforward to the
often very substantial. Fresh ideas are needed each time a new topic is
addressed.

I want to address the issue that you raise when you write:

>But there must be
>  more to this than just doing this for theorem after theorem.

I have already indicated some big picture items above in 1), 2), 3). But I
strongly claim that the classification, itself, is fundamental and
illuminating.

In fact, there is a strong tradition of classification in mathematics and
science, when that classification is manageable and reveals far more
structure than would normally be expected. E.g., in finite groups and
manifolds. Admittedly, these classifications have a sharper nature to them
in that there is a completely mathematical definition of what is being
classified. But this is not the case in the sciences. E.g., classification
of insects, classification of stars, classification of galaxies,
classification of the chemical elements, classification of human genomes,
classification of musical styles, classification of humor, classification
of elementary particles, classification of subjects, classification of
rocks, classification of forces, classification of books, classification of
paintings, etcetera.

Now all of these classifications differ in some interesting ways from each
other. But they generally have some things in common.

i) many specimens are easily classified, where both the specimen and its
classification are unremarkable;
ii) many specimens are not so easily classfied, where both the specimen and
its classification are remarkable.

I have heard it said that

"if you have seen the reversal of one mathematical theorem, you have seen
them all."

Well, this absurdity becomes even more absurd when you say, e.g.,

"if you have seen the classification of one star, you have seen them all."
"if you have seen the classification of one insect, you have seen them all."
"if you have seen the classification of one finite group, you have seen
them all."

Mapping out the logical structure of mathematics in this focused sense is
of obvious fundamental importance. And classical parts of recursion theory,
in one form or another, is the basic tool that pervades reverse
mathematics. Of course, one has to combine this, in hugely varied ways,
with a myriad of mathematical topics, in order to carry this out. What more
could you ask of a definite subject area?

>What I am looking for is a small number (2 or 3) of "big"
>  problems, like I see them in r.e. degrees for example right now:
>
>  1. Is the Sigma2 theory decidable? (This has a big impact on our
>  understanding the algebraic structure, via finite substructures.)
>
>  2. What is the automorphism group of the r.e. degrees? (I am not sure
>  any more I believe Cooper's claim.)
>
>  3. Are the r.e. degrees a prime model of their theory? (The latter two
>  questions tell us a lot about definability in the r.e. degrees.)
>
>  These are all questions about one special structure, but they are the
>  important questions to me: They are the questions an algebraist or
>  model theorist would ask about a structure to get the global
>  picture. And I admit I am pretty fond of that one structure...

These are reasonable technical questions concerning a structure that arose
in connection with the foundations of mathematics. This is not the same as
doing foundations of mathematics. In fact, there are deep problems in the
foundations of mathematics that lie at the heart of classical recursion
theory. Here are three.

1. I have already alluded to this above. Is it the case that every r.e. set
occurring in nature is either (very) recursive or complete r.e.? This is a
dramatic phenomenon. It also suggests that one needs more of a reason than
I usually hear from recursion theorists as to why one intensively studies
(for nearly fifty years) the r.e. sets that are neither recursive nor
complete r.e. Do you know of a single branch of mathematics in which a huge
effort for decades goes into the classification and understanding of a
structure for which not a single natural example of an element of that
structure has ever been given, and where the prevailing opinion is that
there not a single natural example of an element of that structure?

2. What Turing degrees occur in nature? There are various levels of
strictness in the interpretation of this question. The strictest form is
that the degree in question must be the degree of some set that has been
considered in the nonlogic math literature. Less strict is that it must be
the degree of some set that can be given a strictly mathematical (as
opposed to logical) definition. Under the most liberal interpretation, the
natural set can use logical notions. Obviously, the version most amenable
to precise formulation (at this time) is the last one. I alluded to this
above when I mentioned work on Borel functions on Turing degrees. This does
not really address the question directly, but obviously is a good step and
very interesting in its own right.

3. Church's thesis. Perhaps the state of the art on this is present in an
article by William Seig, which I forget the reference to. Does anybody
know? DIscussion of work on Church's thesis could be a very good topic for
FOM. In any case, I still believe that something new and dramatic can be
done along the following lines: conditions are placed on computation and/or
a family of functions, which are strikingly general and fundamental
looking, which, very surprisingly, forces it to give only the usual partial
recursive functions or r.e. sets, or however you set it up.

It is clear that these questions are of incomparably greater general
intellectual interest than the sorts of questions you raise above. However,
these questions differ greatly in that they are not precise yes/no
questions. They demand a kind of general intellectual power that is by no
means limited to the ability to construct technically difficult arguments.
And it may well turn out that proposed answers to them may be more or less
convincing, and that there may be long periods of improvements in the
answers. Nevertheless, these are (perhaps some of) the real questions that
lie at the heart of the point of recursion theory, which came out of the
foundations of mathematics.

But let me make a practical point. These questions 1-3 are extremely
difficult, and have been very neglected in recent years. Consequently,
there is a shortage of good ideas. Thus, from a practical viewpoint, they
cannot be expected to sustain the field of recursion theory at this time.
However, I have no doubt that the work of the leading recursion theorists
over long periods of time will be evaluated far more in terms of what
insights they have provided to these (and perhaps other similar kinds of)
questions 1-3 than to the kinds of questions you emphasize. It therefore is
vital to the area for these questions 1-3 to be at least emphasized.

However, the use of recursion theory in reverse mathematics is already
unquestionably potentially rich and varied. And reverse mathematics, as
opposed to these kinds of questions 1-3 above, has difficulties ranging
from zero to extremely high.

So in summary, for recursion theory, I would emphasize 1,2,3 above, plus
reverse mathematics as a target of application.