FOM: more reverse math/recursion theory

Harvey Friedman friedman at
Sun Aug 2 16:51:35 EDT 1998

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

Lempp wrote:

>  I am not trying to put down any part of logic, I think that logic has
>  many branches that are mathematically intrincically interesting (the
>  MAIN criterion for good mathematics in my opinion), and that we should
>  learn to appreciate all the variety rather than try to convince each
>  other that one branch is more significant than others? Of course,
>  everyone has his/her own opinion about what is more interesting, but I
>  try to emphasize the positive and convince others that what I find
>  interesting really IS so.

The problem with mathematical logic today is that there is too little
variety. The situation has gotten so critical that I find it very hard to
imagine that someone could get hired in a tenure track position for doing
truly innovative work in f.o.m. unless that work was really spectacular - a
very high standard indeed for a junior person looking for a tenure track

This has been the result of consistently bad judgment by most of the
leaders of mathematical logic, who are more interested in perpetuating
their uninspired technical niches, whose significance cannot be
appropriately explained to anyone outside of that niche, than in dealing
with fundamental intellectual problems.

The appropriate way to conduct research in logic is to constantly reassess
the appropriateness and legitimacy of current technical developments in
light of the original purposes from which they evolved. And if new purposes
have emerged, then these should be laid out explicitly, and compared in
importance with the original purposes.

One should also consider traditional mathematical values in order to test
one's ideas. I mentioned in the previous e-mail that the r.e. degrees lack
a property that seems to be crucial in all valued mathematical structures
that have been deeply investigated (that I know of): namely a variety of
interesting exmaples. In this case, people suspect that there are no
natural r.e. sets other than (very) recursive sets, and complete r.e. sets.
As I have indicated earlier, shedding light on why there are no such
examples would be of great interest.

Let me be frank. I would not be saying this kind of thing if I didn't think
that the situation - both in recursion theory and much of the rest of
mathematical logic - has badly deteriorated. It is clear that I did not
have much effect against this deterioration - which, I say again, is by no
means limited to recursion theory! - despite over thirty productive years
of research in this field. Since doing my own work and minding my own
business has had such minimal influence over this deterioration, I might as
well bring these issues out in the open - or stop complaining about what
has happened. I have chosen the former, at least for the moment.

Lempp wrote:

>  I guess I would summarize my point of view as follows:
>  I don't view recursion theory to be an isolated area, but rather (like
>  any field in mathematics) one driven both by mathematically
>  intrinsically interesting problems (which I would judge by their depth
>  and intrinsic mathematical beauty) and by applications to other
>  subfields. I believe that recursion theory (like any other area of
>  mathematics, incl. reverse mathematics) offers problems of both kinds,
>  and I find both types of problems equally interesting. Of course, both
>  directions also have their dangers: on the one hand, the former can
>  become too esoteric; on the other hand, the latter can become too
>  ad-hoc. One has to constantly watch out for these dangers, and they
>  will be judged differently by different people.

The classical part of recursion theory are obviously well embedded in other
parts of logic, and the key definitions are of obvious fundamental
importance. [The classical part consists essentially of the work of Godel,
Turing, and Kleene in recursion theory]. Furthermore, those key definitions
allow us to precisely formulate a variety of important impossibility
theorems. However, the question arises as to the effort/value ratio as we
move far past the classical development. Recursion theorists are not going
to easily convince non recursion theorists of "instrinsic mathematical
beauty." And the lack of examples is a severe impediment.

Let me mention a subject whose history is different, but does bear some
similarities worth discussing. And that is descriptive set theory. Among
set theorists post Cohen, the emphasize was mostly on the projective
hierarchy, and its connections with large cardinals. This is very well
understood now.

In constrast, the emphasis has turned to classification of Borel and
related equivalence relations, and group actions, up to Borel and related
reducibilities. There are zillions of rich examples from lots of branches
of mathematics, and the results in this new descriptive set theory directly
relate to some mathematician's issues. E.g., the Glimm-Effros dichotomy - a
concern of the nonlogicians Glimm and Effros - has been analyzed,
strengthened, extended, and conjectured about in the original as well as
the myriad additional natural contexts. And the techniques involved are
highly sophisticated and varied. There is plenty of interaction with lots
of mathematics. Thus descriptive set theory has undergone a serious
transformation. This is the new descriptive set theory.

It is not so obvious how recursion theory should undergo such a
transformation. Recursive algebra was an earlier attempt at this. However,
it is not as successful, since one often has to formulate things like this:
if the structure is effectively presented, then such and such cannot be
done effectively. The original mathematical situation being addressed
doesn't have effectively considerations stated explicitly. The new
descriptive set theory doesn't have this awkwardness.

Reverse mathematics has a lot of technical overlap with recursive algebra,
but the effectivity considerations are properly behind the scenes. Reverse
mathematics seems like the ideal setup for the new recursion theory, with
substantial points of contact with proof theory and combinatorics.

Finally, I don't see any substantial problems with ad hocness in the
current development of reverse mathematics. *Reverse mathematics is well
positioned to become the new recursion theory.* Fortunately, the overdue
Simpson book is finished and should be available momentarily.

More information about the FOM mailing list