Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Prime models of theories of computable linear orderings


Author: Denis R. Hirschfeldt
Journal: Proc. Amer. Math. Soc. 129 (2001), 3079-3083
MSC (2000): Primary 03D45; Secondary 06A05, 03C57, 03C50, 03C65
DOI: https://doi.org/10.1090/S0002-9939-01-05923-8
Published electronically: February 22, 2001
MathSciNet review: 1840114
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract:

We answer a long-standing question of Rosenstein by exhibiting a complete theory of linear orderings with both a computable model and a prime model, but no computable prime model. The proof uses the relativized version of the concept of limitwise monotonic function.


References [Enhancements On Off] (What's this?)

  • 1. Chris J. Ash, Carl G. Jockusch, Jr., and Julia F. Knight, Jumps of orderings, Trans. Amer. Math. Soc. 319 (1990), 573-599. MR 90j:03081
  • 2. R. J. Coles, R. Downey, and B. Khoussainov, On initial segments of computable linear orders, Order 14 (1997/98), 107-124. MR 99m:03088
  • 3. R. Downey and J. B. Remmel, Questions in computable algebra and combinatorics, in P. Cholak, S. Lempp, M. Lerman, and R. Shore (eds.), Computability Theory and its Applications: Current Trends and Open Problems, Contemporary Mathematics, vol. 257, American Mathematical Society, Providence, RI, 2000, pp. 95-125. CMP 2000:16
  • 4. R. G. Downey, Computability theory and linear orderings, Handbook of Recursive Mathematics (Yu. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, eds.), Stud. Logic Found. Math., vol. 138-139, Elsevier Science, Amsterdam, 1998, pp. 823-976. MR 2000j:03059
  • 5. W. Hodges, Model theory, Encyclopedia Math. Appl., vol. 42, Cambridge University Press, Cambridge, 1993. MR 94e:03002
  • 6. N. G. Khisamiev, A constructibility criterion for the direct product of cyclic $p$-groups, Izv. Akad. Nauk Kaz. SSR, Ser. Fiz.-Mat. 1981 (1981), 51-55, in Russian. MR 82h:20042
  • 7. -, Theory of Abelian groups with constructive models, Siberian Math. J. 27 (1986), 572-585. MR 87m:03050
  • 8. -, Constructive Abelian groups, Handbook of Recursive Mathematics (Yu. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, eds.), Stud. Logic Found. Math., vol. 138-139, Elsevier Science, Amsterdam, 1998, pp. 1177-1231. MR 2000d:03093
  • 9. B. Khoussainov, A. Nies, and R. A. Shore, Computable models of theories with few models, Notre Dame J. Formal Logic 38 (1997), 165-178. MR 99c:03049
  • 10. B. Khoussainov and R. A. Shore, Effective model theory: the number of models and their complexity, Models and Computability (Cambridge) (S. B. Cooper and J. K. Truss, eds.), London Mathematical Society Lecture Note Series, vol. 259, Cambridge University Press, 1999, pp. 193-239. MR 2000i:03048
  • 11. Ivan Rival (ed.), Ordered sets, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 83, D. Reidel Publishing Company, Dordrecht-Boston-London, 1982, Published in cooperation with NATO Scientific Affairs Division. MR 83e:06003
  • 12. Joseph G. Rosenstein, Linear orderings, Pure Appl. Math., vol. 98, Academic Press, New York, etc., 1982. MR 84m:06001
  • 13. Robert I. Soare, Recursively enumerable sets and degrees, Perspect. Math. Logic, Springer-Verlag, Heidelberg, 1987. MR 88m:03003

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03D45, 06A05, 03C57, 03C50, 03C65

Retrieve articles in all journals with MSC (2000): 03D45, 06A05, 03C57, 03C50, 03C65


Additional Information

Denis R. Hirschfeldt
Affiliation: School of Mathematical and Computing Sciences, Victoria University of Wellington, New Zealand
Address at time of publication: Department of Mathematics, The University of Chicago, Chicago, Illinois 60637-1538
Email: Denis.Hirschfeldt@mcs.vuw.ac.nz, drh@math.uchicago.edu

DOI: https://doi.org/10.1090/S0002-9939-01-05923-8
Received by editor(s): December 29, 1999
Received by editor(s) in revised form: February 25, 2000
Published electronically: February 22, 2001
Additional Notes: The author’s research was supported by the Marsden Fund of New Zealand. The author thanks the anonymous referee for valuable historical comments.
Communicated by: Carl G. Jockusch, Jr.
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society