Annals of Pure and Applied Logic 93 (1-3):153-193 (1998)

The spectrum of a relation on a computable structure is the set of Turing degrees of the image of R under all isomorphisms between and any other computable structure . The relation is intrinsically computably enumerable if its image under all such isomorphisms is c.e. We prove that any computable partially ordered set is isomorphic to the spectrum of an intrinsically c.e. relation on a computable structure. Moreover, the isomorphism can be constructed in such a way that the image of the minimum element of the partially ordered set is computable. This solves the spectrum problem. The theorem and modifications of its proof produce computably categorical structures whose expansions by finite number of constants are not computably categorical and, indeed, ones whose expansions can have any finite number of computable isomorphism types. They also provide examples of computably categorical structures that remain computably categorical under expansions by constants but have no Scott family
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/s0168-0072(97)00059-6
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

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

References found in this work BETA

Generic Copies of Countable Structures.Chris Ash, Julia Knight, Mark Manasse & Theodore Slaman - 1989 - Annals of Pure and Applied Logic 42 (3):195-205.
Degrees Coded in Jumps of Orderings.Julia F. Knight - 1986 - Journal of Symbolic Logic 51 (4):1034-1042.
Pairs of Recursive Structures.C. J. Ash & J. F. Knight - 1990 - Annals of Pure and Applied Logic 46 (3):211-234.
Recursive Isomorphism Types of Recursive Boolean Algebras.J. B. Remmel - 1981 - Journal of Symbolic Logic 46 (3):572-594.

View all 14 references / Add more references

Citations of this work BETA

View all 15 citations / Add more citations

Similar books and articles

Degree Spectra of Intrinsically C.E. Relations.Denis R. Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.
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.
The Degree Spectra of Homogeneous Models.Karen Lange - 2008 - Journal of Symbolic Logic 73 (3):1009-1028.


Added to PP index

Total views
36 ( #320,137 of 2,533,586 )

Recent downloads (6 months)
1 ( #390,861 of 2,533,586 )

How can I increase my downloads?


My notes