Degree Spectra and Computable Dimensions in Algebraic Structures
Status: published in the Annals
of Pure and Applied Logic 115 (2002) 71 - 113.
Availability: journal
version and preprint
Abstract. Whenever a structure with a particularly interesting
computability-theoretic property is found, it is natural to ask
whether similar examples can be found within well-known classes of
algebraic structures, such as groups, rings, lattices, and so
forth. One way to give positive answers to this question is to adapt
the original proof to the new setting. However, this can be an
unnecessary duplication of effort, and lacks generality. Another
method is to code the original structure into a structure in the given
class in a way that is effective enough to preserve the property in
which we are interested. In this paper, we show how to transfer a
number of computability-theoretic properties from directed graphs to
structures in the following classes: symmetric, irreflexive graphs;
partial orderings; lattices; rings (with zero-divisors); integral
domains of arbitrary characteristic; commutative semigroups; and
2-step nilpotent groups. This allows us to show that several theorems
about degree spectra of relations on computable structures,
nonpreservation of computable categoricity, and degree spectra of
structures remain true when we restrict our attention to structures in
any of the classes on this list. The codings we present are general
enough to be viewed as establishing that the theories mentioned above
are computably complete in the sense that, for a wide range of
computability-theoretic nonstructure type properties, if there are any
examples of structures with such properties then there are such
examples which are models of each of these theories.
drh@math.uchicago.edu