Article contents
Spectra of structures and relations
Published online by Cambridge University Press: 12 March 2014
Abstract
We consider embeddings of structures which preserve spectra: if g : ℳ → with computable, then ℳ should have the same Turing degree spectrum (as a structure) that g(ℳ) has (as a relation on ). We show that the computable dense linear order ℒ is universal for all countable linear orders under this notion of embedding, and we establish a similar result for the computable random graph Such structures are said to be spectrally universal. We use our results to answer a question of Goncharov, and also to characterize the possible spectra of structures as precisely the spectra of unary relations on . Finally, we consider the extent to which all spectra of unary relations on the structure ℒ may be realized by such embeddings, offering partial results and building the first known example of a structure whose spectrum contains precisely those degrees c with c′ ≥ τ 0″.
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 2007
References
REFERENCES
- 11
- Cited by