Natural definability in degree structures


			Richard A. Shore
		   Department of Mathematics
		       Cornell University
			Ithaca NY 14853


A major focus of research in computability theory in recent years has
involved definability issues in degree structures. The basic question is,
which interesting, but apparently external, relations on degrees can
actually be defined in the structures themselves? Most of the work has
focused on the Turing degrees and on the structures consisting of the
recursively enumerable degrees and all the degrees, respectively. We will
do the same in this talk. 

At the level of establishing abstract definability of relations there has
been great success. In both structures, any relation invariant under
double jump whose definability is not ruled out simply by the structures
being themselves subsystems of first or second order arithmetic,
respectively, is actually definable in the structures. However, these
definitions proceed by coding models of arithmetic and translating the
degrees back into arithmetic. Whatever further success might be won along
these lines they have not provided and will not provide "natural"
definitions of degrees or predicates on the degrees. This investigation is
the provenance of another area of long term interest in the study of
degree structures: the relationships between order-theoretic properties of
degrees and external properties of other sorts. Of particular interest in
the r. e. degrees have been set-theoretic properties described in terms of
the lattice of r. e. sets and dynamic properties of the enumerations of
the r. e. sets. In both the r. e. degrees and the degrees as a whole we
have relations with rates of growth of functions recursive in various
degrees and relations with definability considerations in arithmetic as
expressed by the jump operator. In the degrees as a whole, a central role
has also been played by the jump operator itself, its analogs and their
iterations into the transfinite. We will also emphasize two other notions
that play fundamental roles in computability theory but often seem
difficult to capture in terms of degree theoretic properties alone: 
uniformity and recursion. We will discuss a number of examples, consider
some possible guidelines for the naturalness of definitions in these
degree structures, and suggest questions for further research.