Эффективные свойства вполне разложимых абелевых групп

Эта работа посвящена изучению эффективных свойств абелевых групп без кручения специального естественного класса: вполне разложимых абелевых групп. Впервые (классически) эти группы систематически изучались в работе Бэра [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 — независимые множества применяются для доказательства того факта, что всякая вполне разложимая группа, в которой все слагаемые одинаковые (такие группы называются однородными), категорична относительно О" (или A3 — категорична). Результаты опубликованы в [32].

Естественно задать вопрос, когда такая группа категорична относительно 0'. Глава 5 содержит исчерпывающий ответ на этот вопрос. Показано, что всякая вполне разложимая группа, состоящая из одинаковых элементарных слагаемых, категорична относительно (У тогда и только тогда, когда всякое элементарное слагаемое кодирует некоторое semi-low множество [44]. Доказательство этого факта разбивается на несколько случаев, в каждом из случаев требуется разные стратегии. В ходе доказательства предложено понятие вычислимой грани для монотонной аппроксимации. Это понятие является новым и (в некотором смысле) обобщает понятие монотонной аппроксимации, принадлежащее Хисамиеву [24]. Результаты получены в неразделимом соавторстве с профессором Доуни, по материалам Главы 5 подготовлена совместная публикация. Опубликованы тезисы [34].

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

Заключительная Глава 6 изучает линейно упорядоченные вполне разложимые группы. В первом параграфе главы показано, что такие группы могз’т кодировать произвольный счетный линейный порядок с потерей скачка. Во втором параграфе главы доказано, что кодирование из первого параграфа может быть использовано для построения серии примеров упорядоченных групп, не категоричных относительно сколь угодно сложных (гипер)арифметических оракулов. Результат второго параграфа контрастирует с результатами Главы 4. Результаты Главы 6 опубликованы в [33].