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

российская академия наук институт информационных технологии и прикладном математики

11л правах рухопис хт

КПАНЧИНЦКВ Владимир Ильич

ТКРПРЕТЛЦИЯ НЕ-—ЛОГИКИ НА ПЕРИОДИЧЕСКИХ АЕЕЛЕВЫХ ГРУППАХ

.01.06 — математическая логика, и теория чисел

Автореферат (иссертации на соискание ученой степени: хгшлидата физкжо—математических наук

ОМСК

Работа выполнена в Институте Информационных Технологий и Прикладной Математики СО РАН

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

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

- кандидат физико-математических наук, доцент Мартынов Леонид Матвеевич

Ведущая организация - Иркутский государственный университет

Защита состоится /Ш/ИсЫ 1992 г. в " часов на заседании специализированного совета К 064.35.02 при

Омском государственном университете по адресу: 644077, Омск, пр. Мира 55-А.

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

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

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

специализированного совета Л/) /п

кандидат физ.-мат. наук А. Ромакьков

^ I1

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

В начале 50-х годов теория моделей выделилась в самостоятельный раздел математической логики. Основополагающе работы по теории моделей логики предикатов первого порядка (логики языка ¡-илЛ ) принадлежат Левенгейму, Геделю, Тарскому, Мальцеву. Процесс развития теории моделей Еел таким образом, что многие понятия и построения имели финитарный характер. Например, построение формул языка и л и) или элементарная эквивалентность алгебраических систем, которую можно определить посредством конечных объектов - конечных частичных изоморфизмов [ 3 ], [4 3, С 17 3, С 20 3. Но при этом выяснилось, что многие важные свойства моделей невозможно выразить на языке

■ Например, в теории групп такими свойствами оказались периодичность, конечная порозденность, понятия свободы и аппроксимируемости. Последнее обстоятельство стимулировало исследование моделей в бесконечных логиках. Эти логики возникают, если отказаться от некоторых требований финитности в классической логике первого порядка, а таюке при допущении, что кванторы берутся не только по предметным, но и по сигнатурным символам [ 2 3, [5 3, [ 18 3, [ 20 3, [ 22 3.

В этой связи используется несколько подходов к изучению моделей. Один из них связан с интерпретацией, в модели языка, допускающего бесконечные конъюнкции и дизъюнкции ( Л^Л или 1_ ао с^ )■ Здесь /_<иЛо-> логика, допускающая не более чем счетные конъюнкции и дизъюнкции и конечны" кван-тификации по предметным переменным. Логика оои) в отличие от ¿л, иЗ допускает любые бесконечные конъюнкции и дизъюнкции.

Другой подход связан с рассмотрением многоосновных моделей в рамках обычного языка исчисления предикатов [ 8 3, [ 93. В этом случае допускается действие сигнатурных символов на

различных основных множествах, что расширяет выразительные возможности этих моделей.

Наконец, е ряде работ отмечалась естественность использования при изучении алгебраических объектов слабой логики второго порядка С 7 ], С 93, С 10 3, Е 17]. Далее эту логику будем называть HF-логикой. HF-логика имеет интерпретации указанных выше типов. А именно, интерпретацию HF-логики-на модели можно определить через некоторый фрагмент L н р логики L- , через построение двуосновной модели

- HF-надстройки рассматриваемой модели itt , а также с использованием языка второго порядка. Эквивалентность всех трех подходов доказана в работе [2 3.

В то же время финитарность присутствует в определении этой логики, поскольку HF-надстройка HF()TCL) модели Yit. строится на основе наследственно конечных ( Hereditarily Finite - отсюда и название логики ) множеств над основным универсумом модели WL .

Оказалось, что HF-логика имеет непосредственное отношение к допустимым множествам [ 7 3. [ 17 ]. А именно, можно рассматривать Hf-CW-4) как допустимое множество, то есть как транзитивную ( в смысле теории множеств ) модель, удовлетворяющую аксиомам Крипке-Платека.

В этой логике выразимы различные конечные построения, она допускает интерпретацию натуральных чисел и их арифметики. В ней возможно определение по 21 -рекурсии [ 7 3.1 17 3, что позволяет,в частности,определить конструктивные ординалы, то есть ординалы меньшие первого нерекурсивного ординала Это обстоятельство, а также то, что понятия изоморфизма и элементарной эквивалентности являются ключевыми при изучении моделей, а классификация алгебраических систем с точностью до изоморфизма или элементарной эквивалентности - одна из важнейших задач теории моделей, послужило основанием для гипотез [ 10 3:

Проблема 7. Описать счетно категоричные группы ( алгебраические системы ) в HF-логике;

Проблема 9. Пусть А и В> редуцированные абелевы р -группы. Тогда HFYА) = НР( £>) тогда и только тогда,

когда для всех конструктивных ординалов инварианты Ульма-Кап-ланского у А и ЕЬ либо конечны и равны, либо одновременно бесконечны.

Классическая теорема Хигмана утверждает,что группа - рекурсивно определена тогда и только тогда, когда она изоморфно вложи},а в некоторую конечно определенную группу. Она дает еще один пример алгебраической характеризации условия из теории рекурсии.

Аналогичные утверждения справедливы для полугрупп (В. Л. Муре кий Г 11 3), ассоциативных алгебр над полем, конечно порожденным над простым подполем ( ЕЯ. Беляев [ 1 ]), для алгебр Ли над аналогичным полем характеристики X 4=- 2. (Г. П-Кукин С 6 ]).

3 1979 году Л. А. Бокуть и Г. П. Кукин предложили называть многообразия (классы) алгебр 1П. , в которых любая рекурсивно определенная в алгебра вложит в алгебру, конечно . определенную в "оХ- , хигмановыми многообразиями ( классами )-и поставили вопрос о поиске новых хигмановых классов алгебр ( в частности, многообразий, в которых верен аналог теоремы Хигмана ).

Цель работы. Найти критерии элементарной эквивалентности в НР-логике ( НР-эквивалентности ) для периодических абелевых групп на языке конечных частичных изоморфизмов. Дать алгебраическую характеризации условия элементарной эквивалентности и счетной категоричности в НР- логике для этого класса групп. Найти новые многообразия алгебр в которых верен .аналог теоремы Хигмана.

Методика исследования. Методика исследования носит как теоретико-модельный характер, так и теоретико-групповой. Доказательства некоторых утверждений носят комбинаторный характер.

Научная новизна и практическая ценность. Все основные результаты диссертации являются новыми и имеют теоретическое значение. ' Они применемы при исследовании абелевых групп в НР- логике.

Апробация. Результаты диссертации докладывались на "Алгебраическом семинаре" ОмГУ, семинаре "Теория групп" ОКО ВЦ СО АН СССР, семинаре "Алгебра и логика" НГУ, на 10 Всесоюзной

конференции по математической логике, Алма-Ата 1990, на Международной конференции по алгебре памяти А. К Ширшова, Барнаул 1991.

Публикации. Основные результаты диссертации опубликованы в четырех работах, список которых приведен в конце автореферата. Работы [273 -С 28] написаны в соавторстве с Г. П. Кукиным.

Структура работы. Диссертация состоит из введения, четырех глав и списка цитируемой литературы. Текст диссертации изложен на 106 страницах машинописного текста. Список литературы содержит 33 наименования.

Краткое содержание диссертации. Во введении дан краткий обзор работ по теме диссортагд-ш, сформулированы основные результаты диссертации и описана ее структура. Глава I состоит из трех параграфов и носит б основном вспомогательный характер. В ней приведены основные определения и результаты,используемые в дальнейшем и касающиеся элементарной эквивалентности и НР-логики. В § 1 приведены основные сведения о элементарной эквивалентности, приведены критерии элементарной эквивалентности моделей на языке частичных изоморфизмов. В § 2 согласно работе С 2 ] определен фрагмент нр языка I— ^ , отвечаюадай НИ-логике, приведено определение НГ-надстройки модели.

В работе А. Г. Мясникова г В.Е Ремесленншова [ 21 ] введено понятие со -изоморфизма, определяемое на языке конечных частичных изоморфизмов.

Определение. Алгебраические системы и ко-

нечной сигнатуры называются -изоморфными, если для любого натурального числа т. существуют непустые множества

Фо & фл & > » . £г С

конечных частичных изоморфизмов из ТСТ. в такие,что:

1. 5) для произвольного

Ч>€: Ф^С^О , - < ^ и любых конечных подмножств X \ , У & 1 ТС | найдутся частичные изоморфизмы Ул. , Ч'з. , продолжающие с условием: X & 1>о~и V.

В § 3 доказывается предложение 1.4, утверждающее, что условие oJ -изоморфности моделей является достаточным для их элементарной эквивалентности в KF-логике ( HF-эквивалентности ). Лемма 1.5. показывает, что прямые суммы алгебраических систем сохраняют оУ -изоморфность.

Глава II посвящена периодическим абелевым группам. В первом параграфе приведены определения и результаты о периодических абелевых группах, необходимые для дальнейшего изложения. '

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

Определение. Подгруппа G- группы А выделяется формулой языка L , если

dr = {cl! А ь }

В этом случае G- называется L. -формульной в А .

Предложение 2. 4 показывает, что подгруппа р"*~А периодической группы А является -формульной в А для всех ординалов < . Как следствие получаем формульность в HF-логике ульмоеских подгрупп АСк 1

для к. € oui

Для функции тдеэс-) с множеством значений в множестве кардиналов положим аХс*") — wvivu , } .

Зафиксируем для дальнейшего разложение периодической абелевой группы А. в прямую сумму своих р -примарных компонент А =■ Ар . Здесь и далее *Ар - это максимальная р -подгруппа в группе А . Для произвольной группы А обозначим через Т)С А ) максимальную делимую подгруппу в А , через г. С А ^ ранг группы А и пусть U д ( о(Л - инвариант Ульма-Капланского группы А ( см. [ 15 ] ).

Следующее утверждение показывает, что в HF-эквивалентных периодических абелевых группах инварианты Ульма-Капланского для всех ординалов vL < t-O2' либо конечны и равны, либо одновременно бесконечны.

Предложение 2.8. Пусть А и È> HF-эквивалентные периодические абелевы группа Тогда для простого числа р и произвольного ординала < LK)i выполнено ра-

венство =

фи этом, если р -длина £-р (А ^ < ■ ( то

^ ( = *ске>Р^

Лемма 2.11 утверждает, что свойство периодической абелевой группы быть финитно аппроксимируемой аксиоматизируемо " в языке нр

Лемма 2.12. Класс редуцированных абелевых р -групп конечного ульмовского типа аксиоматизируем в языке I— цр- .

Заметим, что класс редуцированных абелевых р -групп неаксиоматизируем даже в языке I—оо ^ Г 18 3.

В § 3 главы II доказаны утверждения, позволяющие строить продолжения конечных изоморфизмов в абелевых р -группах на конечные подмножества элементов. Техника доказательства этих утверждения опирается на понятие высоты элемента и понятие собственного элемента относительно подгруппы в абелевой р -группе (см. С 15 ], Г 16 ] ).

Пусть А и & абелевы р -группы. Для фиксированного ординала с условием £■(Л), > оС определим множество С-(и.) как множество конечных изоморфизмов из А в Е> , сохраняющих высоты до ординала . А именно: • я { н)

где Сг и Н конечные подгруппы в А и £> соответственно, причем для каждого элемента х ё-

1гА<.*Л < л. -то =

^(х4) ^ оС ло ' К £■(*)) Ъ <*. .

если

если

Основным в этом параграфе' является следующее

Предложение 2.15. Пусть А , & абелевы р -группы такие, что £(А},£-(В) > к* М . Если инварианты Ульма-Капланского групп А и &> таковы, что

йл(Л) = иби)

для всех оС < . Тогда для произвольного конеч-

него изоморфизма £ 6 и любого конечного подмно-

жества £ к А существует конечный изоморфизм У , продолжающий ^ такой, что . ■ £ & Ъоу^ V ,

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

В работе В. Шмелевой С 23 ] получен критерий элементарной эквивалентности абелевых групп в терминах алгебраических инвариантов. Тем самым дана алгебраическая характеризация теоретико-модельного условия элементарной эквивалентности.

В бесконечных логиках аналогичный критерий для периодических абелевых групп был получен в работе Д. Барвайса и П. Ок-лофа С 18 ]. В программных логиках для абелевых р - групп аналогичная характеризация приведена в работе М. А. Тайцлина [ 14 ].

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

Теорема 3.4. Пусть А , периодические абелевы

туппы. Тогда следующие условия эквивалентны:

1) = НР(Ь> ;

2) Для произвольного простого числа р и любого ординала «(. < верно равенство

Если кроме того р -длина 2р(А) < ^^, то

^СЭ(Ар^) = * (ЪСЬр»

3) Группы А и &> являются ск) -изоморфными.

Это утверждение отвечает ча вопрос поставленный А. Г. Мяс-никовым и В. Н. Ремесленниковым С 10 ]', его можно рассматривать и как аналог известной теоремы Ульма, утверждающей, что счетные

редуцированные абелевы р -группы определяются с точностью до изоморфизма своими инвариантами Ульма-Капланского [ 16 ].

Следствия 3.5. и 3.б. указывают на существование различных НТ-эквивалентных, но неизоморфных периодических абелевых групп.

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

Следствие 3.7. Редуцированные абелевы группы А и £> ИТ-эквивалентны тогда и только тогда, когда для любого ке^ элементарно эквивалентны к. -е ульмовские факторы

Ао=Ьо,А-1=: Ьл, >Ч , Ак=. Ьк ,

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

Известно, что элементарно . эквивалентные алгебраические системы, одна из которых конечна, будут изоморфными. Таким образом, элементарная теория ТЯ. С СЛ.) определяет конечную алгебраическую систему СК. с точностью до изоморфизма

Теорема Левенгейма-Скулема говорит, что для бесконечны) моделей в рамках языка с~>со это не так

Естественным в этой связи был вопрос о категоричност! теории 7" в некоторой мощности А . В этом случае категоричность теории означала, что с точностью до изоморфизма существует только одна модель этой теории мощности Л

Оказалось, например, что теория бесконечных элементарны: абелевых р -групп категорична в любой несчетной мощности. Отметим, что в логике /. оо си любая счетная модель опре деляется с точностью до изоморфизма своей элементарной теорией [ 20 ].

Будем говорить, что алгебраическая система являете счетно-категоричной в языке ,если она определяется

классе счетных систем своей э.г- ментарной теорией с точность до изоморфизма. Таким образом, алгебраическая система счетно-категорична в языке 1- со оо тогда и только тогда

когда она счетна

Следствие 3.9. Периодическая абелева группа А счетно-категорична в НР-логике тогда и только тогда, когда сна имеет конечный ульмовский тип.

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

С другой стороны, теорема Скотта [ 22 ] утверждает, что в язике ■ I— и} любая счетно-категоричная модель, определяется одним предложением.

В этой сеязи будем говорить, что алгебраическая система является сильно-категоричкой в языке ¿_ , если существует предложение этого языка такое, что для

любой счетной системы ^ имеем Т^. И Я5 тогда и только тогда, когда ^

М. А. Тайцлин [ 13 ] получил условия сильной категоричности в ЬГ-логике конечно порожденных алгебраических систем в конечном расширении исходной сигнатуры.

В работе И. И. Сухорутченко С 12 ] приведены необходимые и достаточные условия сильной категоричности неограниченных абелевых р -групп в программных логиках.

Следуя этой работе в § 2 главы III мы приводим критерий сильной категоричности неограниченных абелевых р -групп а НР-логике. Заметим, что существуют счетно-категоричные абелевы р -группы, не являющиеся сильно-категоричными.

В работе А. Баудиша С 19 ] исследуются условия, при которых тензорное произведение на абелевых группах сохраняет элементарную эквивалентность. В третьем параграфе рассматриваются тензорные произведения периодических абелевых групп.

Следующее предложение говорит, что в классе периодических абелевых групп тензорное произведение сохраняет элементарную эквивалентность в НР-логике.

Предложение 3.11. Пусть А , Ь, С , !> - пе-

риодические абелевы группы, удовлетворяющие условиям = НРС , = НРСЬ)

ТогДа НГС А® С} = НРСЬ®^^ .

В § 4 главы III получено еще одно следствие основного результата. Предложение 3.14. утверждает, что для любых абеле-вых групп их периодическое произведение сохраняет элементарную эквивалентность в HF-логике.

Предложение 3.14. Пусть А , В , Сi , Ъ - абеле-вы группы и .

НРСА4» - ИГ((ЪУ , ИГСС) = НГСЪ) .

Тогда НР(То* С А, С!^ - НРС"Гоч.С .

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

В работе [ 28 ] автором совместно с Г. П. Кукиным указаны условия достаточные для того, чтобы квазимногообразие алгебр над поле(£, конечно порожденным над простым подполем характе-ристигаЬ'бьию хигмановым. Поиск многообразий алгебр осуществляется с использованием этих достаточных условий. Основным результатом этой главы является

Теорема 4.3. В многообразии алгебр XL над полем I- , конечно порожденным над простым подполем характеристики X ^ 2. , удовлетворяющем тождеству

сэь^ г- = + ос суг^

алгебра рекурсивно определена тогда и только тогда , когда она изоморфно вложима в некоторую конечно определенную алгебру. В заключение отметим, что результаты главы IV получены под руководством Г. П. Кукина, которому автор выражает свою признательность.

Автор благодарен научному руководителю А. Г. Мясникову за постановку задач и полезные обсуждения.

Ли тература

1. Беляев В. Я. Подкольца конечно определенных ассоциативных колец // Алгебра и логика. - 1978. - т. 17, N 6. --с. 327-338.

2. Беляев К Я , Тайцлин М. А. Об элементарных свойствах экзистенциально замкнутых систем // Успехи мат. наук. - 1979. --т. 34, вып. 2. - с. 39-94.

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

4. Ершов Ю. Л., Палютин Е. А. Математическая логика. --Ы.: Наука- 1979.

5. Кейслер X. Основы теории моделей / В кн.: Справ, кн. по мат. логике, ч. 1. Теория моделей. - М.: Наука-1982. - с. 55-109.

6. Кукин Г. П. Подалгебры конечно определенных лиевых алгебр // Алгебра и логика.- 1979.- т. 18, N3.- с. 311-327.

7. Маккаи М. Допустимые множества и бесконечная логика / В кн. Справ, кн. по мат. логике, 4.1. Теория моделей. - М.: Наука. - 1982.

8. Мальцев А. И. Модельные соответствия. В кн.: Избранные труды, т. 2. Матем. логика и общая теория алгебраических систем. -М.: Наука, - 1976.-с. 77-99.

9. Мясников А. Г., Ремесленников В. Н. Допустимые множества в теории групп // Препринт N603. - Новосибирск: ВЦ СО АН СССР.- 1988.- 25 с.

10. Мясников А. Г., Ремесленников Е Е Логика конечных типов в теории групп // Бюллетень Сибирского математического общества- Новосибирск.-1990. - с. 18-25.

11. Мурский К Л. ' Изоморфная вложимость полугрупп с рекурсивно перечислимым множеством определяющих соотношений в конечно определенную полугруппу // Матем. заметки. -1957.--Т. 1, N 2.- с. 217-228.

12. Сухорутченко И. И. Программно категоричные абелевы р-группы // В кн.: Теория нерегулярных кривых в различных геометрических пространствах. Алма-Ата 1979. -с. 77-90.

13. Тайцлин М. А. Описание алгебраических систем в слабой логике порядка и) ив программной логике // В кн.: Теория не-

регулярных кривых в различных геометрических пространствах. Алма-Ата. - с. 91-98.

14. Тайцлин М. А. Программные теории периодических абеле-вых групп // В кн.: Теория нерегулярных кривых в различных геометрических пространствах. Алма-Ата 1979,- с. 98-107.

15. £укс JI Бесконечные абелевы группы. TI.-M.: Мир,1974.

16. йукс JL Бесконечные абелены группы. Т2.-М.: Мир, 1977.

17. Barwise J. Admissible Sets and Structures. --Berlin: Springer, 1975.

18. Barwise J., Eklof P. Infinitary properties of Abelian torsion groups // Annals of Math. Log.- 1970.- v. 2, N1. -p. 25-68.

19. Baudisch A. Tensor products of moduls and elementary equivalence // Universalis Alg. - 1984.- V. 19. - p. 120-127.

20. Karp. Languages with Expression of Infinite Length. - Amster.: North - H'oll. , 1964.

21. Myasnikov A.G. , Remeslennikov V.N. Elementary group equivalence with the integral length function // 111. J. of Math. - 1986.- v. 30, N2.- p. 335-354.

22. Scoott D. Logic with denumerably long formulas and finite strings of qwantifiers // Theory of Kfodels. - 1965. -Amsterdam, North-Holland, -p. 329-341.

23. Szmieleva V. Elementary properties of abelian groups // Fund. Math. - 1954.- v. 41.- p. 203-271.

24. Higmn 6. Subgroups of finitely presented groups // Proo. Roy. Soc. London.-1961.- v. 262.-p. 455-475.

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

25. Epar.chintsev V. I. HF-equivalence of abelian torsion groups // Шздународяая конференция по алгебре памяти А. И. Ершова. Барнаул, 1991: Тез. докл. по логике и универсальной алгебре.-Барнаул: /JГУ, ffli СО АН СССР, ЯГУ. - Новосибирск, - 1391.

- с. -12.

26. Епанчинцез R И. HF- эквивалентность периодических абелевых групп // Препринт м 2, Омск: КИТ и пи СО ДН СССР. --1991. - 23 с.

27. Епанчинцэз В. IL , Кук:: я Г. Я. О квазиьшогосбразшх Хигмана // 18 Всесоюзная алгебраическая конференция. Тез. со-обш, - Кишинев. - 1985. - ч. 2. - с. 185.

28. Епанчиытз В. >1, Кукин Г. П. О кзазимногосбразиях Sir мал а /'/ В сб. Вычислимые инварианты в теории алгебраических систем, Новосибирск: ЕЦ СО АН СССР. - 1987,- с. 90-110.