Абелевы Р-группы и автоустойчивость относительно оракула

Душенин, Дмитрий Игоревич

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

Душенин, Дмитрий Игоревич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Новосибирск МЕСТО ЗАЩИТЫ

2013 ГОД ЗАЩИТЫ

01.01.06 КОД ВАК РФ

Диссертация по математике на тему «Абелевы Р-группы и автоустойчивость относительно оракула»

Автореферат диссертации на тему "Абелевы Р-группы и автоустойчивость относительно оракула"

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

Душенин Дмитрий Игоревич

АБЕЛЕВЫ Р-ГРУППЫ И АВТОУСТОЙЧИВОСТЬ ОТНОСИТЕЛЬНО ОРАКУЛА

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

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

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

31 ОКТ 20(3

005536474

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук.

Научный руководитель:

доктор физико-математических наук, профессор, член-корреспондент РАН Гончаров Сергей Савостьянович

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

Хисамиев Назиф Гарифуллинович, доктор физико-математических наук, профессор, Восточно-Казахстанский государственный технический университет им. Д. Серикбаева, заведующий кафедрой

Мельников Александр Геннадьевич, кандидат физико-математических наук, Университет королевы Виктории, г. Веллингтон, Новая Зеландия, научный сотрудник

Ведущая организация: федеральное государственное автономное образовательное учреждение высшего профессионального образования «Казанский (Приволжский) федеральный университет»

Защита состоится «16» ноября 2013 г. в 15 часов 00 минут па заседании диссертационного совета Д 003.015.02 при Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук по адресу: 630090, Новосибирск, пр. Акад. Коптюга, 4.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института математики им. С. Л. Соболева Сибирского отделения Российской академии наук.

Автореферат разослан «11» октября 2013 г.

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

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

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

Тематика диссертации. Диссертация посвящена исследованию тьюринговых степеней автоустойчивости абелевых р-групп. Эта задача является одной из многих других, изучаемых в теории конструктивных моделей, которая, в свою очередь, берет начало с работ А.И. Мальцева [15], [16] и М. Рабина [37] середины прошлого века и с тех пор активно развивается, благодаря трудам множества математиков со всего мира. Этому разделу математической логики, а также тесно связанной с ним теории вычислимости, посвящено очень большое количество литературы. Так подробную информацию по основам теории вычислимости можно найти в [20], по основам классической теории моделей - в [12]. В качестве особенно важных и современных источников стоит выделить [6], [30] и [41].

Объектом исследования в диссертации являются конструктивизируемые аддитивные абелевы р-группы и тыоринговы степени их автоустойчивости. Известно, что аддитивная абелева группа представляется в виде прямой суммы редуцированной и полной подгрупп. Любая полная аддитивная абелева р-группа является прямой суммой конечного или бесконечного числа квазициклических групп (или групп типа р°°). Что касается редуцированных абелевых р-групп, то еще в 1933-м году Ульмом был получен известный результат о том, что редуцированные р-группы одинакового типа т, все соответствующие факторы которых изоморфны, сами являются изоморфными. Этот результат говорит о том, что любая редуцированная р-группа с точностью до изоморфизма определяется своими факторами. Эти и многие другие известные результаты теории групп можно найти в [13] или [21]. В частности, более подробную информацию по абелевым р-группам можно найти в [32]. Позднее для некоторых видов редуцированных р-групп были предложены иные, более удобные, подходы к доказательству теоремы Ульма. Например, в [39] вводятся понятия р-базисных деревьев, которые ассоциируются с абелевыми р-группами и делают интуитивное понимание их структуры куда более доступным.

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

то ее называют конструктивизируемой и говорят, что она имеет конструктивизацию. Модель называется сильно конструктивизируемой, если она имеет вычислимую изоморфную копию, для которой существует алгоритм, позволяющий по любой формуле исчисления предикатов и любому набору элементов определить, выполнена ли формула на этом наборе. В таком случае также говорят, что модель имеет сильную конструктивизацию. Понятие конструктивной алгебры впервые было предложено А.И. Мальцевым в [15]. Понятие же сильно конструктивной модели впервые было введено Ю.Л. Ершовым в [11].

Вопрос о конструктивизируемости и сильной конструктивизируемости заданной модели является одним из самых важных и интересных в теории конструктивных моделей. Так Ю.Л. Ершов в [10] доказал теорему о ядре, с помощью которой можно переносить конструктивизации алгебры на ее замыкания, Н.Г. Хисамиев в [22] получил результат о том, что любая счетная модель wi-категоричной теории сильно конструктивизируема, а С.С. Гончаровым в [1] и М.Г. Перетятькиным в [19] независимо найдены критерии сильной конструктивизируемости однородных моделей. Что касается классических классов алгебраических структур, то этому вопросу также посвящена целая серия работ. Например, А.И. Мальцевым в [16] были описаны конструктивизируемые абелевы группы без кручения ранга 1. Также М. Рабином в [37] была доказана сильная конструктивизируемость счетного алгебраически замкнутого поля, A.C. Морозовым в [17] получено, что счетные насыщенные булевы алгебры сильно конструктивизируемы, а Дж. Мидом в [36] установлено, что любая счетная простая булева алгебра сильно конструктивизируема.

В.П. Добрица в [8] и А.Т. Нуртазин в [18] также доказали, что конструктивизируемые абелевы группы обладают конструктивизацией с рекурсивно перечислимым базисом:

редуцированной абелевой р-группы для ее конструктивизируемости и сильной конструктивизируемости. Также в [9] доказано, что ульмов тип конструктивной р-группы является конструктивным ординалом. В [24] представлен критерий конструктивизируемости прямых сумм циклических абелевых р-групп, а в [25] и в [26] - аналогичные критерии для прямых сумм циклических и квазициклических абелевых р-групп. Также им доказано, что из конструктивизируемости абелевой группы не следует конструктивизируемость ее редуцированной или полной части. В [28] был впервые сформулирован известнейший критерий конструктивизируемости для редуцированных абелевых р-групп, обладающих элементами бесконечной высоты. Доказательство обобщения этого критерия па нередуцированные р-группы, а также аналогичный критерий сильной конструктивизируемости, можно найти в докторской диссертации Н.Г. Хисамиева. Там же доказан ряд полезных следствий из этих критериев. Также можно выделить критерии существования сильной конструктивизации для р-групп, основанные на определяющих соотношениях и системе порождающих элементов. Найти их можно также в [25]. Там же в качестве примера их применения доказано, что если полная часть сильно конструктивизируемой р-группы имеет конечный ранг, то ее редуцированная часть сильно конструктивизируема.

Что касается конструктивизируемости абелевых групп без кручения, то первым к этому вопросу подошел А.И. Мальцев. В [16] им предложена характеризация групп без кручения ранга 1. А.Г. Курош в [33] и А.И. Мальцев в [14] показали соответствие между классом неизоморфных групп без кручения конечного ранга и некоторым классом матриц с р-адическими числами, а В.П. Добрица в своей работе [7] установил, что группа без кручения конечного ранга обладает конструктивизацией в том и только в том случае, когда соответствующая ей матрица может быть эффективно задана. Далее, Н.Г. Хисамиев в [27] предложил критерий конструктивизируемости абелевых групп бех кручения в терминах образующих и определяющих соотношений, а А.Т. Нуртазин в [18] доказал, что класс всех групп без кручения не является вычислимым.

Говорят, что конструктивизируемая модель автоустойчива, если любые ее две вычислимые копии вычислимо изоморфны. Также автоустойчивые модели называют вычислимо категоричными. Понятие автоустойчивости впервые было введено А.И. Мальцевым в [15].

Им же в [16] впервые была построена неавтоустойчивая модель. В настоящее время получены критерии автоустойчивости для целого ряда известных классов структур. Так в [4] можно найти доказательство того, что булева алгебра автоустойчива тогда и только тогда, когда она имеет конечное число атомов. Работа [38] содержит в себе следующий результат: линейный порядок вычислимо представим в том и только в том случае, когда в нем имеется конечное число непосредственных следований. Следствиями результатов работы [2] являются признаки неавтоустойчивости некоторых видов векторных пространств и полей: бесконечномерные векторные пространства и алгебраически замкнутые поля бесконечного ранга трансцендентности неавтоустойчивы. В [18] доказывается, что абелева группа без кручения автоустойчива тогда и только тогда, когда ее ранг конечен. Отдельно необходимо упомянуть важнейший результат из [5] о том, что если произвольная конструктивизируемая модель ветвится, то класс ее конструктивизаций эффективно бесконечен. Следствием теоремы о ветвящихся моделях является критерий автоустойчивости для абелевых р-групп: абелева р-группа G автоустойчива тогда и только тогда, когда G {С{р°°))к © Gi © (г{р1))ж, где MeN и группа Сг конечна, либо G ~ Gi © С?2, где группа G\ - полная, а группа G2 - конечная. Также этот критерий был независимо доказан в [40]. В работе [3] можно найти еще один признак бесконечной алгоритмической размерности модели.

Если d — некоторая тьюрингова степень, то говорят, что конструктивная модель М - d-автоустойчива, если между ее любыми двумя вычислимыми копиями существует d-рекурсивный изоморфизм. Впервые это понятие было введено в работе [29]. Вопрос об автоустойчивости моделей относительно нерекурсивных степеней зачастую оказывается значительно сложнее, чем вопрос о классической автоустойчивости. Тем не менее, существует ряд частичных результатов по этой теме. Например, в [35] описаны Аз-категоричные линейные порядки и булевы алгебры. Также известно, что для любого п > 1 существуют Д°+1-автоустойчивые структуры, которые не являются Д®-автоустойчивыми. Примером могут служить деревья конечной высоты из работы [34]. Также в [31] содержится результат о том, что редуцированная абелева р-группа типа т < и> является автоустойчивой. При этом существует редуцированная абелева р-группа типа г, которая не является 0-2г_2'-авто устойчивой.

Несмотря на то, что вопрос о степенях автоустойчивости

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

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

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

1. Получена верхняя оценка относительно скачков рекурсивной степени для тьюринговых степеней автоустойчивости нередуцированных абелевых р-групп с максимальной редуцированной подгруппой конечного типа т (опубликовано в [44]).

2. Доказана точность этой оценки для различных видов нередуцированных абелевых р-групп с максимальной редуцированной подгруппой типа 1, 2 и 3 (опубликовано в [42], [43]).

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

Апробация работы. По результатам диссертации были сделаны: доклад на «Международной студенческой конференции 2007» (Новосибирск, Россия), доклад на конференции «Мальцевские чтения 2009» (Новосибирск, Россия), доклад на конференции «Вычислимость и модели-2009» (Усть-Каменогорск, Казахстан). Кроме того, результаты докладывались на совместных семинарах ИМ СО РАН и НГУ «Конструктивные модели» и «Алгебра и логика», а также на логическом семинаре Университета Нотр-Дам (Нотр-Дам, США).

Публикации. Основные результаты изложены в работах [42]- [44], опубликованных в журналах, входящих в перечень ВАК ведущих рецензируемых научных журналов и изданий. Публикация [45] является переводом на английский язык работы [42].

Структура и объем диссертации. Диссертация состоит из введения, четырёх глав и списка литературы (45 наименований). Теоремы и леммы пронумерованы независимо, сквозным образом. Объём диссертации — 105 страниц.

ОБЗОР СОДЕРЖАНИЯ ДИССЕРТАЦИИ

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

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

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

Теорема 1. Абелева р-группа типа т < и), имеющая полную подгруппу, является -автоустойчивой.

Эта теорема обобщает известный факт для редуцированных абелевых р-групп из [31]. Результаты главы опубликованы в [44].

Третья глава содержит серию примеров, подтверждающих точность оценки, представленной во второй главе, для различных видов нередуцированных абелевых р-групп с редуцированной частью типа 1. Она содержит следующие теоремы:

Теорема 2. Абелева р-группа G вида

оо

с = ф Z(PT е (Cip^r ¿=0

обладает двумя конструктивизациями /I и и, не 0'-автозквивалентными между собой.

Теорема 3. Существует абелева р-группа G вида

оо

G = ф ф (Z(p°°)r, где V» * < ш,

¿=о

обладающая двумя конструктивизациями /л и v, не 0'-автоэквивалентными между собой.

Теорема 4. Абелева р-группа G вида

оо

G = ф Z(p!f ф (С(р°°)У, где1<д<и,

г=О

обладает двумя коиструктивизациями ц и V, не 0'-автоэквивалентными между собой.

Теорема 5. Существует абелева р-группа С вида

оо

6 = 0 г{р*Уг © (ССр00))9, где1<д<и иЫ Зг<ш,

г=0

обладающая двумя коиструктивизациями ¡1 и и, не 0'-автоэквивалентными между собой.

Основные результаты главы опубликованы в [42] и [45].

Четвертая глава содержит примеры, подтверждающие точность оценки, представленной во второй главе, для различных видов нередуцированных абелевых р-групп с редуцированной частью типа 2 и 3. Она содержит следующие теоремы:

Теорема 6. Пусть абелева р-группа С7 представляется в виде С? = ф (С(р°°)), где (7Г - редуцированная р-группа типа

2 по улъмовской классификации с ульмовскими факторами (5° и С1, изоморфными группе ф. Тогда С не является 0'"-автоустойчивой.

Теорема 7. Пусть абелева р-группа С? представляется в виде С = © (С(р°°))ш, где - редуцированная р-группа типа

2 по улъмовской классификации с ульмовскими факторами (5° и изоморфньши группе ^{р1) . Тогда не является 0"'-

автоустойчивой.

Теорема 8. Пусть абелева р-группа С представляется в виде С? = <3Г © (С(р°°))ш, где С?г - редуцированная р-группа типа 3 по улъмовской классификации с ульмовскими факторами 0°, (51 и О , изоморфными группе %(р1) . Тогда (3 не является

автоустойчивой.

Основные результаты главы опубликованы в [43].

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

Литература

[1] Гончаров С. С. Сильная конструктивизируемость однородных моделей // Алгебра и логика. 1978. Т. 17. №4. С. 363-388.

[2] Гончаров С. С. Автоустойчивость моделей и абелевых групп // Алгебра и логика. 1980. Т. 19. №1. С. 23-44.

[3] Гончаров С. С. Предельно эквивалентные конструктивизации // Тр. Ин-та математики СО АН СССР. 1980. Т. 2. С. 4-12.

[4] Гончаров С. С. Счетные булевы алгебры и разрешимость. Новосибирск: Научная книга (НИИ МИОО НГУ). 1996.

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

[6] Гончаров С. С., Ершов Ю. Л. Конструктивные модели. Новосибирск: Научная книга. 1999.

[7] Добрица В. П. О конструктивизациях абелевых групп // Сибирск. матем. журн. 1981. Т. 22. №3. С. 208-213.

[8] Добрица В. П. Некоторые конструктивизации абелевых групп // Сибирск. матем. журн. 1983. Т. 24. №2. С. 18-25.

[9] Добрица В. П., Нуртазин А. Т., Хисамиев Н. Г. О конструктивных периодических абелевых группах // Сибирск. математ. журн. 1978. Т. 19. №6. С. 1260-1265.

[10] Ершов Ю. Л. Существование конструктивизаций // Докл. АН СССР. 1972. Т. 204. №5. С. 1041-1044.

[11] Ершов Ю. Л. Конструктивные модели // Избранные вопросы алгебры и логики. 1973. Новосибирск: Наука. С. 111-130.

[12] Кейслер Г., Чэн Ч. Ч. Теория моделей. М.: Мир. 1977.

[13] Курош А. Г. Теория групп. М.: Наука. 1967.

[14] Мальцев А. И. Абелевы группы конечного ранга без кручения // Матем. сб. 1938. Т. 4. №1. С. 45-67.

|15] Мальцев А. И. Конструктивные алгебры // УМН. 1961. Т. 16. №3. С. 3-60.

[16] Мальцев А. И. О рекурсивных абелевых группах // Докл. АН СССР. 1962. Т. 146. №5. С. 1009-1012.

[17] Морозов А. С. Сильная конструктивизируемость счетных насыщенных булевых алгебр // Алгебра и логика. 1982. Т. 21. №2. С. 193-203.

[18] Нуртазин А. Т. Вычислимые классы и алгебраический критерий автоустойчивости: дис. ... канд. физ.-мат. наук: 01.01.06. Институт математики и механики, Алма-Ата, 1974.

[19] Перетятъкин М. Г. Критерий сильной конструктивизируемости однородных моделей // Алгебра и логика. 1978. Т. 17. №4. С. 430454.

[20] Роджерс С. Теория рекурсивных функций и эффективная вычислимость. М.: Мир. 1972.

[21] Фукс Л. Бесконечные абелевы группы. М.: Мир. 1977.

[22] Хисамиев Н. Г. Сильно конструктивные модели разрешимой теории // Изв. АН Каз ССР. Сер. физ.-мат. 1974. №3. С. 83-84.

[23] Хисамиев Н. Г. О сильно конструктивных периодических абелевых группах // Изв. АН Каз ССР. Сер. физ.-мат. 1978. №1. С. 58-62.

[24] Хисамиев Н. Г. Критерий конструктивизируемости прямой суммы циклических р-групп // Изв. АН Каз ССР. Сер. физ.-мат. 1981. №1. С. 51-55.

[25] Хисамиев Н. Г. Сильно конструктивные абелевы р-группы // Алгебра и логика. 1983. Т. 22. №2. С. 198-217.

[26] Хисамиев Н. Г. О конструктивных абелевых р-группах // Тез. докл. 19 всесоюз. конф. по алгебре. Лювов. 1987. С. 299.

[27] Хисамиев Н. Г. Критерий конструктивизируемости абелевых групп без кручения // Тез. докл. 9 всесоюзн. конф. по мат. логике. Ленинград. 1988. С. 168.

[28] Хисамиев Н. Г. Конструктивные редуцированные абелевы р-группы // Тез. докл. международн. конф. по алгебре, посвящ. памяти А.И. Мальцева. Новосибирск. 1989. С. 141.

[29] Ash С. J. Stability of recursive structures in arithmetical degrees // Ann. Pure Appl. Logic. 1986. V. 32. №2. P. 113-135.

[30] Ash C. J., Knight J. F. Computable Structures and the Hyperarith-metical Hierarchy. Elsevier. 2000.

[31] Barker E. J. Back and forth relations for reduced Abelian p-Groups // Ann. Pure Appl. Logic. 1995. V. 75. №3. P. 223-249.

[32] Kaplansky, I. Infinite Abelian Groups. University of Michigan Press. 1954.

[33] Kurosh A. G. Primitive torsionfreie Abelsche Gruppen vom endlichen Range I j Ann. Math. 1937. V. 38. №1. P. 175-203.

[34] Lempp S, McCoy Ch., Miller R., Solomon R. Computable categoricity of trees of finite height // J. Symbolic Logic. 2005. V. 70. №1. P. 151215.

[35] McCoy Ch. A°-Categoricity in Boolean algebras and linear orderings // Ann. Pure Appl. Logic. 2003. V. 119. №1-3. P. 85-120.

[36] Mead J. Recursive prime models for boolean algebras // Coll. Math. 1979. V. 41. №1. P. 25-33.

[37] Rabin M. 0. Computable algebra, general theory and theory of computable fields // Trans. Amer. Math. Soc. 1960. V. 95. №2. P. 341-360.

[38] Remmel J. B. Recursively categorical linear orderings // Proc. Amer. Math. Soc. 1981. V. 83. P. 387-391.

[39] Rogers L. A. Ulm's theorem for partially ordered structures related to simply presented Abelian p-groups // Trans. Amer. Math. Soc. 1977. V. 227. P. 333-343.

[40] Smith R. L. Two theorems on autostability in p-groups I j In: Logic Year 197&-80. LNM. 1981. V. 859. P. 302-311.

[41] Soare R. I. Computability Theory and Applications: The Art of Classical Computability, Computability in Europe Series. Springer-Verlag. 2012.

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

Оригинальные статьи

[42] Душенин Д. И. Относительная автоустойчивость прямых сумм абелевых р-групп // Вестник НГУ. Серия.: матем., механика, информ. 2010. Т. 10. №1. С. 29-39.

[43] Душенин Д. И. Абелевы р-грулпы и автоустойчивость относительно оракула // Алгебра и логика. 2013. Т. 52. №4, С. 403-411.

[44] Душенин Д. И. Арифметические изоморфизмы абелевых р-групп // Вестник НГУ. Серия.: матем., механика, информ. 2013. Т. 13. №1. С. 47-56.

Переводы оригинальных статей на английский язык

[45] Dushenin D. I., Relative autostability of direct sums of Abelian p-groups // Journal of Mathematical Sciences. 2012. V. 186. №3. P. 416425.

Душенин Дмитрий Игоревич

АБЕЛЕВЫ Р-ГРУППЫ И АВТОУСТОЙЧИВОСТЬ ОТНОСИТЕЛЬНО ОРАКУЛА

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

Подписано в печать 8.10.13. Формат 60x84 1/16. Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ № 168.

Отпечатано в ООО «Омега Принт» 630090, Новосибирск, пр.Лаврентьева, 6

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Душенин, Дмитрий Игоревич, Новосибирск

ИНСТИТУТ МАТЕМАТИКИ ИМЕНИ С. Л. СОБОЛЕВА СИБИРСКОГО ОТДЕЛЕНИЯ РАН

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

04201 364166

ДУШЕНИН ДМИТРИЙ ИГОРЕВИЧ

АБЕЛЕВЫ Р-ГРУППЫ И АВТОУСТОЙЧИВОСТЬ ОТНОСИТЕЛЬНО ОРАКУЛА

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

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

Научный руководитель: доктор физ.-мат. наук член-корреспондент РАН С.С. ГОНЧАРОВ

Новосибирск — 2013

Оглавление

Введение 3

0.1 Описание проблематики....................................3

0.2 Обзор результатов диссертации............................7

1 Предварительные сведения 9

1.1 Теория групп................................................9

1.2 Вычислимость................................................19

2 Нередуцированные группы конечного типа 38

3 Нередуцированные группы типа 1. 51

4 Нередуцированные группы типа 2 и 3. 68 Литература 101

Введение

Диссертация посвящена исследованию тьюринговых степеней автоустойчивости абелевых р-групп. Эта задача является одной из многих других, изучаемых в теории конструктивных моделей, которая, в свою очередь, берет начало с работ А.И. Мальцева ([15], [16]) и М. Рабина ([37]) середины прошлого века и с тех пор активно развивается, благодаря трудам множества математиков со всего мира. Этому разделу математической логики, а также тесно связанной с ним теории вычислимости, посвящено очень большое количество литературы, но в качестве особенно важных и современных источников стоит выделить [6], [30] и [41].

0.1 Описание проблематики

Объектом исследования в диссертации являются конструктивизируемые аддитивные абелевы р-группы и тьюринговы степени их автоустойчивости. Известно, что аддитивная абелева группа представляется в виде прямой суммы редуцированной и полной подгрупп. Любая полная аддитивная абелева р-группа является прямой суммой конечного или бесконечного числа квазициклических групп (или групп типа р°°). Что касается редуцированных абелевых р-групп, то еще в 1933-м году Ульмом был получен известный результат о том, что редуцированные р-группы одинакового типа т, все соответствующие факторы

которых изоморфны, сами являются изоморфными. Этот результат говорит о том, что любая редуцированная р-группа с точностью до изоморфизма определяется своими факторами. Эти и многие другие известные результаты теории групп можно найти в [13]. Позднее для некоторых видов редуцированных р-групп были предложены иные, более удобные, подходы к доказательству теоремы Ульма. Например, в [39] вводятся понятия р-базисных деревьев, которые ассоциируются с абелевыми р-группами и делают интуитивное понимание их структуры куда более доступным.

Вопрос о конструктивизируемости и сильной конструктивизируемости заданной модели является одним из самых важных и интересных в теории конструктивных моделей. Так Ю.Л. Ершов в [10] доказал теорему о ядре, с помощью которой можно переносить конструктивизации алгебры на ее замыкания, Н.Г. Хисамиев в [22] получил результат о том, что любая счетная модель ^-категоричной теории сильно конструктивизируема, а С.С. Гончаровым в [1] и М.Г. Перетятькиным в [19] независимо найдены критерии сильной конструктивизируемости однородных моделей. Что касается классических классов алгебраических структур, то этому вопросу также посвящена целая серия работ. Например, А.И. Мальцевым в [16] были описаны конструктивизируемые абелевы группы без кручения ранга 1. Также М. Рабином в [37] была доказана сильная конструктивизируемость счетного алгебраически замкнутого поля, A.C. Морозовым ([17]) получено, что счетные насыщенные булевы алгебры сильно конструктивизируемы, а Дж. Мидом в [36] установлено, что любая счетная простая булева алгебра сильно конструктивизируема.

В.П. Добрица в [8] и А.Т. Нуртазин в [18] также доказали, что конструктивизируемые абелевы группы обладают конструктивизацией с рекурсивно перечислимым базисом.

Изучению различных алгоритмических свойств групп посвящена серия работ Н.Г. Хисамиева, главные результаты которых собраны в его докторской диссертации. Так в [23] показано, что прямая сумма циклических и квазициклических р-групп обладает сильной Х-конструктивизацией тогда и только тогда, когда ее характеристика ^-конструктивна (здесь X - некоторый оракул). В этой же работе, а также в [9] (в соавторстве с В.П. Добрицей и А.Т. Нуртазиным) представлены достаточные условия на ульмовы факторы редуцированной абелевой р-группы для ее конструктивизируемости и сильной конструктивизируемости. Также в [9] доказано, что ульмов тип конструктивной р-группы является конструктивным ординалом. В [24] представлен критерий конструктивизируемости прямых сумм циклических абелевых р-групп, а в [25] и в [26] - аналогичные критерии для прямых сумм циклических и квазициклических абелевых р-групп. Также им доказано, что из конструктивизируемости абелевой группы не следует конструктивизируемость ее редуцированной или полной части. В [28] был впервые сформулирован известнейший критерий конструктивизируемости для редуцированных абелевых р-групп, обладающих элементами бесконечной высоты. Доказательство обобщения этого критерия на нередуцированные р-группы, а также аналогичный критерий сильной конструктивизируемости, можно найти в докторской диссертации Н.Г. Хисамиева. Там же доказан ряд полезных следствий из этих критериев. Также можно выделить критерии существования сильной конструктивизации для р-групп, основанные на определяющих соотношениях и системе порождающих элементов. Найти их можно также в [25]. Там же в качестве примера их применения доказано, что если полная часть сильно конструктивизируемой р-группы имеет конечный ранг, то ее редуцированная часть сильно конструктивизируема.

Понятие автоустойчивости впервые было введено А.И. Мальцевым в [15]. Им же в [16] впервые была построена неавтоустойчивая модель. В настоящее время получены критерии автоустойчивости для целого ряда известных классов структур. Так в [4] можно найти доказательство того, что булева алгебра автоустойчива тогда и только тогда, когда она имеет конечное число атомов. [38] содержит в себе следующий результат: линейный порядок вычислимо представим в том и только в том случае, когда в нем имеется конечное число непосредственных следований. В [18] доказывается, что абелева группа без кручения автоустойчива тогда и только тогда, когда ее ранг конечен. Отдельно необходимо упомянуть интересный результат из [5] о том, что если произвольная конструктивизируемая модель ветвится, то класс ее конструктивизаций эффективно бесконечен. Следствием теоремы о ветвящихся моделях является критерий автоустойчивости для абелевых р-групп.

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

о классической автоустойчивости. Тем не менее, существует ряд частичных результатов по этой теме. Например, в [35] описаны Д^-категоричные линейные порядки и булевы алгебры. Также известно, что для любого п > 1 существуют А°+1-автоустойчивые структуры, которые при этом не являются Д^-автоустойчивыми. Примером могут служить деревья конечной высоты ([34]). Также в [31] содержится результат о том, что редуцированная абелева р-группа типа т < и является 0(2г-1)-автоустойчивой. При этом существует редуцированная абелева р-группа типа т, которая не является автоустойчивой.

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

0.2 Обзор результатов диссертации

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

Вторая глава диссертации посвящена получению верхней оценки для тьюринговых степеней автоустойчивости нередуцированных абелевых р-групп конечного типа т. Этот результат обобщает известный факт для редуцированных абелевых р-групп из [31]. Результаты главы опубликованы в [44].

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

нередуцированных абелевых р-групп с редуцированной частью типа 1. Основные результаты главы опубликованы в [42]. Также существует перевод этой публикации на английский язык ([45]).

Четвертая глава содержит примеры, подтверждающие точность оценки, представленной во второй главе, для нередуцированных абелевых р-групп с редуцированной частью типа 2, обладающих полной частью конечного и бесконечного ранга. Также в ней подтверждается точность этой оценки для нередуцированных абелевых р-групп с редуцированной частью типа 3, обладающих полной частью бесконечного ранга. Основные результаты главы опубликованы в [43].

Глава 1

Предварительные сведения

1.1 Теория групп

Начнем с самых элементарных определений теории групп, которые нам потребуются для понимания сути исследований. Для более подробного ознакомления с этой областью можно обратиться к [13] или [21].

Определение 1. Группой < С, * > называется непустое множество С с заданной на нем бинарной операцией *, для которого выполнены следующие условия:

1)Ассоциативность: \/(а, 6, с Е С): (а * 6) * с = а * (6 * с).

2)Существование нейтрального элемента: Зе Е С \/а Е С: е*а = а * е = а.

3)Существование обратного элемента: \/а € С За-1 € С: а * а-1 = а-1 * а = е.

Определение 2. Подгруппой группы < С, * > называется такая группа < С, * > с той э/се операцией *, что ССС.

Определение 3. Группа < С, * > называется абелевой (или коммутативной), если для всех ее элементов выполнено условие коммутативности: У (а, Ь Е С); а * Ь — Ь * а.

В дальнейшем будем использовать аддитивную запись, то есть в качестве бинарной операции * будем рассматривать Н— операцию сложения. При такой записи для обозначения нейтрального элемента е принято использовать 0, а для обозначения элемента, обратного к элементу а, использовать запись —а. Чтобы кратко записать элемент а + а + ... + а, будем использовать запись па. Также для удобства

п раз

будем вместо полного, "правильного", обозначения группы < С, + > использовать сокращенное - С.

Определение 4. Если Б - подмножество С, то через < 5 > будем обозначать подгруппу группы порожденную элементами множества Б, то есть пересечение всех подгрупп С, содержащих Б. Если Б состоит из элементов а\, а2, ..., ап, ..., то будем также писат,ь

< 5 >=< аь а2,..., ап,... > .

Определение 5. Циклической группой называется группа, порожденная одним элементом.

Определение 6. Порядком группы С называется число элементов в группе.

Определение 7. Порядком элемента а группы С называется минимальное натуральное число т, для которого та = 0. Если такого числа не существует, то говорят, что а - элемент бесконечного порядка.

Определение 8. Если все элементы группы кроме нуля, имеют бесконечный порядок, то назовем С группой без кручения.

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

Объектом исследования в диссертации как раз и будут такие группы. Некоторые определения, связанных с этим объектом, а также его основные свойства будут представлены ниже. Более подробную информацию по абелевым р-группам можно найти в [32].

Введем понятие ранга группы. Для этого дадим определение линейной независимости системы элементов в группе.

Определение 10. Конечную систему элементов д\,...,дп группы С? назовем линейно зависимой, если существуют целые числа ТП1, ...,тп, не все равные нулю, для которых выполнено равенство т191 + ---+тп9п = О .В ином случае назовем эту систему элементов линейно независимой.

Это понятие легко расширить на случай бесконечной системы элементов.

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

Известен следующий факт.

Утверждение 1. Всякая непериодическая группа обладает максимальной линейно независимой системой элементов. Более того, всякая линейно независимая система элементов в ней может быть расширена до максимальной.

Таким образом, мы подходим к определению ранга группы.

Определение 12. Если группа С обладает конечной максимальной линейно независимой системой, то рангом группы С назовем количество элементов в этой системе. В ином случае говорим, что группа С обладает бесконечным рангом.

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

Определение 13. Пусть д € G, д ф 0, где G - группа без кручения. Обозначим через pi i-e простое число. Характеристическим семейством элемента g назовем множество {(i,j)\j < hPi(g), 0 < hPi(g)}, где hp(g) - максимальное к, для которого существует такой элемент h Е G, что pkh = g (если такой h существует для любого к, то полагаем, что hp(g) = 00).

Введем еще одно ключевое понятие в теории групп.

Определение 14. Абелева группа G называется полной (или делимой), если для всякого элемента g Е G и всякого натурального числа п уравнение пх = g имеет в G хотя бы одно решение.

Определим также прямую сумму групп.

Определение 15. Абелева группа G представляется в виде прямой суммы групп G\ и G2 (G = G\($)G<2,), если группу G можно представить как множество {{gi,g2)\9i £ 6 G2} с операцией

+, действующей покомпонентно: (а, Ь) + (с, d) — (а+с, b+d). Группы G\ и С?2 называют прямыми слагаемыми группы G.

Легко заметить, что группы G\ и G2 изоморфны подгруппам {(01,0)101 е Gi} и {(0,^2)1^2 6 G2} соответственно.

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

Определение 16. Абелева группа G представляется в виде прямой суммы счетного числа групп (G^i > 0), если:

1) Носитель группы G представляет из себя множество счетных последовательностей (до, д\,..., дг,...), где для всех г > О верно, что дг б G%, а множество {г\дг Ф 0} конечно.

2) Операция сложения в группе определена покомпонентно:

•••) + (до, 9í, -,9i, •••) = (go + go,gi + gi, + g%, ■■■)•

Тогда будем писать, что G — 0г>о G% или G = фгеа; G%.

Известны следующие полезные факты о полных подгруппах абелевых групп.

Утверждение 2. Если абелева группа G содержит полную подгруппу G', то G' служит для G прямым слагаемым.

Утверждение 3. Сумма любого множества полных подгрупп некоторой абелевой группы сама является полной подгруппой.

С их доказательством можно ознакомиться, например, в [13]. Благодаря этим утверждениям можно заметить, что в произвольной абелевой группе G существует максимальная полная подгруппа D -сумма всех полных подгрупп G.

Определение 17. Редуцированной абелевой группой назовем т,акую абелеву группу, никакая подгруппа которой не является полной.

Теперь мы можем указать следующий полезный факт.

Утверждение 4. Всякая абелева группа разлагается в прямую сумму двух групп - полной и редуцированной.

Также можно легко описать все возможные виды полных групп.

Определение 18. Группой типа R назовем группу, изоморфной аддитивной группе всех рациональных чисел.

Определение 19. Пусть р - простое число. Группой типа р°°, или квазициклической, назовем группу, порожденную элементами с\, сч, .... сп, ..., связанными между собой следующими соотношениями: рсо — 0; рсп+\ — сп для всех п > 0.

Вернемся к описанию абелевых р-групп. Обратим внимание на то, что любая полная абелева р-группа представляет из себя прямую сумму некоторого числа групп типа р°° для фиксированного р.

Определение 20. Корнем элемента д абелевой р-группы С назовем такой элемент д' Е С, что рд' = д.

Определение 21. Элемент а абелевой р-группы С называется элементом бесконечной высоты, если а Ф 0 и для любого к уравнение ркх = а обладает в группе С хотя бы одним решением. Если это уравнение может быть решено в С лишь при к < п, то г