Введение к работе
Актуальность темы. Реферируемая работа посвящена исследованию рекурсивных и частично рекурсивных автоморфизмов булевых алгебр. Проблема восстановления информации о данной структуре с помощью ее группы автоморфизмов является общим вопросом классической математики. Результаты, полученные в этой области, показывают, что группа автоморфизмов конкретной математической структуры во многом определяет ситуацию в самой структуре. Многие важные свойства алгебраических систем находят свое отражение в их группах автоморфизмов. Например, Р. Маккензи [16] показал, что если в счетной булевой алгебре 9Sb, содержащей хотя бы два атома, существует максимальный атомный элемент и для счетной булевой алгебры 2 выполнено Aut% = Aut%, то 9ЭЬ - %.. М. Рубин, исследуя проблему с другой стороны, показал [19], что из элементарной эквивалентности групп автоморфизмов булевых алгебр следует элементарная эквивалентность самих булевых алгебр. Для каждой полной теории булевых алгебр Т он построил такое предложение <рг в языке теории групп, что для любой счетной или конечной булевой алгебры 33, количество атомов которой отлично от единицы, справедлива эквивалентность:
Современное развитие математики и электронно-вычислительной техники привело к тому, что понятие алгоритма стало одним из наиболее фундаментальных понятий в математике. Систематическое изучение алгоритмов привело к необходимости возникновения теории конструктивных моделей и, вместе с тем, к необходимости изучения рекурсивных автоморфизмов этих моделей.
Рекурсивные перестановки в настоящее время очень интенсивно изучаются. Работы в этом направлении показывают, что свойства рекурсивных симметрии часто напоминают свойства обычных симметрии, однако »ти симметрии обладают рядом специфических свойств. Так, модель может иметь континуум автоморфизмов, но не иметь ни одного нетривиального рекурсивного или гиперарифметического автоморфизма. Два элемента модели могут быть изоморфными, но не рекурсивно изоморфными ни в одной консгруктивизации етой модели. (См. [5, 6, 7, 13].) А.С. Морозовым [8, 9] было показано, что если в рекурсивной булевой алгебре % множества атомов, атомных и безатомных элементов рекурсивны и для рекурсивной булевой алгебры 3 выполнено AvtJBo Айг%, то 9 г %. Д. Реммел[17] и, независимо, для атомных булевых алгебр, А.С. Морозов [10] доказали, что для каждой рекурсивной булевой алгебры 23 существует такая булева алгебра 2?, изоморфная , что каждый рекурсивный автоморфизм булевой алгебры 2? передвигает только конечное число атомов. Отсюда, в частности, следует, что нельзя полностью снять ограничения в предыдущем результате А.С. Морозова. Кроме того, иногда обычный изоморфизм булевых алгебр не может быть восстановлен из их групп рекурсивных автоморфизмов. В работе [8] были построены две сильно конструктивные булевы алгебры, которые не изоморфны, но имеют изоморфные группы рекурсивных автоморфизмов.
..,, Исследуя элементарную теорию группы рекурсивных автоморфизмов атомной разрешимой булевой алгебры, А.С. Морозов получил следующий результат, который можно сравнить с результатом М. Рубина [19], и из которого следует, что атомная разрешимая булева алгебра может быть полностью восстановлена из
ее группы рекурсивных автоморфизмов с помощью одного предложения. Он построил [12] для любой атомной разрешимой булевой алгебры Ш такое предложение (р языка теории групп, что для любой группы рекурсивных перестановок натуральных чисел справедлива эквивалентность:
Как бы ни было важно понятие полного преобразования, по мере развития математических теорий выявилась необходимость рассмотрения частичного преобразования. Полугруппы частично рекурсивных частичных автоморфизмов являются естественными объектами, связанными с понятием алгоритма. Рекурсивные автоморфизмы в этом случае оказываются частным случаем частично рекурсивных автоморфизмов. Частичные преобразования изучались в работах [3, 14]. В работах [1, 2, 4] исследуются полугруппы полных преобразований: изотонных, направленных и др. При этом часто граф, а значит и упорядоченное множество, определяется своей полугруппой преобразований с точностью до двойственности. Результаты работ Ю.М. Важенина показывают, что полугруппы частичных преобразований более полно характеризуют граф как в смысле элементарной эквивалентности, так и в смысле изоморфизма, нежели полугруппы полных преобразований. Работа [1] Ю.М. Важенина является, пожалуй, первой работой, где изучаются элементарные свойства полугрупп преобразований, делается попытка восстановления модели из ее полугруппы преобразований с точностью до элементарной эквивалентности.
Цель работы. В диссертации решается, поставленная А.С. Морозовым, проблема характеризации группы рекурсивных автоморфизмов безатомной рекурсивной булевой алгебры одним предло-
жением в классе всех подгрупп рекурсивных перестановок натурального ряда, исследуется тьюрингова сложность теории этой группы.
Кроме того, изучаются связи между рекурсивными моделями и их полугруппами конечных и частично рекурсивных частичных автоморфизмов. Делается попытка восстановления булевой алгебры из ее полугруппы частично рекурсивных частичных автоморфизмов.
Методика исследовании. Все результаты диссертации получены с помощью единого метода, развивающего идеи Р. Маккензи [15, 16], М. Рубина [18, 19] и A.G Морозова [8, 9, 11, -12]. Суть его заключается в том, что в группе рекурсивных автоморфизмов булевой алгебры интерпретируется ее действие на атомах и безатомных елементах этой алгебры, а в полугруппе частичных автоморфизмов произвольной модели интерпретируется ее действие на основном множестве этой модели. Вторая часть метода состоит в том, что конечным числом аксиом выделяется некоторый класс групп, в которых можно формульно интерпретировать их действие на некотором множестве, в частности на атомах и безатомных элементах булевой алгебры, а также можно интерпретировать в этом множестве арифметику, что дает возможность определять в группе аналог вычислимости.
Научная новизна. Все результаты диссертации являются новыми и обоснованы подробными доказательствами.
Теоретическая и практическая ценность. Работа носит теоретический характер. Ее результаты могут найти применение как в теории конструктивных моделей, так и в теории рекурсивных функций при изучении групп автоморфизмов различных алгебра-
ических структур. Полученные результаты в некоторой степени восполняют пробел в исследовании рекурсивных булевых алгебр и их групп рекурсивных автоморфизмов и могут быть использованы при чтении спецкурсов для студентов и аспирантов в университетах.
Апробация работы. Результаты диссертации докладывались на семинарах "Рекурсивные функции" в Казанском государственном университете и "Конструктивные модели" в Новосибирском государственном университете, международной конференции "Алгебра и анализ", посвященной 100-летию со дня рождения Н.Г. Чеботарева (Казань, 1994), международной конференции по математической логике памяти А.И. Мальцева (Новосибирск, 1994), логическом коллоквиуме-96 (Сан Себастьян, 1996).
Публикации. Результаты диссертации опубликованы в работах автора [20,21, 22, 23, 24].
Структура и объем работы. Диссертация состоит из введения, двух глав и списка литературы. Общий объем диссертации 96 страниц, список литературы содержит 55 наименований.