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 |
![]() ![]() ![]() ![]() |
Download options
References found in this work BETA
A Borel Reducibility Theory for Classes of Countable Structures.Harvey Friedman & Lee Stanley - 1989 - Journal of Symbolic Logic 54 (3):894-914.
Degrees Coded in Jumps of Orderings.Julia F. Knight - 1986 - Journal of Symbolic Logic 51 (4):1034-1042.
Computable Isomorphisms, Degree Spectra of Relations, and Scott Families.Bakhadyr Khoussainov & Richard A. Shore - 1998 - Annals of Pure and Applied Logic 93 (1-3):153-193.
Stability of Nilpotent Groups of Class 2 and Prime Exponent.Alan H. Mekler - 1981 - Journal of Symbolic Logic 46 (4):781-788.
Computably Categorical Structures and Expansions by Constants.Peter Cholak, Sergey Goncharov, Bakhadyr Khoussainov & Richard A. Shore - 1999 - Journal of Symbolic Logic 64 (1):13-37.
View all 11 references / Add more references
Citations of this work BETA
Computable Functors and Effective Interpretability.Matthew Harrison-Trainor, Alexander Melnikov, Russell Miller & Antonio Montalbán - 2017 - Journal of Symbolic Logic 82 (1):77-97.
Degrees of Categoricity of Computable Structures.Ekaterina B. Fokina, Iskander Kalimullin & Russell Miller - 2010 - Archive for Mathematical Logic 49 (1):51-67.
A Computable Functor From Graphs to Fields.Russell Miller, Bjorn Poonen, Hans Schoutens & Alexandra Shlapentokh - 2018 - Journal of Symbolic Logic 83 (1):326-348.
Degrees of Categoricity and Spectral Dimension.Nikolay A. Bazhenov, Iskander Sh Kalimullin & Mars M. Yamaleev - 2018 - Journal of Symbolic Logic 83 (1):103-116.
D-Computable Categoricity for Algebraic Fields.Russell Miller - 2009 - Journal of Symbolic Logic 74 (4):1325 - 1351.
View all 39 citations / Add more citations
Similar books and articles
Realizing Levels of the Hyperarithmetic Hierarchy as Degree Spectra of Relations on Computable Structures.Walker M. White & Denis R. Hirschfeldt - 2002 - Notre Dame Journal of Formal Logic 43 (1):51-64.
Computable Isomorphisms of Boolean Algebras with Operators.Bakhadyr Khoussainov & Tomasz Kowalski - 2012 - Studia Logica 100 (3):481-496.
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 Relations on Structures of Finite Computable Dimension.Denis R. Hirschfeldt - 2002 - Annals of Pure and Applied Logic 115 (1-3):233-277.
Computable Isomorphisms, Degree Spectra of Relations, and Scott Families.Bakhadyr Khoussainov & Richard A. Shore - 1998 - Annals of Pure and Applied Logic 93 (1-3):153-193.
Degree Spectra of Intrinsically C.E. Relations.Denis R. Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.
$\Pi _{1}^{0}$ Classes and Strong Degree Spectra of Relations.John Chisholm, Jennifer Chubb, Valentina S. Harizanov, Denis R. Hirschfeldt, Carl G. Jockusch, Timothy McNicholl & Sarah Pingrey - 2007 - Journal of Symbolic Logic 72 (3):1003 - 1018.
Erratum to “Computable Isomorphisms, Degree Spectra of Relations, and Scott Families” [Ann. Pure Appl. Logic 93 (1998) 153–193]. [REVIEW]Bakhadyr Khoussainov & Richard A. Shore - 1999 - Annals of Pure and Applied Logic 98 (1-3):297-298.
D-Computable Categoricity for Algebraic Fields.Russell Miller - 2009 - Journal of Symbolic Logic 74 (4):1325 - 1351.
Degrees of Categoricity of Computable Structures.Ekaterina B. Fokina, Iskander Kalimullin & Russell Miller - 2010 - Archive for Mathematical Logic 49 (1):51-67.
Analytics
Added to PP index
2014-01-16
Total views
15 ( #643,543 of 2,403,017 )
Recent downloads (6 months)
1 ( #552,435 of 2,403,017 )
2014-01-16
Total views
15 ( #643,543 of 2,403,017 )
Recent downloads (6 months)
1 ( #552,435 of 2,403,017 )
How can I increase my downloads?
Downloads