Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-28T05:29:13.148Z Has data issue: false hasContentIssue false
  • English
  • Français

Prime models of finite computable dimension

Published online by Cambridge University Press:  12 March 2014

Pavel Semukhin
Pavel Semukhin*
Affiliation:
Department of Computer Science, The University of Auckland, Private Bag 92019, Auckland, New Zealand, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the following open question in computable model theory: does there exist a structure of computable dimension two which is the prime model of its first-order theory? We construct an example of such a structure by coding a certain family of c.e. sets with exactly two one-to-one computable enumerations into a directed graph. We also show that there are examples of such structures in the classes of undirected graphs, partial orders, lattices, and integral domains.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 74 , Issue 1 , March 2009 , pp. 336 - 348
Copyright
Copyright © Association for Symbolic Logic 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Choiak, P., Goncharov, S., Khoussainov, B., and Shore, R. A., Computably categorical structures and expansions by constants, this Journal, vol. 64 (1999), no. 1, pp. 13–37.Google Scholar
[2]Goncharov, S. S., Computable univalent numerations, Algebra i Logika, vol. 19 (1980), no. 5, pp. 507-551, 617.Google Scholar
[3]Goncharov, S. S., The problem of the number of nonautoequivalent constructivizations, Algebra i Logika, vol. 19 (1980), no. 6, pp. 621–639, 745.Google Scholar
[4]Harizanov, V. S., The possible Turing degree of the nonzero member in a two element degree spectrum, Annals of Pure and Applied Logic, vol. 60 (1993), no. 1, pp. 1–30.CrossRefGoogle Scholar
[5]Hirschfeldt, D. R., Degree spectra of relations on computable structures, Ph.D. thesis, Cornell University, 1999.Google Scholar
[6]Hirschfeldt, D. R., Khoussainov, B., and Shore, R. A., A computably categorical structure whose expansion by a constant has infinite computable dimension, this Journal, vol. 68 (2003), no. 4, pp. 1199–1241.Google Scholar
[7]Hirschfeldt, D. R., Khoussainov, B., Shore, R. A., and Slinko, A. M., Degree spectra and computable dimensions in algebraic structures, Annals of Pure and Applied Logic, vol. 115 (2002), no. 1–3, pp. 71–113.CrossRefGoogle Scholar
[8]Khoussainov, B. and Shore, R. A., Computable isomorphisms, degree spectra of relations, and Scott families. Computability theory, Annals of Pure and Applied Logic, vol. 93 (1998), pp. 153–193, erratum Annals of Pure and Applied Logic, vol. 98 (1999), no. 1–3, pp. 297–298.CrossRefGoogle Scholar