На правах рукописи

Гаврюшкин Александр Николаевич

ВЫЧИСЛИМЫЕ МОДЕЛИ

ЭРЕНФОЙХТОВЫХ ТЕОРИЙ

01.01.06 математическая логика,

алгебра и теория чисел

Автореферат

диссертации на соискание учёной степени

кандидата физико-математических наук

Новосибирск–2009

Работа выполнена в Новосибирском государственном университете

Научный руководитель:

доктор физико-математических наук, профессор, член-корреспондент РАН Гончаров Сергей Савостьянович

Официальные оппоненты:

доктор физико-математических наук, доцент Судоплатов Сергей Владимирович доктор физико-математических наук, профессор Хисамиев Назиф Гарифуллинович

Ведущая организация:

Казанский государственный университет

Защита диссертации состоится 18 июня 2009 г. в 14 часов на заседании диссертационного совета Д 003.015.02 при Институте математики им. С. Л. Соболева СО РАН по адресу:

630090, Новосибирск, пр. Акад. Коптюга, 4.

С диссертацией можно ознакомиться в библиотеке Института математики им. С. Л. Соболева СО РАН.

Автореферат разослан 15 мая 2009 г.

Учёный секретарь диссертационного совета кандидат физико-математических наук А. Н. Ряскин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Тематика диссертации. Диссертация посвящена исследованию некоторых вопросов теории конструктивных (вычислимых) моделей. Её основные результаты относятся к конструктивным моделям эренфойхтовых теорий, хотя некоторые рассматриваемые проблемы имеют более общий характер. Теория конструктивных моделей возникла в 50-ых годах XX века в работах А. И. Мальцева, М. Рабина и других выдающихся математиков, с тех пор активно развивается. Объём литературы, посвящённый этой тематике, очень велик. В качестве наиболее важных и современных источников можно указать [1], [2] и [3]. Эренфойхтовы теории являются классическим объектом не только для теории конструктивных моделей, но и, собственно, для теории моделей, где до сих пор остаются открытыми некоторые важнейшие проблемы, связанные с этим классом теорий.

Основные результаты, касающиеся конструктивных моделей малых теорий, можно найти в [1], [3]. Главные современные открытые вопросы в [4].

Напомним, что полная теория T называется малой, если множество S(T ) её типов (под типом подразумевается максимальное совместное с теорией множество формул) счётно.

Если обозначить через (T ) число попарно неизоморфных счётных моделей счётной полной теории T, то T называется эренфойхтовой, если 3 (T ) <. Если (T ) = 1, теория называется счётно-категоричной. Невозможность случая (T ) = 2 является классическим результатом Воота [5].

Ещё одним подклассом класса малых теорий являются 1 категоричные теории, т. е. теории, любые 2 модели мощности 1 которых изоморфны. В этом случае (T ) =.

Модель называется вычислимой, если её носитель вычислимое подмножество множества натуральных чисел, а операции и предикаты равномерно вычислимые функции на этом подмножестве. В свою очередь, под вычислимыми функциями понимаются те, которые могут быть вычислены с помощью некоторой машины Тьюринга, а под вычислимыми множествами обладающие вычислимыми характеристическими функциями. Понятие конструктивной модели даёт нам другой подход к тому же классу объектов, который фактически основан на использовании другого языка.1) Говорим, что произвольная модель конструктивизируема, если она изоморфна некоторой вычислимой модели.

Главнейшими вопросами теории конструктивных моделей являются: проблема существования вычислимой модели, количество конструктивизируемых моделей данной теории, какие модели являются конструктивизируемыми. Вопросы эти не праздны. К примеру, для классов эренфойхтовых и 1 категоричных теорий на сегодняшний день нет удовлетворительного ответа ни на один из них. Особенно сложно дело обстоит с эренфойхтовыми теориями.

Множество формул назовём разрешимым, если существует алгоритм, проверяющий принадлежность произвольной формулы данному множеству. Модель A разрешима, если найдётся алгоритм, отвечающий на вопрос A |= (a0,..., an ) равномерно по, a0,..., an.2) Для - и 1 -категоричных теорий имеется замечательный результат Харрингтона [6] и Хисамиева [7] об эквивалентности разрешимости теории разрешимости всех её моделей. Последнее же, в свою очередь, равносильно существованию разрешимой модели этой теории. В то время, как для эренфойхтовых теорий сначала Лахлан и Морли [8] построили пример разрешимой теории с шестью моделями, среди которых имеются неразрешимые, а затем Перетятькин [9] обнаружил серию примеров разрешимых эренфойхтовых теорий, имеющих любое число моделей, 1) Эти два подхода (вычислимость и конструктивность) можно охарактеризовать как западный и советский соответственно.

2) Конструктивизируемость модели эквивалентна существованию такого алгоритма лишь для бескванторных формул.

среди которых лишь одна разрешима. Во всех упомянутых примерах неразрешимые модели получаются за счёт наличия неразрешимых типов. В той же статье Морли [8] имеется естественный в этом свете вопрос, который открыт до сих пор, давно стал фольклором и хорошо известен под названием Проблема Морли. Пусть T эренфойхтова теория, и все типы, совместные с T, разрешимы. Любая ли счётная модель теории T разрешима?

Стоит отметить, что если с эренфойхтовой теорией совместны только разрешимые типы, то имеется по крайней мере 3 разрешимые модели: простая (модель, элементарно вкладывающаяся в любую другую модель теории), насыщенная (модель, в которую все остальные модели теории элементарно вкладываются) и слабо насыщенная (модель, реализующая все типы теории), но не насыщенная.3) Поэтому, в случае отрицательного ответа на проблему Морли, контрпример должен иметь, по меньшей мере, 4 модели.

На пути решения этой проблемы возникали различные её аналоги. Например, можно переходить к более высоким уровням алгоритмической сложности. Скажем, что отношение является гиперарифметическим (арифметическим), если оно получено из вычислимого отношения взятием (конечного числа раз) проекций и дополнений. Множество имеет гиперарифметическую (арифметическую) сложность, если проблема принадлежности произвольного элемента этому множеству эквивалентна выполнимости гиперарифметического (арифметического) отношения.

Если в формулировке проблемы Морли все вхождения подслова разрешим заменить на арифметичн, то получится открытый вопрос, впервые предложенный Гончаровым Здесь и далее предполагается, что все рассматриваемые объекты, в частности, модели (не более, чем) счётные.

и Миларом. Для гиперарифметической эренфойхтовой теории можно показать (см., например, [1]), что все модели будут иметь гиперарифметическую сложность.

Изучая связь между алгоритмической сложностью малой теории с алгоритмическими сложностями её моделей, Гончаров и Хусаинов в [10] и [11] построили примеры - и 1 категоричных теорий сколь угодно большой арифметической сложности, и при этом имеющих конструктивизируемые модели. В реферируемой диссертации имеются такие же примеры эренфойхтовых теорий. Аналогичный вопрос в случае гиперарифметической сложности остаётся открытым для всех трёх классов теорий.

Неожиданностью было появление результата Хусаинова, Ниса и Шора [12] о существовании теории с тремя счётными моделями, среди которых лишь насыщенная конструктивизируема. Это вместе с ещё одним результатом диссертации:

существует эренфойхтова теория, обладающая неконструктивизируемой моделью, такая, что и простая, и насыщенная модели конструктивизируемы наталкивает на размышления об отрицательном решении проблемы Морли.

Упомянутые выше три типа изоморфизма моделей: простая, насыщенная и слабо насыщенная являются классическими. Наличие примеров эренфойхтовых теорий, имеющих любое количество моделей с одной стороны, и изученность лишь трёх из них с другой, является существенным камнем преткновения для исследований по данной тематике.

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

виями) и отображение, действующее из этого предпорядка в множество натуральных чисел (тоже с несущественными свойствами). (Назовём эти параметры параметрами эренфойхтовости.) В этой связи, вопрос о расположении разрешимых, конструктивизируемых и др. моделей друг относительно друга стал гораздо осмысленнее. Кроме того, в работе [14] Судоплатовым построены примеры теорий, обладающих произвольными наперёд заданными параметрами эренфойхтовости. Это обнажило весь класс вопросов, связанных со спектром вычислимых моделей теории, т. е. с взаимным расположением конструктивизируемых моделей. К сожалению, конструкция примеров из [14] чрезвычайно сложна, и попытка сразу доказывать теоремы конструктивизируемости наталкивается на серьёзные трудности. Но всё же некоторые частные случаи уже сейчас поддаются анализу. В реферируемой диссертации изучаются некоторые вопросы теории конструктивных моделей для эренфойхтовых теорий, имеющих первым параметром эренфойхтовости конечный линейный порядок. В частности, из результатов диссертации следует существование эренфойхтовой теории, имеющей сколь угодно большое число моделей, при этом конструктивизируемыми являются только модели, очень близкие, в некотором теоретикомодельном смысле, к насыщенной модели. Общий же вопрос характеризации спектра вычислимых моделей в случае эренфойхтовой теории остаётся открытым, равно как и в случае 1 -категоричной теории. Кроме того, в случае эренфойхтовой теории, к нему добавляется также открытый вопрос характеризации спектра разрешимых моделей.

Научная новизна. Все основные результаты диссертации являются новыми.

Основные результаты диссертации.

1. Построен пример эренфойхтовой теории, имеющей любые наперёд заданные число моделей и арифметическую сложность, при этом обладающей конструктивизируемой моделью.

2. Построен пример эренфойхтовой теории, имеющей некоструктивизируемую модель, с конструктивизируемыми простой и насыщенной моделями.

3. Для произвольного конечного линейного порядка построен пример эренфойхтовой теории, имеющей этот порядок в качестве первого параметра эренфойхтовости. Рассмотрены некоторые возможности моделей такой теории быть конструктивизируемыми. В частности, построен пример, когда конструктивизируемы в точности модели, не являющиеся простыми ни над каким конечным обогащением константами.

Теоретическая и практическая ценность. Диссертация имеет теоретический характер, её результаты могут использоваться в дальнейших исследованиях по теории конструктивных моделей.

Апробация работы. По результатам диссертации были сделаны: пленарный доклад на конференции Мальцевские чтения 2007 (Новосибирск, Россия), доклады на конференциях Computability in Europe 2008 (Афины, Греция), Logic Colloquium 2007 (Вроцлав, Польша), Computability in Europe 2006 (Свонси, Великобритания), доклад на Международной студенческой конференции 2006, отмеченный дипломом первой степени, Asian Logic Conference 2005 (Новосибирск, Россия). Кроме того, результаты докладывались на совместных семинарах НГУ и ИМ СО РАН Конструктивные модели, Алгебра и логика, на совместном семинаре ИМ СО РАН (Россия) – The University of Notre Dame (США) Constrictive models, а также на школе-семинаре ИМ СО РАН Workshop Computable Models and Numberings.

Публикации. Основные результаты опубликованы в работах [15]–[20].

Структура и объём диссертации. Диссертация состоит из введения, трёх глав и списка литературы (39 наименований). Объём диссертации 77 стр.

ОБЗОР СОДЕРЖАНИЯ ДИССЕРТАЦИИ

Первая глава диссертации посвящена изучению сложности эренфойхтовой теории, имеющей конструктивизируемую модель. Главным результатом этой главы является Теорема 1. Для всех натуральных чисел n 3иm существует теория Эренфойхта T, эквивалентная по Тьюрингу (m) и имеющая с точностью до изоморфизма n счётных моделей, одна из которых конструктивизируема.

Как в формулировке этой теоремы, так и далее, множества формул отождествляются с множествами их гёделевских номеров. Под эквивалентностью по Тьюрингу и (m) понимается следующее:

Определение 1. Множества A и B эквивалентны по Тьюрингу, если алгоритм вычисления характеристической функции множества A сводим к алгоритму вычисления характеристической функции множества B, и обратно:

алгоритм вычисления характеристической функции множества B сводим к алгоритму вычисления характеристической функции множества A.

Определение 2. Обозначим через (1) множество всех натуральных чисел n, таких, что алгоритм с номером n останавливается через конечное число шагов, если на вход было подано число n. Пусть (m1) определено для m > 1, обозначим через (m) множество всех натуральных чисел n, таких, что алгоритм относительно оракула (m1) с номером n останавливается через конечное число шагов, если на вход было подано число n.

Вторая глава имеет своей целью изучение вопроса: Какие модели эренфойхтовой теории могут быть конструктивизируемы? в его классическом понимании, т. е. при ограничении тремя типами изоморфизма счётных моделей.

Определение 3. Модель A называется элементарной подмоделью модели B (обозначается A B), если для любой формулы и любых элементов a0,..., an из модели A выполнено A |= (a0,..., an ) B |= (a0,..., an ).

Определение 4. Модель A теории T называется простой, если для любой модели B |= T существует C B, т. ч. A C.

Определение 5. Модель A теории T называется насыщенной, если для любой модели B |= T существует C B, т. ч.

В насыщенной модели реализуется любой тип, совместный с теорией. Но не любая модель, реализующая все типы является насыщенной.

Определение 6. Модель A теории T называется слабо насыщенной, если в A реализуется любой тип, совместный с T.

Основными результатами второй главы являются теоремы 2 и 3.

Теорема 2. Существует эренфойхтова теория T, т. ч.

единственная конструктивизируемая модель этой теории не является ни простой, ни насыщенной, ни слабо насыщенной.

Теорема 3. Существует эренфойхтова теория T, т. ч.

простая и насыщенная модели теории T конструктивизируемы, и существует неконструктивизируемая модель теории T.

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

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

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

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

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

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

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

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

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

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

2. |S(T )| =, |RK(T )| <, IL(M) < для всех M Главными результатами третьей главы диссертации являются теоремы 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, Innistic 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, [10] Гончаров, С. С., Хусаинов, Б. М., О сложности теорий вычислимых 1 -категоричных моделей, Вестник НГУ.

Серия: математика, механика, информатика, 1, 2, 63– [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, Работы автора по теме диссертации [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, [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– Гаврюшкин Александр Николаевич

ВЫЧИСЛИМЫЕ МОДЕЛИ ЭРЕНФОЙХТОВЫХ

ТЕОРИЙ

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук Подписано в печать 14.04.09 Формат 60 x 84 1/ Редакционно-издательский центр НГУ.

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