No subject

Tue Aug 3 18:35:38 EDT 1999

TO:	fom at math.psu.edu
FROM:	Robert Soare, University of Chicago
DATE:	Wednesday, August 3, 1999 
RE:	NATURAL EXAMPLES
=========================================================================

NATURAL EXAMPLES IN SCIENCE:

What are "NATURAL" examples in science?  Is a black hole a "natural
example?"  The British Royal Society did not think so when they
severely criticized S. Chandrasekhar (later Hull DSP, Univ of Chicago)
when he wrote his key paper on the later evolution of stars which
won him the 1983 Nobel Prize.

Is Einstein's notion of our locally flat space being "curved" when
observed at distances of billions of light years a "natural" example,
or is it "natural" to consider only the things we can more directly
observe?  For that matter, in 1490, was it "natural" to consider an
earth which was not flat but curved back on itself?

Are these new examples "unnatural" like some heretical religious
notions, or they simply objects which exist in nature (so far as
astrophysicists can determine)?

========================================================================

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

--------------------------  REFUTATION  ------------------------------

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

NATURALNESS OF THE NOTIONS:

1. The notion of COMPUTABLY ENUMERABLE (C.E.) set was defined by
	Kleene and independently by Church in 1936 almost concurrently
	with the notion of computability itself, and is probably the
	second most important notion in computability theory, for
	many reasons.

2. In 1939 Turing defined the notion of relative (Turing)
	computability which he was prevented from developing further
	because he entered the U.K. Bletchley labs in September, 1939
	when the war started.  (Relative computability can be naturally
	defined in terms of c.e.sets.)

3. In 1944 Post combined these two  fundamental ideas to consider 
	Turing degrees in general and of computably enumerable sets.
	He asked for a c.e. set if Turing degree intermediate between
	0 (the computable sets) and 0' (the degree of Godels set),
	in order to see whether theis is only ONE unsolvable problem
	associated with c.e. sets or more than one.

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.  

--------------------------------------------------------------------

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]).
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.

These groups constructed by Boone are *real* groups with *real*
algebraic presentations, perhaps even used in differential geometry
and manifolds.  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.

----------------------------------------------------------

1.  NEW APPLICATION:  C.E. DEGREES PROVIDE SCALES FOR FRACTALS:

USES OF COMPUTABILITY THEORY CLAIMED IN THE NW-2 PAPER:

The Nabutovsky-Weinberger NW-2 exists presently only in draft form
with mostly intuition and statements (and not yet complete proofs) of
results and connections, but it suggests some very interesting
INTERACTIONS between computability and differential topology.  These
are a few direct quotes from NW-2.  There are more quotes there on
connections between c.e. sets, c.e. degrees, and (Turing degrees)
with topology and differential geometry.  See WEB page:

Nabutovsky-Weinberger (NW-2) write:

> ``Informally, each c.e. degree determines a scale, and at that scale
> there are many distinguished local minima of diameter, that are deep
> in that scale.''

For an intuitive explanation designed for logicians, see

www.cs.uchicago.edu/~soare/geometry

Regarding use of computably enumerable degrees and the Sacks Density
Theorem used in the NW-2 theorem on page 3, the authors write,

>   "For every closed smooth manifold M^n of dimension > 4, and every
>   c.e. degree \alpha, there are exp(d^n)
>   local minima of diameter functional on the subset of Met(M)
>   consisting of metrics with curvature bounded in absolute value
>   by 1;  The local minima are represented by points of smoothness
>   C^{1,\alpha}, and have depth > \gamma(d) for any c.e. degree
>   \gamma < \alpha.  These points are \alpha(d)-dense in Met(M).

This means that the c.e. degrees occur naturally in topology and
in the space of manifolds of dimension > 5 with Riemannian metric
modulo diffeomorphisms.

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.

=========================================================================

REVERSE MATHEMATICS:

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?

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.)

*************************************************************************
Robert I. Soare
Paul Snowden Russell 
Distinguished Service Professor
    of Mathematics and Computer Science			
Department of Mathematics 	     PHONE: (773) 702-6029, Secty: 702-7100 
The University of Chicago            FAX:   (773) 702-9787
5734 University Avenue		     E-MAIL:	soare at cs.uchicago.edu
Chicago, IL 60637-1546	USA  	     WEB: http://www.cs.uchicago.edu/~soare
**************************************************************************