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

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

/ / > а !

.,- /

МЕЛЬНИКОВ АЛЕКСАНДР ГЕННАДЬЕВИЧ

ЭФФЕКТИВНЫЕ СВОЙСТВА ВПОЛНЕ РАЗЛОЖИМЫХ АБЕЛЕВЫХ ГРУПП

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

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

12 янв тг

Новосибирск 2011

005007595

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Новосибирский государственный университет».

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

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

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

Ведущая организация: ФГАОУ ВПО «Казанский

(Приволжский) федеральный университет»

Защита состоится " 26 " января 2012 г. в 14.00 часов на заседании диссертационного совета Д 003.015.02 при Институте математики им. С.Л. Соболева Сибирского отделения Российской академии наук по адресу: пр. Академика Коптю-га 4, г. Новосибирск, 630090.

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

Автореферат разослан " 19 " декабря 2011 г. Ученый секретарь

диссертационного совета

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

наук, профессор Хисамиев Назиф Гарифуллинович

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

Добрица Вячеслав Порфирьевич

А.Н.Ряскин

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

В диссертации изучаются эффективные свойства абеле-вых групп без кручения специального естественного класса: вполне разложимых абелевых групп. Впервые (классически) эти группы систематически изучались в работе Бэра [4]. Предложенные в диссертации результаты используют новые теоретико-групповые и теоретико-рекурсивные методы и продолжают традицию, заложенную еще в работах А.И. Мальцева [31], [30].

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

В диссертации исследуются эффективные свойства вполне разложимых абелевых групп. Изучение эффективных процедур в теории групп предшествовало формальному определению алгоритма. Отправной точкой здесь можно считать работы Дена [8] и Хигмана [23], где изучались свойства конечно порожденных групп. Схожие по духу исследования велись и в других разделах алгебры: интуитивно эффективные процедуры применялись в теории полей, колец и других алгебра-

3

ических структур (см., например, ван дер Варден [44], Херр-манн [21]). Современная теория вычислимых групп (не обязательно абелевых) берет своё начало в работах Рабина [39] и Мальцева [30], [31], где использовалось известное к тому времени формальное понятие алгоритма.

Мальцев был также первым, кто предпринял систематическое изучение вычислимых свойств абелевых групп [30], [31]. Вычислимые абелевы группы активно изучаются и представляют собой достаточно хорошо развитую теорию. Подробное изложение основ этой теории можно найти в обзорной статье Хисамиева [25] или в заключительной главе книги До-уни [9]. Последняя глава этой диссертации посвящена случаю, когда вполне разложимая группа является, кроме того, упорядоченной группой. Теория вычислимых линейно упорядоченных абелевых групп является сравнительно молодой, однако активно развивается. Основы этой теории достаточно подробно представлены в работе Гончарова, Лемппа и Соломона [20].

На сегодняшний день теория вычислимых и эффективно представимых абелевых групп является частью более общей теории вычислимых моделей (см. Ершов и Гончаров [18], Найт [3], Доуни [9]). Основными объектами этой теории являются вычислимые алгебраические структуры (или модели): это те алгебраические структуры, в которых множество элементов, операции и отношения заданы некоторыми равномерно вычислимыми процедурами. Если структура имеет вычислимую изоморфную копию, то говорят, что эта структура имеет вычислимое представление или конструктивиза-цию. Естественно также рассматривать вычислимые изомор-

4

физмы между вычислимыми структурами. Как было отмечено Мальцевым [31], две изоморфных вычислимых структуры не обязательно вычислимо изоморфны. По-видимому, первым естественным примером такой алгебраической структуры оказалась именно абелева группа. Мальцев построил две изоморфные вычислимые абелевы группы, которые не являются вычислимо изоморфными. В связи с этим было предложено понятие автоустойчивой структуры. Говорят, что вычислимо представимая структура автоустойчива, если любые ее два вычислимых представления вычислимо изоморфны [18]. Автоустойчивые структуры часто называют вычислимо категоричными [3].

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

Нас интересуют эти проблемы для класса абелевых групп. Для других структур эти проблемы также активно изучались и изучаются (см., например, [18] и [16]). Заметим, что удовлетворительный ответ на любой из двух сформулированных выше проблем для некоторого данного класса структур,

5

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

Что касается критерия вычислимой представимости, то для нас особый интерес представляют результаты в теории вычислимых абелевых групп. Мальцев [31] охарактеризовал вычислимо представимые аддитивные подгруппы рациональных чисел. Эта характеризация, несмотря на ее простоту, до сих пор играет фундаментальную роль в теории абелевых групп без кручения. Значительно более поздний результат -это описание вычислимо представимых абелевых р-групп конечной Ульмовой длины, полученное Хисамиевым [25]. Для этого описания Хисамиев ввел понятие монотонной вычислимой аппроксимации множества. Отметим, что понятие вычислимой монотонной аппроксимации нашло применение в других актуальных задачах теории вычислимых моделей ([27], [24], [6]), а также активно изучается с точки зрения чистой теории вычислимости ([13]). Еще один результат в этом направлении - это недавно полученная характеризация вычислимо представимых абелевых групп без кручения, являющихся прямыми суммами аддитивных групп локализаций целых чисел. Проблема характеризации таких групп была поставлена Хисамиевым в [26]. Хисамиев [26] также получил частичное решение этой проблемы для класса таких групп с некоторыми дополнительными условиями. Проблема была решена в [12]. Было показано, что такая группа имеет вычислимую копию тогда и только тогда, когда множество простых чисел, по которым берется локализация, принадлежит уровню арифметической иерархии (см. [43]).

Заметим, что в предложенных нами выше результатах ис-

6

пользуются простые алгебраические инварианты, но каждая характеризация требует от соответствующего инварианта некоторого эффективного свойства. Классическая простота инварианта вовсе не означает, что доказательства тоже просты, поскольку эффективные свойства инварианта могут оказаться нетривиальными. Как следствие, наличие удовлетворительной классификации для богатых классов структур весьма редки. Например, хорошо известно, что (классически) абе-левы р-группы описываются их Ульмовыми типами [14], причем этот факт нельзя назвать трудным. Однако обобщение результата Хисамиева [25] на случай бесконечной Ульмовой длины неизвестно и является открытой проблемой уже около 20 лет. Для более широких классов проблемы зачастую оказываются чрезвычайно сложными или даже настолько сложными, насколько вообще возможно (см., например, Гончаров и Найт [19]). Доуни и Монталбан [11] показали, что проблема изоморфизма для вычислимых абелевых групп без кручения является полной в классе . Интуитивно это означает, что у вычислимых абелевых групп без кручения не может быть инвариантов, которые описывали бы их с точностью до изоморфизма и которые были бы устроены алгоритмически проще, чем сами группы. Поэтому для более глубокого понимания проблемы вычислимой представимости рассматривают обобщение этой проблемы: Для данного класса алгебраических структур и данного оракула X охарактеризовать все структуры этого класса вычислимые относительно X. Для данной структуры описать все оракулы X, относительно которых эта структура является вычислимо представимой.

Множество оракулов (более точно - Тьюринговых степе-

7

ней), относительно которых структура вычислимо предста-вима, называется степенным спектром данной структуры [41]. Степенные спектры структур активно изучаются [37], [24], [22]. Особое место занимает пример, предложенный Слама-ном [42], и аналогичный пример, построенный независимо Ве-нером [45]. Венер и Сламан показали, что существуют структуры, которые вычислимо представимы относительно произвольного невычислимого оракула, но при этом не являются вычислимо пред ставимыми. Этот пример показывает, что в общем случае невозможно сформулировать достаточного условия на существование вычислимой копии в терминах степенных спектров. Действительно, даже самое сильное из мыслимых условий оказывается недостаточным. Однако для некоторых естественных классов структур такие условия были получены. Например, хорошо известно, что если булева алгебра имеет представление относительно /ои>4 оракула, то эта булева алгебра вычислимо представима [28].

С другой стороны, характеризации вычислимой категоричности для многих богатых классов структур известны. Например, булева алгебра вычислимо категорична тогда и только тогда, когда она имеет конечное число атомов (Гончаров [16|), линейный порядок вычислимо представим если и только если в нем имеется конечное число непосредственных следований (Реммель [40]), и абелева группа без кручения вычислимо категорична в точности когда ее ранг конечен (Гончаров [17], Нуртазин [38]). Говорим, что структура Л является Д® -категоричной, если Л вычислимо категорично относительно оракула 0(п_1), где 0("-1) - это (п- 1)тая итерация проблемы остановки. Если известна характеризация

8

вычислимо категоричных представителей данного класса, то естественно поставить вопрос о характеризации Д° - категоричных представителей этого класса. Как правило, эта проблема оказывается значительно более сложной. Очень немного известно о Д° - категоричных структурах. Из-за проблем технического характера, полную характеризацию А°п - категоричных структур для естественных классов получить, как правило, не удается. Однако есть целый ряд частичных результатов в этом направлении. Например, в [32] описаны - категоричные линейные порядки и булевы алгебры с некоторыми дополнительными условиями. Кроме того, известно, что Д°+1 - категоричность не влечет Л" - категоричности для линейных порядков [1], булевых алгебр [3] и абелевых р -групп [5].

Несмотря на то, что проблема вычислимой представимости и вычислимой категоричности относительно оракула хорошо изучены классов для линейных порядков [10] [2], булевых алгебр [16] и абелевых р-групп [25] [5], эти проблемы для абелевых групп без кручения представляются широко открытыми.

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

Методы исследования. Результаты диссертации получены с использованием методов теории вычислимости [43], теории абелевых групп и модулей [15], [14], а также теории вычислимых алгебраических систем [18], [3].

9

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

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

Основные результаты. В работе получены следующие основные результаты:

• Предложен метод эффективного кодирования семейств конечных множеств во вполне разложимые группы. При помощи этого кодирования построен пример вполне разложимой абелевой группы, имеющей X - вычислимую копию в точности для таких X, что X' = 0'. Это также первый и единственный известный пример абелевой группы со спектром, близким к спектру Сламана-Венера [42], [45].

• Предложено алгебраическое понятие 5-независимости и изучены его свойства. При помощи свойств 51-независимости показано, что всякая однородная вполне разложимая группа категорична относительно О".

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

Апробация результатов диссертации. Результаты диссертации по мере их получения докладывались на следующих конференциях:

Международная конференция "Мальцевские чтения" 2009, 2010 и пленарный доклад в 2011 году.

Международная конференция Asian Logic Colloquium, 2011, секционный доклад.

Международная конференция "Computabilty in Europe" 2007, 2009, 2010.

Международная конференция "Logic colloquium" 2005. 2006.

XLIV и XLV Международная студенческая конференция (Новосибирск, 2006 и 2007).

Результаты докладывались на семинарах:

"Theory Seminar" в 2010 году, (Auckland, The University of Auckland, рук. - профессор Khoussainov В.).

"Алгебра и логика" в 2007 году (Новосибирск, ИМ СО РАН, рук. - академик Ершов Ю.Л.).

Публикация результатов. Результаты автора по теме диссертации опубликованы в работах [46-54], из них [50-53] входят в перечень ВАК рецензируемых научных журналов на английском языке, в которых должны быть опубликованы основные результаты диссертаций на соискание учёных степеней доктора и кандидата наук.

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

СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава содержит понятия, необходимые для дальнейшего изложения. Почти все предложенные понятия являются классическими и могут быть найдены в литературе [43], [18], [14], [29]. Глава состоит из двух параграфов. В первом из двух параграфов напоминаются известные определения из теории вычислимости и теории вычислимых моделей, во втором параграфе содержаться необходимые элементарные основы теории абелевых групп.

Вторая глава содержит необходимые для последующих глав факты и свойства вполне разложимых групп. Эту главу можно считать введением в теорию вычислимых вполне разложимых групп. В первом параграфе доказаны некоторые нетрудные факты о степенных спектрах вполне разложимых абелевых групп. Некоторые из этих фактов хорошо известны, другие же являются новыми. В частности, независимый интерес представляют следующее предложение и следствие, которые отвечает на вопросы Доуни [9] (см. также [7]) о прыжковых степенях групп конечного ранга:

Предложение 6. Всякая абелева группа без кручения имеет прыжковую степень. Более того, всякая степень а > О' реализуется в качестве точной прыжковой степени некоторой абелевой группы без кручения конечного ранга п, где п -произвольное ненулевое число.

Следствие 1. Для всякой Тьюринговой степени а > О", су-

12

ществует вполне разложимая абелева группа без кручения, имеющая точную вторую прыжковую степень а. Для всякой Тьюринговой степени Ь > О'", существует вполне разложимая абелева группа без кручения, имеющая точную третью прыжковую степень

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

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

Теорема 4. Для всякого семейства 7? конечных множеств существует вполне разложимая абелева группа без кручения аК), такая что С(К) имеет ^-вычислимую копию если и только если Я имеет Е^-нумерацию.

Как следствие, показано существование вполне разложимой группы со степенным спектром, близким к спектру типа Сламана-Венера ([42], [45]):

Теорема 5. Существует вполне разложимая абелева группа без кручения С бесконечного ранга, такая что С/ имеет X-вычислимую копию тогда и только тогда, когда X' >т 0', то есть имеет в точности не-низкие копии. Кроме того, всякое прямое слагаемое этой группы в полном прямом разложении этой группы имеет вычислимое представление.

Результаты главы опубликованы в [36].

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

13

вводится новое алгебраическое понятие 5 - независимости, которое является обобщением классического понятия р - независимости [14], а также доказываются свойства 5 - независимых множеств вполне разложимых групп.

Определение 23. Пусть 5-множество простых чисел, и пусть С - абелева группа без кручения. Если 5 Ф 0, то говорим что Ъ\,...,Ьк из й 5-независимы в С если р\ £,е(1 ^ тД т О

влечет Д,е|1.....р\т„ для любых целых гп\,... ,тк и всякого р €

5. В особом случае когда 5=0 полагаем что 5-независимость - это то же, что линейная независимость.

Если базис группы 5- независим, то мы называем его совершенным базисом. Основным результатом параграфа является:

Теорема 6. Пусть @ = ф^ Я, где Н й й, = Г и « имеет тип Г. Тогда @[а] = СР, где Р = [р : ¡гр = оо т а}. Кроме того, если В совершенный Р-базис §[а], то § порожден В над (2(а).

Во втором параграфе 5 - независимые множества применяются для доказательства следующей теоремы, которая является основным результатом всей главы:

Теорема 7. Всякая вычислимая однородная вполне разложимая группа Аз-категорична.

Результаты главы опубликованы в [33]. Пятая Глава содержит полное описание Д^ категоричных однородных вполне разложимых групп. Для этого вводится новое понятие:

Определение 26. Пусть а = (/г,),еы - последовательность, в которой /г, € а) и {оо} для каждого i (другими словами, пусть а

14

- характеристика). Пусть, кроме того, существует неубывающая вычислимая аппроксимация hus такая, что hi - sup? his, для всякого i.

Говорим, что а имеет вычислимую грань, если существует вычислимая функция ф : а> —* ы, такая что

(к{ф{1), если hi конечна, оо, иначе,

для каждого i. Мы также говорим, что ф является вычислимой гранью для (hts)Uei0.

Это понятие является новым и (в некотором смысле) обобщает понятие монотонной аппроксимации, принадлежащее Хисамиеву [25]. Понятие вычислимой грани применяется для доказательства основного результата:

Теорема 9. Вычислимая однородная вполне разложимая абе-лева группа G является Д°-категоричной если и только если G изоморфна Gp, где Р является semi-low.

Множества, являющиеся semi-low, играют фундаментальную роль в описании теоретико-решеточных свойств в.п. множеств (см. [43]). Доказательство основной теоремы разбивается на несколько случаев, в каждом из случаев требуются разные стратегии.

Результаты получены в неразделимом соавторстве с профессором Доуни, по материалам Главы 5 подготовлена совместная публикация. Опубликованы тезисы [35].

Таким образом, Главы 4 и 5 полностью описывают -категоричность в классе однородных вполне разложимых групп.

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

Теорема 10. Существует преобразование Ф класса линейных порядков в класс упорядоченных вполне разложимых абе-левых групп такое, что Ф инъективно на типах изоморфизма. Более того, линейные порядок Ь имеет А? -представление если и только если соответствующая упорядоченная группа Ф(Т) имеет вычислимую копию. Результат релятивизуем.

Мы применим эту теорему и результаты из [2], чтобы получить результаты о прыжковых степенях упорядоченных вполне разложимых групп.

Следствие 5. Для всякого п > 3 и любой Тьюринговой степени а > О"" существует вполне разложимая линейно упорядоченная абелева группа без кручения, имеющая точную я-тую прыжковую степень а.

Во втором параграфе главы кодирование из первого параграфа использовано для доказательства:

Теорема 11. Пусть а = 2п + 1 или а = 6 + 2п - вычислимый ординал, где 5 - это предельный ординал, и п е со. Тогда существует упорядоченная вполне разложимая абелева группа, которая А® - категорична, но не Д^ - категорична, для всех ¡3<а.

Этот результат контрастирует с результатами Главы 4. Результаты Главы 6 опубликованы в [34].

Автор выражает глубокую благодарность своему научному руководителю С. С. Гончарову за постановку задач, всестороннюю поддержку и внимание к работе. Автор благодарен профессору Б. Хусаинову за понимание и поддержку на всех стадиях подготовки текста диссертации, а также за дискуссии по материалам Главы 6. Автор признателен И.Ш. Калимуллину за плодотворные беседы по материалам Главы 5.

Литература

[1] Ash, C.J., Recursive labeling systems and stability of recursive structures in hyperarithmetical degrees, Trans, of Amer. Math. Soc., vol. 298(1986), pp. 497-514.

[2] C. J. Ash, C. G. Jockusch, Jr., and J. F. Knight. Jumps of orderings. Trans. Amer. Math. Soc.. 319(2):573-599, 1990.

[3] Ash, C.J., Knight J.F.. Computable structures and the hyperarithmetical hyerarchy, Elsevier, Amsterdam, 2000.

[4] Baer, R., Abelian Groups Without Elements of Finite Order, Duke Math. J., 3 (1937), 68 - 122.

[5] Barker, E.J.. Back and forth relations for reduced abelian p-groups, Annals of Pure and Applied Logic 75 (1995), pp. 223-249.

[6] Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight, and Robert I. Soare. Bounding prime models. J. Symbolic Logic, Volume 69, Issue 4 (2004), 1117-1142.

[7] Coles, R., Downey, R., Slaman, T., Every Set Has a Least Jump Enumeration. J. London Math. Soc. (2) 62 No.3, 641649.

[8] Dehn, M. "Uber unendlische diskontinuierliche gruppen, Annals of Math., Vol. 71 (1911), 116-144.

[9] Rodney G. Downey. On presentations of algebraic structures. In Complexity, logic, and recursion theory, volume 187 of Lecture Notes in Pure and Appl. Math., pages 157-205. Dekker, New York, 1997.

[10] Rodney Downey and Julia F. Knight. Orderings with ath jump degree 0(ff). Proc. Amer. Math. Soc., 114(2):545-552, 1992.

[11] Downey, R., Montolban, A., The isomorphism problem for torsion-free abelian groups is analytic complete, Journal of Algebra, Vol 320, 2008, pp. 2291-2300.

[12] Rod Downey, Sergei S. Goncharov, Asher Kach, Julia F. Knight, Oleg V. Kudinov, Alexander Melnikov and Daniel Turetsky. Decidability and Computability of Certain TorsionFree Abelian Groups, Notre Dame Journal of Formal Logic, vol 51, number 1, 2010.

[13] Rodney Downey, Asher M. Kach, and Daniel Turetsky. Limitwise monotonic functions and applications. Proceedings of the Asian Logic Conference, to appear.

[14] Laszlo Fuchs. Infinite abelian groups. Vol. I. Pure and Applied Mathematics, Vol. 36. Academic Press, New York, 1970.

[15] Laszlo Fuchs. Infinite abelian groups. Vol. II. Academic Press, New York, 1973. Pure and Applied Mathematics. Vol. 36-11.

[16] Goncharov, S.S. Countable Boolean Algebras and Decidability, Siberian School of Algebra and Logic, Novosibirsk, Nauchnaya Kniga, 1996.

[17] Goncharov, S.S., Autostability of models and abelian groups, Algebra and Logic, 1980, vol. 19, 13 - 27 (English translation).

[18] Goncharov S., Ershov, Yu., Constructive models, Kluwer Academic Pub., 2000.

[19] Goncharov, S., Knight, J., Computable Structure and Non-Structure Theorems, Algebra and Logic, vol. 41 (6), 2002, pp. 351-373.

[20] Goncharov S., Lempp S., Solomon R., The computable dimension of ordered abelian groups, Advances in Mathematics, 175 (2003), pp. 102-143.

[21] Grete Hermann. Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. Vol. 95(l):736-788, 1926.

[22] Hirschfeldt, D., Khoussainov, B., Shore, R., Slinko, A., Degree Spectra and Computable Dimensions in Algebraic Structures, Annals of Pure and Applied Logic, vol. 115 (2002), pp. 71 - 113.

[23] Higman, G., Subgroups of finitely presented groups, Proc. Royal Soc. London, Vol. 262 (1961), 455-475.

[24] Iskander Kalimullin, Bakhadyr Khoussainov, and Alexander Melnikov, Limitwise Monotonic Sequences and Degree

Spectra of Structures (submitted).

20

[25] Khisamiev, N., Constructive abelian groups, in Handbook of recursive mathematics, v.2, part 2, Elsevier, 1998.

[26] Khisamiev, N. On a class of strongly decomposable abelian groups. Algebra Logika, 41(4):493-509, 511-512, 2002.

[27] Bakhadyr Khoussainov, Andre Nies, and Richard A. Shore. Computable models of theories with few models. Notre Dame J. Formal Logic, 38(2):165-178, 1997.

[28] Julia F. Knight, Michael Stob. Computable Boolean Algebras. J. Symb. Log., 2000: 1605 1623.

[29] Lang, S., Algebra, Springer, 2002.

[30] Mal'cev, Anatolii I., Constructive algebra I, Russian Math. Surveys 16 (1961), 77-129.

[31] A. I. Mal'cev. On recursive Abelian groups. Dokl. Akad. Nauk SSSR, 146:1009-1012, 1962.

[32] McCoy, C., A^-Categoricity in Boolean algebras and linear orderings, Annals of Pure and Applied Logic, 119 (2003), 85 - 120.

[33] Melnikov, A., 0"-Categorical Completely Decomposable Torsion-Free Abelian Groups, Lecture Notes in Computer Science,"Mathematical Theory and Computational Practice", Springer, Volume 5635/2009, pp. 362-371.

[34] Melnikov, A.G. Computable ordered abelian groups and fields, Proceedings of CiE 2009, LNCS Springer, Volume 6158/2010, pp. 321-330.

[35] Melnikov, A.G. Interactions of computability and effective group theory, Proceedings of ALC 2011, accepted.

[36] Alexander G. Melnikov. Enumerations and completely decomposable torsion-free abelian groups. Theory of Comp. Sys., 45(4):897-916, 2009.

[37] Miller, R., The A°-Spectrum of a Linear Order, J. Symbolic Logic, Volume 66, Issue 2 (2001), 470-486. .

[38] Nurtazin, A.T., Computable classes and algebraic criteria of autostability. Summary of Scientific Schools, Math. Inst. SB USSRAS, Novosibirsk, 1974.

[39] Rabin, M. O., Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc., vol. 95, (1960), 341-360.

[40] Remmel, J.B., Recursively categorical linear orderings, Proc. Amer. Math. Soc., 83 (1981), 387 - 391.

[41| Linda Jean Richter. Degrees of structures. J. Symbolic Logic, 46(4):723-731, 1981.

[42] T. A. Slaman. Relative to any nonrecursive set. Proc. Amer. Math. Soc. 126 (1998) 2117-2122.

[43] Soare, R.I., Recursively Enumerable Sets and Degrees, Springer-Verlag, Berlin Heidelberg, 1987.

[44] Bartel L. van der Waerden. Eine Bemerkung iiber die Unzerlegbarkeit von Polynomen, Math. Ann., 102(1):738-739, 1930.

[45] Wehner, S., Enumerations, Countable Structures and Turing Degrees. Proc. Amer. Math. Soc., 126 (1998), pp.2131-2139.

Список публикаций автора по теме диссертации

[46] Melnikov, Alexander G., Computable Torsion-Free Abelian Groups: Some Invariants. Sessions of seminar "Algebra I Logika". In: Algebra and Logic, Volume 46 Number 6 / November, 2007: 433-434.

[47] Melnikov, Alexander G., Degree Spectra of Torsion-Free Abelian Groups. Proc. of XLV International Student Conference, Novosibirsk State University, 2007:139.

[48] Melnikov, Alexander G., Lempp's question for torsion free abelian groups of finite rank. The Bulletin of Symbolic Logic, Volume 13, Issue 2, June 2007:208.

[49] Melnikov, Alexander G., Arithmetical categoricity of ordered abelian groups, Mal'tsev Meeting, Collection of abstracts, 2009, published online.

[50] Melnikov, Alexander G., Enumerations and Completely Decomposable Torsion-Free Abelian Groups. Theory of Computing Systems (2009) 45: 897-916.

[51] Melnikov, Alexander G., Enumerations and Torsion Free Abelian Groups. Lecture Notes in Computer Science, 2007, Volume 4497/2007 (Computation and Logic in the Real World): 566-574.

[52] Melnikov, Alexander G., 0"-Categorical Completely Decomposable Torsion-Free Abelian Groups. Lecture Notes in Computer Science, 2009, Volume 5635/2009 (Mathematical Theory and Computational Practice): 362-371.

24

[53] Melnikov, Alexander G., Computable Ordered Abelian Groups and Fields. Lecture Notes in Computer Science, 2010, Volume 6158/2010 (Programs, Proofs, Processes): 321330.

[54] Melnikov, Alexander G., Interactions of computability and effective group theory. Proceedings of ALC 2011, accepted.

Научное издание Мельников Александр Геннадьевич

ЭФФЕКТИВНЫЕ СВОЙСТВА ВПОЛНЕ РАЗЛОЖИМЫХ АБЕЛЕВЫХ ГРУПП

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

Подписано в печать 15.11.2011 г. Формат 60x84 1/16. Уч.-изд. л. 1,25. Усл. печ. л. 1,1. Тираж

100 экз. Заказ №289 Редакционно-издательский центр НГУ 630090, г. Новосибирск, ул. Пирогова, 2

61 12-1/397

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

МЕЛЬНИКОВ АЛЕКСАНДР ГЕННАДЬЕВИЧ

ЭФФЕКТИВНЫЕ СВОЙСТВА ВПОЛНЕ РАЗЛОЖИМЫХ

АБЕЛЕВЫХ ГРУПП

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

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

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

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

Оглавление

Введение 1

0.1 Эффективные свойства групп..............................1

0.2 Эффективные алгебраические инварианты..............3

0.3 Обобщения Проблемы 1 и Проблемы 2....................6

0.4 Класс вполне разложимых групп..........................8

0.5 Обзор резулвтатов..........................................9

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

1.1 Вычислимость ..............................................12

1.2 Абелевв1 группы............................................14

2 Вычислимые вполне разложимые группы 20

2.1 Спектры вполне разложимых абелевых групп ..........20

2.2 Вычислимые группы и модули............................34

3 Нумерация как вычислимый инвариант 37

4 Эффективная категоричность вполне разложимых групп 45

4.1 Совершенные базисы и б'-независимость..................45

4.2 Ад-категоричность............................................52

5 Описание Д^-категоричности. 59

6 Упорядоченные вполне разложимые абелевы группы 76

6.1 Спектры упорядоченных абелевых групп................76

6.2 Эффективная категоричность упорядоченных абелевых групп..............................................83

Введение

Эта работа посвящена изучению эффективных свойств абелевых групп без кручения специального естественного класса: вполне разложимых абелевых групп. Впервые (классически) эти группы систематически изучались в работе Бэра [5]. Предложенные результаты используют новые теоретико-групповые и теоретико-рекурсивные методы и продолжают традицию, заложенную еще в работах А.И. Мальцева [30], [29].

0.1 Эффективные свойства групп

Замечательным является тот исторический факт, что изучение эффективных процедур в теории групп предшествовало формальному определению алгоритма. Отправной точкой здесь можно считать работы Дена [9] и Хигмана [22], где изучались свойства конечно порожденных групп. Схожие по духу исследования велись и в других разделах алгебры: интуитивно эффективные процедуры применялись в теории полей, колец и других алгебраических структур (см., например, ван дер Варден [45], Херрманн [20]). Современная теория вычислимых групп берет своё начало в работах Рабина [38] и Мальцева [29], [30], где использовалось известное к тому времени формальное понятие алгоритма.

Мальцев был также первым, кто предпринял систематическое изучение вычислимых свойств абелевых групп [29], [30]. Вычислимые

абелевы группы активно изучаются и представляют собой достаточно хорошо развитую теорию. Подробное изложение основ этой теории можно найти в обзорной статье Хисамиева [24] или в заключительной главе книги Доуни [10]. Последняя глава этой диссертации посвящена случаю, когда вполне разложимая группа является, кроме того, упорядоченной группой. Теория вычислимых линейно упорядоченных абелевых групп является сравнительно молодой, однако активно развивается. Основы этой теории достаточно подробно представлены в работе Гончарова, Лемппа и Соломона [19].

На сегодняшний день теория вычислимых и эффективно представимых абелевых групп является частью более общей теории вычислимых моделей (см. Ершов и Гончаров [17], Найт [3], Доуни [10]). Основными объектами этой теории являются вычислимые алгебраические структуры (или модели): это те алгебраические структуры, в которых множество элементов, операции и отношения заданы некоторыми равномерно вычислимыми процедурами. Если структура имеет вычислимую изоморфную копию, то говорят, что эта структура имеет вычислимое представление или конструктивизацию.

Естественно рассматривать вычислимые изоморфизмы между вычислимыми структурами. Как было отмечено Мальцевым [30], две изоморфных вычислимых структуры не обязательно вычислимо изоморфны. Мальцев построил две изоморфные вычислимые абелевы группы, которые не являются вычислимо изоморфными. В связи с этим Мальцевым было предложено понятие автоустойчивой структуры. Вычислимо представимая структура автоустойчива, если любые ее два вычислимых представления вычислимо изоморфны [17]. Автоустойчивые структуры часто называют вычислимо категоричными [3].

Итак, мы готовы сформулировать две фундаментальных

проблемы современной теории вычислимых моделей. Первая проблема - это характеризация вычислимой представимости:

Проблема 1. Для данной структуры выяснить, имеет ли эта структура вычислимое представление. Более общо, описать все вычислимо представимые структуры в данном классе структур (например, в классе всех абелевых р-групп).

Вторая проблема - это характеризация вычислимой категоричности:

Проблема 2. Для данной структуры выяснить, является ли эта структура вычислимо категоричной. Более общо, описать все вычислимо категоричные структуры в данном классе структур (например, в классе всех булевых алгебр).

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

0.2 Эффективные алгебраические инварианты

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

Что касается критерия вычислимой представимости, то для нас особый интерес представляют следующие примеры в теории вычислимых абелевых групп. Мальцев [30] охарактеризовал вычислимо представимые аддитивные подгруппы рациональных чисел, и показал, что такая группа имеет вычислимое представление если и только если ее характеристика может быть аппроксимирована вычислимой функцией (мы вернемся к этому примеру позднее, где

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

Другой (значительно более поздний) пример - это описание вычислимо представимых абелевых р-групп, являющихся прямыми суммами циклических групп различных порядков, предложенное Хисамиевым [24]. Хисамиев доказал, что всякая такая группа вычислимо представима тогда и только тогда, когда множество порядков элементарных слагаемых группы имеет монотонную вычислимую аппроксимацию. Отметим, что понятие вычислимой монотонной аппроксимации нашло применение в других актуальных задачах теории вычислимых моделей ([26], [23], [7]), а также активно изучается с точки зрения чистой теории вычислимости ([13]).

Наконец, третий пример - это недавно полученная характеризация вычислимо представимых абелевых групп без кручения, являющихся прямыми суммами аддитивных групп локализаций целых чисел. Проблема характеризация таких групп была поставлена Хисамиевым в [25]. Хисамиев [25] также получил частичное решение этой проблемы для класса таких групп с некоторыми дополнительными условиями. Проблема была решена в [12]. Было показано, что такая группа имеет вычислимую копию тогда и только тогда, когда множество простых чисел, по которым берется локализация, принадлежит уровню арифметической иерархии (классы Е^ будут формально определены ниже).

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

Классическая простота инварианта вовсе не означает, что

доказательства тоже просты, поскольку его эффективные свойства могут оказаться нетривиальными. Как следствие, наличие удовлетворительной классификации для богатых классов структур весьма редки. Например, хорошо известно, что (классически) абелевы р-группы описываются их Ульмовыми типами [14], причем этот факт нельзя назвать трудным. Однако обобщение результата Хисамиева [24], который обсуждался нами выше, на р-группы Ульмовой длины меньше со нетривиально, а обобщение на случай Ульмовой длины > и неизвестно и является открытой проблемой уже около 20 лет.

Для более широких классов проблемы зачастую оказываются чрезвычайно сложными или даже настолько сложными, насколько вообще возможно (см., например, Гончаров и Найт [18]). Для нас особое место занимает следующий результат Доуни и Монталбана [11]. Напомним, что абелева группа без кручения -это такая коммутативная группа, у которой всякий элемент имеет бесконечный порядок. В [11] авторами показано, что проблема изоморфизма для вычислимых абелевых групп без кручения является полной в классе Интуитивно это означает, что вопрос "существует ли изоморфизм между данными двумя вычислимыми абелевыми группами без кручения?" невозможно свести ни к какому более простому вопросу (например, к проверке какой-нибудь формулы первого порядка в данных группах). Другими словами, у вычислимых абелевых групп без кручения не может быть инвариантов, которые описывали бы их с точностью до изоморфизма и которые были бы устроены алгоритмически проще, чем сами группы. Результат Доуни и Монталбана является примером неструктурной теоремы (согласно терминологии, предложенной

в [18]).

С другой стороны, характеризации вычислимой категоричности

для многих богатых классов структур известны. Например, булева алгебра вычислимо категорична тогда и только тогда, когда она имеет конечное число атомов (Гончаров [15]), линейный порядок вычислимо представим если и только если в нем имеется конечное число непосредственных следований (Реммель [39]), и абелева группа без кручения вычислимо категорична в точности, когда ее ранг конечен (Гончаров [16], Нуртазин [37]). Естественно поставить вопрос характеризации тех представителей этих классов, удовлетворяющих более слабым условиям, как предложено в следующем параграфе.

0.3 Обобщения Проблемы 1 и Проблемы 2

Для более глубокого понимания Проблемы 1 и Проблемы 2 полезно рассмотреть их обобщения.

Понятие относительной вычислимости, или вычислимости относительно оракула, является классическим [44]. Оракул для множества А' - это устройство машины Тьюринга, которое разрешает принадлежность натурального числа множеству X. Процедура называется вычислимой относительно X, если она может разрешена при помощи машины Тьюринга с оракулом X. Таким образом, например, можно говорить о вычислимости относительно проблемы остановки. Ясно также, как определить понятие вычислимой относительно оракула алгебраической структуры и вычислимо категоричной относительно оракула структуры [17], [3].

Классическим обобщением Проблемы 1 является:

Проблема 3. Для данного класса алгебраических структур и данного оракула X охарактеризовать все структуры этого класса вычислимые относительно X. Для данной структуры описать все оракулы X, относительно которых эта структура является вычислимо представимой.

Множество оракулов (более точно - Тьюринговых степеней), относительно которых структура вычислимо представима, называется степенным спектром данной структуры [40]. Степенные спектры структур активно изучаются [36], [23], [21]. Особое место занимает пример, предложенный Сламаном [43], и аналогичный пример, построенный независимо Венером [46]. Венер и Сламан показали, что существуют структуры, которые вычислимо представимы относительно произвольного невычислимого оракула, но при этом не являются вычислимо представимыми. Этот пример показывает, что в общем случае невозможно сформулировать достаточного условия на существование вычислимой копии в терминах степенных спектров. Действительно, даже самое сильное из мыслимых условий оказывается недостаточным. С другой стороны, для некоторых естественных классов структур такие условия были получены. Например, хорошо известно, что если булева алгебра имеет представление относительно 1ои>4 оракула, то эта булева алгебра вычислимо представима [27].

Естественным обобщением Проблемы 2 является:

Проблема 4. Для данного класса алгебраических структур и данного оракула X охарактеризовать все структуры этого класса, вычислимо категоричные относительно X. Для данной структуры описать все оракулы X, относительно которых эта структура является вычислимо категоричной.

Говорим, что структура Л является А® -категоричной, если Л вычислимо категорично относительно оракула где п

- это (п-1)тая итерация проблемы остановки. Если известна характеризация вычислимо категоричных представителей данного класса, то естественно поставить вопрос о характеризации Д^

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

известно о - категоричных структурах. Из-за проблем

технического характера полную характеризадию - категоричных структур для естественных классов получить, как правило, не удается. Однако есть целый ряд частичных результатов в этом направлении. Например, в [31] описаны Д® - категоричные линейные порядки и булевы алгебры с некоторыми дополнительными условиями. Кроме того, известно, что - категоричность не

влечет Д^ - категоричности для линейных порядков [1], булевых алгебр [3] и абелевых р -групп [6].

0.4 Класс вполне разложимых групп

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

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

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

порядка вхождения слагаемых [14].

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

0.5 Обзор результатов

Мы начнем наши рассмотрения с необходимых определений и понятий, которые предложены в Главе 1. Все эти понятия являются классическими и могут быть найдены в литературе [44], [17], [14], [28]. Глава 1 состоит из двух параграфов. В первом из двух параграфов напоминаются известные определения из теории вычислимости и теории вычислимых моделей, во втором параграфе содержатся необходимые элементарные основы теории абелевых групп.

Следующая глава (Глава 2) содержит необходимые для последующих глав факты. Эту главу можно считать введением в теорию вычислимых вполне разложимых групп. Некоторые факты, доказанные в Главе 2, являются новыми и отвечают на вопросы теории вычислимых групп (например, Следствие 1 и Предложение 6 являются решениями проблем, поставленных Доуни в [10], см. также [8]). В первом параграфе доказаны некоторые факты о степенных спектрах вполне разложимых абелевых групп. Второй параграф содержит необходимую информацию о вычислимых модулях и их свойствах, которые потребуются в Главе 4. Результаты Главы 2 либо являются элементарными и общеизвестными, либо опубликованы в [35].

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

спектру типа Сламана-Венера ([43], [46]), который упоминался выше. Результат можно считать неожиданным, поскольку (классически) счетные вполне разложимые группы устроены элементарно, в то время как, напротив, модели со спектром типа Сламана-Венера играют роль "монстров" в теории вычислимых моделей. Результат Главы 3 опубликован в [35].

Глава 4 изучает эффективную категоричность вполне разложимых групп. В первом параграфе вводится некоторое новое алгебраическое понятие S - независимости, которое является обобщением классического понятия р - независимости [14], а также доказываются свойства S - независимых подмножеств вполне разложимых групп. Во втором параграфе S - независимые множества применяются для доказательства того факта, что всякая вполне разложимая группа, в которой все слагаемые одинаковые (такие группы называются однородными), категорична относительно О" (или