The degree spectra of homogeneous models

Journal of Symbolic Logic 73 (3):1009-1028 (2008)

Abstract
Much previous study has been done on the degree spectra of prime models of a complete atomic decidable theory. Here we study the analogous questions for homogeneous models. We say a countable model A has a d-basis if the types realized in A are all computable and the Turing degree d can list $\Delta _{0}^{0}$ -indices for all types realized in A. We say A has a d-decidable copy if there exists a model B ≅ A such that the elementary diagram of B is d-computable. Goncharov, Millar, and Peretyat'kin independently showed there exists a homogeneous A with a 0-basis but no decidable copy. We prove that any homogeneous A with a 0'-basis has a low decidable copy. This implies Csima's analogous result for prime models. In the case where all types of the theory T are computable and A is a homogeneous model with a 0-basis, we show A has copies decidable in every nonzero degree. A degree d is 0-homogeneous bounding if any automorphically nontrivial homogeneous A with a 0-basis has a d-decidable copy. We show that the nonlow₂ $\Delta _{2}^{0}$ degrees are 0-homogeneous bounding
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/jsl/1230396762
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: 40,625
Through your library

References found in this work BETA

Degrees Coded in Jumps of Orderings.Julia F. Knight - 1986 - Journal of Symbolic Logic 51 (4):1034-1042.
Foundations of Recursive Model Theory.Terrence S. Millar - 1978 - Annals of Pure and Applied Logic 13 (1):45.
Computability of Homogeneous Models.Karen Lange & Robert I. Soare - 2007 - Notre Dame Journal of Formal Logic 48 (1):143-170.
Recursively Presentable Prime Models.Leo Harrington - 1974 - Journal of Symbolic Logic 39 (2):305-309.
Degree Spectra of Prime Models.Barbara F. Csima - 2004 - Journal of Symbolic Logic 69 (2):430 - 442.

View all 7 references / Add more references

Citations of this work BETA

A Characterization of the 0 -Basis Homogeneous Bounding Degrees.Karen Lange - 2010 - Journal of Symbolic Logic 75 (3):971-995.

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.
Jack and Jill Have Shifted Spectra.Ned Block - 1999 - Behavioral and Brain Sciences 22 (6):946-947.
Computability of Homogeneous Models.Karen Lange & Robert I. Soare - 2007 - Notre Dame Journal of Formal Logic 48 (1):143-170.
Degree Spectra of Prime Models.Barbara F. Csima - 2004 - Journal of Symbolic Logic 69 (2):430 - 442.
Degree Spectra of Relations on Computable Structures.Denis R. Hirschfeldt - 2000 - Bulletin of Symbolic Logic 6 (2):197-212.
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.
A Characterization of the 0 -Basis Homogeneous Bounding Degrees.Karen Lange - 2010 - Journal of Symbolic Logic 75 (3):971-995.

Analytics

Added to PP index
2010-09-12

Total views
14 ( #555,868 of 2,242,355 )

Recent downloads (6 months)
1 ( #1,043,391 of 2,242,355 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature