SPECTRA OF STRUCTURES AND RELATIONS.
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 thi...
| Publicado en: | Journal of Symbolic Logic Vol. 72; no. 1; pp. 324 - 349 |
|---|---|
| Autores principales: | , |
| Formato: | Artículo |
| Publicado: |
Cambridge University Press
Mar2007
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=24665171&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 24665171 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00224812 3TY jtl: Journal of Symbolic Logic issn: 00224812 maglogo: N pubinfo: dt: Mar2007 vid: 72 iid: 1 pid: 15979 pub: Cambridge University Press artinfo: ui: 24665171 10.2178/jsl/1174668398 ppf: 324 ppct: 25 formats: tig: atl: SPECTRA OF STRUCTURES AND RELATIONS. aug: au: Harizanov, Valentina S. Miller, Russell G. affil: Department of Mathematics, The George Washington University, Washington, D.C. 20052, USA Department of Mathematics, Queens College-C.U.N.Y. 65-30 Kissena Blvd., Flushing, New York 11367, USA su: Turing (Computer program language) Embeddings (Mathematics) Unary algebras Mathematical logic Isomorphism (Mathematics) Automorphisms Graph theory Boolean algebra sug: subj: Turing (Computer program language) Embeddings (Mathematics) Unary algebras Mathematical logic Isomorphism (Mathematics) Automorphisms Graph theory Boolean algebra ab: 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′ ≥ 0″. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2007 holdings: @attributes: islocal: N |
|---|