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

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

Гороховская Наталия Германовна

Об определимости понятия "быть свободной алгеброй" в бесконечных логиках и универсальные вложения групп

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

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

Омск-1998

Работа выполнена в лаборатории комбинаторных и вычислительных методов алгебры и логики Института информационных технологий и прикладной математики

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

Официальные оппоненты: доктор физико-математических наук, профессор Н.Г. Хисамиев кандидат физико-математических наук, доцент Т. А. Мартынова

Ведущая организация: Институт математики СО РАН

Защита состоится "29" декабря 1998 г. в 14.00 на заседании диссертационного совета К 064.36.02 при Омском государственном университете по адресу: 644077, г. Омск, пр. Мира, 55а.

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

Автореферат разослан 1998 г.

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

Общая характеристика работы

Актуальность темы. В конце 40х - начале 50х годов теория моделей выделилась п самостоятельный раздел математической логики. Основополагающие работы по теории моделей логики первого порядка принадлежат Левенгейму, Скулему, Ге-делго, Тарскому, Мальцеву. Однако выяснилось, что многие важные свойства моделей не могут быть выражены на языке логики первого порядка ([НВоок]). В теории групп, например, к таким свойствам относится свойство свободы. Это обстоятельство стимулировало развитие логик, допускающих бесконечные дизъюнкции и конъюнкции - логик L0зХ,х > w. Пусть х - бесконечный кардинал. Тогда Lxx -ото логика, формулы которой имеют дизъюнкции и конъюнкции по любому произвольному множеству формул и кванторы по множеству переменных, мощность которого меньше Так, например, все формулы логики Lоош имеют лишь конечное число кванторов в подформулах. Lu¡w - это логика, формулы которой в отличие от Lmx имеют только счетные (< u-'i) дизъюнкции и конъюнкции и кванторы по конечному (< ы) числу переменных.

Впервые бесконечные логики были систематически изучены Карп ([Кагр2]). Мак-каи, Скотт, Малиц, Лопес-Эскобар работали над созданием теории моделей в логике Оказалось, что аналоги многих известных теорем логики первого порядка, например, теорем Левенгейма-Скулема, верны и в Критерий эквивалентности моделей в логике первого порядка, разработанный Эренфойхтом, был адаптирован Карп [Karpl] для L^, а Бендой [Ben] и Калаисом [Cal] - для логики Lxx, х > и. Однако, например, такой важный инструмент изучения свойств моделей, как теорема компактности, оказалось, не имеет аналога уже в логике Д.Барвайс ([В]) ввел понятие допустимых фрагментов логики (и логики L^). Теоремы Барвайса о полноте и E-компактности показали, что допустимые фрагменты обладают свойствами, аналогичными логике первого порядка.

В связи с последним фактом отметим, что в ряде работ А.Г.Мясникова и В.Н.Ре-месленнпкова, а также в работах [НВоок, В] указывалось на естественность использования при изучении алгебраических объектов одного из фрагментов логики ЬШ1Ш - HF-логики. При работе с HF-логикой для данной модели 21 рассматривается двуосновная модель HF{21). Она строится на основе наследственно конечных множеств над основным универсумом модели 21 и называется HF-надстройкой модели 21. Надстройка HF(A) есть на самом деле минимальное допустимое множество с праэлемен-тами из А. Поэтому для HF-логики автоматически справедливы многие логические результаты, описанные, например, в [В].

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

П.Эклоф занимался проблемой эквивалентности произвольной абелевой группы

свободной абелевой группе в логиках ЬссХ, X > Им получен критерий эквивалентности произвольной абелевой группы свободной абелевой группе. С помощью этого критерия было доказано в частности, что класс свободных абелевых групп не определим в логике ЬООШ1.

Справедливость теоремы П.Эклофа в классе всех групп была доказана А.Мек-лером. При доказательстве Меклер использовал понятие почти свободной группы, введенное Г.Хигманом. Теорема Меклера и некоторые результаты Хигмана показали неопределимость класса свободных групп в логике Ь^.

Для получения перечисленных результатов, касающихся теории групп, активно использовалось понятие чистой подгруппы, являющееся аналогом понятия "сервант-ная подгруппа" в категории абелевых групп. Были предприняты и другие попытки обобщения понятия сервантности (Ю.Л.Ершов, Н.А.Сердюкова). С этим понятием тесно связано другое понятие, пришедшее из математической логики, - экзистенциально замкнутая группа. Изучением этих объектов занимались Б.Нейман, У.Скотт, А.Макинтайр, О.В.Белеградек. Важность этого понятия подчеркивает тот факт, что с его помощью получен критерий для разрешимости проблемы тождества слов для конечно порожденных групп.

Цель работы. Изучение определимости понятия "быть свободной алгеброй в бесконечных логиках. Выяснение необходимых и достаточных условий, при которых подгруппа универсально вложена в группу.

Методика исследования. Методы, применяемые в диссертации, опираются на теорию групп, универсальную алгебру и теорию моделей.

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

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

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

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

Содержание работы

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

В разделе 1.1 мы приводим определения логик и Ь^^, а также критерий эквивалентности моделей в логике Ьхх.\ > и. Этот критерий является основным при доказательстве результатов главы 1.

Раздел 1.2 посвящен HF-логике. Здесь мы даем ее определение, следуя стать--[BLR] и, ссылаясь на статью [ВТ], указываем, что существуют фрагменты язы^л l>u¡u (здесь обозначаются Lar и Lr), эквивалентные по выразительной силе языку HF-логики. Языки Lar и Lr удобны тем, что они не требуют расширения сигнатуры и построения надстройки над системой. С использованием этих языков в пункт;-1.2.2 - 1.2.6 доказана выразимость в HF-логике некоторых алгебраических свой« которые не являются выразимыми в логике первого порядка. В пунктах 1.2.2 и 1.2 . показано, что следующие классы алгебраических систем формульны в HF-логике: свободные конечно порожденные полугруппы (предложение 1.2), свободные конечно порожденные группы (предложение 1.3),

свободные конечно порожденные ассоциативные некоммутативные кольца (предложение 1.4),

конечно порожденные алгебры данной сигнатуры (предложение 1.5). В пунктах 1.2.4 - 1.2.6 мы доказываем формульность понятий "быть простой" (предложение 1.6) , "быть финитно аппроксимируемой"(предложение 1.9) и "быть ниль-потентно аппроксимируемой" (предложение 1.11) для групп, а также понятий "быть простым" (предложение 1.8) и "быть нильпотентно аппроксимируемым" (предложение 1.12) для колец.

В разделе 1.3 формулируется основная проблема, решаемая в главе 1. Мы называем ее проблемой определимости. Прежде чем привести ее формулировку, дадш.: необходимые определения.

Определение. Понятие "быть Р-алгеброй", где Р - некоторое абстрактное свойство, будем называть определимым в логике LooX, X > w, если из того, что А В п В — Р-алгебра., следует, что А также Р-алгебра.

Определение. Понятие "быть Р-алгеброй", где Р - некоторое абстрактное свойство, будем называть счетно определимым в логике L0ох, х > ш> если из того, что A =LocX & и А - счетная алгебра, а В Р-алгебра, следует, что А также Р-алгебра.

Проблема. Для каких многообразий алгебраических систем понятие "быть свободной алгеброй" является определимым (счетно определимым) в логиках LcaX, х ^ ш?

Далее, в разделах 1.4, 1.5 и 1.6 приведено решение этой проблемы для различных классов алгебраических систем. Основное внимание уделяется решению этой проблемы в HF-логике.

Раздел 1.4 посвящен решению проблемы в категории абелевых групп. В пунктах 1.4.1 и 1.4.2 собраны необходимые определения, а также основные результаты по проблеме ¿оо^-эквивалептности группы свободной абелевой группе и проблеме определимости. Ключевой является

Теорема П.Эклофа ([Ек]). Абелева группа А ¿^-эквивалентна свободной группе тогда и только тогда, когда каждая ее х~порожденная подгруппа содержится в некоторой свободной, ^-чистой подгруппе.

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

групп в бесконечных логиках и, следовательно, в НЕ-логике. В пункте 1.4.3 мы приводим прямое доказательство этого факта. Оно опирается на Признак эквивалентности двух моделей в логике Ьи1Ы. ([Кб])

Пусть 21 = {Л, о-} и 23 = {В, а} - модели логики первого порядка Ь. Предположим, что для каждого п < и существует отношение ~ между А" и Вп такое, что

1) Если («н ... ап) ~ (¿1... Ъ„), то (с!... а„) удовлетворяет в точности тем же атомным формулам в 21, что и (Ьх...&„) в 23.

2) Если (а!... ап) ~ (¿>!... Ь„), то

(Уа„+а € А)(ЭЬ„+1 е В) (а1... ап+1) ~ ... Ь„+1).

3) Если (ах... а„) ~ (Ьх... 6„), то

(УЬ„+1 6 £)(Эап+: € А) (а!... ая+1) ~ (¿ч ... &„+,).

Тогда 21 23.

В пункте 1.4.3 найдены необходимые и достаточные условия, при которых кортежи (ах...ап) ~ (&1...¿>„), причем в одном случае (а!... а„) £ А, (Ь1.. ,Ьп) 6 В, где А, В - абелевы группы без кручения, в другом случае - (¿¡1... € (6]... Ь„) € Р, где Р - свободная абелева группа.

Неопределимость понятия "быть свободной абелевой группой" показывает следующая

Теорема 1.5. Пусть Я - декартова сумма бесконечного множества копий бесконечной циклической группы. Р - свободная абелева группа счетного ранга. Тогда Я и Р эквивалентны в логике и, следовательно, в НЕ-логике.

В пункте 1.4.4 показана счетная определимость понятия "свободная абелева группа" в Я.Г-логике. Ключом к доказательству этого факта служит критерий Понтря-гина о свободе счетных абелевых групп.

Теорема 1.6. Свойство "быть свободной абелевой группой" счетно определимо в ЯР-логике.

Раздел 1.5 посвящен определимости понятия "свободная группа". В пункте 1.5.1 приведена

Теорема А.Меклера ([Мек]). Группа А ¿^-эквивалентна свободной группе (¿сох ~ свободна) тогда и только тогда, когда А сильно ^-свободна.

В пункте 1.5.2 мы покажем, что теорема, аналогичная этой теореме, справедлива и для НЕ-логики. С помощью теоремы А.Меклера отрицательно решается проблема определимости для класса свободных групп в логике . Следовательно, это понятие не определимо и в ЯР-логике. Тем не менее, оно счетно определимо в этой логике.

Теорема 1.9. Свойство "быть свободной группой" счетно определимо в Я/''-логике.

б

Раздел 1.6 посвящен решению проблемы определимости для произвольных универсальных алгебр. Пункт 1.6.1 содержит необходимые сведения из теории алгебраических систем. Здесь, следуя А.И. Мальцеву [Mall], мы напомним способ задания алгебр с помощью порождающих и определяющих соотношений, а также понятие свободного произведения алгебр. В пункте 1.6.2 по аналогии с группами мы вводим понятия А-свободной, к-чистой и сильно ^-свободной алгебры многообразия алгебр конечной сигнатуры а. Пункт 1.6.3 посвящен условию и Ъну—эквивалентности произвольной алгебры свободной алгебре данной сигнатуры. Доказано,что теорема Эклофа верна и для произвольных универсальных алгебр.

Теорема 1.11. Алгебра А = (А, а) ¿оох-эквивалентна свободной алгебре данной сигнатуры <т тогда и только тогда, когда каждая х-псрожденная подалгебра А содержится в свободной х-чистой подалгебре А.

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

Обобщенный критерий Понтрягина.

Счетная алгебра А свободна тогда и только тогда, когда каждая конечно порожденная подалгебра А содержится в свободной чистой подалгебре А.

В пункте 1.6.4 введено понятие //-многообразия алгебр и указаны некоторые свойства алгебр этого многообразия. Затем в пункте 1.6.5 доказано, что для этих алгебр оказывается верным аналог леммы Хигмана из статьи [Higl]. Аналог леммы Хигмана для Я-многообразий.

Локально свободная алгебра А Я-многообразия счетно свободна тогда и только тогда, когда А сильно локально свободна.

В главе 2 обсуждаются универсальные вложения групп. Это понятие тесно связано с логикой первого порядка. Например, знаменитый критерий модельной полноты Робинсона формулируется на языке универсальных вложений, группа универсально вложима в свою ультрастепень. Поэтому прежде чем ввести понятие "универсальное вложение подгруппы в группу" мы постарались осветить известные факты, так или иначе с ним связанные. Раздел 2.1 посвящен V—, 3—, V3— п 3V—формулам и их основным струтурным свойствам. Здесь приведены некоторые "теоремы об устойчивости", а также примеры индуктивных и универсально аксиоматиз1груемых теорий. В разделе 2.2 рассказывается об ультрафильтрах и ультрапроизведениях, а также приведена теорема компактности и продемонстрированы некоторые применения теоремы компактности и техники ультрапроизведений. Разделы 2.3 и 2.4 посвящены понятиям "модельная полнота" и "алгебраически и экзистенциально замкнутые системы" соответственно.

В разделе 2.5 мы вводим понятие универсального вложения групп.

Определение. Пусть Я - группа, G - подгруппа Я. Будем говорить, что G универсально вложена в Я (обозначение: G <v Я), если для любой конечной системы равенств и неравенств

Г щ{дп, ■■■,д>т, г.-1,-.., X; „) = 1, г € /,

1 ъ^дл,..., дц,х,и хы) ф 1, з € ^

где (/5! - элементы подгруппы й, из разрешимости (1) в Я следует ее разрешимость ъв.

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

Теорема 2.19 Пусть Я - группа, в - подгруппа Я, ТЫ,а{Н) — { множество универсальных предложений с константами из (?, истинных в Я. } Тогда следующие условия эквивалентны:

1) С<уЯ;

2) ГЛу.с(Я') = Т/г¥.с(С), т.е. универсальные теории С? и Я с константами из (? совпадают.

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

Пункт 2.6 содержит необходимые сведения из теории б-групп. Мы даем их, следуя статье Г.Баумслага, А.Мясникова и В.Ремесленникова [ВМ11-АСС1].

В пункте 2.7 мы связываем понятие универсального вложения подгруппы Я в группу С? с понятием С?-дискриминируемости в случае, когда б - нетерова по уравнениям группа.

Определение. Группа С? называется нетеровой по уравнениям, если любая система уравнений над С? эквивалентна некоторой ее конечной части.

Теорема 2.20. Пусть О - нетерова по уравнениям группа, О < II. Тогда <7 <у Я тогда и только тогда, когда любая конечно порожденная над С? подгруппа Я0, С < Я0 < Я, С-дискриминируема.

Пусть <3 = А * В. В пункте 2.8 приведен пример показывающий, что множители не всегда вкладываются универсально в группу й. В связи с этим примером возникает вопрос: при выполнении каких условий множители А и В универсально вложены в (7? Мы решим эту проблему для категории так называемых СТ-групп, теория которых изложена в препринте [ВМ11-АОС2]. По определению группа в принадлежит категории С^-групп, если она удовлетворяет следующим аксиомам: СР1 : С? - неабелева С5Л-группа, не содержащая элементов второго порядка, СР2 : 6" - нетерова по уравнениям. СРЗ : (7 удовлетворяет условию (5').

Определение. Группа, б удовлетворяет условию (5), если для любого элемента и бесконечного порядка и любых элементов д = (д1>.. ,,дь+1), таких, что [<?;, и] ф 1, существует такое натуральное число что множество

= {д1иа'д2 ... дкиа*дш | | а,- |> (}

не содержит 1.

Класс групп, удовлетворяющих этим аксиомам достаточно широк. Он включает свободные группы, яетеровы по уравнениям гиперболические группы без кручения и группы, действующие свободно на Л-деревьях. Более того, большинство групп с одним соотношением содержится в этом классе. Для категории С7"-групп оказывается справедливой следующая

Теорема 2.21. Пусть А, В € CTviTh^A) = Thv(B). G = А*В. Тогда множители А, В универсально вложены в группу G.

Заключительный раздел 2.9 посвящен диофантовым предикатам. Пусть G - группа.

/ = {/i (зТ, х,у),... fm{gm, х, у)} - некоторый набор словарных функций, т.е.

Л 6 G*F(X) * F(Y); X = {хи...,хг}; Y = {у„.,.,уЛ-

Определим формулу

Ф/dV) = 3(2b...,xr)(/j(sr,5,y) = 1 &...&/ra(5m,J,y) = 1)

Определение. Диофантовым предикатом будем называть множество

DjS = {(Ai,..., hs) € G : формула il>js{y) выполняется на (hi,..., h:)}

В разделе 2.9 мы вводим операции над диофалтовыми предикатами и даем классификацию диофантовых предикатов в категории абелевых групп.

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

Пользуясь случаем, автор выражает глубокую благодарность своему научному руководителю Владимиру Никаноровичу Ремесленникову за постановку задач, ценные обсуждения и постоянную поддержку. Доказательства теорем 1.5 и 1.6 были получепы в совместной работе [GR].

Литература

[НВоок] Справочная книга по математической логике: В 4-х частях/ Под ред. Дж.Барвайса.- 4.1. Теория моделей: Пер. с англ.- М.:Наука, 1982.

[Bel] Белеградек О.В. Элементарные свойства алгебраически замкнутых групп. Fund. Math., 1978, 98, N2, 83-101.

[ВТ] Беляев В.Я., Тайцлин М.А. Об элементарных свойствах экзистенциально замкнутых систем. Успехи математических наук, т.34 (1979), N2, 39-94.

[BLR] Беляев В.Я., Лютикова Е.Е., Ремесленников H.H. О категоричности конечно-порожденных алгебраических систем в HF-логике. Алгебра и логика, т.34 (1995), N1, 12-32.

[Erl] Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. М.: Наука, 19S0

[Ег2] Ершов Ю.Л. Об алгебраически компактных группах И. Алгебра и логика, 18, N4(1979), 408-414ю

[KCh] Кейслер Х.Дж., Чэн К.К. Теория моделей: пер. с англ.- М.:Мир, 1977.

[Cohn] Кон П. Универсальная алгебра М.: Мир, 1968.

[Mail] Мальцев А.И. Алгебраические системы. М:Наука, 1970.

[Ма12] Мальцев А.И. Некоторые вопросы теории классов моделей: Избранные труды. Т.2. М.:Наука, 1976, 239-274.

[Ма13] Мальцев А.И. Об одном общем методе получения локальных теорем теории групп: Избранные труды. Т.1. М.:Наука, 1976, 78-83.

[Ма14] Мальцев А.И. Об изоморфном представлении бесконечных групп матрицами: Избранные труды. Т.1. М.:Наука, 1976, 58-73.

[MR-exgrl] Мясников А.Г., Ремесленников В.Н. Степенные группы 1. Препринт N8, ИИТПМ СО РАН, ОмГУ, Омск, 1993, 25с.

[Nov] Новиков П.С. Элементы математической логики. Физматгиз, 1959.

[RR] Ремесленников В.Н., Романьков В.А. Теоретико-модельные и алгоритмические вопросы теории групп. В кн. Итоги науки и техники. Алгебра. Топология. Геометрия. Т.21, М.: ВИНИТИ, 1983.

[R] Роджерс X. Теория рекурсивных функций и эффективная вычислимость М.: Мир, 1972.

[Sacks] Сакс Дж. Е. Теория насыщенных моделей. М.: Мир, 1976.

[F] Фукс Л. Бесконечные абелевы группы. Т.1 - М:Мир, 1966.

[Hall] Hall P. Nilpotent groups. Canad. Math. Congress, Summer Seminar, University of Alberta, 1957.

[Fed] Fedoseyeva J. Analogies of Nullstellensatz for groups. Prep. N 97-01 OmSU. -Omsk: ÔmSU, 1997. - 25p.

[B] Barwise J. Admissible sets aad structures. Springer, Berlin, 1975.

[Ks] Keisler H.J. Model theory for infinitary logic. Amsterdam, 1971.

[BMR] Baumslag G., Myasnikov A., Remeslennikov V. Residually hyperbolic groups, preprint N 24, Omsk, 1995.

[BMR-AGG1] Baumslag G., Myasnikov A., Remeslennikov V. Algebraic geometry ove: groups. Invitation of Mathematics (submitted).

[BMR-AGG2] Baumslag G., Myasnikov A., Remeslennikov V. Algebraic geometry ov; -groups II.

[Ben] Benda M. Reduced products and non-standard logics. J. Symbolic Logic 34 (1969). pp. 424-436.

[Cal] Calais J.P. La méthode de Fraissè dans les languages infints. C. R. Acad. sci. Paria 268 (1969), pp. 785-788.

[Ehr] Ehrenfeucht A. An application of games to the completeness problem for formalized theories. Fund. Math. 49 (1961), pp. 129-141.

[Ek] Eklof P.C. Infinitary equivalence of abelian groups. Fund. Math. 81 (1974), pp. 305-314.

[Higl] Higman G. Almost free groups. Proc. Londod Math. Soc. (3), 1 (1951), pp. 284290.

[Karpl] Karp C. Finite quantifier equivalence. The theory of models, Amsterdam 1965, pp. 407-412.

[Karp2] Karp C. Languafes with Expressions of Infinite Length. Amsterdam: North-Holland, 1964.

[K] Keisler H.J. Model theory for infinitary logic. Amsterdam-London, 1971, pp. 7-9.

[KhMR] Kharlampovich 0., Myasnikov A., Remeslennikov V. Logical languages anc axioms for groups with a length function. Preprint N20, Omsk, 1995, 8 p.

[Mac] Macintyre A. On algebraicall closed groups. Ann. Math., 1972, 96, N1 53-97.

[Mek] Melder A.H. How to constract almost free groups. Canadian J. Math. 32 (19S0), pp. 1206-1228.

[Szm] Szmielev W. Elementary properties of Abelian groups. Fund, math., 1955, 41, N2, 203-271.

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

[Gl] Gorokhovskaya N.G. Algebraic properties expressible in HF-logic. Preprint N 12, IITAM, Omsk, 1993.

[GR] Гороховская Н.Г'., Ремесленников B.H. О понятии "быть свободной алгеброй в HF-логике. Препринт N 23, Омск: Омский государственный университет, 1995.

[G2] Гороховская Н.Г. Об определимости понятия "быть свободной алгеброй в бесконечных логиках. Препринт N 25, Омск: Омский государственный университет, 1996.

[G3] Гороховская Н.Г. Универсальные классы групп и универсальные вложения. Препринт, Омск: Омский государственный университет, 1998.

[G4] Gorokhovskaya N. On definability of the notion "to be a free group" in HF-logic. Второй Сибирский Конгресс по прикладной и Индустриальной Математике, посвященный памяти А.А.Ляпунова, А.П.Ершова и И.А.Полетаева. Тезисы докладов, часть II, с. 198.

[G5] Гороховская Н.Г. Универсальные классы групп и универсальные вложения. Тезисы докладов на международной алгебраической конференции памяти А.Г.Ку-роша 1998 года, Механико-математический ф-т МГУ, 1998г, с.163.

[G6] Гороховская Н.Г. Универсальные классы групп и универсальные вложения. Тезисы докладов на международной конференции "Комбинаторные и вычислительные методы в математике", Омск, 1998, с.46-49.

Министерство общего и профессионального образования РФ Омский государственный университет

Гороховская Наталия Германовна

Об определимости понятия "быть свободной алгеброй" в бесконечных

логиках

и универсальные вложения групп

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

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

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

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

Ремесленников Владимир Никанорович

Омск-1998

Содержание

0 Введение 4

1 Об определимости понятия "быть свободной алгеброй" в бесконечных логиках 11

1.1 Некоторые бесконечные логики и критерии эквивалентности моделей . 11

1.2 НР-логика. Некоторые алгебраические свойства, выразимые в НР-логике 12

1.2.1 Определение НР-логики..............................12

1.2.2 Интерпретируемость свободных конечно порожденных полугрупп, групп и колец в арифметике..................................14

1.2.3 Формульность конечно порожденных алгебр в НР-логике .... 17

1.2.4 Формульность свойства простоты для групп и колец..............18

1.2.5 О формульности понятия "финитно аппроксимируемая группа" . 21

1.2.6 Формульность понятия "нильпотентная аппроксимируемость"

для групп и колец............................23

1.3 Постановка проблемы определимости........................................25

1.4 Об определимости понятия "свободная абелева группа" в бесконечных логиках...........................................................26

1.4.1 Определение почти свободных групп................................26

1.4.2 Сводка основных результатов по проблеме Ь^-эквивалентности группы свободной группе и проблеме определимости..............27

1.4.3 Свойство "быть свободной абелевой группой" не является определимым в НЕ-логике..................................................28

1.4.4 Счетная определимость понятия "свободная абелева группа" в НР-лоттке................................................................32

1.5 Об определимости понятия "свободная группа" в бесконечных логиках 33

1.5.1 Теорема А.Меклера............ . . ..................33

1.5.2 Об определимости понятия "свободная группа" в НР-логике ... 34

1.6 Определимость понятия "быть свободной алгеброй" в бесконечных логиках ............................................................................35

1.6.1 Необходимые сведения из теории алгебраических систем..........35

1.6.2 Определения.........................................36

1.6.3 Условие ¿оох~ и 1 /•'"' г>квивалентности произвольной алгебры свободной алгебре данной сигнатуры ...............................37

1.6.4 Технические результаты..............................................38

1.6.5 Аналоги леммы Хигмана и критерия Понтрягина для универсальных алгебр............................41

2 Универсальные классы групп и универсальные вложения 43

2.1 У—, 3—, УЗ— и ЗУ—формулы и их основные структурные свойства.

Примеры использования теорем об устойчивости............................43

2.1.1 У-, 3-, УЗ- и ЗУ-формулы............................................43

2.1.2 Примеры универсально аксиоматизируемых классов.......47

2.1.3 Примеры классов, теории которых индуктивны..........49

2.2 Ультрафильтры и ультрапроизведения......................................50

2.2.1 Локальные классы и теорема компактности........................52

2.2.2 Примеры................................................................52

2.3 Модельная полнота ............................................................54

2.3.1 Элементарные отображения..........................................54

2.3.2 Определение модельно полной теории и критерий модельной полноты..................................................................56

2.4 Алгебраически и экзистенциально замкнутые системы....................56

2.5 Универсальные вложения групп..............................................58

2.6 Необходимые сведения из теории С-групп .................................61

2.6.1 Категория С-групп ....................................................62

2.6.2 Аппроксимируемость и дискриминируемость ...........63

2.7 Характеризация универсальных вложений..................................63

2.8 Универсальные вложения для свободных произведений....................66

2.9 Диофантовы предикаты........................................................68

3 Литература 73

О Введение

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

В конце 40х - начале 50х годов теория моделей выделилась в самостоятельный раздел математической логики. Основополагающие работы по теории моделей логики первого порядка принадлежат Левенгейму, Скулему, Геделю, Тарскому, Мальцеву. Однако выяснилось, что многие важные свойства моделей не могут быть выражены на языке логики первого порядка ([НВоок]). В теории групп, например, к таким свойствам относится свойство свободы. Это обстоятельство- стимулировало развитие логик, допускающих бесконечные дизъюнкции и конъюнкции - логик £oox,X > Пусть х ~ бесконечный кардинал. Тогда - это логика, формулы которой имеют дизъюнкции и конъюнкции по любому произвольному множеству формул и кванторы по множеству переменных, мощность которого меньше х- Так, например, все формулы логики Loouj имеют лишь конечное число кванторов в подформулах. ЬШ1Ш - это логика, формулы которой в отличие от Lcox имеют только счетные (< дизъюнкции и конъюнкции и кванторы по конечному (< и>) числу переменных.

Впервые бесконечные логики были систематически изучены Карп ([Кагр2]). Мак-каи, Скотт, Малиц, Лопес-Эскобар работали над созданием теории моделей в логике ,u. Оказалось, что аналоги многих известных теорем логики первого порядка, например, теорем Левенгейма-Скулема, верны и в ЬШ1Ш. Критерий эквивалентности моделей в логике первого порядка, разработанный Эренфойхтом, был адаптирован Карп [Karpl] для L^, а Бендой [Ben] и Калаисом [Cal] - для логики Lоох, х > Однако, например, такой важный инструмент изучения свойств моделей, как теорема компактности, оказалось, не имеет аналога уже в логике ЬШ1Ш. Д.Барвайс ([В]) ввел понятие допустимых фрагментов логики ЬШ1Ш (и логики Lcош). Теоремы Барвайса о полноте и E-компактности показали, что допустимые фрагменты обладают свойствами, аналогичными логике первого порядка.

В связи с последним фактом отметим, что в ряде работ А.Г.Мясникова и В.Н.Ремесленникова, а также в работах [НВоок, В] указывалось на естественность использования при изучении алгебраических объектов одного из фрагментов логики Lwiw - HF-логики. При работе с HF-логикой для данной модели 21 рассматривается двуосновная модель HF(%I). Она строится на основе наследственно конечных множеств над основным универсумом модели 21 и называется HF-надстройкой модели 21. Надстройка HF(A) есть на самом деле минимальное допустимое множество с праэлементами из А. Поэтому для HF-логики автоматически справедливы многие логические результаты, описанные, например, в [В].

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

П.Эклоф занимался проблемой эквивалентности произвольной абелевой группы свободной абелевой группе в логиках £<х>х> Х> Им получен критерий эквивалентности произвольной абелевой группы свободной абелевой группе. С помощью этого критерия было доказано в частности, что класс свободных абелевых групп не определим в логике ioowi.

Справедливость теоремы П.Эклофа в классе всех групп была доказана А.Меклером. При доказательстве Меклер использовал понятие почти свободной группы, введенное Г.Хигманом. Теорема Меклера и некоторые результаты Хигмана показали неопределимость класса свободных групп в логике L^w-

Для получения перечисленных результатов, касающихся теории групп, активно использовалось понятие чистой подгруппы, являющееся аналогом понятия "сервант-ная подгруппа" в категории абелевых групп. Были предприняты и другие попытки обобщения понятия сервантности (Ю.Л.Ершов, Н.А.С'ердюкова). С этим понятием тесно связано другое понятие, пришедшее из математической логики, - экзистенциально замкнутая группа. Изучением этих объектов занимались Б.Нейман, У.Скотт, А.Макинтайр, О.В.Белеградек. Важность этого понятия подчеркивает тот факт, что с его помощью получен критерий для разрешимости проблемы тождества слов для конечно порожденных групп.

Опишем структуру диссертации. Диссертация состоит из введения и двух глав.

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

В разделе 1.1 мы приводим определения логик LCXJX и Lw¡ш. а также критерий эквивалентности моделей в логике £оох>Х и• Этот критерий является основным при доказательстве результатов главы 1.

Раздел 1.2 посвящен HF-логике. Здесь мы даем ее определение, следуя статье [BLR] и, ссылаясь на статью [ВТ], указываем, что существуют фрагменты языка Lbj^w (здесь обозначаются Lar и Lr), эквивалентные rio выразительной силе языку HF-логики. Языки Lar и Lr удобны тем, что они не требуют расширения сигнатуры и построения надстройки над системой. С использованием этих языков в пунктах 1.2.2 - 1.2.6 доказана выразимость в HF-логике некоторых алгебраических свойств, которые не являются выразимыми в логике первого порядка. В пунктах 1.2.2 и 1.2.3 показано, что следующие классы алгебраических систем формульны в HF-логике: свободные конечно порожденные полугруппы (предложение 1.2), свободные конечно порожденные группы (предложение 1.3),

свободные конечно порожденные ассоциативные некоммутативные кольца (предложение 1.4),

конечно порожденные алгебры данной сигнатуры (предложение 1.5). В пунктах 1.2.4 - 1.2.6 мы доказываем формульность понятий "быть простой" (предложение 1.6) , "быть финитно аппроксимируемой"(предложение 1.9) и "быть ниль-потентно аппроксимируемой" (предложение 1.11) для групп, а также понятий "быть простым" (предложение 1.8) и "быть нильпотентно аппроксимирз^емым" (предложение 1.12) для колец.

В разделе 1.3 формулируется основная проблема, решаемая в главе 1. Мы назы-

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

Определение. Понятие "быть Р-алгеброй", где Р - некоторое абстрактное свойство, будем называть определимым в логике ЬсоХ, если из того, что А =ЬооХ В и В — Р алгебра,, следует, что А также Р-алгебра.

Определение. Понятие "быть Р-алгеброй", где Р - некоторое абстрактное свойство, будем называть счетно определимым в логике Роох> X ^ и> если из того, что А =/,тох В и А - счетная алгебра, а В Р-алгебра, следует, что А также Р-алгебра.

Проблема. Для каких многообразий алгебраических систем понятие "быть свободной алгеброй" является определимым (счетно определимым) в логиках Ь,У:УХ1

Х>ы?

Далее, в разделах 1.4, 1.5 и 1.6 приведено решение этой проблемы для различных классов алгебраических систем. Основное внимание уделяется решению этой проблемы в НЕ-логике.

Раздел 1.4 посвящен решению проблемы в категории абелевых групп. В пунктах 1.4.1 и 1.4.2 собраны необходимые определения, а также основные результаты по проблеме Р^-эквивалентности группы свободной абелевой группе и проблеме определимости. Ключевой является

Теорема П.Эклофа ([Ек]). Абелева группа А вивалентна свободной

группе тогда и только тогда, когда каждая ее х~порожденная подгруппа содержится в некоторой свободной, ^-чистой подгруппе.

В той же работе П.Эклофа показано, что с помощью этой теоремы отрицательно решается проблема определимости понятия "быть свободной группой" для абелевых групп в бесконечных логиках и, следовательно, в НЕ-логике. В пункте 1.4.3 мы приводим прямое доказательство этого факта. Оно опирается на Признак эквивалентности двух моделей в логике ([Кэ])

Пусть 51 = {А, сг} и = {В, а} - модели логики первого порядка Ь. Предположим, что для каждого п < ш существует отношение ~ между Ап и Вп такое, что

1. Если (ах... ап) ~ (&х...-&„), то (а1... ап) удовлетворяет в точности тем же атомным формулам в 51, что и (61... Ьп) в 03.

2. Если (ах... а„) ~ (61... Ь„), то

(Уап+1 е А)(ЗЬп+1 е В) (ах .. .ап+1) ~ (Ьг... Ьп+1).

3. Если (ах... ап) ~ (Ь\ ... Ь„), то

(Щп+1 е В)(Зап+1 е А) (аг ... ап+1) ~ (6Х... 6„+1).

Тогда, 21 =ьШ1Ы

В пункте 1.4.3 найдены необходимые и достаточные условия, при которых кортежи (а!... ап) ~ {Ь\ ... Ьп), причем в одном случае (щ ... ап) С А, (61... Ьп) € Р, где А, В - абелевы группы без кручения, в другом случае - (01 ... ап) £ Р, (61 ... Ьп) Е Р, где Р - свободная абелева группа.

Неопределимость понятия "быть свободной абелевой группой" показывает следующая

Теорема 1.5. Пусть Н - декартова сумма бесконечного множества копий бесконечной циклической группы. F - свободная абелева группа счетного ранга. Тогда Н и F эквивалентны в логике ЬШ1Ш и, следовательно, в HF-логике.

В пункте 1.4.4 показана счетная определимость понятия "свободная абелева группа" в HF-логике. Ключом к доказательству этого факта служит критерий Понтря-гина о свободе счетных абелевых групп.

Теорема 1.6. Свойство "быть свободной абелевой группой" счетно определимо в HF-погжке.

Раздел 1.5 посвящен определимости понятия "свободная группа". В пункте 1.5.1 приведена

Теорема А.Меклера ([Мек]). Группа А //о^-эквивалентна свободной группе (1<оох ~ свободна) тогда и только тогда, когда А сильно ^-свободна.

В пункте 1.5.2 мы покажем, что теорема, аналогичная этой теореме, справедлива и для HF-логики. С помощью теоремы А.Меклера отрицательно решается проблема определимости для класса свободных групп в логике L^. Следовательно, это понятие не определимо и в II/''-логике. Тем не менее, оно счетно определимо в этой логике.

Теорема 1.9. Свойство "быть свободной группой" счетно определимо в HF-логике.

Раздел 1.6 посвящен решению проблемы определимости для произвольных универсальных алгебр. Пункт 1.6.1 содержит необходимые сведения из теории алгебраических систем. Здесь, следуя А.И. Мальцеву [Mall], мы напомним способ задания алгебр с помощью порождающих и определяющих соотношений, а также понятие свободного произведения алгебр. В пункте 1.6.2 по аналогии с группами мы вводим понятия ¿-свободной, ¿-чистой и сильно ¿-свободной алгебры многообразия алгебр конечной сигнатуры а. Пункт 1.6.3 посвящен условию ¿оох~ и -ktfF-эквивалентности произвольной алгебры свободной алгебре данной сигнатуры. Доказано,что теорема Эклофа верна и для произвольных универсальных алгебр.

Теорема 1.11. Алгебра Л = (А,а) ^^-эквивалентна свободной алгебре данной сигнатуры а тогда и только тогда, когда каждая ^-порожденная подалгебра Л содержится в свободной чистой подалгебре Л.

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

Обобщенный критерий Понтрягина.

Счетная алгебра Л свободна тогда и только тогда, когда каждая конечно порожденная подалгебра А содержится в свободной чистой подалгебре Л.

В пункте 1.6.4 введено понятие Н-многообразия алгебр и указаны некоторые свойства алгебр этого многообразия. Затем в пункте 1.6.5 доказано, что для этих алгебр оказывается верным аналог леммы Хигмана из статьи [Higl],

Аналог леммы Хигмана для Я-многообразий.

Локально свободная алгебра Л Я-многообразия счетно свободна тогда и только тогда, когда Л сильно локально свободна.

В главе 2 обсуждаются универсальные вложения групп. Это понятие тесно связано с логикой первого порядка. Например, знаменитый критерий модельной полноты Робинсона формулируется на языке универсальных вложений, группа универсально вложима в свою ультрастепень. Поэтому прежде чем ввести понятие "универсальное вложение подгруппы в группу" мы постарались осветить известные факты, так или иначе с ним связанные. Раздел 2.1 посвящен У—, 3—, УЗ— и ЗУ—формулам и их основным струтурным свойствам. Здесь приведены некоторые "теоремы об устойчивости", а также примеры индуктивных и универсально аксиоматизируемых теорий. В разделе 2.2 рассказывается об ультрафильтрах и ультрапроизведениях, а также приведена теорема компактности и продемонстрированы некоторые применения теоремы компактности и техники ультрапроизведений. Разделы 2.3 и 2.4 посвящены понятиям "модельная полнота" и "алгебраически и экзистенциально замкнутые системы" соответственно.

В разделе 2.5 мы вводим понятие универсального вложения групп.

Определение. Пусть Н - группа, С - подгруппа Н. Будем говорить, что С универсально вложена в Н (обозначение: С <у Я), если для любой конечной системы равенств и неравенств

ч • • • ■> 9гт 5 ®г15 • • • 5 "£«п) — 1 ? 2 £

• • •, 9ц, Хн, • • •, ®.-п) Ф 1, 3 € </, (22)

где - элементы подгруппы С, из разрешимости (22) в Н следует ее разрешимость в С.

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

Теорема 2.19. Пусть Н - группа, С - подгруппа Н,

= { множество универсальных предложений с константами из С. истинных в Н. } Тогда следующие условия эквивалентны:

1. в <уЯ;

2. Ткуга(Н) = Т/гу^С), т.е. универсальные теории (7 и Н с константами из С совпадают.

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

Пункт 2.6 содержит необхо�