FOM: No natural examples

[Harvey Friedman]

Reply to Soare 5:35PM 8/3/99.

NOTE: I have just seen a very interesting posting of Odifreddi, 10:06AM
8/4/99 in which he discusses a related problem of naturalness. We need to
make a distinction here:

I. Is there a natural example of an r.e. set which is neither recursive nor
of the higher degree? This highest degree is the degree of complete r.e.
sets. The so called complete r.e. degree. An r.e. set can be of the
complete r.e. degree without itself being a complete r.e. set.

II. Is there a natural example of an r.e. set which is neither recursive
nor complete? This is a different question.

Simpson, Shipman, and I were thinking of problem I. This is the version
that is crucial for the theory of r.e. degrees, a subject of intense study
in recursion theory. I.e., is there a natural example of an r.e. degree
other than the minimum or maximum one?

Odifreddi's example of II is of course interesting, and I should have been
aware of this. It is incomparably more natural by far than any example I
know of for I. However, it is most interesting to try to see if Odifreddi's
example can be improved, since it relies on an artificial encoding, any one
of which seems to be unnatural. So it probably does not meet the normal
criteria most mathematicians apply - at least without modification.

In any case, regardless of how definitive, it was an important contribution
to the discussion, and FOM.

**********
Soare quotes Simpson:

	>SIMPSON writes (FOM, July 28-2)
	>
	>>  Usually, when mathematicians undertake an intensive
investigation of
	>>  some specific structure or class of structures, the need for
such an
	>>  investigation has already been motivated by a set of specific,
natural
	>>  examples showing the richness and interest of the subject.
	>> ...
	>
	>>  Contrast this with the r.e. sets and degrees ...
	>>  The only natural examples known to
	>>  date are the original ones, i.e. the halting problem and the
complete
	>>  r.e. degree.
	>>  Thus there is really only one example
	>
Soare writes:

	>This is a canard so spurious and so often refuted that I am amazed
	>anyone would trot it out here.

Below you are challenged to make good on your refutation. You are a leading
recursion theorist, and so many of us expect quite an illuminating response
to this challenge!

	>NATURALNESS OF THE NOTIONS:
	>
....
	>4.  Friedberg and Muchnik in 1956/57 solved Post's problem by
	>	producing an intermediate c.e. degree.  His method (as noted
	>	in his paper) will produce an infinite collection of different
	>	c.e. degrees.

None of which are natural by anything close to the usual standards of
mathematicians.

	>APPLICATIONS OF NONTRIVIAL C.E. DEGREES:
	>
	>1.  OLD APPLICATION: WORD PROBLEMS FOR GROUPS
	>
	>There are a number of examples of "natural" occurrences in mathematics
	>of c.e. degrees other than 0 (the degree of the computable sets) and
	>0' (the degree of Godel's diagonal c.e. noncomputable set K [1931]).

You are challenged below to write one down.

	>For example, after the original Boone-Novikov theorem was proved,
	>Boone improved it to show the stronger statement that for every
	>computably enumerable (c.e.) set A, there is a finitely generated
	>finitely generated group with word problem Turing equivalent to A.

Surely you don't mean "finitely generated," since there are continuumly
many of them. You must mean "finitely presented."

The class of all finitely presented groups is completely natural. However,
obviously only very special individual finitely presented groups are
natural. E.g., the test question:

roughly how big a presentation do you need so that the word problem is of
intermediate degree,

is very difficult. Presumably the usual proof needs a ridiculous number of
generators, with no natural pattern, and therefore not prima facie natural.
Presumably, a big advance would be needed to get a natural finitely
generated group with word problem of intermediate degree. Can you make such
a big advance?

Here is the challenge:

**on the FOM list, write down a finitely presented group that you can prove
has a word problem of intermediate degree.**

	>These groups constructed by Boone are *real* groups with *real*
	>algebraic presentations, perhaps even used in differential geometry
	>and manifolds.

Write down just one of these finitely presented groups for which you can
show its word problem is of intermediate degree, and let's see how natural
it is.

	>They are at LEAST as natural as, say, the Weierstrass
	>example of the continuous nowhere differentiable function and other
	>such examples routinely taught to graduate students in mathematics
	>and covered in standard analysis textbooks like Titchmarsh.

What are "they?" By the way, I recall seeing an example of a continuous
nowhere differentiable function defined through trigonometric series that
is quite elegant and simple to write down. And if my memory serves me
right, you can write down a very sensible geometrically clear sequence of
continuous piecewise linear selfmaps on the closed unit interval which
uniformly converge to a nowhere differentiable selfmap of the unit
interval. Let us compare that with the particular finitely presented group
with word problem of intermediate degree that you are going to write down
for us on the FOM. In fact, I'm sure the FOM readers would like to see any
example of such a group that is remotely comparable to any example of a
continuous nowhere differentiable function that appears in any analysis
textbook.

	>The Nabutovsky-Weinberger NW-2 exists presently only in draft form
	>with mostly intuition and statements...
	>Nabutovsky-Weinberger (NW-2) write:
	[extensive quotes here]

Perhaps some connection like this will be useful to you as you seek to
justify the interest of work on r.e. sets - it's much too early to tell how
this will pan out. In particular, it would be nice to hear from other
recursion theorists about your claim that "the c.e. degrees occur naturally
in topology and in the space of manifolds of dimension > 5 with Riemannian
metric modulo diffeomorphisms." The impression I got from the Boulder
meeting is that they regard your claim as premature.

But this is not on the face of it related to the issue of natural examples.
E.g., can you describe one particular geometric object that represents an
intermediate r.e. degree, here on the FOM?

	>It is unusual and very encouraging to find quotes in a topology paper
	>and results which link up computability and c.e. sets with local
	>minima in differential geometry.

But in order to use this to justify the interest of work on r.e. sets you
are going to have to do much more than find quotes.

NOTE: I am also interested in the problem of finding a fruitful
interpretation of r.e. sets in core mathematics. My efforts along these
lines concern the dynamics of rational piecewise linear selfmaps on the
unit square. Here the mathematics and the recursion theory are easily
mutually understandable.

	>QUESTION FOR SIMPSON AND H. FRIEDMAN:
	>
	>QUESTION 1-RM. (FOR REVERSE MATHEMATIFS RM)
	>
	>WHAT "NATURAL" examples are there of NEW DISCOVERIES (as opposed to
	>analysis of OLD results in some proof system) in topology, manifolds,
	>differential geometry or related areas for contributions of reverse
	>mathematics?

I am going to give a very short answer and also a much longer answer.

The short answer: the number of bytes of publications in reverse
mathematics divided by the number of bytes of publications in recursion
theory is approximately equaled to the number of such things in reverse
mathematics divided by the number of such things in recursion theory, where
0/0 = 0.

Here is the longer answer.

Why do people ask such questions? Outsiders do, when they do not understand
the point of an area of research, and/or suspect that it has veered away
from well defined motivation. They look for applications or at least
connections to something they feel much more positive about.

As you are well aware, people outside recursion theory are not comfortable
with details about the lattice of r.e. sets, r.e. degrees. Such details are
an acquired taste. Recursion theorists know this. They have three main
choices:

1) ignore the whole matter and concentrate on the work that they like to do;
2) try to motivate work on the lattice or the degrees to get people outside
recursion theory to be more positive about it;
3) try to find or document "applications" of work on the lattice or the
degrees to get people outside recursion theory to be more positive about it;
4) try to find or document "applications" of at least the methods used to
work on the lattice or the degrees to get people outside recursion theory
to be more positive about it.

The overwhelming number of recursion theorists have picked choice 1). Soare
has picked 3) and 4), with a very broad interpretation of "applications." A
lot of this activity recently has been motivated by a posting of Simpson of
the Boulder meeting posted on the FOM.

But the recursion theorists have abandoned 2) as far as I can tell. In
other words, activists in the recursion theory community will no longer
rely on the intrinsic interest of the subject in order to get people to be
more positive about it.

**MY ADVICE: expand the scope of recursion theory to include new topics of
greater intrinsic interest.**

The striking developments right at the beginning of what we now call
recursion theory (and you like to call computability theory) are of such
general intellectual interest that they are more striking and of more
general intellectual interest than the sum total of all of the work in
recursion theory that followed, including these so called "applications" of
varying degrees of interest that you cite in your 48K posting. There are
arguable exceptions to this judgment *for particular communities* such as
the pure mathematics community, where most notably the MRDP theorem is such
an exception. But in the wider combined intellectual community of
philosophers, applied mathematicians, scientists, and engineers, I have
little doubt about this.

Similarly, the striking developments right at the beginning of what we now
call proof theory, or also what we now call model theory, or also what we
now call set theory, are also of such gii that they are more striking and
of more general intellectual interest than the sum total ... And again,
*for certain particular communities*, there probably are exceptions.

E.g., in the 1930's do you really want to ask what "NEW DISCOVERIES in
topology, manifolds, differential geometry..." come out of the theorem that
no reasonable consistent formal system proves its own consistency? It is
such a fundamental matter that is of such wide general intellectual
interest that asking this kind of question simply reflects poorly on the
person asking it. It is as if the person asking the question doesn't
understand the point of the theorem.

Similarly, when a formal analysis of algorithms is made, and then many
other ones are made and shown to be equivalent, thereby establishing a
robust analysis of algorithms, if someone turns the crank and grinds out
"what NEW DISCOVERIES in topology, manifolds, differential geometry..."
come out of this, in the sense that you mean; i.e., not: what algorithmic
decidability and undecidability appear in topology, manifolds,..., then
again that reflects poorly on the person asking the question - they simply
don't understand the profundity and importance of what has been
accomplished.

However, if they ask back then: now that you have given a formal analysis
of what algorithmic decidability and undecidability mean, tell us what
algorithmic decidability and undecidability results do you have in
topology, manifolds, differential geometry, ..., according to the new
analysis of algorithm - then that is reasonable. In fact, that is a seminal
question which was later very successfully addressed in many ways.

Analogously, reverse mathematics is in its similarly early stages, when it
is of obvious general intellectual interest, and your question simply
reflects poorly on your understanding of the evolution of subjects in
general, and reverse mathematics in particular. [For more fundamental
misunderstandings on your part, see Simpson's posting 8:56PM 8/3/99]. The
right question, in analogy to the previous paragraph, is: does reverse
mathematics apply to fundamental contexts in mathematics, and that is a
seminal question that is being dealt with; e.g., the Hilbert basis theorem,
etcetera, and the systematic analysis of mathematics from the standard
graduate curriculum.

The right answer to the right question is that I expect reverse mathematics
to ultimately connect up with **most** of mathematics.

	>QUESTION 2-RM.
	>
	>What evidence is there tht Godel did anything in RM or would have been
	>interested at all in RM?  (He certainly very interested in
	>computability theory.)

Barry Mazur and David Mumford ran a seminar at the Harvard mathematics
department on reverse mathematics in the early 80's. Neither Simpson nor I
had anything whatsoever to do with this, except the existence of our work.
I have had frequent and recent discussions with Mazur about reverse
mathematics, and he remembers the main formal systems these days. He
regards the subject as "obvious interesting; its interest is self evident."
My discussions with Godel indicated, as expected, that he also is fully
capable of recognizing self evidently interesting things - just as Mazur
and Mumford are.

Also, from my discussions with Godel, and from my discussions with others
who have talked to Godel, he was quite sensitive to the distinction between
foundations of mathematics and mathematical logic pursued without
motivation from the foundations of mathematics. That is worth keeping in
mind.

**********

What is your hidden agenda for asking this question?:

	>WHAT "NATURAL" examples are there of NEW DISCOVERIES (as opposed to
	>analysis of OLD results in some proof system) in topology, manifolds,
	>differential geometry or related areas for contributions of reverse
	>mathematics?

What is your hidden agenda for asking this question?:

	>What evidence is there tht Godel did anything in RM or would have been
	>interested at all in RM?  (He certainly very interested in
	>computability theory.)

Let me close by repeating:

**MY ADVICE: help to expand the scope of recursion theory to include new
topics of greater intrinsic interest, instead of trying to defend the
subject as it is in terms of "applications" or "applications of its
methods."**

PS: I wouldn't give that advice unless I had concrete suggestions.