Prime models of theories of computable linear orderings
HTML articles powered by AMS MathViewer
- by Denis R. Hirschfeldt PDF
- Proc. Amer. Math. Soc. 129 (2001), 3079-3083 Request permission
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
- C. J. Ash, C. G. Jockusch Jr., and J. F. Knight, Jumps of orderings, Trans. Amer. Math. Soc. 319 (1990), no. 2, 573–599. MR 955487, DOI 10.1090/S0002-9947-1990-0955487-0
- Richard J. Coles, Rod Downey, and Bakhadyr Khoussainov, On initial segments of computable linear orders, Order 14 (1997/98), no. 2, 107–124. MR 1631684, DOI 10.1023/A:1006031314563
- 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.
- R. G. Downey, Computability theory and linear orderings, Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, North-Holland, Amsterdam, 1998, pp. 823–976. MR 1673590, DOI 10.1016/S0049-237X(98)80047-5
- Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741, DOI 10.1017/CBO9780511551574
- N. G. Hisamiev, Criterion for constructivizability of a direct sum of cyclic $p$-groups, Izv. Akad. Nauk Kazakh. SSR Ser. Fiz.-Mat. 1 (1981), 51–55, 86 (Russian, with Kazakh summary). MR 614069
- N. G. Khisamiev, Theory of abelian groups with constructive models, Sibirsk. Mat. Zh. 27 (1986), no. 4, 128–143, 215 (Russian). MR 867866
- N. G. Khisamiev, Constructive abelian groups, Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, North-Holland, Amsterdam, 1998, pp. 1177–1231. MR 1673602, DOI 10.1016/S0049-237X(98)80050-5
- Bakhadyr Khoussainov, Andre Nies, and Richard A. Shore, Computable models of theories with few models, Notre Dame J. Formal Logic 38 (1997), no. 2, 165–178. MR 1489408, DOI 10.1305/ndjfl/1039724885
- Bakhadyr Khoussainov and Richard A. Shore, Effective model theory: the number of models and their complexity, Models and computability (Leeds, 1997) London Math. Soc. Lecture Note Ser., vol. 259, Cambridge Univ. Press, Cambridge, 1999, pp. 193–239. MR 1721168, DOI 10.1017/CBO9780511565670.009
- Ivan Rival (ed.), Ordered sets, NATO Advanced Study Institute Series C: Mathematical and Physical Sciences, vol. 83, D. Reidel Publishing Co., Dordrecht-Boston, Mass., 1982. MR 661289
- Joseph G. Rosenstein, Linear orderings, Pure and Applied Mathematics, vol. 98, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. MR 662564
- Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
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
- MR Author ID: 667877
- Email: Denis.Hirschfeldt@mcs.vuw.ac.nz, drh@math.uchicago.edu
- 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.
- © Copyright 2001 American Mathematical Society
- 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
- MathSciNet review: 1840114