|
Prime models of theories of computable linear orderings
Author(s):
Denis
R.
Hirschfeldt
Journal:
Proc. Amer. Math. Soc.
129
(2001),
3079-3083.
MSC (2000):
Primary 03D45;
Secondary 06A05, 03C57, 03C50, 03C65
Posted:
February 22, 2001
MathSciNet review:
1840114
Retrieve article in:
PDF
This article is available free of charge
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:
-
- 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
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:
10.1090/S0002-9939-01-05923-8
PII:
S 0002-9939(01)05923-8
Received by editor(s):
December 29, 1999
Received by editor(s) in revised form:
February 25, 2000
Posted:
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 of article:
Copyright
2001,
American Mathematical Society
|
