Geodesic
A new spectrum of computable models
The Bulletin of Irkutsk State University. Series Mathematics, Tome 3 (2010) no. 4, pp. 7-20 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In the paper we prove that there exist models $\mathfrak A$ and $\mathfrak B$ of an Ehrenfeucht theory such that $\mathfrak A$ is elementary embeddable into $\mathfrak B$, $\mathfrak B$ is elementary embeddable into $\mathfrak A$, model $\mathfrak A$ has a computable presentation, model $\mathfrak B$ has no computable presentation. This theorem together with the work [6] is the key result for the theorem describing co
Keywords: Ehrenfeucht theory; computable model; decidable model; prime model; homogeneous model. 
@article{IIGUM_2010_3_4_a1,
     author = {A. N. Gavryushkin},
     title = {A new spectrum of computable models},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {7--20},
     year = {2010},
     volume = {3},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2010_3_4_a1/}
}
TY  - JOUR
AU  - A. N. Gavryushkin
TI  - A new spectrum of computable models
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2010
SP  - 7
EP  - 20
VL  - 3
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2010_3_4_a1/
LA  - ru
ID  - IIGUM_2010_3_4_a1
ER  - 
%0 Journal Article
%A A. N. Gavryushkin
%T A new spectrum of computable models
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2010
%P 7-20
%V 3
%N 4
%U http://geodesic.mathdoc.fr/item/IIGUM_2010_3_4_a1/
%G ru
%F IIGUM_2010_3_4_a1
A. N. Gavryushkin. A new spectrum of computable models. The Bulletin of Irkutsk State University. Series Mathematics, Tome 3 (2010) no. 4, pp. 7-20. http://geodesic.mathdoc.fr/item/IIGUM_2010_3_4_a1/

[1] C. Ash, J. Knight, Computable structures and the hyperarithmetical hierarchy, Elsevier, 2000, 270 | MR

[2] C. C. Chang, H. J. Keisler, Model Theory, North Holland, 1990, 350 pp. | MR

[3] A. Gavryushkin, “Complexity of Ehrenfeucht models”, Algebra and Logic, 45:5 (2006), 289–295 | DOI | MR | Zbl

[4] A. Gavryushkin, “Spectra of computable models for Ehrenfeucht theories”, Algebra and Logic, 46:3 (2007), 149–157 | DOI | MR | Zbl

[5] A. Gavryushkin, “On constructive models of theories with linear Rudin–Keisler ordering”, Journal of Logic and Computation, 2010 | DOI

[6] A. Gavryushkin, “Computable limit models”, Izv. Irkut. gos. un-ta. Ser.: Matematika, 2:2 (2009), 56–61

[7] A. Gavryushkin, Computable models of Ehrenfeucht theories, submitted

[8] S. S. Goncharov, “Strong constructivizability of homogeneous models”, Algebra and Logic, 17:4 (1973), 247–263 | DOI | MR

[9] S. S. Goncharov, “A totally transcendental decidable theory without constructivizable homogeneous models”, Algebra and Logic, 19:2 (1980), 85–93 | DOI | MR

[10] L. Harrington, “Recursively presented prime models”, Journal of Symbolic Logic, 39:2 (1974), 305–309 | DOI | MR | Zbl

[11] N. G. Khisamiev, “Criterion for Constructivizability of a Direct Sum of Cyclic $p$-groups”, Izvestiya Akademii Nauk Kazakhskoi SSR. Seriya Fiziko-Matematicheskaya, 86:1 (1981), 51–55 | MR

[12] B. Khoussainov, A. Montalban, “A computable $\aleph_{1}$-categorical structure whose theory computes true arithmetic”, Journal of Symbolic Logic, 75:2 (2010), 728–740 | DOI | MR | Zbl

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

[14] T. Millar, “Homogeneous models and decidability”, Pacific Journal of Mathematics, 91:2 (1980) | DOI | MR | Zbl

[15] M. Morley, “Decidable Models”, Israel Journal of Mathematics, 25 (1976), 233–240 | DOI | MR | Zbl

[16] M. G. Peretyat'kin, “On complete theories with a finite number of denumerable models”, Algebra and Logic, 12:5 (1973), 310–326 | DOI | MR

[17] R. I. Soare, Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets, Springer Verlag, Berlin-New York, 1987 | MR

[18] S. V. Sudoplatov, “Complete theories with finitely many countable models”, Algebra and Logic, 43:1 (2004), 62–69 | DOI | MR | Zbl