Spectra of Structures and Relations

Journal of Symbolic Logic 72 (1):324 - 348 (2007)

Authors
Valentina Harizanov
George Washington University
Abstract
We consider embeddings of structures which preserve spectra: if g: M → S with S computable, then M should have the same Turing degree spectrum (as a structure) that g(M) has (as a relation on S). We show that the computable dense linear order L is universal for all countable linear orders under this notion of embedding, and we establish a similar result for the computable random graph G. 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 G. Finally, we consider the extent to which all spectra of unary relations on the structure L 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′ ≥T 0″
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/jsl/1174668398
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: 42,993
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Effective Algebraicity.Rebecca M. Steiner - 2013 - Archive for Mathematical Logic 52 (1-2):91-112.

Add more citations

Similar books and articles

Degree Spectra of Relations on Computable Structures.Denis R. Hirschfeldt - 2000 - Bulletin of Symbolic Logic 6 (2):197-212.
Jack and Jill Have Shifted Spectra.Ned Block - 1999 - Behavioral and Brain Sciences 22 (6):946-947.
Degree Spectra of Intrinsically C.E. Relations.Denis R. Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.
Spectra of Formulae with Henkin Quantifiers.Joanna Golinska-Pilarek & Konrad Zdanowski - 2003 - In A. Rojszczak, J. Cachro & G. Kurczewski (eds.), Philosophical Dimensions of Logic and Science. Kluwer Academic Publishers.
Maharam Spectra of Loeb Spaces.Renling Jin & H. Jerome Keisler - 2000 - Journal of Symbolic Logic 65 (2):550-566.
Purity, Spectra and Localisation.Mike Prest - 2009 - Cambridge University Press.
Structures and Structural Realism.Décio Krause - 2003 - Logic Journal of the IGPL 13 (1):113-126.

Analytics

Added to PP index
2010-08-24

Total views
18 ( #466,341 of 2,259,729 )

Recent downloads (6 months)
3 ( #496,733 of 2,259,729 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature