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

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.

**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 -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**

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