FOM: "profound changes"

Harvey Friedman friedman at
Tue Aug 11 21:24:08 EDT 1998

Lempp writes (see SImpson 1:57PM 8/11/98):

>  I believe that logic in general, and recursion theory in particular,
>  is already undergoing some profound changes.

How would you characterize these changes? We may not agree on the nature of
many of these profound changes. E.g., one profound change I often point to
is that people in mathematical logic have gotten far removed from
foundations of mathematics in the usual sense of the word. But I am sure
that this is not the profound change you have in mind.

There can be no doubt that model theory has undergone profound change. The
main thrust is now applied model theory, and the scope of applications is
difficult to predict. Also the nature of the applications is diverse - not
only in subject matter, but also in kind. These include
	a) new proofs of known results from other branches of mathematics;
	b) new kinds of generalizations and extensions of known results
from other branches of mathematics;
	c) first proofs of open questions from other branches of mathematics.

Of course c) is the rarest, and c) further subdivides into

	c1) those that can be fairly easily redone by traditional nonlogic
	c2) those that can be redone by traditional nonlogic methods only
with difficulty;
	c3) those that cannot yet be done by traditional nonlogic methods.

Also a) subdivides as follows:

	a1) the new proof is obviously simpler;
	a2) the new proof is not simpler, but is clearly different;
	a3) the new proof is essentially the same, but in a different language.

Also there is the overall subdivision into

	i) proofs that use a little bit of logic and a little bit of math
outside logic;
	ii) proofs that use a lot of logic and a little bit of math outside
	iii) proofs that use both a lot of logic and a lot of math outside
	iv) proofs that use a lot of math outside logic and a a little bit
of logic.

I think that it would be very valuable if someone or some group of model
theorists could write a comprehensive survey of applied model theory that
is based on such a classification, going back to the elementary beginning.
E.g., those old applications of compactness of predicate calculus that
show, e.g., that if every finite subset of a graph has a certain kind of
property, then the whole graph does (Tarski?). It falls into b), a3), i)

>  Let me start with the example of the Turing degrees globally, and
>  the r.e.  Turing degrees, dear to me, and to me simply two beautiful
>  mathematical structures: A number of problems about this structure
>  were posed in the 1960's (algebraic structure, definability
>  questions, homogeneity, rigidity) which turned out to be very hard
>  to answer and which took a lot of technical work. The early 1990's
>  have seen some spectacular developments, and most of these problems
>  have now been solved, using all the very technical and hard results
>  that turned off a lot of people in the meantime. This is regrettable
>  but, given the difficulty of the structure, unavoidable.

This work is certainly intricate, difficult, and challenging. I was under
the impression that one is still very far from any kind of full
understanding of the structure. But for me, the issue is about something
else. There is a tendency for people who engage in this sort of very
focused, specific long term project, to get into an identifiable mindset
which I will describe momentarily. And just to indicate that what I am
concerned about has nothing whatsoever to do specifically with recursion
theorists or recrusion theory, let me generalize about the pattern that I
have witnessed in other subareas of mathematical logic. I suspect that it
occurs in other areas of mathematics as well.

People in the field realize that some basic structures are hard to analyze,
and that if one works hard enough, one can start to get some structural
information. At some point, initial breakthroughs in this vein are made by
some people, which creates a stir. These people become the opinion makers
of the field, and have students extending their results. Then research in
the field starts getting evaluated more and more by what structural
information it reveals about these basic structures, and less and less by
any higher intellectual goals.

By higher intellectual goals, I mean, for instance, the reasons why these
basic structures were defined in the first place - and the strengths and
weaknesses of these basic structures for the purposes they were created
for. The field starts getting redefined in terms of the structural analysis
of these particular basic structures. Other issues that were predominant -
perhaps at an informal level only - in the early stages of the subject,
become downplayed, or even marginalized.

In late stages of this process, researchers start to forget what any of
these higher intellectual goals are or were ever conceived to be.
Eventually, the students no longer come into contact in any substantial way
with any higher intellectual goals.

Before going any further, let me indicate how this is manifested in
practice. Some people will do research that doesn't fall into this focused
mode. In some cases their research deals directly with the higher
intellectual goals - at least more directly than the focused structural
studies that dominate the field. But they find that their careers are
seriously restricted compared to people working on the focused structural
studies. They find that the major places of employment are populated mainly
by the people who made the initial breakthroughs in the focused structural
studies, and their students, and the students of their students, etcetera,
who have become accustomed to automatically evaluating research in terms of
the focused structual studies. In a tight labor market, these people (doing
research that doesn't fall into the focused mode) may even become

In any case, the distinction between the careers of those who concentrate
on the focused structural studies and those who don't becomes well known
and reinforces itself.

Another strong factor in the equation is the peer review method of awarding
grants. When money is tight, mixed reviews will generally kill funding.
Reviewers will naturally reserve their high praise for work that is very
much like theirs; high praise for work very much like theirs is essentially
the same as high praise for their own work. Consideration of higher
intellectual goals could make such a system fairer. But consideration of
higher intellectual goals becomes so remote a consideration that it plays
essentially no role. The difficulties involved in getting funding for
virtually anything outside the focused structural studies become
insurmountable for almost anyone.

Such a development is normally accompanied by striking missed
opportunities, and threatens to throw the field into the "ashcan of
history." Such a striking example for recursion theory is afforded starting
in the 60's by asymptotic complexity theory.

As the computer revolution progressed, it became more and more compelling
to rethink the wider intellectual issues surrounding the very definition of
recursive functions - which is even more basic than degrees and lattices of
r.e. sets. The compelling idea is to consider the resources involved in the
computation of recursive functions. Asymptotic bounds on time and space are
the most natural ideas to start with. This is an incredibly good idea - the
creation of asymptotic complexity theory. The rules are overhauled, the
tables are turned, and a whole different set of issues - technical and
conceptual - arise. And the points of contact with other branches of
mathematics, engineering, and elsewhere, are very striking indeed.

Yet recursion theorists didn't embrace this as recursion theory, or widen
their field at that time by calling it "computability theory" and
refocusing the field on genuine computation. In genuine computability
theory, computation itself is analyzed, and the resources involved
inevitably become of critical importance.

The people in recursion theory at the time of the initial development of
complexity theory were certainly gifted enough to work in it and promote it
and make substantial contributions to it. Yet they continued to remain
focused on these specific structural studies.

I bring this matter of recursion theory and asymptotic complexity theory up
just as a relatively clear example that many people can relate to. There
are many other examples of missed opportunities that are certainly not as
clear; some of which also involve other areas of mathematical logic.

Such is the danger of minimizing higher intellectual goals. Such is the
difficulties that can be created for people who go against the grain. The
founders and initial developers of asymptotic complexity theory thrived
because they developed a constituency in engineering; not because of their
reception in recursion theory.

>  But recursion theory is not only degree theory. There has always
>  been a lot of work in Russia, and more and more in the U.S., on
>  applications to algebra and model theory. Some of the work has not
>  been very enlightening (but of the kind you mention), but a lot of
>  it has been very interesting, and the field still seems in its
>  infancy.

I personally rarely hear much about this, as I have come to be familiar
with the people who seem to generally be called "the leading U.S. recursion
theorists." I think it would be valuable if you could give the FOM a
picture of what these "applications to algebra and model theory" look like.
What are the levels of funding  for applications of recursion theory to
algebra and model theory?

>  Another application of recursion theory has been seen in recent work
>  by Slaman et al. in descriptive set theory, using recursion
>  theoretic methods to solve long-standing problems there.

I appreciate this, and Slaman mentioned it in a posting on FOM. This is, of
course, a typical point that is made by a field - whatever shape it is in.
Namely that it is good for something in another field. But the question
always is (regardless of the context): is this typical or atypical or
highly atypical, or extremely atypical? And to what extent is the
connection permanent? E.g., Slaman is easily good enough to do descriptive
set theory without recursion theory, but certainly will find it convenient
to use recursion theory. What are the levels of funding for applications of
recursion theory to descriptive set theory?

>  You mention reverse mathematics. Remember that many results there
>  are using techniques developed by classical recursion theorists
>  working on "uninspiring topics".

Of course, reverse mathematics will very mostly use nonmodern techniques,
ocassionally use more modern techniques, and sometimes need its own new
recursion theoretic techniques. The same is true of the "new descriptive
set theory" of Hjorth, Kechris, etcetera. Lots and lots of use of classical
Borel theory, lots of forcing arguments, etcetera, and various new

>This simply shows me that
>  intrinsically interesting, beautiful mathematics will survive and
>  find applications no matter what. I welcome the strong connections
>  between recursion theory and reverse mathematics that emerge, and I
>  agree that there are a number of interesting problems in reverse
>  mathematics (some quite deep, some more ad hoc).

I don't agree that what is regarded by accomplished technicians as
"intrinsically interesting and beautiful" will generally survive and find
applications. History shows that many such developments go into the "ashcan
of history," and more typically only a relatively small fragment of such
things have any permanent place in the history of ideas. I want to
emphasize that by far the best way of knowing that - or maximizing the
probability that - one has done something of permanent value is to:

	i) see that it is closely related to issues of obvious higher
intellectual importance; and/or
	ii) see that it is of obvious general intellectual interest.

In contrast, for example, one could

	iii) see that it is extremely difficult and provides deep
information about basic structures.

But the permanent value of iii) depends so much on the status of the basic
structures and the relevance of the information provided to higher
intellectual issues. Thus i) and ii) are a much better bet than iii),
although certainly both are difficult to do.

By the way, give me an example of what you mean by "ad hoc" in this context.

>  What I do object to is people trying to decide what is (objectively)
>  interesting mathematics and what isn't. This will always be
>  subjective, in the judgment of each researcher, and there will
>  always be disagreements. I do believe that while we certainly hav
>  every right to voice our views, we should be tolerant and respectful
>  of each other's mathematical tastes.
Let me repeat what I posted earlier in response to this on the FOM:

 Let me just say, briefly, that in my opinion, there are important
  objective components to this, and that the collective judgments
  determine the levels and nature and effectiveness of employment,
  recognition, influence, education, and communication - in fact, even
  the very survivability of subjects. From your persepctive, perhaps
  Steve and I are intolerant. From my perspective, many subcommunities
  and individuals are intolerant, and we are interested in reform. I
  have more to say about this.

More information about the FOM mailing list