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

На правах рукописи УДК 510.67

ВЛАСОВ ДМИТРИЙ ЮРЬЕВИЧ

СТРУКТУРНАЯ ХАРАКТЕРИЗАЦИЯ

АЛГЕБРАИЧЕСКИХ СИСТЕМ С ОГРАНИЧЕНИЕМ НА СЛОЖНОСТЬ БУЛЕВОЙ АЛГЕБРЫ ФОРМУЛЬНЫХ КЛАССОВ ПОДСИСТЕМ

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

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

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

Работа выполнена в Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук

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

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

профессор Д. Е. Пальчунов - кандидат физико-математических наук, доцент С. В. Судоплатов

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

Защита состоится 3 июня в ч. мин. на заседании диссерта-

ционного совета К 212.174.01 Новосибирского государственного университета по адресу: 630090, Новосибирск-90, ул. Пирогова, 2.

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

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

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

диссертационного совета К 212.174.01 ______

кандидат физико-математических наук >*-Ч~л ° А.Д. Больбот

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

Актуальность темы. Исследование структурных свойств алгебраических объектов является классической задачей, решавшейся на протяжении всего развития современной математики. Но, как правило, полное решение проблемы структурной классификации находилось лишь для узких классов алгебраических систем: конечно порождённых абе-левых групп, векторных пространств, алгебраически замкнутых полей и т.д. Для постановки общей проблемы классификации в 70-80 годах XX века С. Шелахом [1] была разработана теория стабильности, в которой условие классифицируемости для аксиоматизируемых классов систем было точно сформулировано и обосновано [б], [15].

Но, тем не менее, в рамках теории стабильности такой естественный и важный объект как бесконечный линейный порядок оказывается нестабильным, то есть не поддающимся структурной классификации. В связи с эти были предложены и другие подходы к построению структурной теории для нестабильных теорий - в частности теория О-минимальных структур [5], Т*-стабильность [17] и E*-стабильность [14], обобщающие классическое понятие стабильности.

В классической теории стабильности для классификации алгебраических систем используется понятие системы инвариантов - некоторого дерева, листья которого помечены кардиналами. Существование такой системы инвариантов для теории автоматически влечёт немаксимальность функции спектра для достаточно больших мощностей [2], поэтому теория линейного порядка, имеющая максимальный спектр, не может быть классифицирована при помощи такой системы инвариантов. С другой стороны, теория О-минимальных структур возникла из идеи, что в качестве инварианта для классификации алгебраических систем можно взять сам порядковый тип некоторого линейного порядка, то есть линейный порядок изначально брался в качестве базового простейшего объекта [13].

Кроме того, простейшие в смысле классического понятия стабильности объекты - сильно минимальные алгебраические системы - оказываются устроенными весьма не просто. Некоторое время стояла гипотеза Зильбера [11] утверждающая, что сильно минимальные алгебраические системы либо интерпретирут бесконечное поле, либо локально моду-лярны. Однако Хрущовский [12] опроверг эту гипотезу, построив не локально модулярную сильно минимальную алгебраическую систему, в

которой не может интерпретироваться никакая бесконечная группа.

Данная работа посвящена построению теории, подобной теории и -стабильности [3], в которой понятие элементарного типа кортежа замещается на понятие элементарной теории подсистемы. Практически вся теория моделей построена на базовом понятии элементарного типа кортежа - множества формул, характеризующих элементы этого кортежа относительно всех других элементов системы. Понятие типа кортежа по существу описывает отношение между элементарным объектом (кор-тежом), элементы которого не имеют структуры, и всеми остальными элементами структуры. С другой стороны, если мы попытаемся ввести тип принципиально другого объекта - подсистемы в некоторой исходной системе, то этот объект уже может иметь сложную внутреннюю структуру, и в качестве элементарной характеристики такого объекта можно рассмотреть элементарную теорию этой подсистемы. Заметим, что в отличие от классического понятия типа кортежа в системе, элементарная теория подсистемы описывает не отношение этой подсистемы с другими частями исходной системы, а локально-глобальные характеристики элементов этой подсистемы (локально - потому что только для элементов данной подсистемы, а глобальные- потому что предложения описывают строение всей подсистемы глобально, в целом).

Таким образом, подобное замещение позволяет придать стандартным понятиям ранга и степени принципиально иную семантику, по став-нению с рангами в теории стабильности. По аналогии с рангом Морли [3], вводятся понятия субранга и субстепени предложения в некоторой системе, которые характеризуют структурную сложность множества теорий подсистем. Фактически, ранг и степень системы, которые определяются как ранг и степень тождественно истинного предложения, определяют сложность булевой алгебры формульных классов подсистем в исходной системе. Ограничивая ранг и степень, мы ограничиваем сложность этой булевой алгебры, то есть мы задаём класс систем ограниченной сложности (в данном смысле), для которого появляются реальные возможности строить структурную теорию. Основной результат данной диссертации состоит в полном описании структуры систем субранга 1 и субстепени 1 (сильно субминимальных алгебраических систем). Для бесконечных систем конечной предикатной сигнатуры это наименьшие возможные значения субранга и субстепени, то есть сильно субминимальные системы являются простейшими в вышеуказанном смысле системами в классе всех бесконечных систем конечной предикатной сигна-

туры. Показано, что подобные системы тесно связаны с мономорфными и конечноморфными системами, изучавшимися в 60-х годах XX века. В частности, ключевыми для доказательства основных результатов диссертации оказались несколько теорем, доказанных С. Бгазиау [7], [8], [9], и Я. Бга188е [4].

Таким образом, если сравнить предложенную в данной работе методологию классификации алгебраических систем по сложности с классической теорией стабильности, то можно сделать вывод, что две вышеуказанные проблемы - классифицируемость бесконечных линейных порядков и структурная простота простейших в данном смысле объектов - решаются положительно. Бесконечный линейный порядок типа со является сильно субминимальным (то есть простейшим в данном смысле), более того, все сильно субминимальные системы исчерпываются системами, интерпретирующимися бескванторными формулами через некоторый счётный линейный порядок очень простого вида либо через равенство. Кроме того, в отличие от общепринятого определения О-минимальных стуктур, линейный.порядок изначально не фигурирует в определении сложности системы, но возникает естественным образом как простейшая структура. Стоит отметить, что Е.А Палютин характеризовал понятия О-минимальной и слабо О-минимальной теории в терминах 81-определимости [16], которая, в свою очередь, определяется через Е*-стабильность, так что понятие О-минимальной теории может быть определено и без явного введения линейного порядка. Также можно отметить, что хотя не все сильно субминимальные системы сами являются О-минимальными, все они интерпретируются в О-минимальных структурах (соответствующих линейных порядках).

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

Методы исследования. Основными методами исследования являются современные методы теории моделей, комбинаторные методы (в частности теорема Рамсея), теорема о редукции Бгазиау (4.6 из главы 11 в [4], [9]), описывающая достаточно большие конечные подсистемы в мономорфных системах, а также теорема, характеризующая конечно-морфность в терминах бескванторной интерпретируемости в линейных порядках с константами (теорема 9.8 из главы 10 в [4]).

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

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

Доказано, что алгебраическая система конечной предикатной сигнатуры сильно субминимальна (то есть субранга 1 и субстепени 1) тогда и только тогда, когда она мономорфна и множество элементарных типов бесконечных подсистем в ней конечно..

Также доказываются два промежуточных, но тем не менее имеющих самостоятельную ценность факта. А именно, установлена монотонность функции Рго/Ие<ц{к) (эта функция ссопоставляет каждому кардиналу к, не превосходящему мощности носителя системы 21, мощностьмноже-ства типов изоморфизма подсистем в мощности ) для всех кардиналов к < и. Кроме того, дано описание шкалы бескванторной интерпретируемости для систем, бескванторно выражающихся через некоторый заданный линейный порядок.

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

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

Апробация работы. Результаты диссертации докладывались на международной научной студенческой конференции "Студент и научно-технический прогресс" (Новосибиск, 1999), 33-й Региональной молодёжной конференции „Проблемы теоретической и прикладной математики " (Екатеринбург, 2002), на конференции "Пограничные вопросы универсальной алгебры и теории моделей" (Эрлогол, 2003), а также на семинаре "Теория Моделей" ИМ СО РАН и семинаре "Алгебра и логика" в Новосибирском Государственном Университете.

Публикации. По теме диссертации опубликовано 2 статьи (в том числе одна в сборнике "Теория моделей 4") и 2 тезиса (в трудах 33-й Региональной молодёжной конференции „Проблемы теоретической и

прикладной математики" ив материалах XXXVII МНСК "Студент и научно-технический прогресс"), одна статья отдана в печать в журнал „Математические труды" (Новосибирск, издательство института-математики СО РАН). Полный список работ приведён в конце автореферата.

Структура и объём работы. Диссертация состоит из введения и трёх глав. Список литературы содержит 23 наименования. Диссертация изложена на 103 страницах текста.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Лемма 3. Пусть даны два строго т-местных предиката Р и Q, выражающихся через некоторый линейный порядок < бескванторными формулами. Тогда предикат Р выражается через () бескванторной формулой тогда и только тогда, когда Аи1(}(т) < АШр(т)

Основной леммой, широко использующейся в дальнейшем, является следующий критерий частичного изоморфизма:

Лемма 4. Пусть некоторый строго т-местный предикат Р, определённый на множестве А, выражается через некоторый линейный порядок < бескванторной формулой. Тогда любое частичное взаимнооднозначное отображениеф : {а1,...ап} —>• {61,...,¿„} является частичным изоморфизмом относительно Р тогда и только тогда, когда соответствующая характеристическая биекция является автоморфизмом из группы Аи<р(п) автоморфизмов подсистеммощности п

Кроме того, в этом параграфе приводятся некоторые определения из книги [4] (в частности определения индикативных групп - ключевого понятия для развития всей последующей теории) и лемма, обосновывающая взаимно-однозначную связь парных расширений групп в терминологии Фраиссе и групп автоморфизмов конечных подсистем в мономорфных системах.

В параграфе 1.2 вначале определяется функция Рго/Ие^(к), а также вводится понятие аморфной системы, обобщающее понятие моно-морфной системы. Следующее утверждение является основным результатом данного раздела:

Теорема 1. Пусть 21 - счётная алгебраическая система конечной предикатной сигнатуры £ с конечным числом п элементарных типов бесконечных подсистем. Тогда 21 - не более чем п-морфная алгебраическая система.

Следствие 2. Если 21 - бесконечная алгебрическая система конечной предикатной сигнатуры, то Рго/Ие<ц(ы) > Рго/Ие<ц(п) для всех п < и

В силу того, что М. Рошй [10] доказана монотонность функции для всех < , то можно утверждать, что функция монотонно неубывает на отрезке

В параграфе 1.3 изучается строение алгебраических систем конечной сигнатуры с конечным множеством элементарных типов бесконечных подсистем. Вначале рассматриваются диаграммы, описывающих стратегию построения непродолжаемого частичного изоморфизма между двумя линейно упорядоченными системами в игре Эренфойхта [19]. При помощи этих диаграмм доказывается следующая теорема, описывающая алгебраические системы конечной предикатной сигнатуры в терминах бескванторной интерпретируемости в явно заданном классе систем:

Теорема 21. Пусть 21 - некоторая бесконечная алгебраическая система конечной предикатной сигнатуры. Тогда следующие условия эквивалентны:

1. множество элементарных типов бесконечных подсистем в системе 21 конечно.

2. выполнено одно из следующих трёх условий:

(a) система 21 несчётна и все предикаты из сигнатуры £(21) выражаются через конечное число констант С и равенство бескванторными формулами.

(b) система 21 счётна, и существует такой линейный порядок

< типа и + т либо т 4- ы* + и, где т - некоторое натуральное число, на множестве А и такое конечное множество констант С, образующих начальный интервал в порядке <, что все предикаты сигнатуры выражаются через этот порядок < и константы С бескванторными формулами.

(^ система 21 счётна и существует такой линейный порядок

< типа , где - некоторое натуральное число, и такое конечное множество констант С, образующих начальный интервал в порядке < на множестве А, что все предикаты сигнатуры выражаются через предикат' (то есть трансляцию, ограниченную > на множество А\С), и константы С бескванторными формулами.

Глава 2 посвящена изучению шкалы интерпретируемости для систем, бескванторно выражающихся через заданный линейный порядок.

Теорема 3. Пусть {/!,<) - бесконечный линейный порядок. Тогда любая система, интерпретирующаяся бескванторными формулами через этот порядок, взаимно интерпретируется формулами первого порядка с некоторым индикативным предикатом из множества: {<, Тз, /з, £>4, =} и <? > 0} и иыГ > 0}

среди корорых 5 дискретных классов и две бесконечные серии.

Доказательству этой теоремы предшествует ряд лемм о взаимной интерпретируемости индикативных предикатов из одной серии но разной арности формулами с кванторами.

Глава 3 посвящена изучению строения сильно субминимальных систем. В параграфе 3.1 вводятся понятия субранга и субстепени предложения в алгебраической системе. Субранг - это функция, для каждой алгебраической системы определённая на множестве предложений сигнатуры системы и принимающих ординальные значения, а также значения -1 и оо. Субстепень - это функция, определяющаяся через субранг, и принимающая натуральные значения. Доказывается ряд свойств суб-

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

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

Теорема 4. Пусть 21 - бесконечная алгебраическая система конечной предикатной сигнатуры S. Тогда следующие условия эквивалентны:

1. 21 - сильно субминимальна

2. множество элементарных типов бесконечных подсистем в системе 21 конечно и 21 - мономорфна.

Доказательству этой теоремы предшествует ряд технических лемм, описывающих множества решений для ряда формул с индикативными предикатами. Основное назначение этих лемм - показать, что если система 2t сильно субминимальна, то в ней найдётся предложение, выделяющее в точности дискретно упорядоченные подсистемы с наименьшим и наибольшим элементами, которые (см. [18]) попарно элементарно эквивалентны в сигнатуре <. Это требуется для доказательства из 1 в 2. Для доказательства утверждения в обратную сторону, требуется теорема о строении систем с конечным множеством элементарных типов бесконечных подсистем.

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

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

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

[1] 5. Shelah, Classification theory and the number of non-isomorphic models (Stud. Logic Found. Math., 92) Amsterdam, North-Holland, 1978.

[2] S. Shelah, The spectrum problem I, Ng - saturated models the main gap. Israel Journal of Mathematics, vol. 43 (1982), 324-356

[3] M.D. Morley, Categoricity in power, Trans. Am. Math. Soc, 114, N2 (1965), 514-538

[4] R. Fraisse, Theory of relations. Amsterdam a.o.: North-Holland, 1986.

[5] L. P. D. van den Dries, Tame topology and O-minimal structures. Cambridge Univ. Press, New York, 1998.

[6] J.T. Baldwin, Fundamentals of Stability Theory. Springer-Verlag, New York, 1988.

[7] C.Frasnay, Groupes de compatibilite deux orderes totaux; application aux n-morphismes d'une relation m-aire. C. R. Acad. Sci., Paris 259 (1964), 3910-3913

[8] C. Frasnay, Groupes finis de permutations et families d'orderes totaux; application a la theorie des relations. C. R. Acad. Sci., Paris 257 (1963), 2944-2947

[9] C.Frasnay, Quelques problemes combinatoires les orders totaux et les relations monomorphes, (Doctoral Dissert. Paris). Annales Institut Fourier Grenoble vol. 15 (1965) p. 415-524.

[10] M. Pouzet, Application d'une proprietie combinatorie des parties d'un ensemble aux groupes et aux relations. Math. Zeitschrift vol. 150 (1976) p. 117-134.

[11] B. Zilber, The structure of models of uncountably categorical theories. In ICM- Varsavia 1983, North-Holland, 1984, 359-368.

[12] E. Hrushovski, A new strongly minimal set. Ann. Pure Appl. Logic,(1993) 62:147-166

[13] A. Pillay and C. Steinhorn Definable sets in ordered structures I. Trans. Amer. Math. Soc, (1986) 295:565-592

[14] E.A. Палютин, Е*-стабильные теории, Алгебра и Логика, 42, N2 (2003), 194-210

[15] Е.А. Палютин, Спектр и структура моделей полных теорий, Справочная книга по математической логике, часть I. Теория моделей, Москва, Наука, 1982.

[16] Е.А. Палютин, Е*-стабильность и О-минимальность элементарных теорий. Тезисы дальневосточной математической школы-семинара им. ак. Е. В. Золотова, Владивосток 2003.

[17] Т.Г. Мустафин, Новые понятия стабильности теорий, в сб. „Труды советско-французского коллоквиума по теории моделей", Караганда, 1990, 112-125

[18] Ершов Ю. Л., Лавров И. А., Тайманов А. Д., Тайцлин М. А. Элементарные теории. УМН, 20, №4 (1965)

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

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

[20] Д.Ю. Власов, Строение алгебраических систем с полной теорией бесконечных подсистем. Сиб. мат. журнал, 44, №2 (2003), стр. 291302

[21] Д.Ю. Власов, Исследование структурных свойств алгебраических систем с условиями минимальности субранга и субстепени, определяемых по выполнимости предложений на подсистемах. Проблемы теоретической и прикладной математики: труды 33-й региональной молодёжной конференции, Екатеринбург: УрО РАН, 2002, стр. 9-11.

[22] Д.Ю. Власов Строение сильно • субминимальных алгебраических систем. Теория моделей 4, Новосибирск, издательство НГТУ, 2003, 166-192

[23] Д.Ю. Власов Методы теории стабильности в применении к исследованию истинности предложений на подсистемах. Материалы XXXVII МНСК "Студент и научно-технический прогресс": Математика, Новосибирск, НГУ, 1999, стр. 24-25.

ВЛАСОВ Дмитрий Юрьевич

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

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

Подписано в печать 26.04.2004. Формат 60 х 84 1/16. Печать офсетная. Усл.-печ. л. 0,8. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ N 28.

Отпечатано на полиграфическом участке ИМ СО РАН, пр. Академика Коптюга, 4, 630090 Новосибирск, Россия.

NM068Í

1 Строение алгебраических систем конечной сигнатуры с конечным множеством элементарных типов бесконечных подсистем.

1.1 Бескванторная интерпретируемость в мономорфных системах.

1.2 Конечноморфность систем с конечным множеством теорий бесконечных подсистем.

1.3 Строение алгебраических систем конечной сигнатуры с конечным множеством элементарных типов бесконечных подсистем

2 Строение шкалы интерпретируемости для систем, бескван-торно выражающихся через заданный линейный порядок

3 Строение сильно субминимальных систем.

3.1 Определение субранга и субстепени.

3.2 Строение сильно субминимальных систем.

Исследование структурных свойств алгебраических объектов является клас сической задачей, решавшейся на протяжении всего развития современной математики. Но, как правило, полное решение проблемы структурной классификации находилось лишь для узких классов алгебраических систем: конечно порождённых абелевых групп, векторных пространств, алгебраически замкнутых полей и т.д. Для постановки общей проблемы классификации в 70-80 годах XX века С. Шелахом [12] была разработана теория стабильности, в которой условие классифицируемости для аксиоматизируемых классов систем было точно сформулировано и обосновано [1], [20].

Но, тем не менее, в рамках теории стабильности такой естественный и важный объект как бесконечный линейный порядок оказывается нестабильным, то есть не поддающимся структурной классификации. В связи с эти были предложены и другие подходы к построению структурной теории для нестабильных теорий - в частности теория О-минимальных структур [2], Т*-стабильность [18] и ¿¡""-стабильность [19], обобщающие классическое понятие стабильности.

В классической теории стабильности для классификации алгебраических систем используется понятие системы инвариантов - некоторого дерева, листья которого помечены кардиналами. Существование такой системы инвариантов для теории автоматически влечёт немаксимальность функции спектра для достаточно больших мощностей [13], поэтому теория линейного порядка, имеющая максимальный спектр, не может быть классифицирована при помощи такой системы инвариантов. С другой стороны, теория О-минимальных структур возникла из идеи, что в качестве инварианта для классификации алгебраических систем можно взять сам порядковый тип некоторого линейного порядка, то есть линейный порядок изначально брался в качестве базового простейшего объекта [9].

Кроме того, простейшие в смысле классического понятия стабильности объекты - сильно минимальные алгебраические системы - оказываются устроенными весьма не просто. Некоторое время стояла гипотеза Зильбе-ра [14] утверждающая, что сильно минимальные алгебраические системы либо интерпретирут бесконечное поле, либо локально модулярны. Однако Хрущовский [7] опроверг эту гипотезу, построив не локально модулярную сильно минимальную алгебраическую систему, в которой не может интерпретироваться никакая бесконечная группа.

Данная работа посвящена построению теории, подобной теории ш - стабильности [8], в которой понятие элементарного типа кортежа замещается на понятие элементарной теории подсистемы. Практически вся теория моделей построена на базовом понятии элементарного типа кортежа - множества формул, характеризующих элементы этого кортежа относительно всех других элементов системы. Понятие типа кортежа по существу описывает отношение между элементарным объектом (кортежом), элементы которого не имеют структуры, и всеми остальными элементами структуры. С другой стороны, если мы попытаемся ввести тип принципиально другого объекта -подсистемы в некоторой исходной системе, то этот объект уже может иметь сложную внутреннюю структуру, и в качестве элементарной характеристики такого объекта можно рассмотреть элементарную теорию этой подсистемы. Заметим, что в отличие от классического понятия типа кортежа в системе, элементарная теория подсистемы описывает не отношение этой подсистемы с другими частями исходной системы, а локально-глобальные характеристики элементов этой подсистемы (локально - потому что только для элементов данной подсистемы, а глобальные - потому что предложения описывают строение всей подсистемы глобально, в целом).

В классической теории моделей очень много результатов получено при том или ином ограничении на множества типов. В качестве первого, самого сильного, ограничения можно рассмотреть ограничение до конечности множества типов в системе. Хорошим классическим примером, когда ограничение количества типов до конечного даёт сильное структурное свойство, можно привести известную теорему Рылль-Нардзевского [11], характеризую а;-категоричне теории в терминах конечности множеств элементарных п-типов кортежей в теории. Таким образом постановка вопроса о свойствах алгебрических систем с конечным множеством теорий бесконечных подсистем оправдана аналогией с классическим результатом. В первой главе диссертации этот вопрос полностью решается полным описанием таких систем в случае конечной предикатной сигнатуры.

Замещение понятия элементарного типа кортежа на элементарный тип подсистемы позволяет придать стандартным понятиям ранга и степени принципиально иную семантику, по ставнению с рангами в теории стабильности. По аналогии с рангом Морли, в диссертации вводятся понятия субранга и субстепени предложения в некоторой системе, которые характеризуют структурную сложность множества теорий подсистем. Фактически, ранг и степень системы, которые определяются как ранг и степень тождественно истинного предложения, определяют сложность булевой алгебры формульных классов подсистем в исходной системе. Ограничивая ранг и степень, мы ограничиваем сложность этой булевой алгебры, то есть мы задаём класс систем ограниченной сложности (в данном смысле), для которого появляются реальные возможности строить структурную теорию. Основной результат данной диссертации, изложенный в третьей главе, состоит в полном описании структуры систем субранга 1 и субстепени 1 (сильно субминимальных алгебраических систем). Для бесконечных систем конечной предикатной сигнатуры это наименьшие возможные значения субранга и субстепени, то есть сильно субминимальные системы являются простейшими в вышеуказанном смысле системами в классе всех бесконечных систем конечной предикатной сигнатуры. Показано, что подобные системы тесно связаны с мономорфными и конечноморфными системами, изучавшимися в 60-х годах XX века. В частности, ключевыми для доказательства основных результатов диссертации оказались несколько теорем, доказанных С. Ггавпау [4], [5], [6], и И. Г^ве [3].

Помимо описания структурной теории некоторого класса при помощи системы инвариантов, есть и другой подход - описывать элементы класса в терминах биинтерпретируемости с некоторым явно заданным классом систем. Борис Зильбер [15] сформулировал программу, основная идея которой заключается как раз в таком описании элементарных классов. Во второй главе диссертации даётся описание шкалы интерпретируемости для систем, бескванторно выражающихся через заданный линейный порядок. Фактически доказывается, что любая система конечной предикатной сигнатуры, бескванторно инстрпретирующаяся в некотором бесконечном линейном порядке, взаимно интерпретируется формулами первого порядка с одним из явно заданых предикатов (среди которых 5 дискретных и две бесконечные серии). В свете программы классификации Зильбера, этот результат имеет самостоятельную ценность.

Таким образом, если сравнить предложенную в данной работе методологию классификации алгебраических систем по сложности с классической теорией стабильности, то можно сделать вывод, что две вышеуказанные проблемы - классифицируемость бесконечных линейных порядков и структурная простота простейших в данном смысле объектов - решаются положительно. Бесконечный линейный порядок типа и является сильно субминимальным (то есть простейшим в данном смысле), более того, все сильно субминимальные системы исчерпываются системами, интерпретирующимися бескванторными формулами через некоторый счётный линейный порядок очень простого вида либо через равенство. Кроме того, в отличие от общепринятого определения О-минимальных стуктур, линейный порядок изначально не фигурирует в определении сложности системы, но возникает естественным образом как простейшая структура. Стоит отметить, что Е.А. Палютин характеризовал понятия О-минимальной и слабо О-минимальной теории в терминах й^-определимости [21], которая, в свою очередь, определяется через ¿""-стабильность, так что понятие О-минимальной теории может быть определено и без явного введения линейного порядка. Также можно отметить, что хотя не все сильно субминимальные системы сами являются О-минимальными, все они интерпретируются в О-минимальных структурах (соответствующих линейных порядках).

В первой главе диссертации изучается строение алгебраических систем конечной сигнатуры с конечным множеством элементарных типов бесконечных подсистем. Эта глава состоит из трёх параграфов.

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

Лемма 3. Пусть даны два строго т-местных предиката Р и Q, выражающихся через некоторый линейный порядок < бескванторными формулами. Тогда предикат Р выражается через Q бескванторной формулой тогда и только тогда, когда AutQ(m) < Autp(m).

Основной леммой, широко использующейся в дальнейшем, является следующий критерий частичного изоморфизма:

Лемма 4. Пусть некоторый строго т-местный предикат Р, определённый на множестве А, выражается через некоторый линейный порядок < бескванторной формулой. Тогда любое частичное взаимно-однозначное отображение ф : {ai,.a„} —> {b\,. ,bn} является частичным изоморфизмом относительно Р тогда и только тогда, когда соответствующая характеристическая биекция является автоморфизмом из группы Autp(n) автоморфизмов подсистем мощности п.

Кроме того, в этом параграфе приводятся некоторые определения из книги [3] (в частности определения индикативных групп - ключевого понятия для развития всей последующей теории) и лемма, обосновывающая взаимно-однозначную связь n-арных расширений групп в терминологии Фраиссе и групп автоморфизмов конечных подсистем в мономорфных системах.

В параграфе 1.2 вначале определяется функция Рго/Ие%(к), а также вводится понятие в-морфной системы, обобщающее понятие мономорфной системы. Следующее утверждение является основным результатом данного раздела:

Теорема 1. Пусть 21 - счётная алгебраическая система конечной предикатной сигнатуры Е с конечным числом п элементарных типов бесконечных подсистем. Тогда 21 - не более чем п-морфная алгебраическая система.

Следствие 2. Если 21 - бесконечная алгебрическая система конечной предикатной сигнатуры, то Profile^oj) > Profile%(n) для всех п < и.

В силу того, что М. Pouzet [10] доказана монотонность функции Profile для всех п < w, то можно утверждать, что функция Рго/Ие%(к) монотонно неубывает на отрезке к < ш.

В параграфе 1.3 изучается строение алгебраических систем конечной сигнатуры с конечным множеством элементарных типов бесконечных подсистем. Вначале рассматриваются диаграммы, описывающих стратегию построения непродолжаемого частичного изоморфизма между двумя линейно упорядоченными системами в игре Эренфойхта [17]. При помощи этих диаграмм доказывается следующая теорема, описывающая алгебраические системы конечной предикатной сигнатуры в терминах бескванторной интерпретируемости в явно заданном классе систем:

Теорема 2. Пусть 21 - некоторая бесконечная алгебраическая система конечной предикатной сигнатуры. Тогда следующие условия эквивалентны:

1. множество элементарных типов бесконечных подсистем в системе 21 конечно.

2. выполнено одно из следующих трёх условий: a) система 01 несчётна и все предикаты из сигнатуры £(21) выражаются через конечное число констант С и равенство бескванторными формулами. b) система 01 счётна, и существует такой линейный порядок < типа ш + т либо т + ш* + ш, где т - некоторое натуральное число, на множестве А и такое конечное множество констант С, образующих начальный интервал в порядке <, что все предикаты сигнатуры Е(21) выражаются через этот порядок < и константы С бескванторными формулами. c) система 01 счётна и существует такой линейный порядок < типа и • п, где п - некоторое натуральное число, и такое конечное множество констант С, образующих начальный интервал в порядке < на множестве А, что все предикаты сигнатуры 11(21) выражаются через предикат Т<\С3 (то есть трансляцию, ограниченную на множество А\С), и константы С бескванторными формулами.

Глава 2 посвящена изучению шкалы интерпретируемости для систем, бескванторно выражающихся через заданный линейный порядок.

Теорема 3. Пусть (Л, <) - бесконечный линейный порядок. Тогда любая система, интерпретирующаяся бескванторными формулами через этот порядок, взаимно интерпретируется формулами первого порядка с некоторым индикативным предикатом из множества:

Г3, £>4,=} и {/£>,<7 > 0} и Шг > 0} среди корорых 5 дискретных классов и две бесконечные серии.

Доказательству этой теоремы предшествует ряд лемм о взаимной интерпретируемости индикативных предикатов из одной серии но разной арности формулами с кванторами.

Глава 3 посвящена изучению строения сильно субминимальных систем. В параграфе 3.1 вводятся понятия субранга и субстепени предложения в алгебраической системе. Субранг - это функция, для каждой алгебраической системы определённая на множестве предложений сигнатуры системы и принимающих ординальные значения, а также значения -1 и оо. Субстепень - это функция, определяющаяся через субранг, и принимающая натуральные значения. Доказывается ряд свойств субранга и субстепени, а также доказывается предложение, утверждающее что определение субстепени корректно.

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

Теорема 4. Пусть 21 - бесконечная алгебраическая система конечной предикатной сигнатуры Е. Тогда следующие условия эквивалентны:

1. %I - сильно субминимальна

2. множество элементарных типов бесконечных подсистем в системе 21 конечно и 21 - мономорфна.

Доказательству этой теоремы предшествует ряд технических лемм, описывающих множества решений для ряда формул с индикативными предикатами. Основное назначение этих лемм - показать, что если система 21 сильно субминимальна, то в ней найдётся предложение, выделяющее в точности дискретно упорядоченные подсистемы с наименьшим и наибольшим элементами, которые (см. [16]) попарно элементарно эквивалентны в сигнатуре <. Это требуется для доказательства из 1 в 2. Для доказательства утверждения в обратную сторону, требуется теорема о строении систем с конечным множеством элементарных типов бесконечных подсистем.

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

1. J.T. Baldwin, Fundamentals of Stability Theory. Springer-Verlag, New York, 1988.

2. L. P. D. van den Dries, Tame topology and O-minimal structures. Cambridge Univ. Press, New York,1998.

3. R. Fraisse, Theory of relations. Amsterdam a.o.: North-Holland, 1986.

4. C. Frasnay, Groupes de compatibilité deux orderes totaux; application aux n-morphismes d'une relation га-aire. C. R. Acad. Sei., Paris 259 (1964), 3910-3913

5. C. Frasnay, Groupes finis de permutations et familles d'orderes totaux; application a la theorie des relations. C. R. Acad. Sei., Paris 257 (1963), 2944-2947

6. C. Frasnay, Quelques problèmes combinatoires les orders totaux et les relations monomorphes, (Doctoral Dissert. Paris). Annales Institut Fourier Grenoble vol. 15 (1965) p. 415-524.

7. E. Hrushovski, A new strongly minimal set. Ann. Pure Appl. Logic,(1993) 62:147-166

8. M.D. Morley, Categoricity in power, Trans. Am. Math. Soc., 114, N2 (1965), 514-538

9. A. Pillay and С. Steinhorn Definable sets in ordered structures I. Trans. Amer. Math. Soc., (1986) 295:565-592

10. M. Pouzet, Application d'une proprietie combinatorie des parties d'un ensemble aux groupes et aux relations. Math. Zeitschrift vol. 150 (1976) p. 117-134.

11. Ryll-Nardzewski C. On the categoricity in power < No« Bulletin de l'Academie Polonaise des Sciences, vol. 7 (1959), p. 545-548.

12. S. Shelah, Classification theory and the number of non-isomorphic models (Stud. Logic Found. Math., 92) Amsterdam, North-Holland, 1978.

13. S. Shelah, The spectrum problem I, saturated models the main gap. Israel Journal of Mathematics, vol. 43 (1982), 324-356

14. B. Zilber, The structure of models of uncountably categorical theories. In ICM- Varsavia 1983, North-Holland, 1984, 359-368.

15. B. Zilber, Uncountably categorical theories. AMS 1993.

16. Ершов Ю. Л., Лавров И. А., Тайманов А. Д., Тайцлин М. А. Элементарные теории. УМН, 20, №4 (1965)

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

18. Т.Г. Мустафин, Новые понятия стабильности теорий, в сб. „Труды советско-французского коллоквиума по теории моделей", Караганда, 1990, 112-125

19. Е.А. Палютин, Е*-стабильные теории, Алгебра и Логика, 42, N2 (2003), 194-210

20. Е.А. Палютин, Спектр и структура моделей полных теорий, Справочная книга по математической логике, часть I. Теория моделей, Москва, Наука, 1982.

21. Е.А. Палютин, .^-стабильность и О-минимальность элементарных теорий. Тезисы дальневосточной математической школы-семинара им. ак. Е. В. Золотова, Владивосток 2003.Работы автора по теме диссертации

22. Д.Ю. Власов, Строение алгебраических систем с полной теорией бесконечных подсистем. Сиб. мат. журнал, 44, №2 (2003), стр. 291-302

23. Д.Ю. Власов Строение сильно субминимальных алгебраических систем. Теория моделей 4, Новосибирск, издательство НГТУ, 2003, 166192

24. Д.Ю. Власов Методы теории стабильности в применении к исследованию истинности предложений на подсистемах. Материалы XXXVII МНСК "Студент и научно-технический прогресс"¡Математика, Новосибирск, НГУ, 1999, стр. 24-25.