FOM: Slaman on long range goals of recursion theory

[Stephen G Simpson]

In my posting of 24 Jan 1998 18:09:39 I presented a non-exhaustive
list of topics to be discussed on the FOM list.  One of the topics
was:

 > What can technical work in mathematical logic contribute to
 > f.o.m. research?  More specifically:
 > 
 >   a. What can model theory do for f.o.m.?
 > 
 >   b. What can proof theory do for f.o.m.?
 > 
 >   c. What can recursion theory do for f.o.m.?
 > 
 >   d. What can set theory do for f.o.m.?

Apropos subtopic c, there is a recursion theory mailing list at
<comp-thy at listserv.nd.edu> which has been largely inactive.  Recently
Ted Slaman posted his views on the long range goals of recursion
theory.  I reproduce Slaman's message in its entirety, below.

-- Steve

-----

 From: "Theodore A. Slaman" <slaman at math.berkeley.edu>
 Subject:      long range goals
 Date:         Sat, 11 Apr 1998 11:15:53 -0700
 
 Mathematical discussions routinely turn to progress with regard to
 long range goals and to the nature of those goals.  In the past month,
 I have been in such conversations with colleagues, with graduate
 students, with undergraduates who are deciding whether to
 enroll in the graduate program at the University of California, and with
 UC undergraduates who are trying to decide which course to take next.
 
 If I have my way, then I have discussions about recursion theory every
 day of my life.  Even my wife, who is not a mathematician, has learned
 to tolerate it when I talk about recursion theory with her.  (She does
 attempt to change the subject after a while.)
 
 But enough about that.  I would like to attempt something of a
 response to the original question on the directions and goals of
 recursion theory.  Before I do, allow me some caveats. First, I owe
 most of my mathematical perspective to my thesis advisor Gerald Sacks.
 If you know him, then I will be gratified if you recognize his
 teaching in what I write below.  Second, the examples that I used
 reflect my own interests and experience, but I do not intend to imply
 that anyone else should be so limited.  Third, I believe that if these
 discussions are to be valuable, then they have should have
 mathematical consequence, so I will do my best to get to something
 mathematical.
 
 Best regards,
 Ted Slaman
 
 
 ----------------------------------------------------
 
 
 There is a particular perspective obtained by consistently including
 an understanding of "definability" in the solution to mathematical
 problems.  It is the assumption of that vantage point which I identify
 with recursion theory.  Of course, it is not only "recursion
 theorists", but also computer scientists, descriptive set theorists,
 and so forth, have claim to it; many of us ascend but we do not all
 look in the same direction.  You could express what we have in common
 by saying that we are all trying to understand the interaction between
 the mathematical objects and the means needed to speak about them.  I
 am fascinated by this enterprise, which I find as fundamental as any
 other mathematical investigation.
 
 What about that "interaction"?  I will mention a few aspects of it and
 comment on some of them.
 
 -- Calibration:  We have various hierarchies of definability, from
   subrecursive to set theoretic.  We  refine them to suit their
   context.  We study them, their closure properties, their boundaries,
   their robustness, etc.
 
 -- Evaluation:  The mathematical world is full of  natural examples, we
   compute their positions.
 
 -- Structural representation:  We have a variety of structures which
   capture elements of definability.
 
 For example, we have the various structures based on degree such as
 the Turing degrees, the arithmetic degrees, the hyperarithmetic
 degrees.  It is one of my long range goals to characterize their
 theories, their isomorphism types, their definable predicates, their
 automorphism groups, their similarities to each other, their
 differences from each other, and every other thing about them.  And to
 my delight, combining the efforts of many of us over a long period of
 time, this one seems close.
 
 
 
 -- Interaction: We move to other mathematical domains and attempt to
   blend the understanding of definability with the indigenous
   intuitions.
 
 In my own experience, this is a valuable endeavor.  I only wish that I
 had greater range.  But I did have a recent experience along these
 lines.  Sierpinski (1936) asked the following question: Does there
 exist a set of reals $U$ such that every uncountable analytic set $A$
 is a continuous bijective image of $U$?  I showed that the answer is
 "yes".  Though not the most elegant proof known now, the original
 proof was heavily based on definability.  There still the element of a
 priority argument left in the boiled-down proof.
 
 John Steel has the office next to mine, and after I showed him the
 solution to Sierpinski's problem I asked him if I was now a "set
 theorist".  I was hoping for admission to the set theorist's ranks,
 but he told me "no" without even taking a breath.  I was disappointed,
 but I decided that he was right.  My experience while working on the
 problem was based on an understanding of definability, and I was all
 recursion theorist.  (Steel later recanted.  He decided that because I
 had used a well ordering of the reals, I must be a set theorist.  Go
 figure.)
 
 Let me pose a related problem which I am still not able to solve:
 
   Does there exist a projective set of reals $U$ such that every
   uncountable analytic set $A$ is a continuous bijective image of $U$?
 
 -- Introspection: The hierarchies of definability to which I have
   referred are based on natural examples: definability by computation,
   definability in elementary arithmetic, definability in analysis,
   definability in Godel's $L$, etc.  We should ask ourselves to what
   extent are these hierarchies complete, intrinsic, continuous, and so
   forth.
 
 I believe that these issues are the same as the ones in set theory,
 when one considers the consistency strength hierarchy.
 
 There is a beautiful conjecture of Martin and a beautiful theorem of
 Steel, phrased in terms functions from the reals to the reals which
 are invariant under Turing degree, which I find to be strong evidence
 for the view that there is one hierarchy of definability, it is well
 ordered, and it is based on the Turing jump.
 
 Here is a precise conjecture of mine based on Martin's:
 
 Definition: A closure operator is a function $f$ from reals to sets of
   reals such that the following conditions hold.
 
   1. For all $x$, $f(x)$ is closed under join and relative computability.
 
   2. For all $x$, $x\in f(x)$.
 
   3. For all $x$ and $y$, if  $y$ is recursive in $x$, the $f(y)$ is a
   subset of or equal to $f(x)$.
 
 Natural examples of closure operators are the functions that map $x$
 to the set of reals recursive in $x$, or to the set of reals recursive
 in $x'$, or to the set of reals arithmetically definable in $x$, or to
 the set of reals in $L(x)$.  There is nothing in the definition that
 would require $f(x)$ to be identified with a definable closure of $x$,
 but you could well expect an notion of definability to provide such an
 $f$.
 
 Following Martin, for such $f$ and $g$ say that $f<g$ if there is a
 cone of $x$'s such that $f(x)$ is a subset of or equal to $g(x)$.
 
 Conjecture: (AD) The closure operators are well ordered.  Further, if
   on a cone $f(x)$ has a greatest element $a_x$, then on a cone its successor
   has greatest element $(a_x)'$.
 
 Of course, the use of AD should scale appropriately with the class of
 closure operators being considered.  I have verified the conjecture
 for the case of Borel closure operators.  In $L$ the conjecture fails,
 but the counterexample functions exploit the fact that the cone above
 $0^\#$ is missing from the constructible reals.
 
 Even so, just having the conjecture for Borel functions is
 interesting.  For example, the only Borel closure operators which
 associate reals $x$ with Scott sets $f(x)$ are those such that $f(x)$
 is closed under the Turing jump.  Now try to base a notion of "reals
 definable from $x$ using weak Konig's lemma" without reducing to
 something that was already identified in Kleene's hyperarithmetic
 hierarchy.