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



МИНИСТЕРСТВО ОБРАЗОВАНИЯ РФ

- о?

> омский государственный университет

Зег

0-5

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

I

КАЛЕНОВА Бакыпул Советовна

НЕКОТОРЫЕ ВОПРОСЫ ТЕОРИИ КОНСТРУКТИВНЫХ АБЕЛЕВЫХ ГРУПП

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

АВТОРЕФЕРАТ

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

Омск -1997

Работа выполнена на кафедре алгебры и математической логики Восточно-Казахстанского Государственного Университета.

НАУЧНЫЙ РУКОВОДИТЕЛЬ - доктор физико-математических наук,

профессор ХИСАМИЕВ Н.Г.

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ - доктор физико-математических наук,

профессор ДОБРЙЦА В.П. кандидат физико-математических наук, доцент ЕПАЧИНЦЕВ В.И.

ВЕДУЩАЯ ОРГАНИЗАЦИЯ - Институт математики СО РАН

Защита состоится ¿3 _199 г?в У^Ос

часов на заседании специализированного совета К 064.36.02 при Омском Государственном университете по адресу: 644077, Омск, пр. Мира, 55-а.

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

Автореферат разослан ^ / • _199Д-.

Ученый секретарь специализированного совета доктор физико-математических наук

РОМАНЫСОВ В .А.

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

Актуальность темы. А.И. Мальцев в работе [1] ввел понятия нумерованной и конструктивной алгебр. Поясним их на примере группы. Нумерацией v группы G называется отображение v: <o->G множества всех натуральных чисел на группу G. Пара ( G,v ) называется конструктивной, если существует алгоритм, который по любым двум натуральным числам тип определяет, равны или нет элементы vm и vn, а также находит такое число s,4to равенство vm -vn = vs справедливо в G. В этой же работе А.И. Мальцев. сформулировал ряд важных понятий теории конструктивных алгебр и наметил программу дальнейших исследований.

Ю.Л. Ершов [2] ввел понятие сильно конструктивной модели. Конструктивная модель ( M,v ) называется сильно конструктивной, если существует алгоритм , который по произвольной формуле Ф( Vq,...,v„.i ) со свободными переменными vo,...,vn-i УИП сигнатуры модели М и по произвольным натуральным числам ma,...,mn.i определяет, истинна или нет формула <E>(vmo,...,vmn-i ) в модели М. Это понятие привело к плодотворному применению методов теорий моделей при изучении конструктивных систем. В настоящее время конструктивные и сильно конструктивные модели изучаются в тесной взаимосвязи.

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

з

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

Цель »работы. Ввести понятие .п-вычислимости класса конструктивных моделей и исследовать вопросы п-вычислимости для различных классов сильно конструктивизируемых абелевых групп. Описание однородных абелевых Ир-групп без кручения, р-ранги которых равны 1 и решение вопроса С.С. Гончарова о конструктивизируемости редуцированной части для сильно конструктивных однородных абелевых групп.

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

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

Апробация работы. Результаты диссертации докладывались на Международной школе-конференции по теории рекурсии и сложности (Казань, 1997), на 1-ом съезде математиков Казахстана (Шымкент,1996), на конференции по математике, посвященной памяти А.Д.Тайманова ( Алматы, 1997 ), на семинарах по алгебре и математической логике ВКГУ, ВКТУ.

Объем работы. Диссертация состоит из введения, 2-х глав, разбитых на 6 параграфов, а также списка литературы, включающего 51 наименований. Она занимает страниц.

Публикации. Основные результаты диссертации опубликованы в работах, список которых приведен в конце автореферата.

Краткое содержание диссертации. В дальнейшем под словом « группа» понимается не более чем счетная абелева группа.

Первая глава посвящена исследованию вычислимости класса сильно конструктивизируемых р-групп. Понятие вычислимости класса конструктивных моделей вводится аналогично понятию вычислимости класса частично рекурсивных функций. Исследованию вычислимости различных классов конструктивных моделей посвящены работы Ю.Л. Ершова [4], [5 ], С.С. Гончарова [б], [7 ], В.П. Добрица [12], [14], Б.Н.Дроботуна [8], А.Т. Нуртазина [9], [10 ], Н.Г. Хисамиева [11].

Доказаны вычислимость следующих классов конструктивных групп: 1) класс групп без кручения конечных рангов ( А.Т.Нуртазин [10] ); 2) класс периодических групп ( Н.Г. Хисамиев [11] ); 3) класс групп с конечными рангами без кручения (В.П. Добрица [12] ).

Доказаны не вычислимость следующих классов конструктивных групп : 1) класс групп (В.П. Добрица [12]); 2) класс групп без кручения (А.Т. Нуртазин [10] ).

А.Т. Нуртазиным [10] доказан, что класс всех конструктивизируемых групп без кручения вычислим.

В §1 данной главы вводится понятие п-вычислимости, пеши{<в}, .класса конструктивных моделей. Пусть (М,у) - нумерованная модель сигнатуры а, с* = о и {с„ | песо}, Му = < М, >, где значение константы с„ равно уп, у-геделева нумерация всех предложений сигнатуры а*, Г„ -множество всех предложений сигнатуры а*, которые в пренексной форме имеют не более п перемен кванторов, Оо(М,у) - открытая диаграмма модели Му. Вп+|( М,у) = (ш | М„ [= у(ш), у(гп) е Г„}, К - некоторый класс конструктивных моделей сигнатуры а,

Будем говорить, что класс .К п-вычислим, если вычислим класс рекурсивно перечислимых множеств Д,(К) = { Щ М,у ) | ( М,у ) е К }. Класс К называется слабо п-вычислимым, если существует п-вычислимый класс К' конструктивных моделей такой, что любая модель ( М,у ) из К автоэквивалентна некоторой модели ( М',у' ) из К' и наоборот, любая модель ( М',у' ) из К' автоэквивалентна некоторой модели ( М,у ) из К. Очевидно, что О-вычислимостъ совпадает с обычной вычислимостью, а ш-вычислимость - с сигыюй вычислимостью. В дальнейшем вместо О-вычислимости будем говорить просто вычислимость. Класс Ь моделей сигнатуры о назовем п-вычислимым, если существует такой п-вычислимый класс конструктивных моделей К, что для любой модели N из Ь существует пара ( М,у) из К такая, что модель М изоморфна N. и наоборот, для любой пары ( М,у) из К существует модель N из Ь такая, что модели М и N изоморфны.

Группа А называется (сильно) конструкгивизируемой, если существует такая нумерация у группы А, что пара ( А,у ) является (сильно) конструктивный группой.

Доказаны:

Теорема 1.1. Класс всех сильно конструктивизируемых р-групп не является 2-вычислимым.

Следствие 1.1. Класс всех сильно конструктивных р-групп не является слабо 2- вычислимым .

В §2 данной главы исследуется О-вычислимость или просто вычислимость различных классов сильно конструктивизируемых групп.

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

Предложение 1.2. Класс Lo* всех сильно конструктивизируемых р-групп, являющихся прямыми суммами циклических и квазициклических p-ipynn, вычислим.

Пусть А - р-группа . Подгруппа А'сА, состоящая из элементов бесконечной высоты группы А, называется первой ульмовой подгруппой [15]. Фактор-группа Ао= А / А1 называется нулевым ульмовым фактором. Известно, что Ао - прямая сумма циклических р-групп. Подгруппа А[р]сА, состоит из элементов порядка p. Pain- векторного пространства А[р] назовем рангом группы А.

Предложение 1.3. Класс L] всех сильно конструктивизируемых р-групп, ранги первых ульмовых подгрупп которых конечны, вычислим.

Предложение 1.4. Класс L/ всех сильно конструктивизируемых р-групп таких, что ранги первых ульмовых подгрупп редуцированых частей которых конечны, вычислим.

Пусть группа А = ©Zpn; - пряма? сумма циклических групп 2рщ

порядка р™. Множество

Х(А) = { <mjc> | 3 ii (ni, =... = nit= ш ) } называется характеристикой группы А.

Предложение 1.5. Класс L2 всех сильно конструктивизируемых р-групп, содержащих все конечные группы и такие группы, что характеристики их нулевых ульмовых факторов и ранги их первых ульмовых подгрупп бесконечны, вычислим.

Основным результатом главы I является:

Теорема 1.2. .Класс всех сильно конструктивизируемых' р-групп вычислим.

В последнем параграфе данной главы изучаются вопросы

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

Вопрос о 1-вычислимости класса всех сильно конструктивизируемых р-групп остается открытым. Следующая теорема дает отрицательный ответ на этот вопрос для класса Ьо р-групп, являющихся прямыми суммами циклических групп.

Теорема 1.3. Класс Ьо всех сильно конструктивизируемых р-групп, разлагающихся в прямую сумму циклических групп, не является 1- вычислимым.

Теорема 1.4. Класс всех сильно конструктивизируемых редуцированных р-групп не 1-вычислим.

Во второй главе изучаются (конструктивные) однородные группы. Она состоит из трех параграфов. Группа А рассматривается в сигнатуре < +, 0 >. Если а! ,... , а„ элементы группы А, то модель ( А, аь ... ,а„ ) означает, что элементы а\ , ... , ап выделены в качестве константных символов. Если модели А и В элементарны эквивалентны, то это записывается как А = В. Счетная группа А называется однородной , если для любых последовательностей З) ,..., аа ,а„+1 и Ь1 , ... , Ь„ группы А из условия ( А, Я] ,..., а„) = ( А, 1>х,... , Ьп ) следует существование такого элемента Ьп+1 е А, что ( А, а!,..., а„+1) = ( А, Ьн , ..., Ьп+1 ). Однородные модели данного класса моделей К играют важную роль. В теории моделей при исследовании свойств моделей класса К изучались как общие свойства однородных моделей, так и однородные модели конкретных классов алгебр. Некоторые важные результаты по общим свойствам однородных моделей можно найти в монографии Г. Кейслера и Ч.Ч.Чэна [16]. Важный вклад в общую теорию (конструктивных) однородных моделей внесли Г.Кейслер, М.Морли, К.Кудайбергенов,

С.С.Гончаров, М.Г.Перетяткин и другие. Описание однородных булевых алгебр получены A.C. Морозовым [17].

Группа D называется делимой, если для любого элемента d е D и натурального числа п существует такой элемент х из D, что выполнено d = пх, т.е. любой элемент d е D делится на любое натуральное число. Группа R называется редуцированной, если она не содержит делимых • подгрупп. Известно, что любая группа А есть прямая сумма некоторой делимой и редуцированной групп, т.е А = R Ф D. Подгруппа R называется редуцированной, aD - делимой частями группы А.

В §1 главы 2 доказано .

Теорема 2.1. Счетная группа без кручения однородна тогда и только тогда, когда ее редуцированная часть однородна.

: В §2 этой главы получен критерий однородности для следующего класса Rp(1) - групп без кручения. Напомним определения Rp-группы и р-независимой системы элементов, где р - фиксированное простое число. Группу А назовем Rp-группой, если для любого элемента а е А и любого натурального числа п, не делящегося на р, в А существует единственное решение уравнения пх = а. Система элементов { а; | i е I} группы А, не содержащая 0 , называется р-независимой, если для любой конечной подсистемы ао,..........а*.] и любого натурального числа г из

Поао+... + nK.iaK.i е ргА(пд* О, п; е Z) следует, что для любого i ^ к-1 числа п; делятся на рг. Максимально р-независимая система элементов называется р-базисом Куликова [18] или просто р-базисом. Подгруппа, порожденная некоторым р-базисом, называется р-базисной подгруппой. Число элементов р-базиса назовем гр- рангом группы А. Класс Rp-rpynn без кручения, гр-ранги которых

равны 1, обозначим через 11р(1). Пусть группа А является Кр(1)-группой, т.е. А е Яр'1'. Тогда в А существует такой элемент а еД что а не делится на р в А, а фактор-группа А/[а] - делима, где через [а] обозначена наименьшая серванта ая подгруппа содержащая элемент а. Пусть Ъ. - кольцо р-адических чисел . Определим отображение

Пусть с - произвольный элемент из А. Тогда существует однозначно определенная последовательность чисел

БО, , ...

и последовательность элементов

Уо, У1 , -из А такие, что выполнены 0 5 < р,

С + ЭД = руо, Уо + 512 = РУ1 , ... Положим

да(с)=<ю +51Р + 52Р2+...

Известно [22], что если группа А редуцирована , то отображение дл есть изоморфизм группы А на некоторую сервантную подгруппу кольца Ъ^, содержащий единичный элемент е и йа(а) = е . Основным

результатом §2 является

Теорема 2.3. Счетная IV'-группа А без кручения однородна тогда и только тогда, когда выполнены :

1°. Эа(А) есть подкольцо кольца р-адических чисел Ъ .;

2°. Если элемент f из о(А) обратим в Ъ , то Г1 также принадлежит

в 3(А). •

В §3 главы 2 даны применения результатов полученных в параграфах 1 и 2 к решению одного вопроса теории конструктивных однородных групп. Пусть ( A,v ) - конструктивная группа без кручения. Группу ( A,v ) назовем группой с алгоритмом линейной независимости, если в (A,v) существует рекурсивно перечислимая максимально линейно независимая система элементов.

Вначале доказывается

Теорема 2.4. Любая конструктивная Rp(I,-rpyima ( А,а ) без кручения с алгоритмом линейной независимости конструктивно вложима в конструктивную однородную Rp(^-группу (А ,а ) также с алгоритмом линейной независимости.

Эта теорема применяется для решения следующего вопроса С.С. Гончарова [19] в классе однородных групп без кручения. Если группа А (сильно) кояструкгавизируема, то будет ли ее редуцированная часть (сильно) конструкгавизируемой ? Этот вопрос решен отрицательно для следующих классов:

1) периодических групп (С.С. Гончаров, В.П. Добрица [20])

2) р-групп (Н.Г. Хисамиев [21])

3) групп без кручения ( З.Г. Хисамиев, Н.Г. Хисамиев [22])

Для следующих классов получен положительный ответ:

1) р-групп, имеющих конечные Ульмовы длины и делимые части конечных рангов ( Н.Г. Хисамиев [23])

2) сильно конструктиви'зируемые р-группы, делимые части которых имеют конечные ранги (Н.Г. Хисамиев [23])

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

Следующий результат дает отрицательное решение вопроса

С.С. Гончарова в классе однородных Кр(1)-групп без кручения.

Теорема 2.5. Существует сильно конструктивная однородная Ир0'-группа А без кручения такая, что ее редуцированная часть не конструкгивизируема.

Таким образом, в диссертации решены ряд естественных вопросов теории конструктивных групп. Понятие п-вычислимосги, введенная в дисертацш, позволяют более точно установить границы вычислимости класса конструктивных (конструктивизируемых) групп. Найдены новые вычислимые классы групп. Для класса сильно конструктивизируемых р-групл, являющихся прямыми суммами циклических групп, установлены точные границы вычислимости. Доказаны, что класс всех сильно конструктивизируемых р-групп вычислим, но не является 2-вычислимым, а класс сильно конструктивизируемых редуцированных р-групп вычислим, но не является 1- вычислимым.

В диссертации начато исследование однородных групп и получено описание однородных Лр^-групп без кручения. Этот результат применен для решения одного вопроса С.С. Гончарова, в классе однородных конструктивизируемых групп.

Содержание диссертации отражено в статьях [23] - [27]. Теоремы 2.1. - 2.5. содержащиеся в совместной публикации [25] получены в нераздельном соавторстве.

Результаты диссертации докладывались на 1-съезде математиков Казахстана (Шымкент ,1996 г), на Международной школе-конференции по теории рекурсии и теории сложности ( Казань, 1997 г), на конференции по математике, посвященной памяти А.Д. Тайманова ( Апматы, 1997 г), на семинарах по алгебре и математической логике ВКГУ, ВКТУ .

В заключении автор благодарит своего научного руководителя Н.Г.Хисамиева за постановку задач и ценные указания.

ЛИТЕРАТУРА

I. Мальцев А.И. Конструктивные алгебры И Успехи маг. наук. - 1961. -Т.16, №3. - С.3-60.

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

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

L Ershow Y.L. Numbered fields // LMPHS Ш, Amsterdam, 1968. -Amsterdam, 1968. - P. 31-34.

i. Ершов Ю.Л. Теория нумераций Ш. - Новосибирск, Изд. Новосиб. Унта, 1974.

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

. Гончаров С.С. Автоустойчивость и вычислимые семейства конструкти-визаций // Алгебра и логика. - 1975. - Т.14, №6. - С. 647-680.

. Дроботуи Б.Н. О не вычислимости одного класса сильных конструк-тивизаций // Тез. докл.б-й Казахстанской межвуз. науч. конф. по мат. и мех., Алма-Ата, 1977. - Алма-Ата, 1977. - С.130.

. Нуртазин А.Т. Сильные и слабые конструктивизации и вычислимые семейства // Алгебра и логика. - 1974. - Т.13, №3. - С.311-323.

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

И. Хисамиев Н.Г. Конструктивные периодические абелевы группы // Тез. докл. 5-ой Казахстанской конф. по мат. и мех. , 2, Алма-Ата, 1974. - Алма-Ата, 1974. - С. 253.

12. Добрица В.П. Вычислимость некоторых классов конструктивных алгебр // Сиб. маг. журн. -1977. - Т. 18, №. - С.570-579

13. Добрица В.П. О рекурсивно - нумерованных классах конструктивных расширений и автоустойчивости алгебр // Сиб. мат. журн. - 1975. -Т.16, №6. - C.1148-1I54.

14. Добрица В.П. О вычислимых и строго вычислимых классах конструктивных алгебр // Тез. докл. Республиканской конф. молодых ученых, Алма-Ата, 1976. - Алма-Ата, 1976. - С.187.

15. Фукс Л. Бесконечные абелевы группы. Т.1: Пер. с англ. - М.: Мир, 1974.

16. КейслерГ., ЧэнЧ.Ч. Теория моделей. Пер. с англ. - М.: Мир, 1977.

17. Морозов A.C. Счетные однородные булевы алгебры // Алгебра и логика. - 1982. - Т.21, №3. - С.269 - 282:

18. Куликов Л .Я. К теории абелевых групп произвольной мощности // Мат. сб. -1945. - Т.16, №1. - С.129-162.

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

20. Гончаров С.С. Добрица В.П. Пример конструктивной абелевой группы с неконструктивизируемой редуцированной подгруппой // Тез. докл. 4-ой Всесоюзной конф. по мат. логике, Кишинев, 1976. -Кишинев, 1976.-С. 33.

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

22. Хисамиев З.Г., Хисамиев Н.Г. Неконструктивизируемостъ редуциро-

ванной части сильно конструктивной абелевой группы без кручения //Алгебра и логика. - 1985. -Т.24, №1. - С. 108-118.

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

23. Каленова Б.С. Вычислимость класса сильно конструктивизируемых • абелевых р-групп // Тез. докл. 1-съезда математиков Казахстана.-

Шымкент.: Гылым, 1996. - С.181..

24. Каленова Б.С. О 1-вычислимости некоторых классов абелевых групп // Некоторые тенденции развития науки в высшей школе, сб. научных трудов. - Изд. Восточно-Каз. Госун-та. -1997.- С.120-125.

25. Каленова Б.С. Хисамиев Н.Г. Об однородных абелевых группах // Сиб. мат. журн. - 1977. - Т.37, №5. - С.1098-1105.

26. Каленова Б.С. Вычислимость класса сильно конструктивизируемых абелевых р-групп // Депонирование в КазгосИНТИ, 19 с, 15.10.97, №7901-Ка97(19).

27. Kalenova B.S. Computability of class of strongly constructivizable of abelian p-groups // Siberian Advances of Mathematics. - 1998. - V.8, Щ.