journal.isu.ru

Начальная страница

Конечная страница

УДК

Раздел
     

Файл
Скачать Изменить файл

Название RU

Авторы RU

Аннотация RU
<p>В работе доказано существование моделей эренфойхтовой теории, попарно друг в друга элементарно вкладываемых, одна из которых имеет вычислимое представление, а другая нет. Этот результат вместе с работой [6] является ключевым для описания спектров вычислимых моделей эренфойхтовых теорий.</p>

Ключевые слова RU

Литература RU
1. AshC. Computable structures and the hyperarithmetical hierarchy / C. Ash, J. Knight. – Elsevier, 2000. – 270 p. 2. ChangC.C. Model Theory / C. C. Chang, H. J. Keisler. – North Holland, 1990. – 350 p. 3. Gavryushkin A. Complexity of Ehrenfeucht models / A. Gavryushkin // Algebra and Logic. – 2006. – V. 45, No. 5. – P.289–295. 4. Gavryushkin A. Spectra of computable models for Ehrenfeucht theories / A. Gavryushkin // Algebra and Logic. – 2007. – V. 46, No. 3. – P. 149–157. 5. Gavryushkin A. On constructive models of theories with linear Rudin-Keisler ordering / A. Gavryushkin // Journal of Logic and Computation. – doi: 10.1093/logcom/exq043. – 2010. 6. Gavryushkin A. Computable limit models / A. Gavryushkin // Изв. Иркут. гос. ун-та. Сер.: Математика. – 2009. – Т. 2, №. 2. – С. 56–61. 7. Gavryushkin A. Computable models of Ehrenfeucht theories / A. Gavryushkin // submitted. 8. Goncharov S. S. Strong constructivizability of homogeneous models / S. S. Goncharov // Algebra and Logic. – 1973. – V.17, No.4. – P. 247–263. 9. Goncharov S. S. A totally transcendental decidable theory without constructivizable homogeneous models / S. S. Goncharov // Algebra and Logic– 1980. – V. 19, No. 2. – P. 85–93. 10. Harrington L. Recursively presented prime models / L. Harrington // Journal of Symbolic Logic. – 1974. – V. 39, No. 2. – P. 305–309. 11. Khisamiev N.G. Criterion for Constructivizability of a Direct Sum of Cyclic p-groups / N. G. Khisamiev // Izvestiya Akademii Nauk Kazakhskoi SSR. Seriya Fiziko-Matematicheskaya. – 1981. – V. 86, No. 1. – P. 51–55. 12. Khoussainov B. A computable @1-categorical structure whose theory computes true arithmetic / B. Khoussainov, A. Montalban// Journal of Symbolic Logic. – 2010. – V. 75, No. 2. – P. 728–740. 13. Khoussainov B. Computable Models of Theories with Few Models / B. Khoussainov, A. Nies, R. Shore// Notre Dame Journal of Formal Logic. – 1997. – V. 38, No. 2.– P. 165–178. 14. Millar,T. Homogeneous models and decidability / T. Millar // Pacific Journal of Mathematics. – 1980. – V. 91.– No. 2. 15. Morley M. Decidable Models / M. Morley // Israel Journal of Mathematics.– 1976. – No. 25. – P. 233–240. 16. Peretyat’kinM.G. On complete theories with a finite number of denumerable models / M.G. Peretyat’kin // Algebra and Logic. – 1973. – V.12, No.5. – P. 310–326. 17. SoareR. I. Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets / R. I. Soare. – Springer Verlag : Berlin-New York, 1987. 18. Sudoplatov S.V. Complete theories with finitely many countable models / S.V. Sudoplatov// Algebra and Logic. – 2004. – V. 43, No. 1. – P. 62–69.

Название EN

Авторы EN

Аннотация EN
<p>In the paper we prove that there exist models A and B of an Ehrenfeucht theory such that A is elementary embeddable into B, B is elementary embeddable into A, model A has a computable presentation, model B has no computable presentation. This theorem together with the work [6] is the key result for the theorem describing computable models spectra of Ehrenfeucht theories.</p>

Ключевые слова EN

Литература EN
1. AshC. Computable structures and the hyperarithmetical hierarchy / C. Ash, J. Knight. – Elsevier, 2000. – 270 p. 2. ChangC.C. Model Theory / C. C. Chang, H. J. Keisler. – North Holland, 1990. – 350 p. 3. Gavryushkin A. Complexity of Ehrenfeucht models / A. Gavryushkin // Algebra and Logic. – 2006. – V. 45, No. 5. – P.289–295. 4. Gavryushkin A. Spectra of computable models for Ehrenfeucht theories / A. Gavryushkin // Algebra and Logic. – 2007. – V. 46, No. 3. – P. 149–157. 5. Gavryushkin A. On constructive models of theories with linear Rudin-Keisler ordering / A. Gavryushkin // Journal of Logic and Computation. – doi: 10.1093/logcom/exq043. – 2010. 6. Gavryushkin A. Computable limit models / A. Gavryushkin // Изв. Иркут. гос. ун-та. Сер.: Математика. – 2009. – Т. 2, №. 2. – С. 56–61. 7. Gavryushkin A. Computable models of Ehrenfeucht theories / A. Gavryushkin // submitted. 8. Goncharov S. S. Strong constructivizability of homogeneous models / S. S. Goncharov // Algebra and Logic. – 1973. – V.17, No.4. – P. 247–263. 9. Goncharov S. S. A totally transcendental decidable theory without constructivizable homogeneous models / S. S. Goncharov // Algebra and Logic– 1980. – V. 19, No. 2. – P. 85–93. 10. Harrington L. Recursively presented prime models / L. Harrington // Journal of Symbolic Logic. – 1974. – V. 39, No. 2. – P. 305–309. 11. Khisamiev N.G. Criterion for Constructivizability of a Direct Sum of Cyclic p-groups / N. G. Khisamiev // Izvestiya Akademii Nauk Kazakhskoi SSR. Seriya Fiziko-Matematicheskaya. – 1981. – V. 86, No. 1. – P. 51–55. 12. Khoussainov B. A computable @1-categorical structure whose theory computes true arithmetic / B. Khoussainov, A. Montalban// Journal of Symbolic Logic. – 2010. – V. 75, No. 2. – P. 728–740. 13. Khoussainov B. Computable Models of Theories with Few Models / B. Khoussainov, A. Nies, R. Shore// Notre Dame Journal of Formal Logic. – 1997. – V. 38, No. 2.– P. 165–178. 14. Millar,T. Homogeneous models and decidability / T. Millar // Pacific Journal of Mathematics. – 1980. – V. 91.– No. 2. 15. Morley M. Decidable Models / M. Morley // Israel Journal of Mathematics.– 1976. – No. 25. – P. 233–240. 16. Peretyat’kinM.G. On complete theories with a finite number of denumerable models / M.G. Peretyat’kin // Algebra and Logic. – 1973. – V.12, No.5. – P. 310–326. 17. SoareR. I. Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets / R. I. Soare. – Springer Verlag : Berlin-New York, 1987. 18. Sudoplatov S.V. Complete theories with finitely many countable models / S.V. Sudoplatov// Algebra and Logic. – 2004. – V. 43, No. 1. – P. 62–69.