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

АКАДЕМИЯ 11АУК СССР СИЕ1РСК0Е ОТДШШЕ ИНСТИТУТ МАТЕМАТИКИ

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

ХИСАМИЕВ Назиф Гарлфуллинович

УДК 510.

КОНСТРУКТИВНЫЕ АШЕВД ГРУПП!

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

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

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

Диссертация выполнена в Институте математики и механики

АН КазССР

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

профессор Арсланов М.М., доктор физико-математических наук Ремесленников В.Н.,

доктор физико-математических наук, профессор Романовский Н.С.

Ведущее учревдение - Московский государственный педагогический университет им.В.И.Ленина

часов на ааседаняи Специализированного совета Д 002.23.01 при Институте математики СО АН СССР, г. Новосибирск - 90, Университетский проспект, 4. ''..'"

С диссертацией можно ознакомиться в библиотеке Института 'математики СО АН СС^Р. >. '"

Автореферат разослан "_"_____199_г.

Защита состоится

м

и

199 г. в

Ученый секретарь

ованного совет

д.ф.-м.н

Е.А.Палютин

ОЩАЯ ХАРАКТЕРИСТИКА Р/ТУШ

Актуальность теми. Алгоритмические проблемы в алгебре (проблема равенства, сопряженности, изоморфизма и т.д.) возникли еще до появления точного понятия алгоритма. В начала 30-х годов нашего столетия это понятие било уточнено и получены парвыо результаты по теоря' а.-?оритмоз. На основе этах результатов ^ыли решены ряд важных, алгоритмических проблем, которы не поддавались решента долгое время. Напршшр, II.С.Новиковым [21] била доказана фундаментальная теорема о неразрешимости проблемы равенства слов в тоори-г групп.

С целью привлечения развитой теории алгоритмов для более • широкого исслотования алгоритмических проблем алгебры в 60-годах было введено лоня.пе конструкт- зной алгебраической системы. В работах А.Мостовского [34),[35) , ; .В.Кузнецова [13] , А.£рёлиха и Д.Шефердсона |30] впервые, появились коне руктявнвд систает. В этах работах в качестве основных множеств таких систем рассматривались либо множества натуральных часе.", либо множества слов в произвольном конечном .--тфаните.

С другой стороны з теории алгоритмов и ее приложена! : г>чла известна плодотворность введения геделевских нумераций изучаемых объектов. А.Н.Колмогоров впервые отметил важность изучения всех вычислимых нумераций частично рекурсизных функций. Эта программа осуществлялась в работах В.А.Успенского [26], [27] , Х.Райса [Зб] и Х.Рода.рса [зз] .

А.И.Мальцев в своей основополагающей работе [1?] объединил эти два подхода и ввел, понятие. конструктивной алгебры. Пояснил тго на -фжле^э »руппн. Нумерацией группы ■ называется отображение 1) ; —> (Ц- ¿«ножества всех натураль нах чисел оУ на (у . Пара ((£*_, ) называется конс'*/"к~ тивной группе.:, если существует алгоритм, ном; Ш по шЗам

двум натуральным числам XYI и YI определяет, равны или нот элементы Si\Yl и- S1 УЬ , а тают находит такое число S , чтс равенство = ^ S справедливо в Q- . В этой

же работе А.И.Мальцев сформулировал ряд важных понятий теории конструктивных алгебр и н. хотил программу дальнейших исс 'едо-ваний.

ЮЛ.Ершов [VJ ввел понятие сильно конструктивной модели. Конструктивная модель называется сильно конструктивней, если существует алгоритм, который по произвольной формуле УИП сигнатуры модели Iftfl и по произвольным натуральным числам . YYLопределяет ист1шна или нет формула .. в модели Iflfl . Это понятие привело к плодотворному применению методов теории моделей при изучении конструктивных систем. Оно породило ряд новых проблем, аналогичных пробоемам теории моделей, одни из которых уже решены, а другие еще остаются открытыми. В дальнейшем конструктивные и сильно конструктивные модели начали изучаться в теской взаимосвязи,

В настоящее ь^эмя теория конструктивных моделей - бурно развивающаяся область математики, которая находится на стыке алге 'ры, математической логики и теории алгоритмов. Она находит важные применения в теоретическом программировании и в, : теории баз данных. Существенный вклад в эту область внесли гак советские математики А.И.Мальцев, Ю.Л.Ершов, С.С.Гончаров, М.Г.Пзретятькин, так и рарубелшые - P.Boot, Ы.Морли, А.Нероуд и другие. Основные проблемы и результаты данной области изложены в мое графин Ю.Л.Ершова [э] .

Основными проблемами (см. {5, С.ЗОО}) теории конструк -тивных моделей являются:

1) проблема существования (сильной) ковструктивизации у заданной модели;

2) проблема существования (сильно) конструктивизируемой подели у заданной теории;

3) проблема перекоса, единственности конструктивизаций, и т.д.

Исследование этих проблем проводятся как длч общей теории -оделей, та: и длу ко.деретшх классов алгебр. В настоящее время .зчболее полно изучены проблемы конструктивных булев' ал-

гебр. Основные результаты этой ооласти изложены в монографии С.С.Ггтчарова .

Исследования по теории конструктивных аболевых групп начаты работой А.И.Мальцева ¡I8J . Здесь А.И.Мальцеа следующим образом характеризует проблемы данной области: "остсствонь. возникает общая задача - определить, какие конетру гивные нумерации допускают те или иные аоотрактно задашшо группы, какие из подгрупп -той или иной конструктивной группы является еэ рекурсивными или рекурсивно поречкел; мд подгруппам?., и т.п." Конструктивные абелевы группы в дальнейшем исследовались в раоотах Ю.Л.Ершова, С.С.Гончарова, В.Д.Дзгоева, В.П.Добрица, С.Лин, А.В.Молокова, А.Т.Нуртазина, О.Ричманз, П.Смиса и других.

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

Ochobi тм/ мотолкли являются комбинации методов приоркто-та, теории нумераций и построения групп порождающими элементами и определяющими соотношениями.

Научная новизна. Все основные результаты диссертация являются новыми. В работе ешэна основное проблемы теории конструктивных абелевых групп. Проблема сущестг вания конструк-тивизациЁ абеловой р -группы f\ сведена к оценкаг. алгоритмической сложности подгруппы А элементов бесконечной высоты и. фактор—группы А/А , что является порвнм результатом такого типа з теории конструктивных моделей. п терминах базисных формул, описаны теории абелевых групп, имеющие конструкта визируемые модели. Решена проблема соотношений, конструктиви-зпруемости и сильной коштруктивязкруомасх моделей политix теорий абелевых групп. Установлена соглюшения классов арифметической иерархии дай абелэшх групп без кручения, р-групп и периодических групп. Ка основе по.-гченвйх ■результатов pi лен ряд широко дзвос.-'ных вопросов Теории конструктирчых ; jелевых групп. ' . .

Пра^ткческ"ч и : .оц .¡тическая ценность. Результат!- jx. боти представля-.р теоретический интерес. Ок« нашли применения в ть -ории конструктивных полей и общей теории нумераций. На оо..."че результатов д. ¿сертации были прочитаны спецкурсы в Казахском Государственном Университете.имени СЛЛ. Кирова и написаны дчп-

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

■I т>обация работы и публикации. Содержание диссертации п. частям докладывались на общегородском семинаре "Математическая логика" г.Алма-Аты, на итоговых конференциях Института математики и механики АН КазССР; на семинарах "Теория нумераций", "Теория конструктивных моделей", "Алгебра и логика" Но-1 сибирского Университет«, на общеинститутском математическом семинаре ИГЛ СО АН СССР, на "-й Всесоюгчой школе по прикладной логике; на П - IX Всесоюзных конференциях по математической лс ико; на XII - XIX Всесоюзных конференциях по алгебре; на Международной конференции по алгебре, посвященной памяти А.И.Мальцева (1309-1967); на пленарных докладах 6-й и 8-й Всесоюзных конференциях по математической логике. Все основный результаты опубликованы в статьях [41 - 60] . Результаты совместней работы {41^ получаны в нераздельном соавторстве. Остальные результаты диссертации получены лично автором.

Объем и структура работы. Диссертационная работа состоит из введения, трех глав, разбитых на 13 параграфов и списка литера ...уры, насчитывающего 90 наименований. Общий объем работы 293 страницы. , "

СОДЕРШШЕ РАБОТЫ

■ В дальнейшем под словом "группа" понимается не более чем счетная "аоелева группа". Напомним необходимые в дальнейшем определения. Пусть "У - геделева нумерация всех формул групповой сигнатуры б* с переменными из множества \ • \ • Через . обозначим формулу номера Иг- , свободные переменные которой могут быть только среди 'Ц^. По дгчной нумерованной группе (А;т)) определим множества

Пусть - некоторый класс подмножеств мнок г:ва Ц?* . Пара ( А^ ) называется (сильно) -копструктклпой, если

множество ( ^ ("А)) 0 ^ (*А) принадлежит Ц, . Если класс состоит из множеств рекурсивных относительно одного и того ко множества X , то вместо " % -конструктивна" гово рят " X -конструктивна". Группа А называется 'сильно) ^ -конетруктивлзируемой, если существует такая нумерация ч) группы А , что пара (А,"'?) является (сильно) ^ -конструктивной.

Пусть ЦТ - частично рекурсивная относительно июже-ства Л функция, имеющая клшшев номер УЬ . Множество

X — ^ УЬ | ^^(и)-определенаназывается скачком множества X . ДЧЯ ЛЮбОГО И £ иУ ПОЛОЖИ?'!' X = X , Х(П+^(Х(а>)/ • Как обычно г^П^Д^о.

обозначают классы арифметической иерархии множеств.

Пусть для. функции С ь, эс,) ■ справедливы условия: I) для любого I. одноместная функция от

ОС является ^убывающей; 2) для любого и существует

- УУ1 • . Тогда £ назовем §-функцией. Ее-эс иг

ли же кроме этого верно <. <. • . . , то 4- назовем -функцией. Положим

{< т.. к > V.. ик ( = ...ИгСк * т)},

П-"оть груша А изоморйиа (+) 7 ц ■, где 2 _ к.. -

... р V Р "

циклическая группа порядка р С- . Тогда множество

Ц < иг, к > | 2 V . Лк = • = =

назовем характеристикой группы А

Глава I посвящек- проблеме существования (сильной1* •".он-структивизг жл у заданной грулпы. Она • устоит-из §§1-7.

3 §§ I - 2 данная проблема сведена к таковым пробльпм для р -груг-г и груш без : ручения.

В §§ 3 - 6 эта проблема рассмотрена для -групп. На-

ломним определение ульмовцх инвариантов р -группы а .Через А™ обозначим подгруппу группы А , состоящую из элементов бесконечной шсоты. Если б7 - ординал, то б'-я ульмова

а С л о л

подгруппа А определи тся следущш образом: А — А ,

^А5" ^ ; если б' - предельный ординал, то А -

/"Ъ ы . Ульыовой длиной или типом и.(А) группы А

называв "¡я наименьший : одинал ^С , для которого верно л<гГ , д

= А • Для любогг 6> Ч/ фактор-группа ~

а7а

, в

называется С* -м ульмовым фактором группы

А . По теореме Прюфера любой фактор А разлагается в прямую сумму циклических групп. В частности, если и,(А)=.£, то А - прямая сумма циклических и квазициклических групп. По известной теореме Ульма любая редуцированная р -группа А однозначно определяется своими ульмовыши факторами. Характеристики ульмовых факторов А ^ пазовом ульмовыми инвариантами группы

В 197? году Ю.Л.Ершовым была поставлена проблема нахождения необходимых и достн точных условий на эти инварианты для (сильной) конструктивизируемости р -группы А , имеющей конечную ульмсву длину.

В § 3 эта проблема решена для р -группы, ульмов тип которой равен 1 ,

ТЕОРЕМА 3.1. Пусть р -группа (г изоморфна

сЬ ^ и? , гдо а - прямая сумма циклических групп. Тогда (у- сильно X -конструктишзируема в том и только в том слу .¡о, когда характеристика группы А рекурсив-

на.

ТЕОРЕМА 3.2. Пусть &■-

прямая суша циклических р -групп, порядки которых небграничоны в совокупности. Тогда От X -кэнструктивизируема в том и только в том случае, когда выполнен.* у товия: ^

1°. характеристика б") принадлежит классу ;

2°. ."тцест. 'ег. такая X -рекурсивная Ъ^ -функции

, ЧТО С

Следующий результат даот еще одни критерий ¡счструктиш-г-зируемости прямой суммы циклических и квазацякллчосклх групп. Пусть .^ункция ноубывзот. Е<-та но существует

у.) , то положим fem. £ ( ос, yj- со . Пусть Р -

множество всех простых чисел. л

ТЕОРЕМА 3.5. Пусть группа А разлагается в прямую сумму циклических и квазпцлклпче .сих групп. Тогда /\ У -копструктиБИзлруе.ма в том и только . том случае, когда существует такая X-частично рекурсивная функция ,

реР . от 3-х арг^лентов pj3cj ^ . что выполнены условия:

I. для любых чисел 2 , осли значе-

ние определено, то оиродолено и

3 § 4 дано решений упомянутой проблемы Ю.Л.Ершова. Первоначальное доказательство этого результата, было сложным. С.С.Гончаровым Jbura высказана гипотеза о возможности упрощения этого доказательства посредством установления связи конструк-тивизируемости р -группы А с оценками алгоритмической

сложности подгруппы г\ а фактор-группы

А/А*

. Иксе

следующие теоремы 4.1, 4.2 и их слодс.лш 4.1 - 4.4.С показывают справедливость этой гипотезы. Они являются основными результатами данной главы. д

ТЕОРЕМА 4.1. Пусть р - группа не является прямой суммой циклических и квазициклическлх груп*-. Тогда А X -конструктивна ируема 'S том и только в том с у чае, когда, ее под -группа А . состоящая из элементов бесконечной высоты,

X ' -конструктивпзируема,.а фактор-группа А/А X -конструктивна ируема. •■ . '. ' ■

ТЕОРЬДА 4.2. Пусть группа а такая же как в теореме

1.1. Torjri А сильно Х-Уонетруктивизируема в том . г^ль-

Д-

ío в том случае, когда ее подгруппа М Л -конструктивен-'

руемз, а фактор-группа А/А сильно X-конструктивлзи-' руол-.а.

Приводам некоторые следствия этой тоорош, которые отвечают "а рад известных вопросов теории конструктивных групг. Слэдстзкя 4-Х - 4.4,С. решают вышеупомянутую проблему Ь.Л.Ер-. шова. Если не оговорено противное, то во всех нижеприведенных следствиях через А обозначена р -группа, ульмов тип Ц.(А) которой конечен и равен УЬ .

СЛ£ .ЗТВлЕ 4.1. Ред. доровашгая группа А X -конструк-тиапзируема тохда и только тогда, когда ее ульмовы факторы

АI , и < п. , являются ХС ' -конструхтивизируешш груп-

l-.mii.

СЛЕДСТВИЕ 4.1.0. Редуцированная группа А сильно X -конструктиьизируема тогда и только тогда, когда ее нулевой ульмов фактор А сильно X -конструктивизируем, а

А , • V (?Л-±)

ульмовы (¿акторы /~» ^ ,'1^1, , д • -конструкти-

шзируа.л. " «)

СЛЕДСТВИЕ 4.". Пусть р -группа А равйа а©2Гроо ,

г^е Я, - аудированная подгруппа. Тогда А X -конст-рук" визируема в том и только в том случае, когда ульмовы факторы , С «£ П.-± , группы Я/ -конструкти-

визг уемы, а характеристика С ^ ) есть 21 -множество.

СЛЕДСТВИЕ 4.3.С. Ьусть группа А такая же. как и в следствии 4.Я. Тогда А сильно X -конструктивизируема в том и только в том случае, когда нулевой ульмов фактор сильно X-конструктивизируем и для каждого ь ,1 й С <У1-± ,

о Ч/ ;

ульмовы факторы 'Ь/ ' -констр^ктивизкруемц, а

хар .ктерястика ( Я- есть "¿Е. -шожвство-

СЛЕДСТВИЕ 4.4. Пусть О -группа А равна

о со • I ' • редуцированная подгруп-

па. Тогда А X -конструктивизируема в том .« только в том случае, ко: ,а ее -эд^цированная часть й. X -конструктивизм уема.

:о

СЛЕДСТВИЕ 4.4.С. Пусть груши Ач такал ко г к и в следствии 4.4. Тогда А сильно Х-чонструктивкзпрусг/я в ток и только в том случаю, когда ее редуциропг .нал часть Я. сильно X -конотруктпннзируема.

С.С.Гончаров в £[] сформулировал следующие два шьроса:

1. в каких случаях из конструктпвиаируемости гоуаяы А следует конструктивпзируемость ег редуцированной и делимой частей? %

2. если декартов квадрат Ьг гоупгш (г" конструктиви-зируем, го будет ли сама группа 0" конструктивизируемой?

Эти вопросы аналогично, можно сформулировать и для случая сильно конструктивизируемих групп. С.С.Гончаров, В.П.Добрица

[3] построили пример конструктивизируемой периодической группы, редуцированная часть ко.ор^й не .конструктивизируома.

Рассмотрим 1-ый вопрос Гончарова для класса р -групп, име'тцих конечные ульмовн тмин. Следствия 4.3, 4.3.С указывают случаи, когда редуцированная часть (сильно) конструктивизируемой группы А из % (сильно) коиструктг-визируема. На основании теорем 3.2 и следстьия 4.4 для любого П 6 иХ пострс на такая конструктив;«ируемая группа А № , что ее редуцированная часть но констр., ктивизируема и ульмов тип Ч-(Ац-) равен П . Аналогичное верьо и для сильно

конструктивизируемых групп. Таким образом для рассматриваемого класса групп 1-ый вопрос Гончаров^. решен полностью.

Рассмотрим 2-й вопрос Гончарова. Как показал В.Д.Дзгоев

[4] , ответ на этот вопрос для класса групп без кручения отрицателен. Положительный ответ для вышеупомянутого класса Дает ' к'

СЛЕДСТВИЕ 4.6. Конечная прямая стс чэнь а группы (сильно; X -конетруктивизиру ема тогда и только тогда, ..огда а (сильно) X -конст^уктивизируема.

СЛЕДСТВИЕ 4.Пусть, а x -конструктивизир'емая Р -групла, имевдая произвольный ульмов тип о'-.шчный от I, Тогда существуют таки- Ч-конструктивизируемыэ группы и Е , чтг А = В4©Е и группа 8Д> есть прямая сумма

циклических групп, порядки которых неограничены в совоку^ -ности. ■

^тс следствие ость конструктивный аналог известного тео-рст.'—.о-группоЕОГо результата о том, что любая счетная р -группа есть прямая су.сла двух своих нетривиальных подгрупп. Аналог сдьдствня 4.5 такке сь^аводлив для случая сильно ко!' -т-руктивизируемых хрупп.

Легко доказать, что группа из следствия 4.5 неав-

тоустойчива. Поэтов по следствию 4.5 имеем, что автоустойчи-выш р -группами могут б,ттъ только пря.ше суммы циклических к квазициклпчсскнх групп. Отсюда модно получить новое доказательство известных результатов С.С.Гопхарова [[I]] и П.Смиса [ЗЭ] об автоустойчлвых р -группах.

СЛЕДСТВИЕ 4.7. Если р -группа А (сильно) X -конст

руктивизкруема, то для любого 5 < \ъ фактор-группа А/А5 также (сильно) X -конструктивизируема.

Показано, что это следствие неверно при Б-Уь.

СЛЕДСТВИЕ 4.8. Если р -группа А сильно X -конструк-тигизкруема, то ее редуцированная часть X" -конструктивизиру* ема.

Следунцх™ результат .используется в главе 2. Он показывает, ч о следствие 4.8 в общем случае нельзя усилить.

СлЕДСТБгЛЗ 4.9. Пусть В - некоторая сильно Х-конст--руктлвизируемая р -группа бесконечного периода, которая разлагаем .я в пря;лую сумму циклических групп. Тогда существует сильно X -конструктизлзчруемая р -группа Н такая, что шполкены: I) ульг-лов тип II ( Н ) равен 2; 2) нулевой уль-мов фактор Н0 изоморфен группа В ; 3) редуцированная-часть Я» групгш Н не сильно X -конструктивизируема.

Из теоремы 3.1 следует, что в этом следствии нельзя понизить ульков тип до I.

Следующей результат такие необходим в дальнейшем.

СЛЕДСТВИЕ 4.10. Существует сильно X-конструктивизируема я редуцированная р -группа А, такая, что выполнены: I) ульмов тип И ГА) равен 2; 2) подгруппа но кон -

структивизируема.'

В § 5 даны дс гаточкые условия на ульмовы инварианты ра-X. дарованной р -гр-чп„ А (произвольного ульмового типа) для л (сильной) конструктивизичуемости (теоремы 5.1, 5.Г\ а такя.е Дч,«а ¡но, что уль. т-п —жстр^кгпвизир—щой

р -группы ость коиструктяшзируешй ординал (теорема 5.3). Теоремы 5.1, ¿3.3 получены совместно с В.П.Добрииа, АЛ'.Нур-тазиг-тм jjiy в нераздельном соавторство.

В § 6 дан критерии сильной конструктивизируокостл р -группы А (произвольного ульмового типа) на язык13 иорог-данцих элементов и определяющих соотношений» который приме .зн для решения вышеупомянутого 1-го вопроса С.С.Гонч рою. Понятие р -базиса, введенное Л.Я.Куликовым [I4J , играет важную роль в теории групп. В дальнейшем такой базис назовем р -базисом Куликова. Оказывается сущестг 'ет тесная связь между конструктпвлзируол'остью группы с алгоритмом делимости па р"'", У1 б UX , и существованием в ней рекурсивно перечислило го Р -базиса Куликова.

ПРЕДЯОйШЕ 6.1. Если конструктивная группа ( А, "\> j имеет рекурсивно перечислим^ р -базис Кулик-"за, то в (А^ алгоритмически разрешима проблема делимости па tt.e.10* ,

Кодгруп; i В группы А , пороздешая некоторым р-оазисом назовем р -подгруппой Куликова. Для р -групп р -базис и р -подгруппу Куликова просто называют базлсом к подгруппой Куликова. Следующая теорема показывает, что для р -трупп взрно утзорнд&ние, обра-ное лредложз"кю 6.1.

ТЕОРЕЛА 5.1. Пусть для конструктивной -группы (А^) j алгоритмически разрешима проблема делимости. Тогда .зкоторгт подгруппа Куликова группы А рекурсивна.

Показано, что эта теорема для конструктивных групп неверна. С помощью теорем 6.1 доказана /

ТЕ0РЫ.1А 6.2. Для сильной конструктивизируемости р -группы А необходимо и достаточно, чтобы А была задана порождающими Q.^ > Cj^ J ¿<сС_, к си/и определяющими соотношениями

oL, р S U7+ ± , поргдок I р ^ и функ-

13 •

ции = =

,1 зюжество М - | Уп, 5 > | 3к,- • • (Я; = . .. =

П15 = Гп) ^ рекурс-вш.

Элементы } С ^ , определенные в этой теореме,

называют квазибазисом группы

СЛЕДСТВИЕ 6.1. Любая сильно конструктивная нумерация ^ р -гру1._-Ы А рекурсивно эквивалентна нумерации [Л , определенной некоторым квазиба^исом.

На основании теоремы 6.2 получено следу идее усиление с тедствия 4.4.С .

ТЕОРЕМА 6.3. Пусть делимая часть произвольной р -группы А имеет конечный ранг. Тогда А сильно конструктива -зируема в том и только в том случае, когда ее редуцированная часть сильно конструктивизируема.

Этот результат и следствие 4.9 полностью отвечают на 1-й из вышеприведенных, вопросов С.С.Гончарова для случая сильной конструктивизируёкости в классе р -групп.

ЗАМЕЧ"ТМЕ. Теоремы 6.1 - 6.3 и следствие 6.1 справедливы ,-ля Ко-групп без кручения.

В § 7 рассмотрена проблема существования конструктивиэи-руемости для групп без кручения. А.И.Мальцев [18] описал коногруктивлзируешв группы без кручения ранга I. А.Г.Курош . [31] и А.И.Мальцев [1^] установили соответствие между классом неизоморфных групп без кручения конечного ранга и некоторым классом матриц с р -адическими числами. В.П.Добрица [5] показал, что группа без кручения конечного ранга конструктиви-зирудма тогда и только тогда, когда соответствующая ей матрица эффективно задана. В данном параграфе получено описание конструктивязируемых групп без кручения произвольного ранга на «зыке порождающих элементов и определяющих соотношений. В качестве приложения этого результата доказано существование главной вычасхт~юй нумерации класса конструктивных групп без кручения с алгоритмами линейной нез^ зисимог

В гл">ве 2, состоящей из §§8-11, рассмо'нэены проблемы существозг .ия ко' "5т^уктивизируемой модели у заданной теории и соотношения ко не трук ти визиру емос ти и сильной '.онст- ■

руктивизируемости. Основными результатами здесь являются теоремы 8.1 и ЮЛ. Методы доказательства этих теорем применены для ответа на вопросы С.С.Гончарова и А.^акинтайра. Далее рассмотрены вопросы- переноса конструктивизаций на подгруппы и фактор-группы.

Для формулировки результатов § 8 введем следующие обо -значения. Известные инварианты В.Емэлевоп <=1р п С^О.» >

^рС^) группы 0" определяются через базисные формулы "^Р^К > и' (?Р >ь1<. (СМ. у, с.15б]).

Пусть Т" - некоторая полная теория групп. Положил

Г(т) ={< т>

Множество р , состоящее -з пар чисел <Р_,К>,К>|3/ называется "Г -расширением множества- Р» если выполнены условия: I) ' ; 2) если 4 ъ,К> <=: Г '

Г(т) , то р^Р(Т); 3) если <р,К>£Г' ,0<5<

К , то -Ср,$>6 Г' , _

ТЕОРИЯМ. 8.1. Полная теория 1 групп имеет конструктиви-зируемую модель тогда и только тогда, когда выполнены условие. I) А (Т ) £ 2ГI ; 2) 8(Т ) 6 211 ; з) множество V С ) имеет "г -расширение Г £ 21 о •

л %

СЛЕДСТВИЕ 8.1. Если группа (у элэментарно эквивалентна своей периодической части, го теория *Т группы иыет -

конструктивизшуемую модель ">гда и только тогда, логда

** « — О ~ ¿ "т

СЛдГчСТВ'ЛЕ 4.4. Любая -теория I групп без кру-

»V

чешш имое? конструкткзизируемуа модель.

Пока: ;но, что все условия теорема 8.1 существенна, В § 3 рассмотрены вопроси (сильной) кокструктявлзируе-мо^ти простых а насыщенных моделей теории групп.

ПРЕ^ЛОЕШЕ 3.2. Су. '¡ствуот колкая теория р -групп, которая имеет конструктявизируему» модель и простую .кодажь ко (?■ г конструктивизируема.

П?ЕдЛ022НИЕ 9.4. Пусть полная теория "Т* групп имеет ка-сиагчн/и модель. Тогда следующие условия эквивалентны:

1. существует конструктивпзлруемая группа теории ' 2 ; 2 все счетные шдела теории "Т" сильно канехруктивп-

зирун:.ы;

3. теория Т разрешена.

В § Т.С описаны полные разрешимые теории, у которых згахс-дая конструктиви-чруемая модель сильно конструктивизиру-ома.,

ТЕ0?Е.7А 10.1. Пусть группа А имеет разрешимую теорию. Если имеет место хотя бы одно из еле пущих условий;

для некоторого простого числа р множество

11г I ^ Р,, 1г ( А ) ф О бесконечно,

2. м кество р | (А) бесконечно;

3. для некоторого простого числа р верно равенство

то существует консгруктквизируемая, но не сильно конст-

руктквизируемая группа А , которая элементарн.. эквивалентна Р .В -ро'пгаком случав из кокструктивизируемости группы А следует ее си ¿пая конструктивкзируемость.

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

П.и.Гончаров на дне проблем.5-й Всесоюзной конференции по математической логике сформулировал такой вопрос: конст-

руктивизяруеыа ли редуцированная часть конструктив;! .груемой вдцгщ без кручения?

СЛВДСТЖЗ ПЛ. Существует такая сильно У\ -конструк-тивизируомая группа без кручения, что ее редуцирования часть не -консг чукти-нзпруема.

Г-Е.;-ВД на дне проблем 7-й Всесоюзной конференции по мате?-ЩТЛчес!;оп логике сообщал следуиций вопрос А.Маккнтайра: конструктнвлзируемо ли упорядоченное поле примит. зко рекурсивных вещественных чисел?

СЛЕДСТВИЕ 11.4. Любое упорядоченное поле вещественных чисел, содержащее поле всех примитивно рекурсивных веществе!, них чисел, не конструктивпзируемо.

Далее рассмотрены вопросы переноса конструктивизации группы на подгруппы и фактор-группы. ,

ТЕОРЕМА 11.1. Пусть фактор-группа 0"/Т группы Ог по ее периодической части Т имеет конечный ранг и индекс подгруппы Н в £- конечен. Тогда группа 0- (сильно) конструктивизируема в том и только в том случае, когда по; -группа Н (сильно) конструктивизируема.

. Показано, что условие конечности ранга факторгруппы (г/т в этой теоремо существенно.

А.И.Г.'эльцевш [ХЗ^ показано, что периодическая часть конструктивизируекой "руппы (г конструктивизируема. А.Т.Нуртазин [23^ доказал, что эте же верно ~л для факторгруппы 0-/ Т .3 заключении главы 2 доказано, ч^о эти результаты не переносятся .для случая сильно конст"-/ктивизиру-емых групп.

Глава 3 посвящена исследованию соотношений между классами арифметической иерархии групп. В теории рекурсивных функций важную р.-ль играют классы } П,' ; ИбО? ,

арифметической иерархии множеств. Пусть У обозначает один из этих классов. Если 1Я, - -^который класс групп, то через 'Н- (У) обозначим У -конструктивизируемые группы из Щ, . Классы ЩУ) образуют иерархию групп для . Естественно гозникае" проблема исследования соотношений классов ^(УJ . Л.Фвйнер [[29]] у чазал, что су -¡ствурт ^ ^ -констъуктизи-

зируемая г-*лева алг 'ра, ко'" рая н^ конструх.дпм. ада.

л!«1!.Одинцов, В.Л.Сь. .Иванов <] установили, что любая

-конструктивизируемая булева алгебра 2Г ^ -конст-

.руктивизируемл.

В § 12 установлеш соотношения между классами арифметической иерархии групп без кручения. Для этого оказалось весь-Жг полезней следующая тео"эш, которая обобщает теорему Доб-■рида - Иуртазпна о существовании конструктивиза-

ции с рог.-'рсивно перечлслимым базисом. Ока является основним результатом этого параграфа.

ТЕОРЕМА 12.1. Пусть (- (сильно) X-конструктивная группа и В - такая ее X-рекурсивно перочислимая подгруг-а, что фактор-группа А/ 8 без кручения. Тогда существует нумерация , группы А для которой справедливы следуздие свойства: 1) группа (А, [И ^ (сильно) X -конст -руктивг:а; 2) подгруппа Ё> X -рекурсивна в (А^ ; 3) существует такая X -рекурсивно перечислимая система элементов | Х^- ь (А,/VI) , что смежные классы

+ в} состаг./шя максимально ли эйно независимую систему альментоз в фактор-группе а/в.

Показано, что все условия этой теоремы сущоствешш.

СЛЕ£СТК1Е 12.2. Если (А^) - X -конструктивная

группа без кручения и В - ее -рекурсивно перечислили серзантная : дгоуппа, то фактор-группа а /в x -конст-рукт—ё/зируома. ^

СЛЩСТВЖ 12.3, Любая 21 ^ -конетруктивизпруомая группа боз кручения X -конетруктивизпруема.

ЩВДСТРЧЕ 12.4. Любая рекурсивно перечислило определенная группа без ;ручония конструктиаизируема.

И.В.Латкин [15^ анонсировал, что последнее следствие для 2-х ступенко нильпотентных групп без кручения неверно.

ТЕОРЕМА 12.3. Пусть ££ - класс.групп без кручения. Любой класс арифметической иерархии для <6 совпадает дяя некоторого ' . >: О с классом {£г(Г|° ) . Схема включений мевду этиш. классами следувдая: ^

В § 13 рассмотрена иерархии периодических групп. ТЕОРЕЛА 13.1. Пусть СГ0- класс групп, которь- разллга-ются в прямые с;, мы ц 'лических групп. Тогда все классы иерархии для й0 различны.

Показано, чг:о в иерархии дая ос, , в отличие от иерархии множеств, теорема Поста не верна, т.о. сущ. .¡твует некон-структувизируемая группа А из класса (Х0 , которая одновременно и П1 -конструктивизируема.

ТЕОРЕЛА 13.2. Пусть 01р - класс р -групп, которые

разлагаются в прямые суммы циклических и квазициклических групп. Тогда любая Дц^^ -конструктивпзируеиля группа из

Щр П1г -конструктивизируема. Схема включений классов

иерархии для 01 р следущая;

При доказательства теорем 13.1 и 13.2 установлены различные критерии X -конструктивизируемости групп, которые представляют самостоятельный интерес.

ЛЙТ'ЗРАТУРА

1. Гончаров С.С. Автоустойчивость моделей: и абелевйх групп//Алгебра и лс ика, - 1930. - Т.19, .'cl. - С.-23-44,.

2. Гончаров С.С. Счетные булевы алгебры. - Новосибирск:: Kai Сиб. отд-ние, 1088.

3. 1~нчаров С.С., До^лца B.ÏI. Пример конст^^ктнййой' абалевой группы с неконструктивизпруемэй редуцированной й'од-группой/."аз. докл. 4 Всесоюз. конф. по мат.. л&гик&> Кишинев, IS76. - Кишинев, 1976. - С.33.

1. Дз^оез В.Д. Конструктивизации прямые произведении алгебраических систем //Алгебра и логика. - 1982:-Ji 2. - ..138-143.

•5. Добраца В.П. О конструктив..зациях абёлеваг грущ// Сис.мат. ж урн. - IS8I. - Т.22, №3. - С. 203-2131.

6. Дзбрпца В.II. Некоторые копструктпв;:зац:гп; абзяешх групп //Сиб. мат. яурн. - 1983. - Т.24, -G'.-lâ-25..

7. Ершов 'Л.Л. КокструктпЕНые модели /Дзбранше -вопросы ал ;бры и логики. - Новосибирск, 1973. - 0.1X1-130.

8. Ершов Ю.Д. Теория нумераций. - М. : Наука,. 1977..

9. Ершов Ю.Л. Проблема разрешимости и конструктиввде модели. -".: Наука, 1980.

10. Ершот< Ю.Л., Палюти Е.А. !.!атематическая логикам 2-е /.д. -М.: ..аука, 1987.

11. Каргаполов М.Л., Мерзляков Ю.И. Основы теории групп. - 3-е изд. - I.!.: Наука, 1982.

12. Кузнецов A.B. О проблемах тождеств и фукъ /анальной полноты для ал: браических систем //Труды Ш Всесоюз. матем. съезда. - Т.2, M. : 1958. - С.145-146.

13. Кузнецов A.B. Алгоритмы как операции в алгебраических системах //Успехи мат. наук. - 1958. - Т.13, Jf 3. -

С.240-24".

!.. Куликов А.Я. К теории абелевых групп произвольной мг-даости./Аат. сб. - 1945. - T.I6, 31. - С.129-162.

IS> И.В. Иерархии нильпотентных групп без круче-

ния //Тез. Докл. 9 Всесоюз. конф. по мат. лотке, Ленинград, 1588. - Ленинград: 1988. - С. SI.

16* мальцев А.И. Абелевн группы коночного ранг без :ру-чею1й/Л(з¥ем, С - Io38. - Т.4, Jé I. - С.45-67.

VIi ЙаЛьц&в А.И. Конструктивные алгебры /Дспехи мат. на*!«, 1961. - Т. 16, й 3. - С. 3-60.

1&.í Мальцев А.И. О рекурсивных абелевых групг->х //Докл. Ml ШЯ?, - 1962. - Т. 146. й5. - С. IC09-I0I2.

Í9V Мальцев А.И. Алгоритма и рекурсивные функции. - 2-е йёй* Наука, 1986.

20* Молоков A.B. Простые модели теории групп //Некоторая 6ро<5йемы и задачи алгебры и анализа. - Н^восибир ч, í9Wr О, Ш-П9.

25, Новиков П.С. Об алгоритмической неразрешимости про'бЖ5й!¥ ФоАдоотва // Докл. АН СССР. - 1952. - Т.05, Jé 4. -с, láv

fe-, Йуртазин А.Т. Bi делимые классы и алгебраические усуговяй автоустойчивостн: Автореф. дисс.,. Канд. физ.-мат. наук 0f.-0I.06. - Новосибирск, 1974.

23. Нуртазин А.Т. О конструктивных группах //Тез. ;,окл, 4 Всесоюз. конф. пс мат. логике, Кишинев, 1976. - Кишинев, 1976. - С. 106.

24. Одинцов С.П., Селиванов В.Л., Арифметическая иерархия и идеалы нумерационных булевых алгебр // ,иб. мат. яурн. - 1988. - т. 30,Л6. - С. 140-149.

25. Поретятькин М.Г. Сильно конструктивные модели и нумерации булевой алгебры рекурсивных множеств // Алгебра и логика. - 1971. - Т. 10, JS. - С.435-557.

26. Успенский В.А. Системы пэрачислимых множеств я их нумерации //Докл. АН СССР. - 1955. - T.I05, Й6. - C.II55-II58.

27. Успенский В.А. О вычислимых операциях // Докл. АН СССР. - 1955. - 103, J®. -С.773-776.

йсЗ. Успенокий В.А. Лекцт'ч о быч.^лимых функщ х. - М.:

г з, 196и.

29. Feiner L. Hiera hies of Poolean algebras//J. Symbolic Logic. - 1970. - Vol. 35. N3. - P. 365-373.

30. Frcehlich A. . Shepherdson J. Effective procedures in field theory//Phi 1Л. ans. Roy 5oc. , London. - 1955. - Ser. A248. -P. 407 -432.

32. Kurosh A. G. Primitive torsionfreie Abelshe Gruppen ,vcm endl ic,.en Range// Ann. "ith. - 1937. - Bd. 38, N1. - 5.175203.

32. ' in C. Recursive presented abelian groups: effective p-group theory //J.Symbolic logic.- Vol.46, N3.- P.617-624.

Xi. Lin C. The effective content of Ulm's theorem// Aspects Effective algebra - Clayton, 1979. - P. 147-160.

34 Mostowski A. On models of axiomatic systems //Fund. Math. - 1952. Vol.39, N1. - P. 133-"58.

35. Mostowski A. On a system of axioms which has no recursivel" enumerable arithmetic model //Fund. Math. - 1953. -Vol.40, N1. - P. 56-5?.

36. Rice G. Classes of recursively enumerable sets of position problems //Trans. Aner. Math. Soc. - 1353. - Vol.74, N2. - P. 35^-366.

37. Richman F. The constructive theory of countable abolian p-group // Рас. J. Wath. - 1973. - Vol.45, N2. -P. 621-637.

38. Rotters H. Codel numberings of partial recursive functions// J. Symbolic L^ic. - 1Q53. - Vol.23, N3. -P. 331 341.

39. Smith P. Two theorems on autostability in p-groups // Lect. Motes Math. - 1981. -.859. - P. 301-311.

40. Szmielev V. Elementary properties of abeb л groups// Fund. ..л1Ь. - 1Р^5. - Vol.41, N2. - P.201-271.

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

41. Добрпца В.П., Нургаэлн А.Т., Хисаилев К.Г. 0 инструктивных периодических абелевы^ грушах //Сиб.мат.журн. -1Э78. - 1.19, 0&. - С.1260-1265.

4<.. Хисамиев З.Г., Хисамиев Н.Г. Неконструктивизируекость рег-'цированной части сильно конструктгвной абелевой группы

без кручения //Алгебра и логика. - 1985. - Т.24, Ж. - C.I08-118.

43.<Хисамиев Н.Г. Сильно конструктивные модели разрешимой теории //Лзв. AJI КазССР, сер. физ.-мат. - 1974. - Ж. -С.83-64.

44. Хиеамиоь Н.Г. J периодической части сильно конструк-тивизируемой абелевой группы //Теоретич. и прикладные задачи мат. и mx¿ - Алма-Ата, 1977. - С.299-303.

45. ХИсамиев Н.Г. О сильно конструктивных периодических абелезых fp^tinax /Д1зв. АН Каз.ССР, сер. физ.-мат. - 1978. -С.58-62,

46.- Хкйамиев Н.Г. О подгруппах конечного индекса абеле-вых гру'гй //-Йв. АН КазССР, сер. физ.-мат. - 1979. - JS 3. -С.43-47»

47» ЗСйёамиев Н.Г. Конструктивизируемый ординал сильно конструк^Шзируем / Ред. журн. "Сиб. шт. журн. " - Новосибирск, Ш9< - 12 с. - Деп. в ВИНИТИ 13.04.79, 'Я604.

481 Хисамиев Н.Г. Критерий конструктивизируемости прямой суммы циклических Р -групп//Изв, АН КазССР, сер. мат. - IS8X. - Ж. - С.51-о5.

49. Хисамиев Н.Г. Сильно конструктивные абелевы р -группы // Алгебра и логика. - 1983. - Т.22, 82. - С.198-217.

50. Хисамиев Н.Г. Связь между конструктивизируемостью и сильной конструктиви^ируемостью для различных классов абеле-вых групп // Алгебра и логика. - 1^84. - Т.23, № 3. - С.305-321.

. 51. Хисамиев Н.Г. Не сильная конструктиви^ируемость фактор-группы абелевой группы по ее периодической части // Тез. 8 респ. межвуз. науч. конф. по мат. и мех., посвящ. 50-летию Казахского университета имени С.М.Кирова, Алма-Ата, 1984. -4.1, Алма-Ала, 1984. - С.202.

52. Хисамиев Н.Г. Теория абелевых групп о конструктиву ш моделями//Сиб. мат. яу~ч. - 1986. - Т.27, й 4. - С.128-143.

53. Хисамиев Н.Г. Иерархии абелевых групп без кручения //Алгебра и логика. - 1986. - Т.25, F*. - C.205-22R.

54. Хибамиг - Н.Г. Неконсг уктизт"зируемость некоторых уп^рядоч-лных полей -вещественных ч ^ел//Сиб il.¿ урн. -l^^i, i

ZL

Т.25, 5 5. - С. Г93-195.

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

56. Хисамиев Н.Г. Арифметическая иерархия абелевых групп //Сиб.мат. журн. - 1988. - Т.29, .Кб. - С ..144-159.

57. Хисамиев Н.Г. Критерий конструктивизируемости аболозой гругмн без кручения //Тез. докл. 9 Всесоюз. конф. по м£ логаке, Ленинград, 1988. - Ленинград, 1988. - С.168.

58. Хисамиев Н.Г. Конструктивные редуцированные абелевы Р -группа ,/Тез. докл. мазд. конф. по алгебра, посвящ. памяти А.И.Мальцева (1909-1967), Новосибирск, 1989. - Новосибирск, 1969. - С.147.

59. Хисамиев Н.Г. Конструктивные абелевы р -группы. -

, Новосибирск, 1989. - С.51. - (Препринт/АН СССР. Сиб. отд-ние. Ин-т матметики; З-.'.

60. Хисамиев а.Г. Конструктивные абелевы р -группы // Докл. АК СССР.- 1990.- Т.313, № 6,- С.1365-1367.

Подписано к пе .ати 5.И.90

Формат бумаги 60x34 1/16 Объем 1,5 п.л., 1,25 уч.-изд.л. Заказ Тираж 100 экз.

Отпечатано на ротапринте Института математики СО АН ьССР 630090, Новосибирсч-90, Университетский проспект, 4