FOM: Slaman on long range goals of recursion theory
Stephen G Simpson
simpson at math.psu.edu
Wed Apr 15 11:48:54 EDT 1998
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
> 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.
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
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
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
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
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
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
More information about the FOM