Spectra of Structures and Relations

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

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″

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,174

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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. pp. 29-45.
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
2010-08-24

Downloads
24 (#476,600)

6 months
1 (#413,813)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Valentina Harizanov
George Washington University

Citations of this work

Effective Algebraicity.Rebecca M. Steiner - 2013 - Archive for Mathematical Logic 52 (1-2):91-112.
Low N Boolean Subalgebras.Rebecca M. Steiner - 2012 - In S. Barry Cooper (ed.), How the World Computes. pp. 696--702.

Add more citations

References found in this work

No references found.

Add more references