Geodesic
Complexity of categorical theories with computable models
Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 5 (2005) no. 2, pp. 77-85 
E. Fokina. Complexity of categorical theories with computable models. Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 5 (2005) no. 2, pp. 77-85. http://geodesic.mathdoc.fr/item/VNGU_2005_5_2_a4/
@article{VNGU_2005_5_2_a4,
     author = {E. Fokina},
     title = {Complexity of categorical theories with computable models},
     journal = {Sibirskij \v{z}urnal \v{c}istoj i prikladnoj matematiki},
     pages = {77--85},
     year = {2005},
     volume = {5},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VNGU_2005_5_2_a4/}
}
TY  - JOUR
AU  - E. Fokina
TI  - Complexity of categorical theories with computable models
JO  - Sibirskij žurnal čistoj i prikladnoj matematiki
PY  - 2005
SP  - 77
EP  - 85
VL  - 5
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VNGU_2005_5_2_a4/
LA  - ru
ID  - VNGU_2005_5_2_a4
ER  - 
%0 Journal Article
%A E. Fokina
%T Complexity of categorical theories with computable models
%J Sibirskij žurnal čistoj i prikladnoj matematiki
%D 2005
%P 77-85
%V 5
%N 2
%U http://geodesic.mathdoc.fr/item/VNGU_2005_5_2_a4/
%G ru
%F VNGU_2005_5_2_a4

Voir la notice de l'article provenant de la source Math-Net.Ru

In the paper 2 theorems are proved: There is an uncountably categorical but not countably categorical theory of an arbitrary given arithmetical complexity with a computable model. All countable models of this theory are computable. There is a countably categorical theory of an arbitrary given arithmetical complexity with a computable model.

[1] S. S. Goncharov, “Konstruktivnye modeli $\omega_1$-kategorichnykh teorii”, Matem. Zametki, 23 (1978), 885–888 | MR | Zbl

[2] S. S. Goncharov, B. M. Khusainov, “Slozhnost kategorichnykh teorii s vychislimymi modelyami”, DAN, 385:3 (2002)

[3] S. S. Goncharov, B. M. Khusainov, “O slozhnosti teorii vychislimykh $\aleph_1$-kategorichnykh modelei”, Vestnik NGU, Seriya: matem., mekhanika, inform., 1:2 (2001), 63–76 | MR

[4] G. Keisler, Ch. Ch. Chen, Teoriya modelei, Mir, M., 1977 | MR

[5] K. Z. Kudaibergenov, “O konstruktivnykh modelyakh nerazreshimykh teorii”, Sib. matem. zhur., 21:5 (1980), 155–158 | MR | Zbl

[6] N. G. Khisamiev, “Silno konstruktivnye modeli razreshimoi teorii”, Izv. AN Kazakh. SSR, Ser. fiz.-mat., 35:1 (1974), 83–84 | MR

[7] J. Baldwin, A. Lachlan, “On Strongly Minimal Sets”, J. of Symbolic Logic, 36 (1971), 79–96 | DOI | MR | Zbl

[8] L. Harrington, “Recursively Presentable Prime Models”, J. of Symbolic Logic, 39 (1974), 305–309 | DOI | MR | Zbl

[9] B. Khoussainov, A. Nies, R. Shore, “On Recursive Models of Theories”, Notre Dame Journal of Formal Logic, 38:2 (1997), 165–178 | DOI | MR | Zbl

[10] J. Knight, “Nonarithmetical $\aleph_0$-categorical Theories with Recursive Models”, J. Symbolic Logic, 59:1 (1994), 106–112 | DOI | MR | Zbl

[11] M. Lerman, J. Scmerl, “Theories With Recursive Models”, J. Symbolic Logic, 44:1 (1979), 59–76 | DOI | MR | Zbl

[12] D. Marker, “Non-$\Sigma_n$-axiomatizable almost strongly minimal theories”, J. Symbolic Logic, 54 (1989), 921–927 | DOI | MR | Zbl

[13] A. Nies, “A new spectrum of recursive models”, Notre Dame Journal of Formal Logic, 40 (1999), 307–314 | DOI | MR | Zbl

[14] M. C. Veenning, Type structures of $\aleph_0$-categorical theories, A thesis presented to the faculty of the Graduate School of Cornell University for the Degree of the Doctor of Philosophy, Ithaca, 1976