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

Морозов, Андрей Сергеевич АВТОР
доктора физико-математических наук УЧЕНАЯ СТЕПЕНЬ
Новосибирск МЕСТО ЗАЩИТЫ
1995 ГОД ЗАЩИТЫ
   
01.01.06 КОД ВАК РФ
Автореферат по математике на тему «Группы вычислимых автоморфизмов»
 
Автореферат диссертации на тему "Группы вычислимых автоморфизмов"

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

На правах рукописи Морозов Андрей Сергеевич

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

I ,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Е.А.Палютин

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

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

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

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

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

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

Автоморфизм ф рекурсивной модели ЗЛ называется рекурсивным автоморфизмом модели Ш, если он является частично-рекурсивной функцией на основном множестве модели И; автоморфизм ф конструктивной модели (Ж!,у> называется рекурсивным автоморфизмом этой конструктивной модели, если существует такая частично-рекурсивная функция f, что фу=у/. Все такие автоморфизмы рекурсивной модели К образуют группу, которую мы будем обозначать АШШ. Для конструктивной модели мы будем обозначать такую группу через 5И,г>).

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

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

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

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

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

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

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

[24-43].

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

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

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

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

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

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

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

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

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

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

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

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

Обозначим через С0 класс всех конструктивизируемых груш, через К^ - класс всех груш рекурсивных автоморфизмов и через £>(4и4гш) - класс всех груш рекурсивных перестановок. Нетрудно видеть, что

К0 £ Кр £ З(АШи))

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

Тк(3(АиХи)) ё 17гКг £ Ш!о, а также получена точная оценка их алгоритмической сложности

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

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

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

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

2.4 Л .ТЕОРЕМА. Существует предложение ц>{Е) языка теории групп с добавленным одноместным предикстом й такое, что множество подмножеств АМ ы, которое реализуются, как группа всех рекурсивных автоморфизмов, совпадает с

{ ХяАШы | £ срШ }.

(здесь Д интерпретируется, как К)

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

а

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

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

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

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

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

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

4.2.1 .ТЕОРЕМА. Пустъ 93о - атомная разрешимая булева алгебра, a - произвольная рекурсивная булева алгебра. Тогда если Aut © =Aut Ъ , то Ф s 5В .

г О г 1 ' О г i

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

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

физмов.

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

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

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

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

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

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

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

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

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

Литература:

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

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

3. Гончаров С.С. 0 проблеме числа неэквивалентных конструк-тивизаций. //Алгебра и логика -1980. -T.I9.Ji6. -С.621-639.

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

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

5. Гончаров С.С. Свириденко Д.И. Математические основы семантического программирования.//ДАН СССР. -1986. -T.289,Jé6. -C.I324-I328.

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

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

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

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

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

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

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

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

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

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

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

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

I

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

Gottingen. Heidelberg. Springer-Verlag, 197519. Robinson R.M. Primitive recursive functions. //Bull. Amer. Math. Soc. -1947- -V.53. -P.925-942. 20. Robinson J. General recursive functions. //Proc. Araer. Math. Soc. -1950. -7.1. -P. 703-718.

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

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

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

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

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

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

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

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

28.- .Морозов А.С.Группа 4uir«D»0 не конструктивизируема. Ма-тем. заметки, -1984. -Т.36,№4. -С.437-452.

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

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

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

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

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

34. Морозов A.C. Перестановки натурального ряда и неявная определимость. // Алгебра и логика.-1988.-Т.27,№1 .-С.19-36. Зг>. Морозов A.C. Одна характеризация класса всех груш рекурсивных автоморфизмов. // В кн.:9 Всесоюзн.конф. по матем. логике. -Ленинград.-1988.-С.106.

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

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

за. Морозов 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 Colloquium'88. Abstracts. -Padova, Italy, -1988. -P. 105.

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

-С.80. .

¿1.

Подписано к печати 5.11.9С

Формат бумаги 60x34 1/16 Объем I п.л., 0,75 уч.изд.л. Заказ яч9 Тира^ 100 экз.

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