Premium
Turing degrees of isomorphism types of algebraic objects
Author(s) -
Calvert Wesley,
Harizanov Valentina,
Shlapentokh Alexandra
Publication year - 2007
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/jdl012
Subject(s) - mathematics , countable set , turing , isomorphism (crystallography) , abelian group , discrete mathematics , combinatorics , pure mathematics , computer science , chemistry , crystal structure , crystallography , programming language
The Turing degree spectrum of a countable structure is the set of all Turing degrees of isomorphic copies of . The Turing degree of the isomorphism type of , is the least Turing degree in its degree spectrum. We show that there are structures with isomorphism types of arbitrary Turing degrees in each of the following classes: countable fields, rings, and torsion‐free Abelian groups of any finite rank. We also show that there are structures in each of these classes the isomorphism types of which do not have Turing degrees. The case of torsion‐free Abelian groups of finite rank settles a question left open by Knight, Downey and Jockusch [Downey, Complexity, logic, and recursion theory , Lecture Notes in Pure and Applied Mathematics 187 (ed. A. Sorbi; Marcel Dekker, New York, 1997) 157–205].