Computable trees, prime models, and relative decidability

Author:
Denis R. Hirschfeldt

Journal:
Proc. Amer. Math. Soc. **134** (2006), 1495-1498

MSC (2000):
Primary 03C57, 03D45

Published electronically:
October 4, 2005

MathSciNet review:
2199197

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We show that for every computable tree with no dead ends and all paths computable, and every , there is a -computable listing of the isolated paths of . It follows that for every complete decidable theory such that all the types of are computable and every , there is a -decidable prime model of . This result extends a theorem of Csima and yields a stronger version of the theorem, due independently to Slaman and Wehner, that there is a structure with presentations of every nonzero degree but no computable presentation.

**1.**Barbara F. Csima,*Degree spectra of prime models*, J. Symbolic Logic**69**(2004), no. 2, 430–442. MR**2058182**, 10.2178/jsl/1082418536**2.**B. F. Csima, D. R. Hirschfeldt, V. S. Harizanov, and R. I. Soare, Bounding homogeneous models, to appear.**3.**Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight, and Robert I. Soare,*Bounding prime models*, J. Symbolic Logic**69**(2004), no. 4, 1117–1142. MR**2135658**, 10.2178/jsl/1102022214**4.**S. S. Gončarov and A. T. Nurtazin,*Constructive models of complete decidable theories*, Algebra i Logika**12**(1973), 125–142, 243 (Russian). MR**0398816****5.**Valentina S. Harizanov,*Pure computable model theory*, Handbook of recursive mathematics, Vol. 1, Stud. Logic Found. Math., vol. 138, North-Holland, Amsterdam, 1998, pp. 3–114. MR**1673621**, 10.1016/S0049-237X(98)80002-5**6.**Leo Harrington,*Recursively presentable prime models*, J. Symbolic Logic**39**(1974), 305–309. MR**0351804****7.**Terrence S. Millar,*Foundations of recursive model theory*, Ann. Math. Logic**13**(1978), no. 1, 45–72. MR**482430**, 10.1016/0003-4843(78)90030-X**8.**Theodore A. Slaman,*Relative to any nonrecursive set*, Proc. Amer. Math. Soc.**126**(1998), no. 7, 2117–2122. MR**1443408**, 10.1090/S0002-9939-98-04307-X**9.**Stephan Wehner,*Enumerations, countable structures and Turing degrees*, Proc. Amer. Math. Soc.**126**(1998), no. 7, 2131–2139. MR**1443415**, 10.1090/S0002-9939-98-04314-7

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC (2000):
03C57,
03D45

Retrieve articles in all journals with MSC (2000): 03C57, 03D45

Additional Information

**Denis R. Hirschfeldt**

Affiliation:
Department of Mathematics, The University of Chicago, 5734 S. University Ave., Chicago, Illinois 60637

Email:
drh@math.uchicago.edu

DOI:
https://doi.org/10.1090/S0002-9939-05-08097-4

Received by editor(s):
November 17, 2004

Published electronically:
October 4, 2005

Additional Notes:
This research was partially supported by NSF Grant DMS-02-00465.

The author thanks Robert Soare for many enlightening discussions related to this paper.

Communicated by:
Carl G. Jockusch, Jr.

Article copyright:
© Copyright 2005
American Mathematical Society