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

• Дворжецкий, Юрий Сергеевич
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Дворжецкий, Юрий Сергеевич

Оглавление

Введение

Глава 1. Предварительные сведения

1.1 Предварительные сведения из алгебры логики

1.2 Сведения из теории моделей

1.3 Предварительные сведения из теории решёток

1.3.1 Решётки, дистрибутивные решётки

1.3.2 Дополнения, алгебры Ершова

1.4 Сведения из универсальной алгебраической геометрии

1.4.1 Основные определения

1.4.2 Алгебраическая геометрия над булевыми алгебрами 21 Глава 2. Атомарная стабильность

2.1 Типы и атомарные типы

2.1.1 Полный тип п-ки элементов над множеством

2.1.2 Атомарные типы п-ки элементов над множеством

2.1.3 Атомарные типы над множеством

2.1.4 Атомарные типы теории

2.2 Атомарная стабильность

2.3 Атомарная Л-стабильность

2.4 Нётеровость по уравнениям и атомарная стабильность

3.1 Нормальный вид систем уравнений в дистрибутивных решётках

3.2 Нётеровость по уравнениям дистрибутивных решёток

3.3 Дистрибутивные решётки и слабая нётеровость по уравнениям

3.4 Нормальный вид систем уравнений в алгебрах Ершова

3.5 Нётеровость по уравнениям алгебр Ершова

3.6 Другой нормальный вид систем уравнений над алгебрами Ершова

3.7 Слабая нётеровость по уравнениям в алгебрах Ершова

4.1 Идеалы в решётках, решётки с выделенным идеалом

4.2 Нётеровость по уравнениям в решётках с предикатами

4.3 Канонический вид систем уравнений

4.4 Слабая нётеровость по уравнениям в булевых решётках с идеальным предикатом

Заключение

Литература

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

Введение

Актуальность темы исследования

Системы уравнений и их решения над алгебраическими системами рассматривались Г. Баумслагом, А. Г. Мясниковым и В. Н. Ремесленнико-вым. В работах [9,18] была построена алгебраическая геометрия над группами. Подходы, применённые в этих статьях, были обобщены Э. Ю. Дания-ровой, А. Г. Мясниковым и В. Н. Ремесленниковым на случай произвольной алгебраической системы в работах [2,11-14].

В работах [2,11-14] задача классификации алгебраических множеств с точностью до изоморфизма сведена к задаче классификации координатных алгебр. Также в этих работах доказаны так называемые объединяющие теоремы, которые показывают эквивалентность семи различных способов описания координатных алгебр.

Необходимым условием применения этих объединяющих теорем для какой-либо алгебраической системы является наличие у этой системы свойства нётеровости по уравнениям.

Э. Ю. Данияровой, А. Г. Мясниковым и В. Н. Ремесленниковым в работе [13] было показано, что все результаты применимы не только к алгебраическим системам (без предикатных символов), но и к системам с произвольным языком. Следовательно, стало возможным говорить о нётеровости по уравнениям вообще в произвольных системах.

Э. Ю. Данияровой, А. Г. Мясниковым и В. Н. Ремесленниковым было доказано, что объединяющие теоремы, а также некоторые другие результаты верны не только для нётеровых по уравнениям алгебраических систем, но и для систем с более слабыми свойствами [11]. Таким образом, были сформулированы понятия слабой нётеровости, дш- и ^-компактности. Соответствующие классы нётеровых и слабо нётеровых систем обозначают N

и Г^', а классы и ^-компактных систем — и и соответственно. Таким образом, чтобы применить объединяющие теоремы, необходимо просто показать принадлежность алгебраической системы к классам С^ и и.

Впервые свойства нётеровости булевых алгебр с константами рассматривал А. Н. Шевляков [21]. В его работе построен нормальный вид систем уравнений над булевыми алгебрами с константами. А. Н. Шевляков доказал критерии принадлежности булевых алгебр к классам N и — нётеровых и слабо нётеровых алгебраических систем, и и — классам Яш~ и ^-компактных алгебраических систем, соответственно. Также был доказан критерий геометрической эквивалентности булевых алгебр с константами.

Результаты А. Н. Шевлякова могут быть перенесены на более общие дистрибутивные решётки с константами и алгебры Ершова. Эти результаты также переносятся на булевы алгебры с выделенными идеалами, изучаемые Д. Е. Пальчуновым [3-7].

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

Для достижения поставленной цели были решены следующие задачи:

1. Определить понятия атомарной стабильности и атомарной А-стабиль-ности алгебраических систем по аналогии с понятиями стабильности и А-стабильности как критериев для дальнейшего изучения алгебраической геометрии.

2. Исследовать связь атомарной стабильности с нётеровостью по уравнениям.

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

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

Апробация работы. Основные результаты работы докладывались на следующих конференциях и семинарах:

1. Международная конференция «Мальцевские чтения» (ИМ им. С. Л. Соболева, Новосибирск, 2008, 2009, 2012, 2013 гг.).

2. Международная школа-семинар «Новые алгебро-логические методы решения систем уравнений» (ОФ ИМ им. С. Л. Соболева, Омск, 2009 г.).

3. Омский алгебраический семинар (ОФ ИМ им. С. Л. Соболева, Омск, 2010, 2012, 2013 гг.).

4. Международная конференция «Стохастические модели в биологии и предельные алгебры» (ОФ ИМ им. С. Л. Соболева, Омск, 2013 г.).

5. Школа-конференция «Математические проблемы информатики» (ОФ ИМ им. С. Л. Соболева, Омск, 2013 г.).

6. Семинар «Алгебра и логика» (ИМ им. С. Л. Соболева, Новосибирск, 2014 г.).

Публикации. Основные результаты по теме диссертации изложены в 3 печатных изданиях [24,26,27], Все результаты опубликованы в журналах, рекомендованных ВАК. Работа [22] выполнена вместе с М. В. Котовым при равном вкладе соавторов.

Объем и структура работы. Диссертация состоит из введения, четырёх глав и заключения. Полный объем диссертации составляет 93 страницы. Список литературы содержит 30 наименований.

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

Во второй главе даются определения понятий атомарной стабильности и атомарной Л-стабильности вместе с необходимыми понятиями атомарных типов, аналогичных понятиям стабильности, Л-стабильности и типов из теории моделей, определённых не над множеством всех формул, а только над множеством атомарных формул. В этой главе также доказаны результаты, которые переносятся из теории моделей на определения атомарной стабильности, в частности, следующий результат. Теорема 1. Пусть Т — полная теория языка первого порядка С. Если по крайней мере для одного бесконечного кардинала X, такого что \С\ < А; теория Т атомарно \-стабилъна, то Т атомарно стабильна.

Также показана непосредственная связь между атомарной стабильностью и свойством нётеровости по уравнениям.

Теорема 2. Теории, у которых все модели нётеровы по уравнениям, являются атомарно стабильными.

В этой главе приведён пример алгебраической системы М.\

Л4 ~ (М; тогео(х),тоге1(х),тоге2(х),... ,0,1,2,...) ,

где

{О, х < г 1, х > г

демонстрирующей, что обратное утверждение неверно, т.е. ЛЛ не является нётеровой по уравнениям, но теория ТН(Л4) атомарно стабильна.

Третья глава посвящена системам уравнений и свойствам нётеро-вости по уравнениям над дистрибутивными решётками. Здесь показан нормальный вид систем уравнений в дистрибутивных решётках, доказан следующий критерий нётеровости по уравнениям.

Теорема 6. Дистрибутивная С-решётка А нётерова по уравнениям тогда и только тогда, когда дистрибутивная решётка С, порождённая константами, конечна.

Также в главе приводится пример решётки ЛЛ\

М = ^[0,1]; V = тах(2), Л = тт(2), [0,1]^ ,

которая показывает, что критерий слабой нётеровости по уравнениям булевых алгебр, доказанный А.Н. Шевляковым, на дистрибутивные решётки не переносится.

Далее рассматриваются системы уравнений над алгебрами Ершова. Доказан следующий критерий нётеровости по уравнениям. Теорема 9. С-алгебра Ершова А нётерова по уравнениям тогда и только тогда, когда подалгебра констант С конечна.

А также критерий слабой нётеровости по уравнениям. Теорема 11. Пусть А — С-алгебра Ершова. Тогда А слабо нётерова по уравнениям тогда и только тогда, когда:

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

2. для любого неограниченного сверху мноэ/сества констант\cj\j Е </} из С и для некоторого с верна следующая эквивалентность:

{,х Л с^ = е 7} ~ х < с.

В четвёртой главе изучаются булевы алгебры с выделенным идеалом и более общие дистрибутивные решётки с произвольным конечным набором предикатов. Для дистрибутивных решёток с произвольным набором предикатов доказан следующий критерий нётеровости по уравнениям: Теорема 12. Дистрибутивная С-решётка

с конечным набором предикатов Р^г\ ъ = 1,..., к местности нётеро-ва по уравнениям тогда и только тогда, когда дистрибутивная решётка С, порождённая константами, конечна.

Для решёток с выделенным простым идеалом доказан критерий слабой нётеровости по уравнениям.

Теорема 15. Булева С-решётка В с предикатом Р^ принадлежности к простому А-идеалу I С В слабо нётерова по уравнениям тогда и только тогда, когда для любого множества констант К С С идеал Ьо\у(К) = {а Е В\а < Ъ,Щ Е К} конечно порождён константами из С или может быть представлен в виде пересечения идеала I и идеала, конечно порождённого константами из С.

Глава 1. Предварительные сведения

В главе приводятся сведения из алгебры логики (параграф 1.1), теории моделей (параграф 1.2), теории решёток (параграф 1.3), алгебраической геометрии и универсальной алгебраической геометрии (параграф 1.4).

1.1. Предварительные сведения из алгебры логики

В данном параграфе мы сформулируем только важные определения, которые понадобятся нам в дальнейшем. Все необходимые сведения из математической логики можно найти в [2,11-14] и [17].

Напомним, что языком С первого порядка называют набор множеств С = (Т, "Р, С) функциональных, предикатных и константных символов, соответственно, с заданной местностью для каждого функционального и предикатного символа. Если язык не содержит предикатных символов, т.е. V = 0, то такой язык мы будем называть функциональным.

Зафиксируем язык первого порядка С. Определение 1 (Терм, [14]).

Термы языка С от переменных х = (жо, х\,..., хп^\), — это формальные выражения, определяемые рекурсивно:

1. переменные жо, х\, ..., хп являются термами;

2. константные символы языка С являются термами;

3. если ¿о, ¿ь • • • ^ ¿/с-1 — термы, и / Е Т — /^-местный функциональный символ, то / (¿о, ¿1, • • •, tk~l) является термом.

Множество термов языка С от переменных х = (жо, .. ., хп-\) обозначим за Тс {х).

Определение 2 (Формулы, атомарные формулы, [14]). Формулы языка С от переменных х = (хо, ^ь • • •, %п-1) ~ это формальные выражения, определяемые рекурсивно:

1. если ¿,5 Е Тс{х) (термы языка £ от переменных х), то (£ = в) есть формула;

2. если ¿о, ¿ъ • • • ¿/с-1 £ Тс(х) и Р — /с-местный предикатный символ языка £, то Р(г0, ¿1, ■ • ■, ^-1) есть формула;

3. если <р и ф — формулы, то -лу?, (<р\/ф), (срАф), (<р —>• есть формулы;

4. если </? — формула их — переменная из х, то Зх р и \/х <р есть формулы.

Формулы, построенные только по правилам 1 и 2, будем называть атомарными.

Множество всех формул языка £ от переменных^ = (жо, х\,..., хп-\) обозначим за а множество всех атомарных формул от переменных

х языка £ за АЬс(х).

Также введём множество всех отрицаний атомарных формул языка £ от переменных х:

-^Агс{х) = {^<р{х) I <р(х) е Агс(х)},

Множество всех атомарных формул языка £ от переменных х и отрицаний всех атомарных формул обозначим за,Тс(х) = АЬц^х) и ->АЬс(х).

Множество Тс(х) нам понадобится, когда мы будем вводить понятия типов и понятие стабильности.

Систему Л языка £ будем обозначать как А = (Л; С). Через Т}г(Л) обозначим множество всех предложений, истинных в А. Пусть А = (А] £) — £-система, Е С А — произвольное множество элементов носителя. Обозначим через Се обогащение языка £, полученное добавлением новых (отсутствующих в £) констант са, для всех а £ Е. Обозначим за Ае систему Ае — (А; Се) уже расширенного языка Се, с

той же интерпретацией символов языка С и естественной интерпретацией новых констант: = а £ Е С А.

1.2. Сведения из теории моделей

Определение 3 (Элементарное вложение). Пусть ЛиБ - системы языка С. £-гомоморфизм / : А В называют элементарным вложением, если / сохраняет истинность всех формул языка то есть для любой формулы <р(х) языка С и для любых элементов а £ А выполнено В |= ip (/(а)) тогда и только тогда, когда выполнено А |= у(а). Определение 4 (Элементарная эквивалентность, элементарное расширение, элементарная подсистема). Две системы А я В языка С называются элементарно эквивалентными, если Th(A) = Th{B).

Систему В называют элементарным расширением системы А, если В Э А и £-гомоморфизм / : А —> В является элементарным вложением, то есть для любой формулы (р(х) языка С и для любых элементов а Е А выполнено В \= tp (а) А \= <р{а).

Систему А в этом случае называют элементарной подсистемой. Факт 1 (Критерий элементарных подсистем Тарского-Вота, [15]). Пусть А и В системы языка С, А Я: В. Тогда следующие утверждения эквивалентны:

1. А является элементарной подсистемой В.

2. Для каждой формулы ф(х, у) языка С и всех кортежей a G А из того, что В [= 3уф(а,у), следует, что существует элемент d € А, что В [= ф(а, d).

Пусть А = {А\ С) — система языка С. Пусть а € А — набор порождающих А элементов, а с — набор соответствующих константных символов. Расширим язык С, до языка добавив константы с, и будем рассматривать расширенную систему Ас = (А; Сс).

Определение 5 (Элементарная диаграмма, [15, р.56]). Элементарной

диаграммой системы А мы будем называть теорию расширенной системы ТНс-(Ас), где с — любая последовательность констант для порождающих А элементов:

Элементарную диаграмму мы будем обозначать eldiag(Д). Лемма 1 (Лемма об элементарных диаграммах, [15, р.55]). Пусть А и В — системы языка С,с — кортеж констант, отсутствующих в языке С, Ас и Вс — системы расширенного языка Сс и сЛъ = а, свъ = а, причём а порождает Ас- Тогда следующие утверждения эквивалентны:

1. для любой формулы (р(х) языка С, если Ас [= <р(с), то Вс (= <р(с);

2. существует такое элементарное вложение / : А —>■ В, что /(а) =

ъ.

Исходя из этой леммы, можно получить следствие [15, р.56], которое мы будем использовать.

Следствие 1. Если система Т>с языка является моделью элементарной диаграммы cldiag(Д) системы А языка С, то существует элементарное вложение А в ограничение V = Т>с\с-

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

Факт 2 (Теорема компактности Гёделя-Мальцева). Пусть Т — теория некоторого языка. Теория Т имеет модель тогда и только тогда, когда любое конечное подмножество формул теории Т имеет модель.

1.3. Предварительные сведения из теории решёток

В данном параграфе будут представлены основные сведения из теории решёток. В параграфе 1.3.1 будут даны определения решёток и дистрибутивных решёток, в параграфе 1.3.2 будут определены алгебры Ершова.

1.3.1. Решётки, дистрибутивные решётки

Дадим определение решётки.

Рассмотрим язык состоящий из двух бинарных

функциональных символов — V и Л.

Определение 6 (Решётка). Алгебраическую систему А = (А; V, Л) языка £о мы будем называть решёткой, если для любых а, 6, с Е А выполнены следующие аксиомы:

1. Идемпотентность: а Л а = а, а V а = а.

2. Коммутативность: а Л Ь = Ь Л а, а V Ь — 6 V а.

3. Ассоциативность: (а Л 6) Л с = а Л (Ь Л с), (а V Ъ) V с = а V (6 V с).

4. Законы поглощения: а А (а V 6) = а, а V (а Л 6) = а.

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

Факт 3 (Принцип двойственности). Если какая-то формула языка Со верна на всём классе решёток, то двойственная формула, полученная взаимной заменой символов У и А, также истинна па всём классе решёток.

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

В дальнейшем будут рассматриваться решётки со свойством дистрибутивности.

Определение 7 (Дистрибутивная решётка). Решётку Л = (А\ V, Л) мы будем называть дистрибутивной, если для любых элементов а,Ь,с Е А выполнено:

а А (Ь V с) = (а А Ь) V (а Л с), а V (£> Л с) = (а V Ь) А (а Ус).

Можно ввести несколько эквивалентных определений дистрибутивной решётки.

Утверждение 1. Пусть А = (Л; V, А) — решётка. Тогда следующие утверждения эквивалентны:

1. Уа, Ь, с Е А а А (Ь V с) = (а А Ь) V (а А с); 2 .\/а,Ъ,сеА аУ(6Лс) = (аУ&)А(аУс); 3. Уа, 6, с £ Л (а А с = Ь Л с) & (а V с = Ъ V с) ->• а = 6. Пример 1 (Решётка подмножеств). Пусть X — некоторое множество элементов. Пусть Л - это множество подмножеств множества X, замкнутое относительно операций объединения и пересечения, тогда алгебраическая система А = (Л; = и, Л^ = п) является дистрибутивной решёткой.

Такую дистрибутивную решётку мы будем называть решёткой подмножеств. Если множество Л — это множество всех подмножеств множества X, то в этом случае А будем называть решёткой всех подмножеств.

Расширим язык Со до языка С, добавив бесконечное множество констант:

С = С0и{фе I}.

Введём понятия С-решётки и дистрибутивной С-решётки. Определение 8 (С-решётка). Решётку А расширенного языка С мы будем называть С-решёткой, где через С обозначена решётка, порождённая константами {с^|г Е /}.

Определение 9 (Дистрибутивная С-решётка). Дистрибутивную решётку А расширенного языка С мы будем называть дистрибутивной С-решёткой, где через С обозначена дистрибутивная решётка, порождённая константами {с^|г Е /}.

Также отметим, что на любой решётке можно ввести частичный порядок, положив:

Операции V и А могут быть интерпретированы следующим образом:

Определение 10 (Цепь, антицепь). Любое линейно упорядоченное подмножество элементов решётки мы будем называть цепью. Антицепью мы будем называть подможество элементов решётки, в котором любые два элемента несравнимы.

Определение 11 (АСС, DCC). Будем говорить, что решётка удовлетворяет условию обрыва возрастающих цепей (АСС), если в решётке не существует бесконечных строго возрастающих цепей элементов.

Будем говорить, что решётка удовлетворяет условию обрыва убывающих цепей (DCC), если в решётке не существует бесконечных строго убывающих цепей элементов.

Определение 12 (JID, MID). Будем говорить, что полная решётка И. удовлетворяет свойству бесконечной дистрибутивности JID, если

а < b а /\Ь = а

или

а < Ъ ^ а У Ъ = Ь.

а V b = sup{a, 6},

a Ab — inf {а, b}.

и свойству бесконечной дистрибутивности MID, если в Л выполнено

х\/ f\xi = Д(х V Xi),

iel iel

1.3.2. Дополнения, алгебры Ершова

Наименьший и наибольший элементы решётки называют нулём и единицей и обозначают 0 и 1, соответственно.

Определение 13 (Дополнение). Дополнением к элементу х в решётке с О и 1 мы будем называть такой элемент ж', что х Л х' — 0 и х V х' = 1. Дополнение х' к элементу х мы будем обозначать х. В решётках существуют и другие дополнения. Определение 14 (Псевдодополнение элемента). Пусть Л — дистрибутивная решётка с 0. Элемент а* называется псевдодополнением элемента а, если а* Л а = 0, и для любого другого х Е Л из того, что х Л а = 0, следует х < а*.

Определение 15 (Относительные дополнения). Дополнением к элементу х относительно элементов а и b (а < х < Ь) мы будем называть такой элемент х', что х' Л х = а, х' V х = Ъ.

Из определений очевидно, что дополнение х' к элементу х — это дополнение к элементу х относительно 0 и 1.

Отметим, что в любой дистрибутивной решётке существует не более одного относительного дополнения к элементу в каждом интервале его содержащем. В дальнейшем мы будем рассматривать только дистрибутивные решётки.

Относительное дополнение к элементу — это тернарная операция, для которой нужны три элемента — a, b и сам элемент х. Поэтому, если в решётке есть 0, то относительное дополнение определяют в виде бинарной операции следующим образом.

Определение 16 (Относительное дополнение). Дополнением к элементу а относительно элемента Ъ (а < Ъ) мы будем называть такой элемент а', что а' Л а = 0, а' V а = 6.

Также удобно рассматривать не дополнение к а относительно Ь, а дополнение к а относительно аМЪ. В этом случае относительное дополнение определяется для любых а и Ь.

Такое дополнение к а относительно а V Ъ мы будем обозначать Ь \ а. Эту бинарную операцию мы будем называть разностью. Определение 17 (Алгебра Ершова). Дистрибутивную решётку Л =

с 0 и относительными дополнениями мы будем называть алгеброй Ершова.

Очевидно, что если в алгебре Ершова существует наибольший элемент 1, то эта алгебра Ершова является булевой алгеброй:

х = 1 \ х.

Некоторые свойства алгебр Ершова и относительных дополнений будут доказаны в параграфе 3.4.

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

В параграфе 1.4.1 будут даны основные определения из универсальной алгебраической геометрии. Далее, в параграфе 1.4.2 будут приведены критерии принадлежности к классам С^, и, N и 14', доказанные А. Н. Шев-ляковым в [21].

1.4.1. Основные определения

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

Зафиксируем язык С без предикатных символов. Определение 18 (Уравнение, система уравнений). Пусть п € N — натуральное число, х = (xq ,Х\,..., хп ) — n-ка переменных. Уравнением от переменных х мы будем называть любую атомарную формулу языка £ от переменных ж, системой уравнений S(x) от переменных х будем называть любое множество уравнений от переменных х.

Пусть А = {А] С) — ^-алгебра (система языка без предикатных символов).

Определение 19 (Решение уравнения). Пусть <р(х) — уравнение от переменных х, \х\ = п. п-ку элементов а € Ап будем называть решением уравнения <р(х), если А |=

Определение 20 (Решение системы уравнений). Пусть S(x) — система уравнений от переменных х, = п. Кортеж элементов a £ Ап будем называть решением системы уравнений S(x), если а является решением каждого уравнения из S(x).

Множество решений системы уравнений S обозначим за V(S) . Определение 21 (Эквивалентные системы уравнений). Две системы уравнений S\(x) и 62 (ж) от переменных х будем называть эквивалентными в алгебраической системе А, если Va(Si) = Уа{$2)-

Введём понятия нётеровости и слабой нётеровости по уравнениям. Определение 22 (Нётеровость по уравнениям). £-алгебру А будем называть нётеровой по уравнениям, если для любого п G N, для любой

системы уравнений S(x) от переменных х, \х\ = п, существует такая конечная подсистема уравнений Sq(x) С S{x), что Va(S) = V^So).

Класс всех нётеровых по уравнениям систем обозначим через N. Нётеровость системы по уравнениям — это необходимое условие применения так называемых «Объединяющих теорем» [14]. Приведём некоторые обобщения свойства нётеровости по уравнениям. Определение 23 (Слабая нётеровость по уравнениям). £-алгебру А будем называть слабо нётеровой по уравнениям, если для любого п G N, для любой системы уравнений S(x) от переменных х, |ж| = п, существует такая конечная система уравнений So(x), что Уд(S) = Va(Sq).

Класс всех слабо нётеровых по уравнениям систем обозначим через

N'.

Также приведём понятия и и^-компактности. Определение 24 (д^-компактноеть). С-алгебру А будем называть qu-компактной, если для любой системы S(x) и любого уравнения t(x) = s(x) такого, что Va{S) С Уд(£ = s) существует конечная подсистема S'(x) С S(x) со свойством Va{S') Q Уа{t ~ s)•

Класс всех ^-компактных систем обозначим через Q. Определение 25 (^-компактность). £-алгебру А будем называть иш-компактной, если для любой системы S(x) и любого конечного множества уравнений U(x) = Si(x) от переменных х, где 1 < г < т, Е N, таких, что:

т

VA{S)Q[jVA{ti = 8i\

г=1

существует конечная подсистема S'(x) С S(x) со свойством

т

VAiS^QljVAiti^Si). i=1

Класс всех и^-компактных систем обозначим через и. В работе [13] все понятия и результаты были обобщены на случай произвольной сигнатуры системы. То есть, считая формулу Р(ж), где Р — произвольный предикатный символ языка уравнением, можно сформулировать все приведённые выше понятия и применять существующие результаты, доказанные для случая функционального языка £. Это обобщение будет применяться в главе 4, когда будут исследоваться системы уравнений над решётками с предикатом принадлежности к некоторому идеалу.

1.4.2. Алгебраическая геометрия над булевыми алгебрами

А. Н. Шевляковым в [21] были доказаны следующие критерии принадлежности булевых алгебр к классам С^, ТГ, N и

Теорема (А. Н. Шевляков). Булева С-алгебра В нётерова по уравнениям тогда и только тогда, когда подалгебра С, порождённая константами, конечна.

Теорема (А. Н. Шевляков). Булева С-алгебра В слабо нётерова по уравнениям тогда и только тогда, когда алгебра С полна в В.

Для формулировки критериев и ^-компактности булевых алгебр приведём определение ^-системы, впервые введённое М. В. Котовым в [16].

Определение 26 (^-система). Система уравнений 5(х) от переменных х над £-алгеброй А называется ^-системой, если |Уд(5(х))| = к Е М, но для любой конечной подсистемы 5"(х) С выполнено |Уд(6"(х))| = оо. Теорема (А. Н. Шевляков). Булева С-алгебра В является дш-компактной тогда и только тогда, когда над В не существует Ео и Е\ систем. Теорема (А. Н. Шевляков). Булева С-алгебра В является иш-компактной тогда и только тогда, когда над В не существует Ек систем для любого к Е N.

Аналогичные этим критерии для более общих дистрибутивных решёток, алгебр Ершова, а также решёток с выделенным идеалом, будут доказаны в главах 3 и 4.

Глава 2. Атомарная стабильность

Во второй главе будут сформулированы результаты об атомарной стабильности — общего подхода к алгебраическим системам, в которых формульно выразим частичный порядок. Сначала будут даны определения и показаны свойства всевозможных атомарных типов (параграф 2.1), далее будет дано и разобрано определение атомарной стабильности (параграф 2.2) и атомарной А-стабильности (параграф 2.3). А в конце будет показана связь между атомарной стабильностью и нётеровостью по уравнениям (параграф 2.4).

2.1. Типы и атомарные типы

В этом параграфе наряду с определениями неатомарных типов (параграф 2.1.1) будут даны определения атомарных типов п-ки над множеством (параграф 2.1.2), атомарных типов над множеством (параграф 2.1.3) и атомарных типов теории (параграф 2.1.4).

Определения получены из соответствующих определений обычных неатомарных типов [15]. Существуют другие способы определения атомарных типов, например, в [14]. Эквивалентность этих подходов показана в утверждении 3.

2.1.1. Полный тип п-ки элементов над множеством

Приведём определение полного типа п-ки над множеством, как оно дано в [17].

Список литературы диссертационного исследования кандидат наук Дворжецкий, Юрий Сергеевич, 2014 год

Литература

1. Гретцер Г. Общая теория решёток— Москва: Мир, 1982 — 456 с.

2. Даииярова Э. Ю., Мясников А. Г., Ремесленников В. Н. Алгебраическая геометрия над алгебраическими системами II: Основания // Фундаментальная и прикладная математика. — 2012. — Т. 17, №1. — С. 65-106.

3. Пальчунов Д. Е. Конечно-аксиоматизируемые булевы алгебры с выделенными идеалами // Алгебра и логика. — 1987. — Т. 26, №4. — С. 435-455.

4. Пальчунов Д. Е. О неразрешимости теорий булевых алгебр с выделенным идеалом // Алгебра и логика. — 1986. — Т. 25, №3. — С. 326346.

5. Пальчунов Д. Е. Простые и счётно-насыщенные булевы алгебры с выделенными идеалами // Труды Института математики СО РАН. — 1993. - Т. 25. - С. 82-103.

6. Пальчунов Д. Е. Прямые слагаемые булевых алгебр с выделенными идеалами // Алгебра и логика. — 1992. — Т. 31, №5. — С. 499-537.

7. Пальчунов Д. Е. Теории булевых алгебр с выделенными идеалами, не имеющие простой модели // Труды Института математики СО РАН. - 1993 - Т. 25. - С. 104-132.

8. Салий В.Н. Решётки с единственными дополнениями—- Москва: Наука, 1984. - 128 с.

9. Baumslag G., Myasnikov A. G., Remeslennikov V. N. Algebraic geometry over groups I: Algebraic sets and ideal theory //J. Algebra. — 1999. — Vol. 219. - P. 16-79.

10. Birkhoff G. Lattice theory— American Mathematical Soc., 1967. — 283 p.

11. Daniyarova E., Miasnikov A., Remeslennikov V. Algebraic geometry over algebraic structures III: Equationally Noetherian Property and Compactness // Southeast Asian Bulletin of Mathematics. — 2011. — Vol. 35. - P. 35-68.

12. Daniyarova E., Miasnikov A., Remeslennikov V. Algebraic geometry over algebraic structures IV: Equational domains and co-domains // Algebra and Logic. - 2011. - Vol. 49, No. 6. - P. 715-756.

13. Daniyarova E., Miasnikov A., Remeslennikov V. Algebraic geometry over algebraic structures V: The case of arbitrary signature // Algebra and Logic. - 2012. - Vol. 51, No. 1. - P. 28-40.

14. Daniyarova E., Miasnikov A., Remeslennikov V. Unification theorems in algebraic geometry // Algebra and Discrete Mathematics. — 2008. — №1, P. 80-112.

15. Hodges W. Model Theory — Camridge: Cambridge university press, 1993. - 772 p.

16. Kotov M. Equationally Noetherian Property and Close Property; Southeast Asian Bulletin of Mathematics - 2011. - No. 35. - P. 419-429.

17. Marker D. Model Theory— New York: Springer-Verlag — 2002. — 342 p.

18. Myasnikov A., Remeslennikov V. Algebraic geometry over groups II: Logical foundations // J. Algebra. - 2000. - Vol. 234. - P. 225-276.

19. Shelah S. Stable Theories // Israel Journal of Mathematics — 1969. — No. 7. - P. 187-202.

20. Shelah S. The Number of non-isomorphic models of an unstable firstorder theory // Israel Journal of Mathematics — 1971. — No. 9 — P. 473487.

21. Shevlyakov A. Algebraic geometry over Boolean algebras in the language with constants j/ arXiv.org, Cornell University Library, 2013 — 23 pp. URL: http://arxiv.org/pdf/1305.6844.pdf (дата обращения: 05.05.2014).

Публикации автора по теме диссертации

22. Дворжецкий Ю. С., Котов М. В. Минимаксные алгебраические системы // Вестник Омского университета. — 2008. — спец. выпуск «Комбинаторные методы алгебры и сложность вычислений». — С. 130-136.

23. Дворжецкий Ю. С. Об атомарной стабильности // Стохастические модели в биологии и предельные алгебры: тр. Междунар. конф., Россия, Омск - 2010. - С. 17.

24. Дворжецкий Ю. С. Атомарная стабильность // Вестник Омского университета. — 2011. — №4. — С. 37-44.

25. Дворжецкий Ю. С. Алгебраическая геометрия над дистрибутивными решётками // Мальцевские чтения: тр. Междунар. конф., Россия, Новосибирск — 2012. — С. 138.

26. Дворжецкий Ю. С. Алгебраическая геометрия над дистрибутивными решётками // Вестник Омского университета. — 2013. — №2. — С. 23-29.

27. Дворжецкий Ю. С. Алгебраическая геометрия над решётками с выделенным идеалом // Вестник Омского университета. — 2013. — №2. — С. 30-35.

28. Дворжецкий Ю. С. Алгебраическая геометрия над дистрибутивными решётками // Мальцевские чтения: тр. Междунар. конф., Россия, Новосибирск — 2013. — С. 153.

29. Дворжецкий Ю. С. Алгебраическая геометрия над алгебрами Ершова // Математические проблемы информатики: тр. Междунар. конф., Россия, Омск - 2013. - С. 24.

30. Y. Dvorzhetskiy Equationally Noetherian property of Ershov algebras // arXiv.org, Cornell University Library, 2014. — 11 pp. URL: http://arxiv.org/pdf/1405.0954.pdf (дата обращения: 05.05.2014).