Computable models of theories with few models. (English) Zbl 0891.03013

Summary: We investigate computable models of \(\aleph_1\)-categorical theories and Ehrenfeucht theories. For instance, we give an example of an \(\aleph_1\)-categorical but not \(\aleph_0\)-categorical theory \(T\) such that all the countable models of \(T\) except its prime model have computable presentations. We also show that there exists an \(\aleph_1\)-categorical but not \(\aleph_0\)-categorical theory \(T\) such that all the countable models of \(T\) except the saturated model, have computable presentations.


03C57 Computable structure theory, computable model theory
03C35 Categoricity and completeness of theories
03C15 Model theory of denumerable and separable structures
Full Text: DOI


[1] Baldwin, J., and A. Lachlan, “On strongly minimal sets,” The Journal of Symbolic Logic , vol. 36 (1971), pp. 79–96. JSTOR: · Zbl 0217.30402 · doi:10.2307/2271517
[2] Ershov, Yu., Constructive Models and Problems of Decidability , Nauka, Moskow, 1980.
[3] Goncharov, S., “Constructive models of \(\omega_1\)-categorical theories,” Matematicheskie Zametki , vol. 23 (1978), pp. 885–9. · Zbl 0403.03025 · doi:10.1007/BF01431432
[4] Goncharov, S., “Strong constructivability of homogeneous models,” Algebra and Logic , vol. 17 (1978), pp. 363–8. · Zbl 0441.03015 · doi:10.1007/BF01674776
[5] Logic Notebook , edited by Yu. Ershov and S. Goncharov, Novosibirsk University, Novosibirsk, 1986.
[6] Khissamiev, N.,“On strongly constructive models of decidable theories,” Izvestiya AN Kaz. SSR , vol. 1 (1974), pp. 83–4.
[7] Kudeiberganov, K., “On constructive models of undecidable theories,” Siberian Mathematical Journal , vol. 21 (1980), pp. 155–8.
[8] Harrington, L., “Recursively presentable prime models,” The Journal of Symbolic Logic , vol. 39 (1973), pp. 305–9. JSTOR: · Zbl 0332.02055 · doi:10.2307/2272643
[9] Millar, T., “The theory of recursively presented models,” Ph.D. Dissertation, Cornell University, Ithaca, 1976. · Zbl 0354.35014
[10] Morley, M., “Decidable models,” Israel Journal of Mathematics , vol. 25 (1976), pp. 233–40. · Zbl 0361.02067 · doi:10.1007/BF02757002
[11] Peretýatkin, M., “On complete theories with finite number of countable models,” Algebra and Logic , vol. 12 (1973), pp. 550–70. · Zbl 0298.02047 · doi:10.1007/BF02218589
[12] Rosenstein, J., Linear Orderings , Academic Press, New York, 1982. · Zbl 0488.04002
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.