Prime models of theories of computable linear orderings. (English) Zbl 0974.03040
In his book: Linear orderings [Academic Press, New York (1982; Zbl 0488.04002)], J. G. Rosenstein asked if there was a complete theory of linear orderings with a computable model and a prime model, but no computable prime model. The author uses Khisamiev’s technique of “limitwise monotonic” functions, together with coding a construction from the literature (specifically, R. J. Coles, R. Downey and B. Khoussainov [Order 14, 107-124 (1998; Zbl 0915.03040)]) to give an affirmative answer to this longstanding question.
Reviewer: R.Downey (Wellington)
MSC:
| 03D45 | Theory of numerations, effectively presented structures |
| 06A05 | Total orders |
| 03C57 | Computable structure theory, computable model theory |
| 03C50 | Models with special properties (saturated, rigid, etc.) |
| 03C65 | Models of other mathematical theories |
References:
| [1] | C. J. Ash, C. G. Jockusch Jr., and J. F. Knight, Jumps of orderings, Trans. Amer. Math. Soc. 319 (1990), no. 2, 573 – 599. · Zbl 0705.03022 |
| [2] | Richard J. Coles, Rod Downey, and Bakhadyr Khoussainov, On initial segments of computable linear orders, Order 14 (1997/98), no. 2, 107 – 124. · Zbl 0915.03040 · doi:10.1023/A:1006031314563 |
| [3] | R. Downey and J. B. Remmel, Questions in computable algebra and combinatorics, in P. Cholak, S. Lempp, M. Lerman, and R. Shore , 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 · Zbl 0980.03045 |
| [4] | 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. · Zbl 0941.03045 · doi:10.1016/S0049-237X(98)80047-5 |
| [5] | Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. · Zbl 0789.03031 |
| [6] | N. G. Hisamiev, Criterion for constructivizability of a direct sum of cyclic \?-groups, Izv. Akad. Nauk Kazakh. SSR Ser. Fiz.-Mat. 1 (1981), 51 – 55, 86 (Russian, with Kazakh summary). |
| [7] | N. G. Khisamiev, Theory of abelian groups with constructive models, Sibirsk. Mat. Zh. 27 (1986), no. 4, 128 – 143, 215 (Russian). · Zbl 0625.03015 |
| [8] | 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. · Zbl 0940.03044 · doi:10.1016/S0049-237X(98)80050-5 |
| [9] | 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. · Zbl 0891.03013 · doi:10.1305/ndjfl/1039724885 |
| [10] | 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. · Zbl 0940.03045 · doi:10.1017/CBO9780511565670.009 |
| [11] | Ivan Rival , Ordered sets, NATO Advanced Study Institute Series C: Mathematical and Physical Sciences, vol. 83, D. Reidel Publishing Co., Dordrecht-Boston, Mass., 1982. · Zbl 0484.00004 |
| [12] | Joseph G. Rosenstein, Linear orderings, Pure and Applied Mathematics, vol. 98, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. · Zbl 0488.04002 |
| [13] | 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. · Zbl 0667.03030 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
