WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     ||
|

Третья глава посвящена вопросу разрешимости и вычислимости моделей эренфойхтовой теории в терминах характеризационной теоремы Судоплатова. Обратимся сначала к работе [13], где и доказана упомянутая теорема, для введения необходимых определений.

Через Mp обозначим класс (изоморфных) простых над реализацией типа p моделей, т. е. Mp = {M| существует модель N |= p(), M, простая модель теории T h( N, )}, где T h(A) = { | A |= }.

Определение 7. Тип p не превосходит тип q по предпорядку Рудина-Кейслера (p RK q), если Mq |= p.5) p RK q (p RK q & q RK p).6) Обозначим через RK(T ) множество типов изоморфизма моделей Mp по всем p S(T ). Отношение RK естественным образом переносится на множество RK(T ), поэтому индуцированное отношение будем обозначать так же: RK, а само множество RK(T ) считать предупорядоченным.

Определение 8. Тип p теории T называется властным, если из того, что p реализуется в некоторой модели M теории T следует, что в M реализуются все типы из S(T ).

Определение 9. Последовательность M0 M1... называется элементарной цепью над типом p, если Mn Mp = для всех n.

Определение 10. Модель M называется предельной над типом p, если M = Mn, для некоторой элементарной над n типом p цепи (Mn)n, но M Mp.

= 5) Равносильно Mp Mq.

6) В случае, когда типы p и q находятся в некотором отношении по RK-порядку, говорят, что и модели Mp и Mq находятся в этом же отношении.

Для M RK(T )/ RK обозначим через IL(M) число попарно неизоморфных моделей, предельных над элементами из M.

Теорема 4. (Судоплатов [13]). Следующие условия эквивалентны:

1. (T ) < ;

2. |S(T )| =, |RK(T )| <, IL(M) < для всех M RK(T )/ RK.

Главными результатами третьей главы диссертации являются теоремы 5 и 6.

Определение 11. Модель M |= T называется квазипростой, если она проста над реализацией некоторого типа теории T.

Обозначим через Ln линейный порядок, состоящий из n + 1 элемента: {x0 < x1 <... < xn}.

Теорема 5. Пусть N n 1, 0 k n. Существует эрен фойхтова теория Tn, для которой RK(Tn) Ln, при этом, = модели, соответствующие элементам x0, x1,..., xk порядка Ln, разрешимы, модели, соответствующие элементам xk+1,..., xn не конструктивизируемы.

Теорема 6. Для любого 1 n существует эренфойх това теория Tn, RK(Tn) Ln, все квази-простые модели = Tn неконструктивизируемы, существует конструктивизируемая модель теории Tn.

В заключение, автор выражает огромную благодарность и сердечную признательность своему научному руководителю, Сергею Савостьяновичу Гончарову, за незабываемое приглашение в мир науки, в мир математики, определившее мои профессиональные интересы.

Список литературы [1] Гончаров, С. С., Ершов, Ю. Л., Конструктивные модели, Научная книга, Новосибирск, 1999.

[2] Ash, C., Knight, J., Computable structures and the hyperarithmetical hierarchy, Elsevier, 2000.

[3] Handbook of Recursive Mathematics, Elsevier, 1998.

[4] Goncharov, S., Khoussainov, B., Open Problems in the Theory of Constructive Algebraic Systems, CDMTCS Research Report Series, CDMTCS-124, 2000.

[5] Vaught, R., Denumerable Models of Complete Theories, Infinistic Methods, Proceedings of the Symposium on Foundations of Mathematics, Warshaw, 303–321, 1959.

[6] Harrington, L., Recursively Presented Prime Models, Journal of Symbolic Logic, 39, 305–309, 1974.

[7] Хисамиев, Н. Г., О сильно конструктивных моделях разрешимой теории, Изв. АН Каз ССР. Сер. 1. Физика и математика, 3, 83–84, 1974.

[8] Morley, M., Decidable Models, Israel Journal of Mathematics, 25, 233–240, 1976.

[9] Перетятькин, М. Г., О полных теориях с конечным числом счётных моделей, Алгебра и логика, 12, 550–576, 1973.

[10] Гончаров, С. С., Хусаинов, Б. М., О сложности теорий вычислимых 1-категоричных моделей, Вестник НГУ.

Серия: математика, механика, информатика, 1, 2, 63– 76, 2001.

[11] Гончаров, С. С., Хусаинов, Б. М., Сложность теорий вычислимых категоричных моделей, Алгебра и логика, 43, 6, 650–665, 2004.

[12] Khoussainov, B., Nies, A., Shore, R., Computable Models of Theories with Few Models, Notre Dame Journal of Formal Logic, 38, 165–178, 1997.

[13] Судоплатов, С. В., Полные теории с конечным числом счётных моделей I, Алгебра и логика, 43, 1, 110–124, 2004.

[14] Судоплатов, С. В., Полные теории с конечным числом счётных моделей II, Алгебра и логика, 45, 3, 314–353, 2006.

Работы автора по теме диссертации [15] Gavryushkin, A., On Complexity of Ehrenfeucht Theories with Computable Model, Logical Approaches to Computational Barriers (Second Conference on Computability in Europe), Report Series, Swansea University, 105–108, 2006.

[16] Гаврюшкин, А. Н., Сложность эренфойхтовых моделей, Алгебра и логика, 45, 5, 507–519, 2006.

[17] Gavryushkin, A., Computable Models Spectra of Ehrenfeucht Theories, Logic Colloquium 2007, Book of Abstracts, Uniwersytet Wroclawski, 46–47, 2007.

[18] Гаврюшкин, А. Н., Спектры вычислимых моделей эренфойхтовых теорий, Алгебра и логика, 46, 3, 275–289, 2007.

[19] Gavryushkin, A., Computable Models Spectra of Ehrenfeucht Theories, Logic and Theory of Algorithms, Fourth Conference on Computability in Europe, CiE Local Proceedings, University of Athens, 50–51, 2008.

[20] Гаврюшкин, А. Н., О конструктивных моделях теорий с линейным порядком Рудина-Кейслера, Вестник НГУ.

Серия: математика, механика, информатика, 9, 2, 30– 37, 2009.

Гаврюшкин Александр Николаевич ВЫЧИСЛИМЫЕ МОДЕЛИ ЭРЕНФОЙХТОВЫХ ТЕОРИЙ Автореферат диссертации на соискание учёной степени кандидата физико-математических наук Подписано в печать 14.04.09 Формат 60 x 84 1/Печать офсетная Усл. печ. л. 1.Заказ № Тираж 100 экз.

Редакционно-издательский центр НГУ.

630090, Новосибирск–90, ул.Пирогова

Pages:     ||
|



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.