Содержание к диссертации
Введение
Глава 1. Предварительные сведения 10
1.1 Предварительные сведения из алгебры логики 10
1.2 Сведения из теории моделей 12
1.3 Предварительные сведения из теории решёток 13
1.3.1 Решётки, дистрибутивные решётки 14
1.3.2 Дополнения, алгебры Ершова 17
1.4 Сведения из универсальной алгебраической геометрии . 18
1.4.1 Основные определения 19
1.4.2 Алгебраическая геометрия над булевыми алгебрами 21
Глава 2. Атомарная стабильность 23
2.1 Типы и атомарные типы 23
2.1.1 Полный тип n-ки элементов над множеством 23
2.1.2 Атомарные типы n-ки элементов над множеством . 24
2.1.3 Атомарные типы над множеством 25
2.1.4 Атомарные типы теории 28
2.2 Атомарная стабильность 30
2.3 Атомарная Л-стабильность 31
2.4 Нётеровость по уравнениям и атомарная стабильность . 37
Глава 3. Системы уравнений над дистрибутивными решётками . 42
3.1 Нормальный вид систем уравнений в дистрибутивных решётках 42
3.2 Нётеровость по уравнениям дистрибутивных решёток . 47
3.3 Дистрибутивные решётки и слабая нётеровость по уравнениям 51
3.4 Нормальный вид систем уравнений в алгебрах Ершова
3.5 Нётеровость по уравнениям алгебр Ершова 63
3.6 Другой нормальный вид систем уравнений над алгебрами Ершова 63
3.7 Слабая нётеровость по уравнениям в алгебрах Ершова 68
Глава 4. Системы уравнений над решётками с выделенным идеалом 76
4.1 Идеалы в решётках, решётки с выделенным идеалом 76
4.2 Нётеровость по уравнениям в решётках с предикатами 79
4.3 Канонический вид систем уравнений 80
4.4 Слабая нётеровость по уравнениям в булевых решётках с идеальным предикатом 85
Заключение 89
Литература
- Сведения из теории моделей
- Атомарные типы над множеством
- Нормальный вид систем уравнений в алгебрах Ершова
- Нётеровость по уравнениям в решётках с предикатами
Введение к работе
Актуальность работы.
Системы уравнений и их решения над алгебраическими системами рассматривались Г. Баумслагом, А. Г. Мясниковым и В. И. Ремеслен-никовым. В работах [9,18] была построена алгебраическая геометрия над группами. Подходы, применённые в этих статьях, были обобщены Э. Ю. Данияровой, А. Г. Мясниковым и В. И. Ремесленниковым на случай произвольной алгебраической системы в работах [2,11-14].
В работах [2,11-14] задача классификации алгебраических множеств с точностью до изоморфизма сведена к задаче классификации координатных алгебр. Также в этих работах доказаны так называемые объединяющие теоремы, которые показывают эквивалентность семи различных способов описания координатных алгебр.
Необходимым условием применения этих объединяющих теорем для какой-либо алгебраической системы является наличие у этой системы свойства нётеровости по уравнениям.
Э. Ю. Данияровой, А. Г. Мясниковым и В. И. Ремесленниковым в работе [13] было показано, что все результаты применимы не только к алгебраическим системам (без предикатных символов), но и к системам с произвольным языком. Следовательно, стало возможным говорить о нётеровости по уравнениям вообще в произвольных системах.
Э. Ю. Данияровой, А. Г. Мясниковым и В. И. Ремесленниковым было доказано, что объединяющие теоремы, а также некоторые другие результаты верны не только для нётеровых по уравнениям алгебраических систем, но и для систем с более слабыми свойствами [11]. Таким образом, были сформулированы понятия слабой нётеровости, qu- и иш-компактности. Соответствующие классы нётеровых и слабо нётеровых систем обозначают N и N', а классы оы- и иш-компактных систем — Q и U соответственно. Таким образом, чтобы применить объединяющие теоремы, необходимо просто показать принадлежность алгебраической системы к классам N, N', Q и U.
Впервые свойства нётеровости булевых алгебр с константами рассматривал А. И. Шевляков [21]. В его работе построен нормальный вид систем уравнений над булевыми алгебрами с константами. А. И. Шевляков доказал критерии принадлежности булевых алгебр к классам N и N' — нётеровых и слабо нётеровых алгебраических систем, Q и U — классам qu- и иш-компактных алгебраических систем, соответственно.
Также был доказан критерий геометрической эквивалентности булевых алгебр с константами.
Результаты А. Н. Шевлякова могут быть перенесены на более общие дистрибутивные решётки с константами и алгебры Ершова. Эти результаты также переносятся на булевы алгебры с выделенными идеалами, изучаемые Д. Е. Пальчуновым [3-7].
Целью диссертационной работы является изучение систем уравнений над алгебраическими системами с порядком и исследование связи свойства нётеровости по уравнениям с наличием порядка в алгебраической системе.
Для достижения поставленной цели были решены следующие задачи:
-
Определить понятия атомарной стабильности и атомарной А-ста-бильности алгебраических систем по аналогии с понятиями стабильности и А-стабильности как критериев для дальнейшего изучения алгебраической геометрии.
-
Исследовать связь атомарной стабильности с нётеровостью по уравнениям.
-
Построить канонический вид систем уравнений, доказать критерии нётеровости и слабой нётеровости над дистрибутивными решётками, решётками с выделенным идеалом, алгебрами Ершова.
Научная новизна. Все основные результаты диссертации являются новыми.
Теоретическая и практическая значимость. Диссертационная работа имеет теоретический характер. Введено понятие атомарной стабильности, построены критерии нётеровости и слабой нётеровости по уравнениям для дистрибутивных решёток, решёток с выделенным идеалом, алгебр Ершова. Результаты диссертационной работы могут быть использованы при дальнейшем изучении алгебраической геометрии над алгебраическими системами.
Апробация работы. Основные результаты работы докладывались на следующих конференциях и семинарах:
1. Международная конференция «Мальцевские чтения» (ИМ им. С. Л. Соболева, Новосибирск, 2008, 2009, 2012, 2013 гг.).
-
Международная школа-семинар «Новые алгебро-логические методы решения систем уравнений» (ОФ ИМ им. С. Л. Соболева, Омск, 2009 г.).
-
Омский алгебраический семинар (ОФ ИМ им. С. Л. Соболева, Омск, 2010, 2012, 2013 гг.).
-
Международная конференция «Стохастические модели в биологии и предельные алгебры» (ОФ ИМ им. С. Л. Соболева, Омск, 2013 г.).
-
Школа-конференция «Математические проблемы информатики» (ОФ ИМ им. С. Л. Соболева, Омск, 2013 г.).
-
Семинар «Алгебра и логика» (ИМ им. С. Л. Соболева, Новосибирск, 2014 г.).
Объем и структура работы. Диссертация состоит из введения, четырёх глав и заключения. Полный объем диссертации составляет 93 страницы. Список литературы содержит 30 наименований.
Сведения из теории моделей
Определение 3 (Элементарное вложение). Пусть A n B - системы языка С. С-гомоморфизм f : A - B называют элементарным вложением, если f сохраняет истинность всех формул языка С, то есть для любой формулы (р(х) языка С и для любых элементов a G A выполнено B = ip (f(a)) тогда и только тогда, когда выполнено A \= if (a). Определение 4 (Элементарная эквивалентность, элементарное расширение, элементарная подсистема). Две системы A и B языка С называются элементарно эквивалентными, если Th(A) = Th(B).
Систему B называют элементарным расширением системы A, ес-ли B : A и С-гомоморфизм f : A - B является элементарным вложением, то есть для любой формулы р(х) языка С и для любых элементов aGA выполнено B = ір (a) A \= ф).
Систему A в этом случае называют элементарной подсистемой. Факт 1 (Критерий элементарных подсистем Тарского-Вота, [15]). Пусть AиB системы языка С, A С B. Тогда следующее утверждения эквивалентны: 1. A является элементарной подсистемой В. 2. Для каждой формулы ф(х,y) лзыка С и всех кортежйй a G A из того, nто В = Зуф(a,y)7 следует, что существует элементе! G A7 чтоB=ф(a,(1).
Пусть A = (A; С) - система языка С. Пусть a G A - набор порождающих A элементов, aс- набор соответствующих константных символов. Расширим язык С до языка С-С7 добавив константы c, и будем рассматривать расширенную систему Д- = (A; Сс). Определение 5 (Элементарная диаграмма, [15, р.56]). Элементарной диаграммой системы A мы будем называть теорию расширенной системы Thcc(Ac), где c — любая последовательность констант для порождающих A элементов.
Элементарную диаграмму мы будем обозначать eldiag(A). Лемма 1 (Лемма об элементарных диаграммах, [15, р.55]). Пусть A и B — системы языка С, c — кортеж констант, отсутствующих в языке С, Ас иВъ системы расширенного языка Сс и сл = a, с3 = а, причём, a порождает Ас- Тогда следующие утверждения эквиваллнтны: 1. для любой формулы ф) языка С, если Ac = Ф)7 то В-с = р(c); 2. существует такое элементарное вложенее f : A — B7 что f(a) = b. Исходя из этой леммы, можно получить следствие [15, р.56], которое мы будем использовать.
Следствие 1. Если система D-c языка С-с является моделью элементарной диаграммы eldiag(A) системы A языка С, то существует элементарное вложенее A в ограничение D = Т Т\ц.
В дальнейшем нам также понадобится следующая теорема, играющая важную роль в теории моделей.
Факт 2 (Теорема компактности Гёделя-Мальцева). Пусть T — теория некоторого языка. Теория T имеет модель тогда и только тогда, когда любое конечное подмножество формул теории T имеет модель.
В данном параграфе будут представлены основные сведения из теории решёток. В параграфе 1.3.1 будут даны определения решёток и дистрибутивных решёток, в параграфе 1.3.2 будут определены алгебры Ершова. 1.3.1. Решётки, дистрибутивные решётки
Определение 6 (Решётка). Алгебраическую систему A = (A; V, Л) языка Со мы будем называть решёткой, если для любых a,b,c G A выполнены следующие аксиомы: 1. Идемпотентность: a Л a = a, a V a = a. 2. Коммутативность: a Лb = b Л a, aV b = bV a. 3. Ассоциативность: (a Л b) Л c = a Л (b Л c), (a V b) V c = a V (b V c). 4. Законы поглощения: a Л (a V b) = a, a V (a Л b) = a. В дальнейшем мы будем активно использовать следующий принцип двойственности.
Факт 3 (Принцип двойственности). Если какая-то формула язика Со верна на всём классе решёток, то двойствннная формула, полученная взаимной заменой символов V и Л, также истинна на всём классе решёток.
Понятие решётки неизменно связано с порядком. Любое частично-упорядоченное множество, в котором для любых двух элементов есть точные верхняя и нижняя грани, является решёткой. В дальнейшем будут рассматриваться решётки со свойством дистрибутивности.
Определение 7 (Дистрибутивная решётка). Решётку A = (A; V,Л) мы будем называть дистрибутивной, если для любых элементов a,b,c G A выполнено: Пример 1 (Решётка подмножеств). Пусть X - некоторое множество элементов. Пусть A - это множество подмножеств множества X, замкнутое относительно операций объединения и пересечения, тогда алгебраическая система A = (A; V = U, Л = п) является дистрибутивной решёткой.
Такую дистрибутивную решётку мы будем называть решёткой подмножеств. Если множество A — это множество всех подмножеств множества X, то в этом случае А будем называть решёткой всех подмножеств.
Введём понятия С-решётки и дистрибутивной С-решётки. Определение 8 (С-решётки). Решётку A расширенного языка С мы будем называть С-решёткой, где через С обозначена решётка, порождённая константами {с;г е I}.
Определение 9 (Дистрибутивная С-решётка). Дистрибутивную решётку A расширенного языка С мы будем называть дистрибутивной С-решёткой, где через С обозначена дистрибутивная решётка, порождённая константами {с;г е I}. Также отметим, что на любой решётке можно ввести частичный порядок, положив:
Определение 10 (Цепь, антицепь). Любое линейно упорядоченное подмножество элементов решётки мы будем называть цепью. Антицепью мы будем называть подможество элементов решётки, в котором любые два элемента несравнимы.
Определение 11 (АСС, DCC). Будем говорить, что решётка удовлетворяет условию обрыва возрастающих цепей (АСС), если в решётке не существует бесконечных строго возрастающих цепей элементов.
Будем говорить, что решётка удовлетворяет условию обрыва убывающих цепей (DCC), если в решётке не существует бесконечных строго убывающих цепей элементов.
Определение 12 (JID, MID). Будем говорить, что полная решётка A удовлетворяет свойству бесконечной дистрибутивности JID, если
В решётках существуют и другие дополнения. Определение 14 (Псевдодополнение элемента). Пусть A - дистрибутивная решётка с 0. Элемент a называется псевдодополнением элемента a, если a Л a = 0, и для любого другого x Е A из того, что x Л a = 0, следует x a\
Определение 15 (Относительные дополнения). Дополнением к элементу x относительно элементов a и b (a x b) мы будем называть такой элемент x что x Л x = a, x V x = b.
Из определений очевидно, что дополнение x к элементу x — это дополнение к элементу x относительно 0 и 1.
Отметим, что в любой дистрибутивной решётке существует не более одного относительного дополнения к элементу в каждом интервале его содержащем. В дальнейшем мы будем рассматривать только дистрибутивные решётки.
Атомарные типы над множеством
В этом параграфе даётся определение атомарной Л-стабильности, по аналогии с понятием А-стабильности из теории моделей, только атомарная стабильность определяется не с помощью типов, а с помощью атомарных типов.
Определение 38 (Атомарная Л-стабильность). Пусть T - теория язы-ка д Л _ бесконечный кардинал. Будем называть теорию T атомарно Л-стабильной, если для любой модели A = (A; С) теории T и любого подмножества Y С A, Y Л выполнено SatA(Y; A) Л.
Теорию T будем называть атомарно Л-нестабильной, если она не является А-стабильной. Систему A будем называть атомарно А-(не-)стабильной, если Th(A) атомарно Л-(не-)стабильна.
Как уже говорилось, все введённые определения атомарной стабильности являются аналогами соответствующих классических определений. Следующая теорема показывает связь этих определений стабильности, аналогичную существующей для классических определений стабильности. Теорема 1 (Сравнение определений атомарной стабильности). Пусть T — полная теория языка первого порядка С. Если по крайней мере для одного бесконечнооо кардинала Л, такого что С X, теория T атомарно Л-стабильна, то T атомарно стабильна. Доказательство. Прежде чем приступить к доказательству теоремы, при ведём несколько фактов и докажем лемму. В доказательстве Леммы 2 будет использоваться следствие из теорем Лёвенгейма-Скулема вверх и вниз.
Факт 4 (Следствие теорем Лёвенгейма-Скулема). Пусть А — бесконечный кардинал, С - язык первого порядка, \С\ X, А - С-система. Тогда существует такая элементарно эквивалентная A система В = {В; С), что \В\ = А.
Следующая лемма является аналогом соответствующего утверждения для неатомарного случая [15].
Лемма 2. Пусть А = (А, С) - С-система, Л - бесконечный кардинал, \С\ X, Y С A, \Y\ Л. Допустим существует такое п Є N7 что \Satin{Y-A)\ \Y\. Тогда система A атомарно Х-нестабильна. Доказательство. Докажем это утверждение индукцией по п. База: п = 1. 5 П(У; А)\ \Y\ Л. Получаем, что А атомарно А-нестабильна по определению (Определение 38).
Переход: Пусть п 1. По определению полного атомарного п-типа над множеством (Определение 31) для каждого полного атомарного тетина р{х) Є Sat,n{Y;A) выберем элементарное расширение Вр = (ВР;С) системы А (можно считать, что Y С А С Вр), а также кортеж Ър = (6рд,,.., ЬРуП-і) Є Вп 1 длины (n — 1) и элемент ср Є Вр, такие, что полный атомарный n-тип р над Y системы А реализуется в системе Вр на п-ке d = (ЪрЛ,..., bp,n-i,Cp). Т. к. А \С\, то по Факту 4 можно допустить, что для каждого р(х) Є Satn{Y] А) носитель Вр системы Вр имеет мощность А. Обозначим для каждого типар(ж) Є 5аі)П(У; А) полный атомарный (п-1)-тип atpBp (bp/Y) (п - 1)-ки Ър над Y системы Вр. Возможно 2 г .арианта: 1. Число различных полных атомарных (n- 1))типов atpBp (bp/Y) соответствующей (п-1)-ки больше Л. Т. к. для каждогоp(x) Е 5 П(У; A) система Вр элементарно эквивалентна A, то по Утверждению 2 каждый полный атомарный (n - 1))тип atpBp (bp/Y) данной (п - 1)-ки в соответствующей системе является полным (n — 1)-типом над Y в A. Следовательно, мы имеем больше Л полных атомарных (n - 1)-типов над Y системы A, т.е. Sat;n-i(Y;A) Л. По предположению индукции для n — 1 получаем, что A атомарно Л-нестабильна.
2. Число различных полных атомарных (n- 1))типов atpBp (bp/Y) соответствующей (n - 1))ки не больше А. Пусть А+ - наименьший регулярный кардинал, больший А. Значит, должно существовать подмножество S С Sat;n(Y;A) мощности Л+ такое, что все атомарные типы atpBp (bp/Y), где p Е S, равны. Выберем произвольный тип s Е S С /Sa,n(Y; Л.) и введём для каждого полного n-типа p Е S новое множество формул от одной переменной qp(x) = {(fi{bs,x) : (р{х) Е р{х)} с параметрами из Y U {bs} С Bs в системе Bs (параметры из Y формул ір(х) Е р(ж) явно записывать не будем).
Заметим, что по Утверждению 3 все полные атомарные n-типы из p Е Sat;n(Y;A) попарно несовместны (т.е. объединение любых двух типов есть несовместное множество формул). Следовательно, и все построенные множества формул qp(x) с параметрами из Y U {bs} будут попарно несовместны вBs, и поэтому различны. Значит, мы имеем ровно Л+ множеств. По построению формул qp(x) и элемента cs Е Bs эти множества формул конечно реализуемы на множестве YU{6S} в системе Bs. Поэтому по утверждению 3 они являются атомарными 1-типами над YU{bs} в системе Bs. Итак, мы имеет ровно Л+ несовместных 1-типов над Y U {bs} системы Bs. Дополним каждый из них до полного атомарного 1-типа над Y U {ЪЛ системы Bs. Т. к. исходные типы были попарно несовместны, то полученные типы тоже будут попарно несовместны, а, следовательно, и различны. Получили подмножество T С Sat;i(Y U {bs} ;Ва). В силу элементарной эквивалентности Вр и A, а также в силу
Нормальный вид систем уравнений в алгебрах Ершова .
В этом разделе мы докажем, что дистрибутивная C-решётка Л нёте-рова по уравнениям тогда и только тогда, когда решётка С конечна. Теорема 4 (АСС и DCC в нётеровых по уравнениям С-решётках). Если С-решётка Л нётерова по уравнениям, то в С выполнены АСС и DCC
Доказательство. Допустим противное, т.е. в С существует или бесконечно возрастающая цепь с\ с2 ..,, или бесконечно убывающая цепь с\ С і ..,, и рассмотрим в каждом случае систему от одной переменной: S(x) = {х сг\іє Щ или S(x) = {х сг\іє Щ. Очевидно, что для любой конечной подсистемы (любой из этих систем) ре шением является константа Ck для достаточно большого к Є N, но никакое из Q, і Є N не является решением целой системы. Следовательно, Л — не является нётеровой по уравнениям.
Таким образом, в решётке С любая цепь конечна. Далее покажем, что в С конечна и любая антицепь.
Определение 40 (Л- и V-неприводимые элементы). Элемент а мы будем называть Л-неприводимым (V-неприводимым), если из того, что а = х Л у (пли а = хУу, соответственно), следует, что х = « или у = а. Теорема 5 ( [10]). Пусть Л — дистрибутивная решётка, удовлетворяющая DCC, Р С Л - множество всех У-неприводимых элементов. Тогда каждый элемент а Є Л представим единственным образом (с точностью до сокращения) в виде а = Ъх V ... V Ъп, где Ъг - У-неприводимые элементы.
Введём частично упорядоченное множество Р - множество всех V-неприводимых элементов решётки Л, упорядоченное порядком из Л. Покажем некоторые свойства этого множества Р в случае бесконечной решётки Л.
Утверждение 7. Пусть Л — дистрибутивная решётка, удовлетворяющая DCC и АСС, Р С А — частично упорядоченное множество всех V-неприводимых элементов, с порядком из Л. Пусть решётка Л бесконечна, тогда: 1. Множество Р бесконечно. 2. Множество Р также удовлетворяет DCC и АСС. 3. Число всех максимальных элементов в Р также бесконечно. Доказательство. Докажем эти утверждения по порядку. 1. Очевидно, что P бесконечно, иначе по Теореме 5 исходная решётка будет конечной. 2. Действительно, т.к. P С A и т.к. P упорядочено порядком из A, то если найдётся необрывающаяся возрастающая или убывающая цепь в P, то, эта же цепь, с сохранением порядка, будет лежать и в Л, но A удовлетворяет DCC и АСС. 3. Т.к. множество P удовлетворяет АСС, то любая возрастающая цепь заканчивается максимальным элементом. Рассмотрим множество этих максимальных элементов и все цепи, спускающиеся вниз из этих элементов (в порядке убывания элементов). Далее, т.к. множество P удовлетворяет АСС, то, спускаясь из соответствующего максимального элемента, мы можем дойти до любого элемента из P. Заметим также, что никакой элемент p из P не может быть больше двух других несравнимых между собой элементов — иначе в A найдутся два элемента, которые в объединении дадут p, но p - V-неразложимый. Следовательно, если мы спускаемся из максимального элемента, то мы сможем спуститься только по одной цепи, т.е. эти цепи не «разветвляются» (хотя могут «склеиваться»). Т.к. P удовлетворяет DCC, то все эти цепи ещё и конечны.
Допустим противное — число максимальных элементов в P конечно. Следовательно, число всех этих спускающихся конечных цепей конечно. В этих цепях лежат все элементы P, значит, частично упорядоченное множество P конечно — противоречие с уже доказанной бесконечностью P.
Доказательство этой леммы можно найти в [10]. Лемма 3. Если в дистрибутивной решётке элемента У-неразложим и а ЬхУ ...УЪп, тоа Ъг, для некоторого i = 1,..., п. Теорема 6. Дистрибутивная С-решётка Л нётерова по уравнениям, тогда и только тогда, когда дистрибутивная решёткаС, порождённяя константам,, конечна.
Доказательство. Если С конечна, то и число возможных уравнений тоже конечно, следовательно, любая бесконечная система уравнений является конечной.
Докажем в другую сторону. Пусть решётка С бесконечна, тогда и число всех максимальных V-неприводимых бесконечно (Утверждение 7). Все эти элементы несравнимы между собой. Т. е. существует бесконечная антицепь а,і, i Є N V-неприводимых элементов. Рассмотрим бесконечную систему уравнений от одной переменной: {аг х і Є N} . Т. к. Л нётерова по уравнениям, то эта система эквивалентна в Л некоторой конечной подсистеме. Не умаляя общности, можно считать, что эквивалентная система имеет вид {а х \ і = 11.. п}.
Рассмотрим решение х = а1 V ... V ап. Оно, действительно, является решением первой системы: аг ц V ... V ап для любого i = 1... п. Т. к. системы эквивалентны, то х = а1 V ... V ап должно являться решением любого другого уравнения бесконечной системы: ttn+i = «і V ... V ап. По Лемме 3 (если рассматривать всё только в подрешётке С) ап+ї di, для некоторого i. Получили противоречие, т. к. все (ц несравнимы. Сле довательно, решётка С конечна.
. Дистрибутивные решётки и слабая нётеровость по уравнениям А.Н. Шевляковым был доказан следующий критерий слабой нётеро-вости по уравнениям для булевых решёток. Теорема 7 (А.Н. Шевляков). Булева С-решётка В слабо нётерова по уравнениям тогда и только тогда, когда решётка С, порождённая константами, полна в Л.
Подобный критерий для дистрибутивных решёток не верен. В этом разделе мы покажем, что наличие в решётке 0 и 1, а также полноты этой решётки и полноты подрешётки констант, наличие свойств бесконечной дистрибутивности JID и MID, а также псевдодополнений и относительных псевдодополнений не достаточно для слабой нётеровости по уравнениям.
Нётеровость по уравнениям в решётках с предикатами
Теперь всё готово для введения предикатного символа, выделяющего некоторый идеал в решётке. Пусть в решётке А зафиксирован некоторый идеал I. Добавим в язык L одноместный предикат р\1\ проинтерпретировав его на А следующим образом:
Такой предикат в дальнейшем мы будем называть идеальным предикатом. Решётки с таким предикатом мы будем называть решётками с выделенным идеалом. Теоретико-модельные свойства этих решёток были исследованы Д.Е. Пальчуновым [4].
Отметим, что в булевых решётках дуальный идеал совпадает со всей решёткой. Действительно, пусть I — дуальный идеал в B, рассмотрим произвольный элемент а этой решётки. Т.к. I является V-идеалом, то все элементы x а принадлежат I. Т.к. 1 а, то и 1 е I. Но I также является и Л-идеалом, следовательно, все элементы x 1 также принадлежат I, т.е. идеал I включает в себя всю решётку. В силу двойственности понятий Л- и V-идеалов в дальнейшем мы будем исследовать только Л-идеалы, те, которые в классическом смысле понимаются под термином "идеал решётки".
Нётеровость по уравнениям в решётках с предикатами В этом разделе мы докажем критерий нётеровости по уравнениям для дистрибутивных решёток с конечным набором произвольных предикатов. Все необходимые определения алгебраической геометрии можно найти в статьях [14]- [12], а истинность всех результатов для систем с предикатом описана в [13].
Критерий нётеровости по уравнениям был доказан А.Н. Шевляко-вым для булевых решёток [21]. Он также верен для более общих дистрибутивных решёток [26] и останется неизменным при добавлении в язык произвольного конечного набора предикатов. Об этом следующая теорема. Теорема 12. Дистрибутивная С-решётка А = (A; V 2 ; Pl},pf2...,. , ffc);C) с конечным набором предикатов Р г), i = 1,...,k местности Ni7 нётеро-ва по уравнениям тогда и только тогда, когда дистрибутивная решётка C, порождённая константами, конечна.
Доказательство. Пусть подрешётка C конечна, покажем, что А нётерова по уравнениям. Заметим, что если C конечна, то конечно и число всевозможных неэкБивалентных уравнений от конечного числа переменных ж. Действительно, любое уравнение имеет вид tx{x) = t2(x) или Pi(t1(X), ...,tN((x)), где все ti(x) — термы языка С. Заметим, что в записи каждого уравнения участ 80 вует только конечное число термов. Запишем каждый этот терм в ДНФ. Заметим, что общее число таких различных ДНФ конечно, т.к. в записи каждой конъюнкции может участвовать только конечное число символов — или символы констант или символы переменных. Следовательно, общее число неэквивалентных уравнений, а также систем уравнений, конечно. Это влечёт нётеровость по уравнениям.
Тот факт, что из бесконечности C следует ненётеровость А, следует из конструкции, приведённой в [26], т.к. эта конструкция никак не зависит от добавления в язык новых предикатов. Отсюда следует, что критерий нётеровости по уравнениям верен для булевых и более общих дистрибутивных решёток с идеальным предикатным символом, вне зависимости от идеала, который выделяет предикат. 4.3. Канонический вид систем уравнений В этом разделе мы опишем канонический вид для уравнений и систем уравнений в решётках с идеальным предикатным символом. Зафиксируем язык С = Ы2\ Л(2\ Р]1\с). Пусть Л={А-М2\ 2\Р\1\С) - дистрибутивная C-решётка с идеальным предикатом р\1, где I - некоторый идеал А, а C — подрешётка, порождённая константами языка С. В этой системе любое уравнение от переменных x имеет вид t(x) = S(X) или РМх)), где t(x) и S(X) - термы языка С.
В статье [26] доказано, что любая система уравнений без предикатного символа может быть эквивалентно переписана в систему уравнений следующего вида: (хч Л ... Л х1т Л са) (хп V ... V x3l V съ где в каждой части уравнения символы переменных не повторяются (одна и та же переменная не может быть и в левой, и правой частях), и в каждой части уравнения не более одного константного символа, причём, если в каждой части есть константный символ, то са сь.
Здесь же мы рассмотрим уравнения видаР/(/(x)), где Р/ — предикат принадлежности к двустороннему идеалу /. а /(x) — терм языка С. Лемма 6. Пусть А = /A; V(2\ Л(2\ Р\1\С\ - дистрибутивная С-решётка с предикатом принадлежности к некоторому идеалу /. Тогда: 1. Если / — Л-идеал, то в A верна следующая эквивалентность:
