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

• Душенин, Дмитрий Игоревич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Душенин, Дмитрий Игоревич

Оглавление

Введение

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

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

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

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

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

ч

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

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

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

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

Введение

Диссертация посвящена исследованию тьюринговых степеней автоустойчивости абелевых р-групп. Эта задача является одной из многих других, изучаемых в теории конструктивных моделей, которая, в свою очередь, берет начало с работ А.И. Мальцева ([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]. Там же в качестве примера их применения доказано, что если полная часть сильно конструктивизируемой р-группы имеет конечный ранг, то ее редуцированная часть сильно конструктивизируема.

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

Понятие автоустойчивости впервые было введено А.И. Мальцевым в [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 и для любого к уравнение ркх = а обладает в группе С хотя бы одним решением. Если это уравнение может быть решено в С лишь при к < п, то говорят, что элемент а имеет высоту п.

Определение 22. Пусть группа С! — ^рпг ■ Характеристикой р-группы С? назовем множество х(С) = {{т, к)\3г1..31к(щ1 = ... = щк = т)}.

Пусть С - произвольная абелева р-группа. Так как сумма и разность двух элементов бесконечной высоты также является элементом бесконечной высоты, то множество всех элементов, имеющих бесконечную высоту, в совокупности с нулем образует подгруппу группы Обозначим ее через С1. Далее продолжим цепочку следующим образом. Если для всех а < (3 уже определены подгруппы Са, то в качестве С? выбираем при непредельном (3 подгруппу, составленную из элементов, имеющих в бесконечную высоту, а при предельном (3 - пересечение всех подгрупп где а < (3. Существует такое 7, не превосходящее мощности группы, что С7 = С7+1. Заметим, что если Я. - редуцированная р-группа, то Ю = 0.

Определение 23. Если II - редуцированная р-группа, то наименьшее 7. при котором Ю = 0; называется типом группы Я.

Определение 24. Элемент д редуцированной абелевой р-группы Я называется элементом типа а, если он содержится в подгруппе Яа, но не содержится в подгруппе Яа+1.

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

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

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

Теорема 1 (Куликов). Абелева р-группа С тогда и только тогда разложима в прямую сумму циклических групп, когда она является объединением возрастающей последовательности А\ С А2 С ... С Ап С ... таких своих подгрупп, что у каждой из них высоты элементов в группе С конечны и ограничены в совокупности.

Следствие 1 (Прюфер). Всякая абелева р-группа с ограниченными в совокупности порядками элементов разлагается в прямую сумму циклических подгрупп.

Следствие 2 (Прюфер). Счетная абелева р-группа, не содержащая элементов бесконечной высоты, разлагается в прямую сумму циклических подгрупп.

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

Определение 26. Пусть редуцированная группа И имеет тип т. Для всех а < т рассмотрим фактор-группы Йа = Да/Яа+1. При

построении фактор-группы для а = 0 считаем, что Я0 = Я. Полученная последовательность групп Я®, Я},..., Яа,..., са т, называется последовательностью ульмовских факторов группы Я.

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

Определение 27. Подгруппу С абелевой группы С назовем сервантной, если для всех с 6 С ип < и из разрешимости в группе С уравнения пх — с следует его разрешимость в С.

Известен следующий факт относительно этого определения, рассмотренного в абелевой р-группе.

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

Можно расширить определение сервантной подгруппы на факторы следующим образом.

Определение 28. Пусть X - подгруппа С и а < т. X П Са является подгруппой Через будем обозначать подгруппу группы (5а; которая является образом X П Са при естественном гомоморфном отображении группы Са на фактор 0а. Подгруппу X назовем совершенной подгруппой группы С, если для всех а < т подгруппа является сервантной в группе Оа.

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

Определение 29. Пусть в группах А и В выбраны подгруппы С\ и соответственно, изоморфные между собой. Будем говорить, что изоморфизм {р между этими подгруппами - сохраняющий типы, если он сопоставляет друг другу элементы и (?2, имеющие одинаковые типы в группах А и В соответственно.

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

Теорема 2 (Ульм). Если счетные редуцированные абелевы р-группы А и В имеют один и тот же тип т и если для всякого а < т их ульмовские факторы Аа и Ва изоморфны, то группы А и В сами изоморфны между собой.

Абелевы р-группы с редуцированной частью произвольного ульмовского типа т могут иметь достаточно сложную структуру. Как следствие, конструкции на них могут быть очень громоздкими и не всегда ясными для понимания. Здесь на помощь приходит работа [39], в которой указывается связь между абелевыми р-группами и деревьями, которые, в свою очередь, являются куда более наглядными объектами.

Определение 30. Определим р-базисное дерево X как множество с заданной в нем операцией умножения на фиксированное простое число р, в котором выполнены условия:

(1) рх € X для всех х € X.

(2) В X существует такой элемент 0, что рО — 0.

(3) Для любого ненулевого х Е X существует такое п > 0, что рпх = 0.

Определение 31. Пусть X - р-базисное дерево. Степень элемента х Е X определим как наименьшее п > 0, для которого рпх — 0.

Определение 32. Пусть X -р-базисное дерево. Высотой элемента х Е X назовем такой ординал а, что х Е раХ, но х £ ра+1Х.

Определение 33. Пусть X - р-базисное дерево. Через [X] обозначим группу с порождающими X и определяющими соотношениями рх — у, где х,у Е X таковы, что рх — у.

Укажем некоторые полезные свойства р-базисных деревьев.

Утверждение 6. Пусть X - поддерево и)<ш. Тогда [X] - абелева р-группа. Более того, если X не имеет бесконечных путей, то [X] - редуцированная.

Утверждение 7. Для любой счетной редуцированной абелевой р-группы G существует, дерево X С uj<UJ, для которой [X] = G.

Предложение 1 ([39]). Пусть X - р-базисное дерево, a b -ненулевой элемент [X], который представляется в виде Yli=irixi-Тогда высота элемента b в группе [X] равна минимальной из высот элеметов х\, ...,хь в дереве X.

Также в [39] указано следующее важнейшее свойство р-базисных деревьев.

Определение 34. Пусть X, Y - р-базисные деревья и а : X —» Y - биекция между ними, а называется обнажающей функцией, если она сохраняет высоты элементов, и из а{рх) ф ра{х) следует ра(х) = 0.

Утверждение 8. Если X, Y - р-базисные деревья и а : X —> Y -обнажающая функция, то [X] = [У].

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

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

В этом разделе мы вспомним основные понятия теории вычислимости, а также известные результаты из области конструктивных моделей. Более подробную информацию по основам теории вычислимости можно найти в [20], по основам классической теории моделей - в [12]. С современным состоянием области теории вычислимости можно ознакомиться в [41], а с исследованиями из области конструктивных моделей - в [6].

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

Определение 35. Функция / вычислима с оракулом X (или X-вычислима), если она может быть вычислена с помощью некоторой машины Тьюринга с оракулом X.

Можно естественным образом расширить это понятие на множества. Это приведет нас к сводимости по Тьюрингу (<т)-

Определение 36. Множество X вычислимо относительно множества У (X <т У), если его характеристическая функция У -вычислима.

Если X <т У и У <т X, то имеет место запись X =т У. Нетрудно заметить, что =т является отношением эквивалентности.

Определение 37. Степенью множества X (обозначается как дед{Х)) называется класс эквивалентности относительно =т, которому принадлежит множество X.

Степень, содержащую рекурсивные множества, обозначим через О (взято из [20]). Теперь определим одно из основных понятий теории вычислимости - операцию скачка.

Определение 38. Для любого множества А положим А' := {п\(Рп{п) = {п\п Е где ~ функция, которую вычисляет

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

Нетрудно определить итерации скачка: полагаем := А

и У4(гг+1) := (А^у. Также можно расширить операцию скачка на степени, определив а' как степень, которая содержит скачок произвольного множество А из степени а.

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

Определение 39. Отношение Я(х) принадлежит классу Е®, когда его можно представить в виде 3уЗ(х,у), где в(х,у) - вычислимое. Отношение С^{х) принадлежит классу если ~1Я{х) Е Продолжаем по индукции. Для всех п > 1 полагаем Я(х) Е если Я(х) представим в виде ЗуЗ(х,у), где Б(х,у) Е П®^. Для всех п > 1 полагаем <3(ж) € П®. если Е Е®. Наконец, для всех

Список литературы диссертационного исследования кандидат наук Душенин, Дмитрий Игоревич, 2013 год

Литература

[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] Хисамиев H. Г. Сильно конструктивные модели разрешимой теории // Изв. АН Каз ССР. Сер. физ.-мат. 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 Hyper arithmetical Hierarchy. Elsevier. 2000.

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

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

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

[34] Lempp S, McCoy Ch., Miller R., Solomon R. Computable categoric-ity of trees of finite height // J. Symbolic Logic. 2005. V. 70. №1. P. 151-215.

[35] McCoy Ch. Ag-Categoricity in Boolean algebras and linear orderings 11 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. O. 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 // In: Logic Year 1979-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. SpringerVerlag. 2012.

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

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

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

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

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

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

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