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

Академия наук СССР Сибирское отделение Институт Математики

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

Морозов Андрей Сергеевич

ГРУППЫ ВЫЧИСЛИМЫХ АВТОМОРФИЗМОВ

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

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

Новосибирск - 1990

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

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

доктор физико-математических наук, профессор Перетятькин М.Г.

доктор физико-математических наук, профессор Плоткин Б.И.

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

Ведущее учреждение - Механико-математический факультет

Московского государственного университета им. М.В.Ломоносова

Защита состоится "_"_1990 г. в _ часов на

заседании Специализированного совета Д 002.23.01 при Институте математики СО АН СССР, г.Новосибирск-90, Университетский проспект, 4.

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

Автореферат разослан "_" 1990 года.

Ученый секретарь Специализированного совета, д. ф.-м. н., профессор

Е.А.Палютин

Понятие алгоритма, введенное в математику в первой половине нашего века, является одним из фундаментальнейших понятий, которое по своей значимости, пожалуй, не уступает понятию натурального числа. Изучение алгоритма породило множество различных научных направлений и постановок проблем, которые отражают различные аспекты этого понятия. К ним относятся, например,изучение алгебр рекурсивных функций [ю, 19,20], изучение различных понятий определимости во множествах натуральных чисел [1,2,12,14,16,17], тесно связанное с ним изучение сводимостей и степеней неразрешимости [1,2, 10,12,14,16,17], изучение абстрактной вычислимости на алгеб-раичесских системах [3,4,8,13,14,18], изучение возможностей получения алгоритма решения задачи по ее описанию [4,5], построения различных семантик алгоритмических процессов и многие другие. При этом понятие алгоритма связывается с другими понятиями и областями математики. Так при изучении различных аспектов этого понятия используются алгебраические, топологические, теоретико-модельные и другие методы и результаты [8,12,14(т.З)]. В сбою очередь понятие алгоритма дает новое осмысление известным ранее математическим понятиям. В качестве примера можно было бы привести изучение вопросов эффективности в вещественных числах и попытки

переизложить весь математический анализ, с использованием понятия алгоритма [6,9]. В каждой из этих областей уже достигнут значительный прогресс и перечисление даже основных работ по любой из этих тематик было бы делом весьма затруднительным. В монографии [151 дан подробный обзор научных направлений, связанных с понятием алгоритма.

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

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

С понятием конструктивной модели с связанными с ними

понятиями можно познакомиться по [7].

Автоморфизм ф рекурсивной модели К называется рекурсивным автоморфизмом модели 3)1, если он является частично-рекурсивной функцией на основном множестве модели 931; автоморфизм ф конструктивной модели (ТО,и) называется рекурсивным автоморфизмом этой конструктивной модели, если существует такая частично-рекурсивная функция /, что tyv=vf. Все такие автоморфизмы рекурсивной модели !Ю образуют группу, которую мы будем обозначать АМШ. Для конструктивной модели мы будем обозначать такую группу через

Перейдем к обзору содержания диссертации. Диссертация состоит из введения и четырех глав. Объем диссертации, - 208 страниц, библиография состоит из 92 наименований.

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

1) Получена точная оценка алгоритмической сложности теорий классов групп рекурсивных перестановок, груш рекурсивных автоморфизмов, рекурсивных груш в арифметической и аналитической иерархии. Доказано различие этих классов и различие их теорий.

2) Изучены вопросы определимости и относительной конструк-тивизируемости для груш перестановок, рекурсивных с оракулом.

3) Получены характеризации группы всех рекурсивных перестановок, класса всех груш рекурсивных автоморфизмов, класса вычислимых групп рекурсивных автоморфизмов.

4) Изучено соответствие между грушами рекурсивных автоморфизмов булевых алгебр и самими алгебрами.

Все основные результаты диссертации опубликованы в

[24-433.

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

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

Во втором параграфе первой главы изучены вопросы алгоритмической сложности конструктивизаций для групп рекурсивных автоморфизмов, а именно, получено полное описание степеней конструктивизируемости для таких групп и неулучшае-мая оценка сложности орбит в арифметической иерархии при действии такими группами.

В третьем параграфе построена счетно-категоричная разрешимая модель, не имеющая нетривиальных рекурсивных автоморфизмов. Как хорошо известно [11], счетно-категоричные модели имеют континуум автоморфизмов. Результаты этого параграфа дают пример отличия свойств рекурсивных автоморфизмов от свойств обычных автоморфизмов.

В четвертом параграфе решаются два естественных вопроса о конечнопорожденных группах рекурсивных автоморфизмов. В следующей теореме получено полное описание конечно-порожденных групп всех рекурсивных автоморфизмов:

1.4.1. ТЕОРЕМА. Произвольная конечно-порожденная группа изоморфна группе всех рекурсивных автоморфизмов некоторой рекурсивной модели в том и только в том случае, когда она

б

конструтивизируема.

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

1.4.2 ТЕОРЕМА. Существует 4-порожденная группа с коперечислимой проблемой равенства, которая не вкладывается в группу всех рекурсивных перестановок ЛиХы.

Вторая глава диссертации посвящена элементарным теориям и характеризациям некоторых классов групп рекурсивных перестановок.

В первом параграфе доказана конечная аксиоматизируемость и категоричность группы всех рекурсивных перестановок в классе всех групп рекурсивных перестановок.

2.1.1 ТЕОРЕМА Существует предложение <р языка теории, групп первого порядка такое, что для всякой группы в $ Ли^ы в N ф выполнено тогда и только тогда, когда б г Ли^ш.

Обозначим через Ко класс всех конструктивизируемых групп, через Кг - класс всех групп рекурсивных автоморфизмов и через ш) - класс всех групп рекурсивных

перестановок. Нетрудно видеть, что

£о Ш Сг § БЦиг^))

Во втором параграфе доказано различие теорий классов групп рекурсивных перестановок, рекурсивных автоморфизмов и рекурсивных групп. Более точно, установлено, что

ТПСБШгы)) ё ЧЖг £ ТЛ£о, а также получена точная оценка их алгоритмической сложности

в арифметической и аналитической иерархиях. При этом установлено, что теории классов групп рекурсивных автоморфизмов и рекурсивных групп рекурсивно изоморфны арифметике, т.е. 0(ш), а теория класса групп всех рекурсивных перестановок является п|-полным множеством.

В третьем параграфе второй главы получена характери-зация группы всех рекурсивных перестановок в классе всех •групп:

2.3.1. ТЕОРЕМА. Существует предложение ф языка теории групп такое, что группа Ли^ш является единственной с точностью до изоморфизм моделью <р, содержащей всего лишь две нетривиальные нормальные подгруппы. Все остальные модели предложения <р содержат не менее трех различных собственных нормальных подгрупп. Иначе говоря, АШы есть единственная модель <р, имеющая наименьшее возможное число нормальных подгрупп.

Теперь, имея две характеризации группы всех рекурсивных перестановок, можно охарактеризовать и класс всех групп рекурсивных автоморфизмов. Это основной результат четвертого параграфа второй главы:

2.4.1.ТЕОРЕМА. Существует предложение (р(И) языка теории групп с добавленным одноместным предикатом Я такое, что множество подмножеств АиЬ ш, которое реализуются, как группа всех рекурсивных автоморфизмов, совпадает с

{ ХаАШы | ГА^и.Я) N фГЙ.) }. (здесь Я интерпретируется, как К)

В третьей глаЕе изучается связь между группами перестановок, рекурсивных относительно некоторых оракулов и самими

этими оракулами. Оказывается, такие группы строго определяют степень вышеупомянутых оракулов и кроме того, многие характеристики оракула можно восстановить даже по элементарной теории такой группы. Фактически во многих случаях можно восстановить по элементарной теории такой группы степень оракула, а саму группу удается охарактеризовать всаго лишь одним предложением в классе всех групп перестановок, рекурсивных с некоторым оракулом.

Кроме этого в третьей главе получены некоторые утверждения о неявно определимых классах множеств.

Метода этой главы позволяют получить точную оценку степени конструктивизируемости группы Auíru.

Четвертая глава посвящена изучению групп рекурсивных автоморфизмов рекурсивных булевых алгебр.

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

Основным результатом второго параграфа является следующая

4.2.1.ТЕОРЕМА. Пусть ® - атомная разрешимы булева алгебра, а 93 - произвольная рекурсивная булева алгебра. Тогда если Aut 93 =Aut 93 , то 93 = 93 .

ГО г t Orí

Заметим, что рекурсивный изоморфизм булевых алгебр следует из обычного изоморфизма груш рекурсивных автоморфизмов. Этот результат будет в дальнейшем усилен.

Третий параграф посвящен восстановлению рекурсивной Нулевой алгебры по действию ее группы рекурсивных автомор-

физмов.

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

4.4Л.ТЕОРЕМА. Пусть К - класс всех групп, изоморфных подгруппам группы всех рекурсивных перестановок натурального ряда. Для любой атомной рекурсиивной булевой алгебры В с рекурсивным тожеством атомов существует предложение <р языка теории групп первого порядка такое, что для всякой группы с ( /С условие в И ср выполняется в том и только в том случае когда й изоморфна группе всех рекурсивных автоморфизмов сигебри 93.

Это в свою очередь позволяет существенно усилить теорему 4.2.1:

4.4.10.СЛЕДСТВИЕ. Пустъ 93о - рекурсивная атомная булева алгебра с рекурсивным множеством атомов, а - произвольная рекурсивная булева алгебра.

Если АМЪ^АМ^, то 93о и рекурсивно изоморфны.

4.4.11. СЛЕДСТВИЕ. Элементарная теория класса всех групп рекурсивных автоморфизмов рекурсивных булевых алгебр, а также элементарная группы рекурсивных автоморфизмов любой рекурсивной бесконечной разрешимой атомной булевой алгебры рекурсивно изоморфны 0(ь1) (арифметике).

Результаты диссертации докладывались на 6,7,8' и 9

ю

Всесоюзных конференциях по математической логике (Тбилиси-1982, Новосибирск-1984, Москва-1986, Ленинград-1988), ряде всесоюзных школ по теории алгоритмов, 8 Международном конгрессе по логике.методологии и философии науки (Москва, 1988), Первой международной конференции по упорядоченной алгебре (Франция,Марсель,1984), Международных конференциях "Логический коллоквиум-88" (Италия,Падуя), "Клини-90" (Болгария, Варна), "Логический коллоквиум-90" (Финляндия, Хельсинки), Международной конференции по упорядоченной алгебре и бесконечным группам перестановок (Франция,Марсель,1990), а также на семинарах "Алгебра и логика", "Теория нумераций", "Конструктивные модели" в Новосибирском государственном университете и Институте математики СО АН СССР, научно-исследовательском семинаре по математической логике в Московском государственном университете.

Автор благодарит профессора С.С.Гончарова за многочисленные полезные обсуждения.

Литература:

1. Арсланов М.М. Рекурсивно перечислите множества и степени неразрешимости. -Казань.: Изд-во Казанского ун-та, 1986.

2. Арсланов М.М. Локальная теория степеней неразрешимости. -Казань.: Изд-во Казанского ун-та, 1987.

3. Гончаров С.С. О проблеме числа неэквивалентных конструк-тивизаций. //Алгебра и логика -1980. -T.I9,)G6. -C.G2I-639.

4. Гончаров С.С. Свириденко Д.И. Логическое программирование в широком смысле. //В кн: Теория алгоритмов и ее прило-

жения. (Вычислительные системы 129). -1989. Новосибирск. -С.3-48.

5. Гончаров С.С. Свириденко Д.И. Математические основы семантического программирования.//ДАН СССР. -1986. -Т.289,№6. -С.1324-1328.

6. Гудстейн Р.Л. Рекурсивный математический анализ. -М.: Наука, 1970.

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

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

9. Кушнер Б.А. Лекции по конструктивному математическому анализу. -М.: Наука, 1973.

10. Мальцев А.И. Алгоритмы и рекурсивные функции. -М.: Наука,

1986.

11. Плоткин Б.И. Группы автоморфизмов алгебраических систем. -М.: Наука, 1966.

12. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. -М.: Мир,1972.

13. Соловьев В.Д. Автоморфизмы структуры вычислительных теорий. //В кн:. 9 Всесоюзная конференция по математической логике. Тезисы. Ленинград.-1988. -С.153.

14. Справочная книге по математической логике, (в 4-х томах) -М.: Наука, 1982.

15. Успенский В.А., Семенов А.Л., Теория алгоритмов: основные открытия и приложения. М.: Наука. 1987.

16. Шенфилд Дж. Математическая логика. -М.: Наука,1975.

17. Шенфилд Дж. Степени неразрешимости. -М.: Наука. 1977.

I

J8. Barwise. J. Admissible sets and structures. -Berlin.

Gottingen. Heidelberg. Springer-Verlag, 1975.

19. Robinson R.M. Primitive recursive functions. //Bull. Arner. Math. Soc. -1947- -V.53. -P.925-942.

20. Robinson J. General recursive functions. //Proc. Amer. Math. Soo. -1950. -V.1. -Р. 703-718.

21. Mostowsky A. A formula with no recursively enumerable model. //Fund. Math. -1955. -V.42.J61. -P.125-140.

22. Vaught R.L. Sentences true in all constructive models. //Summ, talks Summ Inst. Symb. Log..Cornell Univ., -1957, -V.1. -P.51-55.

23- Remmel J.B. Recursively rigid boolean algebras.//Ann. Pure and Appl. bogie.-1987.-V.36,-P.39-52.

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

24- Морозов A.C. Группы рекурсивных автоморфизмов конструктивных булевых алгебр. //В кн:. 6 Всес.конф. по мат. логике. Тезисы. -Тбилиси. -1982. -С.119.

25. Морозов A.C. Группы рекурсивных автоморфизмов конструктивных булевых алгебр. //Алгебра и логика.-1983. -T.22.J6 2. -С.138-158.

26. Морозов A.C. Конструктивные булевы алгебры с почти тождественными автоморфизмами.//В кн. Всесоюзн алгебраическая конференция. Тезисы, ч.2, Минск,-1983, -C.I63.

27.Морозов A.C. О существенно неконструктивизируемых группах. //В кн:. 7-я всесоюзн. конф. по мат. логике. Тезисы. -Новосибирск. -1984. -С.113.

28. Морозов А.С.Группа Aut <iD.O не конструктивизируема. Матом. заметки, -1984. -T.36,J£4. -С.437-452.

29. Морозов A.C. Автоморфизмы конструктивизаций булевых алгебр. //Сиб. мат. журнал.-1985.-Т.26,№ 4.-С.98-110.

30. Морозов A.C. О конструктивных булевых алгебрах с почти тождественными автоморфизмами. //Мат. заметки. -1985. -Т.37, № 4,-С.478-482.

31. Морозов A.C. Теории групп рекурсивных перестановок. // В кн.: 8 Всесоюзн. конф. по матем. логике (тезисы).-М,-1986. -С.124.

32. Морозов A.C. О вычислимых грушах автоморфизмов моделей. // Алгебра и логика.-1986.-Т.25.-М.-С.415-424.

33. Морозов A.C. Элементарные свойства груш рекурсивных, перестановок. //В кн:. XIX Всес. алгебраическая конференция. -Львов. -1987. -ч.И. -С.191.

34. Морозов A.C. Перестановки натурального ряда и неявная определимость. // Алгебра и логика.-1988.-Т.27,Jil.-С. 19-36.

35. Морозов A.C. Одна характеризация класса всех груш рекурсивных автоморфизмов. // В кн.:9 Всесоюзн.конф. по матем. логике. -Ленинград.-1988.-С.106.

36. Морозов A.C. Элементарные свойства груш рекурсивных перестановок. //ДАН СССР. -1989. -T.305..J62. -С.274-276.

37. Морозов A.C. Счетно категоричная разрешимая модель без нетривиальных рекурсивных автоморфизмов.//Сиб. матем. ж. -1989. -T.XXX.Jfc2. -С.221-224.

38. Морозов A.C. О теориях классов груш рекурсивных перестановок. //Математическая логика и алгоритмические проблемы. -Труда института математики СО АН СССР. -1989. -Т.12. -С.91-104.

«

39. Морозов A.C. Об одном вопросе Хигмэна. //Алгебра и

логика. -1990. -Т.29.Ш. -С.29-34.

40. Морозов А.С. О рекурсивных автоморфизмах атомных булевых алгеор. // Алгебра и логика. -1990. -Т.29,

41. Morozov A.S. Permutations of natural numbers and implicit definability. //In:. VIII Int. Congress of logic, philos. and methodol. of sci. Moscow, -1987. -V.5. part 1. -P. 115.

42. Morozov A.S. On the theories of classes of recursive permutation groups. //In:. Logic Colloquiuui'88. Abstracts. -Padova, Italy, -1988. -P. 105.

43. Morozov A.S. On finite generated recursive permutation groups. //Международная конф. по алгебре. Тезисы докл. по теории моделей и алгебраических систем. -Новосибирск. -1989.

-С.80.

Подписано к печати 5.it.90

Формат бумаги 60x34 I/I6 Объем I п.л., 0,75 уч.изд.л.

Отпечатано на ротапринте Института математики СС АН СССР 630090, Новосибирск-90, Университетский проспект, 4

Заказ rw

Тирачс 100 экз.