FOM: "natural" Turing degrees

Stephen G Simpson simpson at
Sat Aug 29 10:18:19 EDT 1998

Steffen Lempp writes:

 > the search for natural degrees: ....  I propose instead as a
 > preliminary working definition "natural" to mean "definable in the
 > degree structure using only the partial ordering".  ...

This definition of "natural" is somewhat introverted for my taste.
And also, it may not correspond very well to intuition about natural
mathematical problems.  But yes, it has the advantage of being
mathematically rigorous.  And I agree that this direction of research
is very interesting.  (In fact, I made an early contribution to it in
my paper "First order theory of the degrees of recursive
unsolvability", Annals of Mathematics, 105, 1977, pp. 121-139.)

 > Work on this, of course, has been going on for a while, in several
 > directions, by Slaman-Woodin on the bi-interpretability conjecture,

What's the bi-interpretability conjecture?  What "natural" degrees
would emerge from it?

 > the degrees being a prime model of their theory (known for the
 > Delta2 Turing degrees, open for the others)

I don't understand.  Does this give rise to some "natural" Delta2
Turing degrees?  If the r.e. degrees are a prime model of their
theory, would that give rise to some "natural" r.e. degrees?

 > The r.e. Turing degrees coincide, of course, e.g., with the Turing
 > degrees of word problems of finitely presented groups, or the
 > Turing degrees of solution sets of diophantine equations. This
 > provides another angle on the r.e. degrees being "natural".

However, we are very far away from finding an r.e. degree other than 0
and 0' which arises from a *manageably small* finite presentation, or
a *manageably small* system of Diophantine equations, or any other
*manageably small* mathematical problem.  Even if one finds Turing
degrees which are "natural" in your sense of being first order
definable in a degree structure, it's not at all clear that the
defining formulas will be *manageably small*.

This notion of *manageable smallness* (or even better, the related
notion of *understandability*) is extremely important, even if it's
not mathematically rigorous.  Compare the ongoing FOM debate over
understandability of Con(ZFC).

-- Steve

More information about the FOM mailing list