Определимость в итерированных расширениях тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

- - - РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ

Институт математики им. С.Л. Соболева

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

Алаев Павел Евгеньевич

ОПРЕДЕЛИМОСТЬ В ИТЕРИРОВАННЫХ РАСШИРЕНИЯХ

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

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

Новосибирск - 1998

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

Научный руководитель - член-корр. РАН

профессор С.С.Гончаров

Официальные оппоненты: доктор физико-математических наук

А.Г.Пинус,

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

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

Зашита состоится 9 июня 1998 года в 17 часов на заседании специализированного совета Д 002.23.01 при Институте математики Сибирского отделения РАН по адресу: 630090, Новосибирск, проспект акад. Коптюга 4.

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

Автореферат разослан 8 мая 1998 года.

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

специализированного совета Д 002.23.01

Кандидат физико-математических наук

А.Н.Ряскин

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

Основные результаты работы относятся к теории моделей, одному из важнейших направлений математической логики, впервые оформившемуся в работах А.Тарского и А.И.Мальцева. Одной из традиционных задач теории моделей является описание типов изоморфизма для какого-либо класса моделей, поскольку изоморфность двух моделей является наиболее сильным отношением "схожести" моделей среди всех, рассматриваемых в рамках предмета. Другое важное направление работы — исследование свойств моделей, выразимых средствами стандартной логики первого порядка. Два класса задач такого рода часто оказываются далеки друг от друга в силу того, что в обычной логике может быть выражена лишь малая часть всех возможных свойств модели и ее элементов (примером может служить отношение элементарной эквивалентности двух моделей).

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

Одна из первых систематизаций результатов в этой области была сделана в работе Д. Скотта [17], где были сформулированы основные теоремы для такой логики, ранее полученные разными авторами. Среди известных математиков, занимавшихся этими вопросами, можно назвать К.Карпа, Ч.Ч.Чэна, Дж.Барвайса, Г.Кейслера. В последующем результаты неоднократно обобщались в различных монографиях, в частности, в [12] и [9].

Расширение логики указанными операциями позволяет синтаксическими

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

Булевы алгебры являются одним из традиционных математических объектов, постоянно возникающим б алгебре, математической логике и в других математических дисциплинах. В качестве основных трудов в этой области можно указать [6], [14] и [1]. Суператомные булевы алгебры являются важным подклассом булевых алгебр. С одной стороны, они хорошо изучены, с другой, па их основе можно построить описание произвольных булевых алгебр, как показано в [3| и в [13].

Одним из старых и хорошо известных результатов теории моделей (см. [15], [4]) является утверждение о.том, что любая алгебраическая система элементарно вкладывается в однородную систему. В [2] С.С.Гончаровым был предложен новый подход к полному описанию строения модели синтаксическими средствами, за счет итерированного обогащения сигнатуры модели новыми предикатами для реализующихсчя неглавных типов. Этот метод, являясь в целом эквивалентным работе с логикой Ь^ш, тем не менее предоставляет некоторые новые средства для исследования свойств алгебраических систем. При этом на класс моделей с такой обогащенной сигнатурой был перенесен ряд результатов из обычпой теории моделей, в частности то,

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

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

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

Теоретическая и практическая ценность. Работа носит теоретический характер. Ее результаты и методы могут найти применение в различных областях математической логики, в том числе в теории моделей и теории булевых алгебр. Материалы диссертации могут быть использованы при чтении спецкурсов для студентов университетов.

Апробация. Результаты диссертации докладывались па различных семинарах НГУ, в том числе на "Алгебре и логике", на международной конференции по математической логике, посвященной 85-летию со дня рождения Л.И.Мальцева (Новосибирск, 1994), на Мальцевских чтениях (Новосибирск, 1997).

Публикации. Основные результаты диссертации опубликованы в работах автора [19 - 24].

Структура и объем работы. Диссертация состоит из введения, трех глав и списка литературы. Каждая глава разбита на несколько параграфов. Общий объем диссертации — 88 страниц, список литературы содержит 24 наименований.

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

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

в §1.2 описываются признаки а-эквивалентности произвольных булевых алгебр для конечного ординала а, на основе этого описываются все булевы алгебры конечного ранга Скотта и дается формула для вычисления их ранга. В §1.3 доказывается критерий а-эквивалентности для а-атомных булевых алгебр и на его основе приводится способ вычислять ранг а-атомной булевой алгебры через ранг факторизации по итерированному идеалу Фреше уровня а. В частности, это позволяет установить непосредственную связь между рангом Скотта суператомной булевой алгебры и ее обычной алгебраической характеристикой (рангом Фреше), а для произвольной булевой алгебры оценить ее ранг Скотта снизу через ранг Фреше. Кроме того, в главе 1 дается близкая к точной оценка рапга прямого произведения конечного числа булевых алгебр, и устанавливается, что любая булева алгебра ранга а имеет предложение Скотта, ранг которого не превосходит а + 2; показывается также, что предложением Скотта ранга а + 1 обладают пе все алгебры.

В обозначениях придерживаемся [1], [9]- Если в предложение то

Яг(б?) — его сложность, являющаяся ординалом. Обозначение 21 г" 93 означает, что модели 21,® не различимы никаким предложением, сложность которого не превосходит а, через 21 93 обозначаем частичную изоморф-ность 01 и 93. Ранг Скотта системы 21 ■— нг(01). Конечную булеву алгебру с к атомам обозначаем Еа — идеал Фреше уровня а, сЬ(21) — элементарная характеристика булевой алгебры 21, В* — класс булевых алгебр характеристики (0,&,0), В£ — характеристики (0, /с, 1). Булева алгебра 21 аг-атомиая, если 21/^'д(21) атомная булева алгебра для всех ¡} < а. Точные формулировки результатов главы 1:

Теорема 1.1. 1) всякая булева алгебра с конечным рангом Скотта лежит в одном из В* или В£ для к Е ш,

2) зг(Во) = 0, яг (ВО = 0, зг(В*) = [1оё2(Л- - 1)] при к > 2,

3) = 0, зг(в;) = 2, зг(В;) = 2, вгф;) = [к>&2(к + 7)] при к > 3. Предложение 1.3. Если 21, 93 — булевы алгебры, вг(01) < а, 21 =с<+2 Ф, то 21 93.

Теорема 1.2. Пусть 21 а-атомная булева алгебра, а — ординал, 21/^(21) ^ ®0. Тогда зг(Я) = из ■ а + 5г(Я/Ра(Я)).

Теорема 1.3. Пусть 21 булева алгебра, о(21) = а ф 0. Тогда:

1) если а —■ предельный ординал, то зг(01) > из ■ а,

2) если а = оо + 1 и в Я/^0(Я) бесконечное количество атомов, то зг(Я) > из ■ а,

3) если а = ао+1 и в 21/^„(Я) ровно к атомов, к е из, то вг(Я) >

4) если 21 — суператомная булева алгебра, то а = ого+1, в 21/К,0(21) к атомов для некоторого яг(Я) = из ■ ад + зг(®ь).

Предложение 1.4. Пусть Я, 23 — булевы алгебры, тах(гг(Я), зг(®)) = а. Тогда а < 8т(01 + ®) < а + 4.

Тем самым на классе суператомных булевых алгебр естественная мера сложности (ранг Фреше) и ранг Скотта — практически одно и то же. Возникает естественный вопрос, можно ли каким-либо образом обобщить эту связь на класс всех булевых алгебр. Глава 2 посвящена отрицательному ответу на этот вопрос. Параграф 2.1 содержит некоторые технические леммы. В §2.2 для каждой счетной булевой алгебры Я строится другая счетная алгебра фактор-алгебра которой по некоторому простому идеалу равна Я и ранг Скотта которой не превосходит из + Тем самым уже класс счетных булевых алгебр таких рангов в некотором смысле содержит в себе все сколь угодно сложные счетные булевы алгебры. В §2.3 дается частичный ответ на вопрос, не можем ли мы в булевой алгебре большого ранга Скотта находить составляющие промежуточной сложности. Для любого счетного ординала а строится пример счетной булевой алгебры, такой, что все прямые слагаемые в пей либо имеют ранг не меньший а, либо меньший из + из.

Приведем точные формулировки. Если Я булева алгебра, а 6 А, то через а обозначаем булеву алгебру, носитель которой равен идеалу, порожденному а. Через /'(Я) обозначаем идеал Фреше, через 5(Я) идеал, равный {1 | х = хг и х2, XI € ^(Я), х% — безатомный элемент в Я}. Если I идеал в Я, £ идеал в Я//, то / о Ь = {1 е А | х/1 <Е I}.

Теорема 2.1. Для любой счетной булевой алгебры Я существует счетная

булева алгебра ® такая, что !В/Г о5о ~ 01 и 8г(23) < и + ш.

Теорема 2.2. Пусть а счетный ординал. Тогда существует счетная булева алгебра 93 такая, что для любого а 6 В верио: ат{а) < и> + и или аг(а) > а.

Глаза 3 посвящена отрицательному решению вопроса о том, можно ли любую алгебраическую систему элементарно вложить в однородную или хотя бы найти однородную систему, элементарно эквивалентную ей, оставаясь в классе стандартных моделей обогащенной сигнатуры, о которой шла речь выше, то есть моделей, в которых реализация цовых предикатных символов совпадает с реализацией соответствующих типов. Параграф 3.1 содержит описание некоторой вспомогательной конструкции, позволяющей цри определенных ограничениях строить системы вида 911, наследующие ряд свойств данной системы 9Н. Она необходима для построения контрпримеров в следующих параграфах. В §3.2 строится пример системы, такой, что ее обогащение 9Л1 не имеет однородных стандартных систем, элементарно-эквивалентных ей. Как уже отмечалось выше, если теория ТЬ(ЗЯ1) атомная, то такая система всегда существует. В §3.3 при таком предположении опровергается другое свойство обычных систем — строится пример системы ИТ такой, что ТЬ(ЯЯ1) атомна, но 9Я1 не вкладывается элементарно ни в какую стандартную однородную систему.

Точные формулировки результатов главы 3 таковы. Более подробно с вопросом можно познакомиться по [2]. Если Е некоторая сигнатура, то через Еа для всех ординалов а обозначаем обогащение Е, определяемое по индукции: Е° = £; если Е° определено, то Еа+1 = Еа и I р(х) — неко-

торые полный тип в Е°, х = (хх,... ,Х1ц) — набор переменных}, где Р^ — некоторый новый ^-местный предикатный символ, не лежащий в Еа; если А предельный ординал, то Ел = и„<л Бели Е фиксировано, Е1 С Е°, ЯЯ — модель то Ш — стандартная модель Е], если для любого предиката Рр(х) 6 Ей+1 \ Е*3, ¡3 < а, верно: ШТ Рр(х)(а) тогда и только тогда, когда ЯЯ |= р(а). Если ШТ модель Е, то через ЯЯа обозначаем единственное стандартное обогащение ШТ до подъязыка Еа, состоящего из Е и всех символов Еа \ Е. реализация которых не пуста в ЯЯ.

Теорема 3.2. Существует ОТ* — счетная модель счетного языка Е* такая, что ТЬ((2Л*)') не имеет однородных стандартных относительно £* моделей. Теорема 3.3. Существует ОТ* - счетная модель счетного языка £* такая: что (ОТ*)1 обладает атомной теорией и не имеет стандартных относительно £" однородных элементарных расширений.

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

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

[1] С.С.Гончаров, "Счетные булевы алгебры", Новосибирск, Научная книга, 1996.

[2] С.С.Гончаров, М.Пурмахдиан, "Итерированные обогащения счетных теорий и их применение", Алгебра и логика, 34, N 6 (1995), НИИ МИОО НГУ, Новосибирск, с. 623-645.

[3] Ю.Л.Ершов, "Дистрибутивные решетки с относительными дополнениями". Алгебра и логика, 18, п.6, 1979, c.6S0-722.

[4] Г.Кейслер, Ч.Ч.Чэн, "Теория моделей", М., Мир, 1977, 614 с.

[5] А.С.Морозов, "Счетные однородные булевы алгебры", Алгебра и логика, т.21, N.3, с.269-282, 1982.

[6] П.Сикорский, "Булевы алгебры", М., Мир, 1969.

[7] Banvise J., "The Syntax and Semantics of Infmitary Logic", Berliri-Heidelberg-New York, Springer, 1968.

[8] Barwise J., "Abstract Logics and Ann. of Math. Logic. 4, 1973, pp. 309-340.

[9] Barvise J., "Admissible sets and structures", Berlin, a.o.: Springer, 1975, 394 p.

[10] Day C.W., "Supcratomic Boolean Algebras", Pac.J.Math., 23, 1967, pp. 479-489.

[11] Karp C.R., "Languages with expressions of infinite length", Amsterdam, 1964, 183 pp.

[12] Keislcr H.J., "Model Theory for infmitary logic, Logic with contable conjunctions and finite quantifiers", Amsterdam-London, N.H.Publ.Comp., 1971.

[13] Ketonen J., "The structure of countable Boolean algebras", Ann. Math., 108, 1978, pp. 41-89.

[14] Koppelberg S., "Handbook of Boolean Algebras", 1-3, North-Holland, Amsterdam-New York, 1989.

[15] Moily M., Vaught R., "Homogeneous universal models", Math. Scand, 1962, 11, p. 37-57.

[16] Scott D., "Invariant Borel Sets", Fund.Math., 56, pp.117-128, 1964.

[17] Scott D., "Logic with denumerably long formulas and finite strings of quantifiers", The theory of Models, pp. 329-341, Amsterdam, North-Holland, 1965.

[18] Stone M.N., "The theory of representations for Boolean algebras", Trans.Am.Math.Soc., 40, n.l, 1936, pp. 37-111.

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

[19] П.Е.Алаев, "Ранг Скотта булевых алгебр", Тезисы сообщений на международной конференции по математической логике, посвящепной 85-летию со дня рождения А.И.Мальцева, 1994, с.5-6.

[20] П.Е.Алаев, "Ранги Скотта булевых алгебр", Труды ИМ СО РАН, т.ЗО, 1996, с.3-25.

[21] П.Е.Алаев, "Однородность в итерированных моделях", Вычислительные системы, 156, Новосибирск, 1996.

[22] P.E.Alaev, "Homogeneity in Iterated Models", Siberian Advanced in Mathematics, v.7, n.l, 1997, p.1-25.

[23] P.E.Alaev, "Scott ranges of boolean algebras", Siberian Advanced in Mathematics, (принята к печати), 1998.

[24] П.Е.Алаев, "Сложные булевы алгебры с малым рангом", Препринт п.22, Издательство НИИ МИОО НГУ, 1998.

1одписано в печать 4.06.98 1ечать офсетная >аказ N 25

Формат 60x84/16 Уч.-изд. л. 1.6 Тираж 100 экз.

Отпечатано па полиграфическом участке издательства НИИ МИОО НГУ, 14Б (03), 630090, Новосибирск-90. Пирогова 2