Degree spectra and computable dimensions in algebraic structures

Annals of Pure and Applied Logic 115 (1-3):71-113 (2002)

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 ; 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 that are models of each of these theories
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/s0168-0072(01)00087-2
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 40,649
Through your library

References found in this work BETA

Degrees Coded in Jumps of Orderings.Julia F. Knight - 1986 - Journal of Symbolic Logic 51 (4):1034-1042.

View all 10 references / Add more references

Citations of this work BETA

View all 34 citations / Add more citations

Similar books and articles

Effective Algebraicity.Rebecca M. Steiner - 2013 - Archive for Mathematical Logic 52 (1-2):91-112.
Spectra of Structures and Relations.Valentina S. Harizanov & Russel G. Miller - 2007 - Journal of Symbolic Logic 72 (1):324 - 348.
Degree Spectra of Relations on Computable Structures.Denis R. Hirschfeldt - 2000 - Bulletin of Symbolic Logic 6 (2):197-212.
Degree Spectra of Intrinsically C.E. Relations.Denis R. Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.
D-Computable Categoricity for Algebraic Fields.Russell Miller - 2009 - Journal of Symbolic Logic 74 (4):1325 - 1351.

Analytics

Added to PP index
2014-01-16

Total views
12 ( #621,193 of 2,242,427 )

Recent downloads (6 months)
2 ( #815,164 of 2,242,427 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature