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

• Гороховская, Наталия Германовна
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Гороховская, Наталия Германовна

Содержание

0 Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.2 Примеры

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

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

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

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

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

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

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

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

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

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

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

3 Литература

Введение диссертации (часть автореферата) на тему «Об определимости понятия "быть свободной алгеброй" в бесконечных логиках и универсальные вложения групп»

О Введение

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

В конце 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 содержит необходимые сведения из теории С?-групп. Мы даем их, следуя статье Г.Баумслага, А.Мясникова и В.Ремесленникова [ВМК-АССП ].

В пункте 2.7 мы связываем понятие универсального вложения подгруппы Н в группу (2 с понятием &'-дискриминируемое™ в случае, когда С - нетерова по уравнениям группа.

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

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

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

Определение. Группа С удовлетворяет условию (51), если для любого элемента и бесконечного порядка и любых элементов д = (д\..... дк+1), таких, что и] ф 1, существует такое натуральное число I, что множество

Зи,д,г = {д\иа1д2 • ..дкиакдк+1 | | а,- |>

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

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

Теорема 2.21. Пусть А,В и Тку(А) = Тку(В). в = А*В. Тогда множители А, В универсально вложены в группу С.

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

/ = ... ¡т(д^,х,у)}

- некоторый набор словарных функций, т.е.

/г е С * Р(Х) * ^(Г); X = {а*,. .., аГ}; У = {У1,. .., у,}. Определим формулу

= 3(^1,..., (/1(^1, ж, у) = 1 к...к/т(д^,х,у) = 1) Определение. Диофантовым предикатом будем называть множество

Ал® = • • • > к а) € С* : формула выполняется на ..., /¿5)}

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

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

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

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

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

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

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

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

Определение 1.2 Пусть х ~ бесконечный кардинал. Тогда Loox - это логика, формулы которой имеют дизъюнкции и конъюнкции по любому произвольному множеству формул и кванторы по множеству переменных, мощность которого меньше Х-

Так, например, все формулы логики Ь0ош имеют лишь конечное число кванторов в подформулах.

Определение 1.3 ЬШ1Ш - это логика, формулы которой имеют счетные (< uii) дизъюнкции и конъюнкции и кванторы по конечному (< и>) числу переменных.

При доказательстве фактов, приводимых в данной работе, используется критерий эквивалентности моделей в бесконечных логиках, основанный на игре Эренфойхта [Ehr]. Этот критерий был первоначально разработан Эренфойхтом для доказательства эквивалентности моделей в логике первого порядка. Затем он был адаптирован Карп [Karpl] для L^, а Бендой [Ben] и Калаисом [Cal] - для логики LooX, х > Для формулировки критерия нам необходимы следующие понятия. Пусть А = {А, а) и В = {В, а) - модели сигнатуры а с основными множествами А и В соответственно.

Определение 1.4 Частичный изоморфизм из модели А в людель В - это изоморфизм f : А' —> В', где А! и В' - подмодели А и В соответственно.

Определение 1.5 Систему J частичных изоморфизмов из А в В назовем х~ расширимой, если для любого f : А' В', f € J, и для любых множеств X £ А и Y £ В, \Х\ < х, 1^1 < Х> существует частичный изоморфизм f : А!' —> В" такой, что / С /' иХ С A", Y С В".

Теперь мы можем привести

Критерий эквивалентности эквивалентности моделей в логике £ооХ;Х ^ lo. Модель А £ооХ-эквивалентна модели В тогда и только тогда, когда существуют Х расширимые системы частичных изоморфизмов из А в В и из В к А .

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

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

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

1.2.1 Определение HF-логики

Дадим, следуя статье трех авторов [BLR], необходимые определения.

Пусть А = (А; а) - алгебраическая система конечной сигнатуры. Рассмотрим некоторую надстройку системы А , которую будем обозначать HF(A). Для произвольного множества М обозначим через F{M) множество всех конечных подмножеств М. Определяем множество HF(A) по индукции:

оо

Ао = F{A), Ап+1 = F(AU An), HF{A) = 1J An.

n=0

Тогда

HF(A) = {A U HF(A), <7, €),

где £ - предикат принадлежности на A U HF(A). Это обычная алгебраическая система сигнатуры <т* = сг U в которой для определенности все предикаты из а на элементах из HF(Á) ложны, а операции принимают в качестве значения элемент 0 £ HF(A). Элементы из А называются праэлементами. Считаем, что ни один элемент из A U HF{A) не принадлежит никакому элементу из А. Формулы языка HF-логики (языка Lhf) сигнатуры а - это формулы логики первого порядка с равенством сигнатуры <т* . Таким образом, изучать систему А в HF-логике - это все равно, что рассматривать систему HF(A) в обычной логике первого порядка.

Определение 1 3 Алгебраические системы А и В называются HF-эквивалент-ными (пишем А=НР В), если на них истинны одни и те же формулы HF-логики без свободных переменных.

Надстройка HF(A) есть на самом деле минимальное допустимое множество с праэ-лементами из А. Поэтому для HF-логики автоматически справедливы многие логические результаты, описанные, например, в [В]. В частности во множестве HF(A) с помощью E-формул интерпретируются натуральные числа N (0 —» 0 , п + 1 —> nU{n}) и все рекурсивно перечислимые отношения на них.

В [ВТ] описан фрагмент языка ЬШ1Ш (здесь обозначается Lar), который эквивалентен по выразительной силе HF-логике, но не требует расширения сигнатуры и построения надстройки. Напомним определение этого языка. Пусть ip G Ьш%ш - произвольная формула. Определим для нее понятия >р G Lar, r(ip) < п (ранг (р для натуральных п) и v(<p) (номер <р).

а) Все атомарные формулы сигнатуры а логики первого порядка принадлежат

LAr] для этих ср полагаем, что r(<p) < п для любого п, и и(<р) - геделев номер.

б) Пусть <р - одна из формул <pi&¿<p2, <р>\ У <¿>2, <fii <¿>2i ¥2, "Vi- Предположим,

что понятия ipi G Lar, </?2 G Lar, v(<p 1) и v(y2) известны и для всякого п известно, что означают высказывания г(tp\) < п и г((р2) < п. Тогда:

Ч> ^ LAr;

r(p>) < п 4=Ф- r((pi) < п и г(у)2) < та; г/(9?) эффективно вычисляется по v(<p\) и

c) Пусть р> G Д-ш- Тогда Vx^(x) G LAr и Зж^(ж) G ¿ля!

если r(c¿>) <п ж <р = У уф если r(<£>) < п и <р не начинается с V

если r((¿?) < п и = если r{ip) < п и (р не начинается с 3

d) ь>(Ух<р) и г/(3ж<£>) эффективно вычисляются по и(х) и

Пусть Ф С ЬШ1Ш. Допустим, что <р G Lar для всех р> из Ф и что существует такое г, что \/tp G Ф г(</?) < г. Кроме того пусть существует такое т, что все свободные переменные каждой с/? G Ф содержатся в списке Vq, ..., vm. Наконец допустим, что множество X = {v(ip) | <р> G Ф} арифметическое. Тогда:

УФ G Lar и &Ф G LAr;

г (УФ) < п + 1 (и г(&Ф) < п + 1) r(X) < п и У(р G Ф г(<р) < п, где г(Х) есть минимальное такое т, что X определимо в арифметике Ет-формулой;

номер г/(УФ) и г/(&Ф) эффективно вычисляется по г(Х) и минимальному ЕГ(;г)-индексу множества X.

г(\/ж<£>(ж)) <

п

п + 1

г(3жс^(ж)) <

п

п + 1

Итак, мы определили для произвольной формулы <р 6 ЬШ1Ш понятия <р G Lar, ранга формулы и ее номера. Определим теперь соотвествуюгцие понятия для <р £

Lr.

а), в) и с) - из определения языка Lard) В этом случае мы предполагаем, что ^(Ф) = п - предикат. Пусть Ф С LWlUJ. Допустим, что (р G Lr для всех ip из Ф и существует такое г, V<¿> G Ф г(ц>) < г. Кроме того, для любой формулы ip из Ф существует номер nv = причем

множество

Г = {nv | <р е Ф}

рекурсивно перечислимо. Тогда

УФ G Lar и &Ф е LAr;

г(УФ) < п + 1 (и г(&Ф) < п + 1) V<¿> G Ф г(<р) < п.

Номер z/(V#) и г^(&Ф) эффективно вычисляется по номеру машины Тьюринга, для которой Г является множеством остановки при определенном выборе Г.

Предложение 1.1 ([ВТ]) Справедливо следующее:

1. Для любой LnF-формулы ip(xi,...,xn) существует

ф(хi,... ,хп) в Lr эквивалентная ей на праэлементах любой модели.

2. Для любой lr-формулы <p(xi,..., хп) существует ей эквивалентная ф(хi,..., хп) в Lar-

3. Для любой lar-формулы <р(хг,.. ., хп) существует ф(хг,..., хп) в l}{p эквивалентная ей на праэлементах любой модели.

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

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

В этом пункте мы докажем формульность в HF-логике классов свободных конечно порожденных полугрупп и групп, а также класса свободных конечно порожденных ассоциативных некоммутативных колец. Все доказательства будут проведены с помощью следующего приема: мы проинтерпретируем эти объекты в арифметике N = {+,-,0,1}. Поскольку арифметика сама интерпретируема в любой HF-модели (см. [В]), то мы докажем таким образом, что эти объекты также интерпретируемы в любой HF-модели.

Предложение 1.2 Класс свободных конечно порожденных полугрупп формульно определим в HF-логике.

Доказательство. Пусть А = {йо, • • •, «а-1 } ~ непустое множество. Будем называть его алфавитом. РДА) - свободная полугруппа над алфавитом А. Пусть а^ ... а;т и ал ■■■аы ~ слова из Р8(А). Определим операцию умножения на РДА) следующим образом:

ап • • ■ агт ' а31 ■ ■ ■ а]гг ~ ан ■ ■ • аг,паЛ ■ ■ • а]п

Для того, чтобы интерпретировать РДА) в арифметике достаточно закодировать все слова от букв а0,..., а к-1 и определить на полученных кодах операцию, соответствующую операции умножения.

Пусть ю = а,0 ... - некоторое слово, 1(ги) ~ его длина. Сопоставим слову го номер у(и)) по следующему правилу:

1. Номером буквы является ее порядковый номер в алфавите.

2. Номер слова - это выражение вида:

и{ю) = Ка»о) + + • • • + и{щТ)кг (1)

Обозначим операцию кодирования буквой А. Тогда, А(го) = {и{ги), /(»•'))• Теперь, если

V = и ■ IV, то

у = и-ю& (и(и) + 1у(ю)к1{и))к(1(у) = 1{и) + /(ю))

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

!/(и) < к1{ь).

<1

Предложение 1.3 Класс свободных конечно порожденных групп является формульным в НР-логике.

Доказательство. Чтобы решить проблему интерпретируемости свободной группы в арифметике дополним кодировку элементов свободной полугруппы. Пусть снова А = {«о, • • •, о/с-а} - алфавит. Обозначим А-1 = {а^\ • • •, а^}. Рд(А) - свободная группа над алфавитом А. Элементы Р<з(А) - это редуцированные слова. Закодируем их парами натуральных чисел. Номер а"1 - это выражение вида

Список литературы диссертационного исследования кандидат физико-математических наук Гороховская, Наталия Германовна, 1998 год

Список литературы

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

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

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

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

[GR] Гороховская Н.Г., Ремесленников В.Н. О понятии "быть свободной алгеброй в 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.

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

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

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

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

[Mall] Мальцев А.И. Алгебраические системы. М:Наука, 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] Фукс JI. Бесконечные абелевы группы. Т.1 - М:Мир, 1966.

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

[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: OmSU, 1997. - 25p.

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

[Ks] Keisler H.J. Model theory for iniinitary 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 over groups. Invitation of Mathematics (submitted).

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

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

[Cal] Calais J.P. La methode de Fraisse dans les languages infints." C. R. Acad. sci. Paris 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 Р.С. 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 O., Myasnikov A., Remeslennikov V. Logical languages and 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] Mekler A.H. How to constract almost free groups. Canadian J. Math. 32 (1980), pp. 1206-1228.

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