Автоустойчивость конструктивных моделей тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

■ , РОССИЙСКАЯ АКАДЕМИЯ НАУК

СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ ~~ им. СЛ. Соболева

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

УДК 517.15

КУДИНОВ Олог Викторович

АВТОУСТОЙЧИВОСТЬ КОНСТРУКТИВНЫХ МОДЕЛЕЙ

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск . 1995

Работа выполнена в Институте математики Сибирского отделения Российской Академии наук.

Научный руководитель - академик МАН ВШ,

доктор физико-математических наук, профес с ор С.С.Гончаров.

Официальные оппоненты: доктор физико-математических наук

В.П.Добрица,

кандидат физико-математических наук А.А.Мальцев.

Ведущая организация - Омский государственный университет.

Защита состоится " 22. " февраля 199 6г. в ^ часов на заседании специализированного совета Д 002.23.01 при Институте математики Сибирского отделения РАН по адресу: 630090, Новосибирск, 90, Университетский проспект, 4.

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

Автореферат разослан 15"» января 1996 г.

Ученый секретарь специализированного совета Д 002.23.01

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

С.Т.Федоряев

ОБДАЛ ХАРАКТЕРИСТИКА ДИССЕРТАЦИИ

Результаты диссертации относятся к теории конструктивных моделей - области математики, возникшей на стыке теории алгоритмов и теории моделей почти одновременно в работах как западных математиков, где такие модели называются рекурсивными, так и в трудах А.И.Мальцева.

Особенно стоит отметить основополагающую статью А.И. Мальцева [13] , где обобщены методы изучения конструктивных алгебраических объектов и заложены основы теории, а также намечены пути дальнейшего исследования.

При этом именно использование понятия нумерации позволяет с единой точки зрения взглянуть на природу вычислимости алгебраических и теоретико-модельных конструкций и объединить методы теории алгоритмов с методами алгебры и теории моделей.

В монографии Ю.Л.Ершова [ 12 ] подведены итоги первого этапа развития теории конструктивных моделей и сформулированы две основные проблемы: проблема существования конструктивиза-ции модели (возможно, со специальными свойствами) и проблема числа неэквивалентных конструктивизаций.

Со второй проблемой тесно связаны проблемы существования и характеризации моделей конечной и бесконечной алгоритмической размерности, а также автоустойчивых моделей, которые по существу уже рассматривались в [19 ] , а также в [21 ] .

Поскольку понятие автоустойчивости является очень естест-

венным - речь идет о единственности с точностью до автоэквивалентности конструктивизации у конструктивной модели - оно исследовалось в работах очень многих авторов, но особенно стоит отметить работы С.С.Гончарова Г 5-9] . Так, в [9] построен пример ± -однородной неавтоустойчивой модели конечной алгоритмической размерности, а в [ 5, 6] показана связь автоустойчивости с теоретико-модельным понятием ¿-полноты, дан критерий автоустойчивости доя 2-конструктивных моделей в терминах вычислимого плотного семейства атомных 3 --формул с параметрами (семейства 3 -формул Скотта) и аналогичный критерий для понятия рекурсивной устойчивости в классе 1 -конструктивных моделей.

Настоящая диссертация связана с попыткой описания автоустойчивых моделей в теоретико-модельных терминах. Эту задачу удалось полностью решить в классе ±-конструктивных моделей и в некоторых других классах моделей, близких к полям алгебраических чисел.

В общем случае проблема существования такого описания остается открытой, поскольку работа [ 33 , отрицательно отвечавшая на этот вопрос, содержит ошибку, что отмечается в главе 3 диссертации.

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

Кроме того, предложен критерий рекурсивной устойчивости моделей (что соответствует автоустойчивости жестких моделей) в терминах некоторой новой сводимости конструктивизаций, а

также введены и изучены понятия равномерной автоустойчивости по классам и по индексам конструктивизаций.

ОНЦАЯ МЕТОДИКА ИССЛЕДОВАНИЙ

В диссертации используются методы теории алгоритмов и рекурсивных функций, в частности, метод приоритета с нарушениями, конечность которых устанавливается в ходе доказательства , метод элиминации кванторов в модифицированном виде для установления разрешимости 3-теории, а также широко применяются идея моделирования, аппарат теории категорий, а также аппарат и результаты из статей [7, 8] .

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

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

Апробация. Результаты диссертации докладывались и анонсировались в разное время на семинарах ИМ СО РАН, НГУ ,

на логическом коллоквиуме Клини-90 (Варна, 1990), межреспубликанской конференции по математической логике (Казань, 1992), и международной конференции по математической логике памяти А.И.Мальцева (Новосибирск, 1994).

Основные результаты диссертации опубликованы в работах автора [23 - 27] •

Структура диссертации. Диссертация состоит из введения, трех глав и списка литературы. Названия глав следующие: "Критерии автоустойчивости некоторых классов моделей", "Автоустойчивость 1 -разрешимых моделей", "Проблемаи описания автоустойчивых моделей". Объем диссертации - 89 страниц, список литературы включает 27 наименований.

содержание диссертации При определении понятий, используемых в диссертации, автор придерживался терминологии из монографий [II, 12] . Через КСш), И1~~1(т) обозначим, соответственно, класс кон-структивизаций и класс однозначных конструктивизаций модели 7Т1 , через М^^ - множество кортежей элементов модели ТМ с носителем М .

Через ©з обозначим 5 -й кортеж из ¡Н в их канонической нумерации. Для , & , с & М^1^ запишем $ С- » 0СЛИ выполняются: для всякой 3 -формулы

Используем также обозначения Ог£_ (I )=* { Зе М<и)1 ЗЧеАиКтр):

Приведем список основных результатов главы I. ТЕОРЕМА 1.1. Конструктивная модель рекурсивно

устойчива тогда и только тогда, когда она устойчива по отношению к сводимости конструктивизаций по ограниченной перечислимости.

Данный критерий рекурсивной устойчивости моделей не явля-

ется равномерным.

ЛЕММА 1.2. Пусть (Ш,^) - конструктивная модель и множество 5 — ОгВ(<^о г)ц.>) наследственно рекурсивно перечислимо. Тогда модель 7У1 автоустойчива.

Условие этой леммы называется в тексте общим достаточным условием автоустойчивости моделей.

Далее рассматриваются критерии автоустойчивости некоторых классов моделей К0 и , из которых выводится важное

СЛЕДСТВИЕ. Пусть к - р.п. подполе своего нормального расширения (Р,^) . Тогда Р автоустойчиво над К тогда и только тогда, когда чисто несепарабельное замыкание поля к в Р разрешимо относительно V .

В главе 2 изучаются автоустойчивые \ -разрешимые модели. Доказывается, что для всякой такой модели (Ш^) найдется а е I 'УтЬ | ^ ^ такой, что множество ^ £ ^ разрешимо и модель 1 -однородна. Критерий автоустойчивости таков:

ТЕОРЕМА 2.1. Если - ± -разрешимая модель, то

следующие два условия эквивалентны:

1) модель "Ж. автоустойчива;

2) существует о. & М< ^ такой, что множество

наследственно разрешимо.

Рассмотрим следующее

ОПРЕДЕЛЕНИЕ 2.2. Модель (т,\)) называется равномерно автоустойчивой по классам (конструктивизаций), если для всякого вычислимого класса К - С I I а ы) конструктивизаций этой модели существуют а & М< °° и двуместная

ч.р.ф. F такие, что если ^ (а) - то значение FC*, S) определено, является о.р.ф. и для

некоторого У е Ао* (Ш, а) * ° = * oi>£.

ТЕОРЕМ 2.2. Всякая автоустойчивая ±-разрешимая модель (Ulj^) равномерно автоустойчива по классам.

В отличие от класса 2-конструктивных моделей ( f5J ), не все автоустойчивые ±-разрешимые модели обладают вычислимым семейством Скотта 3 -формул с конечным набором параметров.

ТЕОРЕМА 2.3. Существует автоустойчивый 1-разрешимый унар, не обладащий вычислимым семейством Скотта 3-формул с конечным набором параметров.

При этом в главе П построен функтор, осуществляющий эквивалентность между категорией вычислимых нумераций семейства о.р.ф. S с бесконечными прообразами элементов и категорией i-i-конструктивизаций унара Mj,

Введены естественные понятия &-конструктивной модели и модели, автоустойчивой в степени о. , где CL - произвольная тьйрингова степень. Получен следующий признак автоустойчивости 1 -разрешимых моделей.

ПРЕДЛОЖЕНИЕ 2.6. Пусть модель (Ш,^) ¿-разрешима и автоустойчива во всех степенях & таких, что о' ,

Тогда модель (Ш,»?) автоустойчива.

Кроме того, установлено, что критерием автоустойчивости в степени о' 1 -разрешимой модели (TYt^Р) является 1 -простота модели (т^с) для подходящего С- .

Зафиксируем вычислимую индексацию С Л ^егс^з позитивных однозначных нумераций счетных моделей.

ОПРЕДЕЛЕНИЕ 2.3. Модель (Ш,^) называется равномерно автоустойчивой по индексам (конструктивизаций), если существует двуместная ч.р.ф. А Р ( ¿,]') , вычислящая клиниевский индекс о.р.ф., сводящей нумерацию к Д

при условии, что обе они лежат в К(тгь) , т.е. Р (¿' ,

3 У е Аи.1 (т) : о у о ы .

Унар, построенный в теореме 2.3, не является равномерно автоустойчивым по индексам.

В главе 3 описана конструкция, сопоставляющая вычислимому семейству р.п.м. 5 унар ЬЦг ^^ , наследующий алгоритмические свойства $ . Фактически все результаты главы 3, кроме теоремы 3.1, являются ее следствиями. Отмечена связь общего достаточного условия авгоустойчивости с общим критерием автоустойчивости, а также доказано важное

ПРЕДЛОЖЕНИЕ 3.2. Существует автоустойчивый унар, не удовлетворяющий общему достаточному условию автоустойчивости.

Общий критерий автоустойчивости дан в теореме 3.1.

Обозначим через ^БР , ЬСС.А классы моде-

лей, обладающих вычислимым семейством Скотта Э -формул с параметрами, равномерно автоустойчивых по классам и по индексам конструктивизаций в конечном константном обогащении соответственно.

Строятся примеры, показывающие, что

ЬЕР

ТЕОРЕМА 3.1. Для всякой конструктивной модели

9

эквивалентны следующие условия:

1) модель автоустойчива;

2) для всякой /л. е найдется множество

V — Ь ~ I/ Ог6(<.^о} Vн>) , обладающее свойст-

ваш:

а) _ - 'т1 дая всякого Vе V ;

У/Э V

б) множество А рекурсивно перечислимо. Кроме того, опровергнут основной результат работы ГЗ] ,

где изучалось понятие равномерной автоустойчивости.

УТВЕРЖДЕНИЕ 3.4. Всякая автоустойчивая модель равномерно автоустойчива.

В заключение автор выражает крайнюю признательность С.С.Гончарову за руководство работой и всестороннюю помощь и поддержку.

ЛИТЕРАТУРА

1. М.М.Арсланов, Семейства рекурсивно перечислимых множеств и их степени неразрешимости. - Изв. вузов. Математика, 1985, № 4, 13-19.

2. Ю.Г.Венцов, Алгоритмические свойства ветвящихся моделей, Алгебра и логика, 25, № 4(1986), 369-383.

3. Ю.Г.Венцов, Неравномерная автоустойчивость моделей, Алгебра и логика, 26, № 6(1987), 422-440.

4. В.В.Выогин, 0 некоторых примерах верхних полурешеток вычислимых нумераций, Алгебра и логика, 12, № 5 (1973),

с.512-529.

5. С.С.Гончаров, Автоустойчивость и вычислимые семейства конструктивизаций, Алгебра и логика,14, №6(1975), 647-680.

6. С.С.Гончаров, 0 числе неавтоэквивалентных конструк-тивизаций, Алгебра и логика, 18, № 3(1977), 257-282.

7. С.С.Гончаров, Автоустойчивость моделей и абелевых групп, Алгебра и логика, 19, № 1(1980), 23-44.

8. С.С.Гончаров, Б.Д.Дзгоев, Автоустойчивость моделей, Алгебра и логика, 19, № 1(1980), 45-58.

9. С.С.Гончаров, Проблема числа неавтоэквивалентных конструктивизаций, Алгебра и логика, 19, № 6(1980),621-639.

10. Ю.Л.Ершов, Теория нумераций, Ч.З, Конструктивные модели, Новосибирск, НГУ, 1974.

11. Ю.Л.Ершов, Теория нумераций, М., Наука, 1977.

12. Ю.Л.Ершов, Проблемы разрешимости и конструктивные модели, М., Наука, 1980.

13. А.И.Мальцев, Конструктивные модели, I, УМН, 16, № 3 (1961), 3-60.

14. А.И.Мальцев, 0 рекурсивных абедевых группах, ДАН СССР, 146, № 5(1962), I009-1012.

15. А.Т.Нуртазин, Сильные и слабые конструктивизации, Алгебра и логика, 13, № 3(1974), 311-323.

16. Логическая тетрадь, Нерешенные вопросы математической логики, Новосибирск, ИМ СО АН СССР, 1986.

1?. С. X Ash, ÎCLUforioity in hyperarUhm--bicai denrées', o.f Р«-Г£ and Apfii&J

Logic , 14 , iïAi (m?), l-14.

18. С.г Ask, A. Verode, lui rin.sicaii«f recar-sive re ia.tion f Aspects, ap Effective Ai^b

га, troc. Сол Mort a<;h Uh.îv'., Austraiia,i'l8i)26-

1«. Л. Frdlich , J.C. Skefkerdsoia, Effectu/e

рг осе dures in field the-ory, Ph.il. Trans. Hoyal Society, London., A 24 8 f 195 6) , ЧОТ--Ч ъг.

Ю. G. лиtakit/ел, A. Veroiie, Effective content at fieid theory, Ann, Ma.tk.Lo<}ic, <7, >/sl

( i 9 7- 9) i89- UO,

11, M.o. Hftbin, Cowtpw.tab 1 e a igrCbra, general tbeor^ and iheor^ Of computable fields, ТАМ S, V*Zimo), 341-350.

Я2 £>• Scott , Loaic dtnu.ne.rab f e long

f0rmu ias artd -fin ite string of ?ua*iifxerS, in: 3.W. AddiSOH., 1 НенкЫ and A.TarsKi ids., The Theory 04 Mode.1% > tforth -Hoilcincl, AHSitr-claM, 1S6S.

Работы автора по теме диссертации

23. О.В.Кудинов, Неравномерный критерий рекурсивной устойчивости конструктивизируемых моделей, в сб.: У школа молодых математиков Сибири и Дальнего Востока. Тезисы докладов, Новосибирск, ИМ СО АН СССР, 1990, 58-59.

24. O.V. KndiH.oV7 On Ш criteria Of Q.u.to~ stab¿¿ity for some classes o-F models, Abstracts of Third Logical 81еШа.1, Sofia, 1990, 39-40.

25. О.В.Кудинов, 0 полных системах финитных аппроксимаций множеств из класса , в сб.¡Теория вычислимости и языки спецификаций. Вычислимые системы 139 (1991), III-II6.

26. О.В.Кудинов, Критерий автоустойчивости -разрешимых моделей. Алгебра и логика, 31, № 5 (1992), 479-492.

27. О.В.Кудинов, Проблема описания автоустойчивых моделей, препринт Jf 14, изд-во НИИ МИОО НГУ, Новосибирск, 1995.