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

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

УДК 510.5

Рекурсивные и частичные автоморфизмы булевых алгебр

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

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

ЕКАТЕРИНБУРГ —

1997

Работа выполнена на кафедре алгебры и магемагаческой логики Казанского государственного университета.

Научные руководители: доктор физико-математических

наук, профессор М.М. Арсланов,

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

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

наук, профессор Ю.М.Важенин,

кандидат физико-математических наук, доцент С.П. Одинцов.

Ведущая организация: Новосибирский государственный

педагогический университет

Защита состоится "15" Кси* 1997 года в Ш часов на заседании диссертационного совета К 002.07.02 в Институте математики и механики УрО РАН по адресу:

620219, г. Екатеринбург, ул. Софьи Ковалевской, 16.

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

Автореферат разослан " (3 " си^сл^ 1997 года.

Ученый секретарь диссертационного совета . ,

д.ф.-м.н., профессор уСт/ААЛ/ A.C. Кондратьев

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

Актуальность темы. Реферируемая работа посвящена исследованию рекурсивных и частично рекурсивных автоморфизмов булевых алгебр. Проблема восстановления информации о данной структуре с помощью ее группы автоморфизмов является общим вопросом классической математики. Результаты, полученные в этой области, показывают, что группа автоморфизмов конкретной математической структуры во многом определяет ситуацию в самой структуре. Многие важные свойства алгебраических систем находят свое отражение в их группах автоморфизмов. Например, Р. Маккензи [16] показал, что если в счетной булевой алгебре ЗЗЬ, содержащей хотя бы два атома, существует максимальный атомный элемент и для счетной булевой алгебры ЗЗх выполнено Аи1;95Ь = АиЩ, то 9ЭЬ - М. Рубин, исследуя проблему с другой стороны, показал [19], что из элементарной эквивалентности групп автоморфизмов булевых алгебр следует элементарная эквивалентность самих булевых алгебр. Для каждой полной теории булевых алгебр Т он построил такое предложение <рг в языке теории групп, что для любой счетной или конечной булевой алгебры 93, количество атомов которой отлично от единицы, справедлива эквивалентность:

%\= Т А.м№\= (рг.

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

Рекурсивные перестановки в настоящее время очень интенсивно изучаются. Работы в этом направлении показывают, что свойства рекурсивных симметрий часто напоминают свойства обычных симметрии, однако &ти симметрии обладают рядом специфических свойств. Так, модель может иметь континуум автоморфизмов, но не иметь ни одного нетривиального рекурсивного или гиперарифметического автоморфизма» Два элемента модели могут быть изоморфными, но не рекурсивно изоморфными ни в одной консгруктивизации втой модели. (См. [5, 6, 7, 13].) A.C. Морозовым [8, 9] было показано, что если в рекурсивной булевой алгебре 9ВЬ множества атомов, атомных и безатомных элементов рекурсивны и для рекурсивной булевой алгебры выполнено ÄutJBo й Autто 93о -г Д- Реммел [17] и, независимо, для атомных булевых алгебр, A.C. Морозов [10] доказали, что для каждой рекурсивной булевой алгебры 53 существует такая булева алгебра 9?, изоморфная 58, что каждый рекурсивный автоморфизм булевой алгебры передвигает только конечное число атомов. Отсюда, в частности, следует, что нельзя полностью снять ограничения в предыдущем результате A.C. Морозова. Кроме того, иногда обычный изоморфизм булевых алгебр не может быть восстановлен из их груш рекурсивных автоморфизмов. В работе [8] были построены две сильно конструктивные булевы алгебры, которые не изоморфны, но имеют изоморфные группы рекурсивных автоморфизмов.

.... Исследуя элементарную теорию группы рекурсивных автоморфизмов атомной разрешимой булевой алгебры, A.C. Морозов получил следующий результат, который можно сравнить с результатом М. Рубина [19], и из которого следует, что атомная разрешимая булева алгебра может быть полностью восстановлена из

ее группы рекурсивных автоморфизмов с помощью одного предложения. Он построил [12] для любой атомной разрешимой булевой алгебры Ш такое предложение (р языка теории групп, что для любой группы рекурсивных перестановок натуральных чисел справедлива эквивалентность:

G\=(p Autr93.

Как бы ни было важно понятие полного преобразования, по мере развития математических теорий выявилась необходимость рассмотрения частичного преобразования. Полугруппы частично рекурсивных частичных автоморфизмов являются естественными объектами, связанными с понятием алгоритма. Рекурсивные автоморфизмы в этом случае оказываются частным случаем частично рекурсивных автоморфизмов. Частичные преобразования изучались в работах [3, 14]. В работах [1, 2, 4] исследуются полугруппы полных преобразований: изотонных, направленных и др. При этом часто граф, а значит и упорядоченное множество, определяется своей полугруппой преобразований с точностью до двойственности. Результаты работ Ю.М. Важенина показывают, что полугруппы частичных преобразований более полно характеризуют граф как в смысле элементарной эквивалентности, так и в смысле изоморфизма, нежели полугруппы полных преобразований. Работа [1] Ю.М. Важенина является, пожалуй, первой работой, где изучаются элементарные свойства полугрупп преобразований, делается попытка восстановления модели из ее полугруппы преобразований с точностью до элементарной эквивалентности.

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

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

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

Методика исследовании. Все результаты диссертации получены с помощью единого метода, развивающего идеи Р. Маккензи [15, 16], М. Рубина [18, 19] и A.C. Морозова [8, 9, 11, -12]." Суть его заключается в том, что в группе рекурсивных автоморфизмов булевой алгебры интерпретируется ее действие на атомах и безатомных элементах этой алгебры, а в полугруппе частичных автоморфизмов произвольной модели интерпретируется ее действие на основном множестве этой модели. Вторая часть метода состоит в том, что конечным числом аксиом выделяется некоторый класс групп, в которых можно формульно интерпретировать их действие на некотором множестве, в частности на атомах и безатомных элементах булевой алгебры, а также можно интерпретировать в этом множестве арифметику, что дает возможность определять в группе аналог вычислимости.

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

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

ических структур. Полученные результаты в некоторой степени восполняют пробел в исследовании рекурсивных булевых алгебр и их групп рекурсивных автоморфизмов и могут быть ИСПОЛЬЗОВЭг ны при чтении спецкурсов для студентов и аспирантов в университетах.

Апробация работы. Результаты диссертации докладывались на семинарах "Рекурсивные функции" в Казанском государственном университете и "Конструктивные модели" в Новосибирском государственном университете, международной конференции "Алгебра и анализ", посвященной 100-летию со дня рождения Н.Г. Чеботарева (Казань, 1994), международной конференции по математической логике памяти А.И. Мальцева (Новосибирск, 1994), логическом колловвиуме-96 (Сан Себастьян, 1996).

Публикации. Результаты диссертации опубликованы в работах автора [20,21, 22, 23, 24].

Структура и объем работы. Диссертация состоит из введения, двух глав и списка литературы. Общий объем диссертации 96 страниц, список литературы содержит 55 наименований.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Отображение ' f : А-+ А С , называется частичным автоморфизмом модели ЯЛ, если для любого предиката Р языка модели для любого кортежа £ € dorn(f) справедлива эквивалентность:

Ш\=Щ ЯЯ}=Я(/(Д!))

Частичный автоморфизм / называется конечным частичным автоморфизмом, если его область определения dorn/ является конечным множеством, и частично рекурсивным частичным авто-

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

Обозначим множество всех конечных частичных автоморфизмов модели Ш. через 1/{Щ, а множество всех частично рекурсивных частичных автоморфизмов - через

В первой главе исследуются полугруппы частичных автоморфизмов счетных моделей. Решая проблему восстановления модели из ее полугруппы частичных автоморфизмов, мы получили следующий результат: если ШЬ и произвольные модели конечных языков и 10УЬ) £ то модели и Щ интерпретируемы

Друг в друге с помощью бескванторных формул. Точнее, верна следующая теорема.

Теорема 1. Пуст» ЭДГ = = (|Ш&|;

^В^} модели произвольной конечной сигнатуры. Тогда еле-дующие условия эквивалентны:

1. 10Ь) - 10к).

■ 2. Существует биещия А : —> такая, что для любого Р^ существует бескванторная формула (рд языка модели ¡¡Щ, что для любого кортежа X £ [ШЬ^' справедливо

И, наоборот, для любого И? существует бескванторная формула языка модели ШЪ, что для любого кортежа X 6 |Щ|е' справедливо

ш и в?® т и

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

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

Теорема 2. Пусть (91), <} и <) частичные порядки и 10Ь) ^ 10Ъ), тогда % и изоморфны илиантиизоморфны.

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

Теорема 3. Пусть ®Ь « ®1 счетные булевы алгебры и //(%) — 1/(®0, тогда .

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

Теорема 4. Пуст» и $1 рекурсивные булевы алгебры, и Тогда

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

Теорема 5. Пусть 29Ь и ®1 рекурсивные булевы алгебры, и в алгебре % существует безатомный элемент. Тогда если /г(95Ь) — 1Щ), то

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

Вторая глава полностью посвящена решению проблемы харак-теризации группы рекурсивных автоморфизмов безатомной рекурсивной булевой алгебры одним предложением языка теории груш в классе всех групп рекурсивных перестановок. Эта проблема была поднята A.C. Морозовым после доказательства им аналогичного утверждения об атомных разрешимых булевых алгебрах. Используя результаты М. Рубина [18] и A.C. Морозова [11], мы интерпретируем арифметику в группе AutrS, доказывая тем самым, что теория группы Autr53 имеет тьюрингову сложность .

Теорема 6. Пустv 95 - рекурсивная безатомная булева алгебра. Тогда теория Th(Autr23) рекурсивно изоморфна множеству истинных высказываний элементарной арифметики.

Затем, используя построенную арифметику, мы доказываем теорему, в которой строится предложение групповой сигнатуры, характеризующее группу Auf,г® в классе всех групп рекурсивных перестановок натурального ряда, с точностью до изоморфизма.

Теорема Т. Для любой безатомной рекурсивной булевой алгебры 55 существует такое предложение Щ языка теории групп, что для любой подгруппы G группы рекурсивных перестановок натурального ряда G\=(ßQ тогда и только тогда, когда G— Autr95.

Л итер ату р а

[1] Важенин Ю. М. Элементарные свойства полугрупп преобразований упорядоченных множеств // Алгебра и логика. - 1970.

- Т. 9, №3.-С. 281-301.

[2] Важенин Ю. М. Об элементарной определяемости и элементарной характеризуемости классов рефлексивных графов // Известия ВУЗов. Математика. - 1972. - № 7. - С. 3 - 11.

[3] Важенин Ю. М. Элементарные свойства полугрупп частичных преобразований рефлексивных графов // "Исслед. по соврем, алгебре". Мат. записки. Свердловск, УрГУ. - 1977. - Т. 10, №3.

- С. 3 - 19.

[4] Глускин JI. М. Полугруппы изотопных преобразований // Успехи мат. наук. - 1961. - Т. 16; №5. - С. 157 - 162.

[5] Гончаров С. С., Дзгоев В. Д. Автоустойчивость моделей // Алгебра и логика. -1980. - Т. 19, № 1. - С. 45 - 58.

[6] Дзгоев В. Д. Рекурсивные автоморфизмы конструктивных алгебраических систем // 15-я Всесоюз. алгебраическая конф., Новосибирск, ч. 2.: Тез. докл. - Новосибирск, 1977. - С. 93.

[7] Кудайбергенов К. Ж. Об эффективно однородных моделях // Сиб. мат. жура - 1986. - Т. 27, № 1. - С. 180- 182.

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

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

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

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

[12] Морозов А. С. О рекурсивных автоморфизмах атомных булевых алгебр // Алгебра и логика. - 1990. - Т. 29, №4. - С. 464 -490.

[13] Морозов А. С. Функциональные деревья и автоморфизмы моделей // Алгебра и логика. - 1993. - Т. 32, № 1. - С. 19 - 39.

[14] Попова JI. М. Полугруппы частичных эндоморфизмов множеств с отношением // Сиб. мат. журн. -1963. - Т. 4, К® 2. -С. 309 - 317.

[15] McKenzie R. On elementary types of symmetric groups // Algebra Universalis -1971. - V. 1, № 1. - P. 13 - 20.

[16] McKenzie R. Automorphism group of denumerable Boolean algebras 11 Canad. J. Math. - 1977. - V. 29, № 3. - P. 466 - 471.

[17] Remmel J. B. Recursively rigid Boolean algebras // Ann. Pure and Applied Logic. - 1987. - V. 36, № 1. - P. 39 - 52.

[18] Rubin M. On the Automorphism groups of homogenous and saturated Boolean algebras // Algebra Universalis - 1979. - V. 9, № 1. - P. 54 -86.

[19] Rubin M. On the Automorphism groups of countable Boolean algebras jI Israel J. Math. - 1980. - V. 35, №1-2. - P. 151 -170.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[20] Липачева Е. В. Об автоморфизмах безатомных счетных булевых алгебр // Междун. конф. по мат. логике, Новосибирск: Тез. докл. - Новосибирск, 1994. - С. 62 - 63.

[21] Липачева Е. В. Частичные автоморфизмы счетных моделей Ц Известия ВУЗов. Математика. - 1997. - № 1. - С. 12 - 21.

[22] Липачева Е. В. Группы рекурсивных автоморфизмов и полугруппы частичных автоморфизмов булевых алгебр. - Казань, 1996. - 37 с. - (Препринт / Каз. гос. у нив. НИИ матем. и механ. им. Н. Г. Чеботарева; №96-1).

[23] LipachevaE. V. On the recursive automorphism group of the atomless recursive Boolean algebra // Abstracts of the Intern. Conf. "Algebra and Analysis" in honour of N. G. Chebotarev, Kazan, part 1. - Kazan, 1994.-P. 135.

[24] Lipacheva E. V. On partial automorphism semigroups of recursive models // Abstracts of the European Summer Meeting "Logic colloquium'96" of the Association for Symbolic logic, San Sebastian, Spain. - San Sebastian, 1996. - P. 126.