d, e c, d a, e d a, b, c e a, b a, c b, c a b c Рис. 14: Решётка J(Z5) Доказательство. Если элемент b неразложим, то b = b b. Пусть b = b1 b2 и b1 = b = b2. Если и b1, и b2 неразложимы, то лемма доказана. В противном случае представляем b1 и/или b2 в виде объединения строго содержащихся в них элементов, и т.д. В силу конечности решётки указанный процесс закончится, и исходный элемент b будет представлен в виде объединения неразложимых элементов.
Множество неразложимых в объединение элементов решётки L будем обозначать Irr L. На этом множестве можно ввести порядок, наследуемый от L и рассматривать Irr L как ч.у. множество.
Лемма 2.15. Если P ч.у. множество, то Irr J(P ) P.
= Доказательство. Пусть P ч.у. множество. Тогда J(P ) дистрибутивная решётка его порядковых идеалов. Ясно, что порядковый идеал решётки неразложим, если и только если он является главным. Поэтому между неразложимыми в объединение элементами из J(P ) и элементами P существует взаимнооднозначное соответствие. Ранее же был показан изоморфизм между ч.у. множеством и совокупностью его главных идеалов.
Пример 30. 1. Рассмотрим ч.у. множество P, заданное диаграммой Хассе на рис. 15 a). Множество её идеалов J(P ) представлено на на рис. 15 b), где выделены неразложимые элементы J(P ).
2. Для ч.у. множества P, заданного диаграммой Хассе на рис. 16 a), решётка J(P ) и ч.у. множество Irr J(P ) приведены на b) и c).
b, c c J(b) J(c) b a J(a) a) P b) J(P ) Рис. 15: Диаграммы Хассе ч.у. множества P и множества его идеалов J(P ) (элементы Irr J(P ) выделены) c, d c J(c) J(d) J(c) J(d) d a, b a J(a) J(b) J(a) J(b) b a) P b) J(P ) c) Irr J(P ) Рис. 16: Диаграммы Хассе ч.у. множества P, J(P ) и Irr J(P ) Для дистрибутивных решёток справедлива Теорема 2.16 (Биркгофа). Всякая дистрибутивная решётка вложима в решётку всех подмножеств подходящего множества.
Мы докажем эту теорему для класса конечных решёток, где она допускает следующее усиление.
Доказательство. Пусть L,, конечная дистрибутивная решётка, Irr L подмножество неразложимых в объединение элементов J(L) (дистрибутивная в силу леммы 2.13) и J(Irr L) соответствующая подрешётка J(L).
В силу леммы 2.15 достаточно показать, что L J(Irr L). Ясно, что J(x) J(Irr L), = где J(x) = x главных идеал x L и отображение : x J(x) есть изотонное и обратно изотонное вложение L в J(Irr L) (см. доказательство теоремы 2.9). Следовательно, нам осталось показать, что сюръективно.
Пусть I некоторый идеал из J(Irr L). Теорема будет доказана, если будет установлено, что идеал I главный.
Обозначим x = sup { y | y I }. Ясно, что I J(x) и x = sup { y | y I } = sup { y | y J(x) }.
Пусть z некоторый элемент J(x). Вычислим x z. В силу дистрибутивности, имеем sup { y z | y I } = sup { y z | y J(x) }. (2.2) Правая часть (2.2) есть в точности z, т.к. один из элементов J(x) есть z, а все другие элементы J(x) в z содержатся. Поскольку z Irr L, то z неразложим. Отсюда из (2.2) следует, что некоторый элемент y I удовлетворяет условию y z = z, т.е. z y. Так как I порядковый идеал и z I, то J(x) I, откуда I = J(x), т.е. I главный идеал.
Пример 31. Для конечной дистрибутивной решётки, представленной на рис. 17 a) ч.у.
множество Irr J(L) и решётка J(Irr L) приведены на b) и c).
b, c c c J(b) J(c) b b a a J(a) o a) L b) Irr L b) J(Irr L) Рис. 17: Диаграммы Хассе решётки L, ч.у. множества Irr L и дистрибутивной решётки J(Irr L) Теорема Биркгофа позволяет представлять элементы любой дистрибутивной решётки подмножествами некоторого множества A и пользоваться диаграммами Эйлера-Венна.
Из теоремы также вытекает интересное Следствие. Всякая конечная дистрибутивная решётка вложима в упорядоченную делимостью решётку натуральных чисел.
Доказательство. Из теоремы Биркгофа следует, что конечная дистрибутивная решётка L вкладывается в булеан P(S) некоторого конечного множества S. С другой стороны, пример 25.5 показывает, что P(S), вложима в N,,. Таким образом, L вкладывается в N,,, и, следовательно, в N, |.
Покажем, как конечная дистрибутивная решётка L может быть вложена в N,,.
Наименьшему элементу o решётки L сопоставляется число 1, а её атомам p1,..., pn первые n простых чисел. Пусть состоялось приписывание всем элементам множества x x элемента x решётки L. Если элементу x непосредственно предшествует единственный элемент, которому сопоставлено число k, то сопоставляем x число kp, где p первое из ещё не использованных простых чисел. Если элементу x непосредственно предшествуют несколько элементов, то сопоставляем x наименьшее общее кратное всех чисел, им соответствующих. Такое сопоставление для решёток из примера 31 и J(P ) из примера 20 приведён на рис. 18.
30 6 10 6 2 2 1 a) b) Рис. 18: Вложения конечных дистрибутивных решёток в решётку N, | 2.3.3 Решётки с дополнениями Определение 2.18. Если в решётке L,, с универсальными гранями для элемента x существует элемент y такой, что x y = o, x y =, то последний называется дополнением элемента x.
Решётка называется решёткой с дополнениями, если в ней каждый элемент имеет хотя бы одно дополнение. Если каждый элемент решётки обладает в точности одним дополнением, то её называют решёткой с единственными дополнениями.
Ясно, что если y дополнение x, то и x дополнение y, и что в любой ограниченной решётке o и являются единственными дополнениями друг для друга.
Пример 32. 1. В решётке алгебры подмножеств множества A каждый элемент X A имеет единственное дополнение X = A {X}. Это классический пример решётки с единственными дополнениями.
2. В решётке, представленной на рис. 18 a) элемент 2 не имеет дополнения.
3. Пятиугольник N5 решётка с дополнениями. В ней (см. рис. 8.c) ) дополнениями a и c будет элемент b, а дополнениями b элементы a и c.
Следствием того, что в дистрибутивной решётке справедливо правило сокращения Abbr (см. утверждение 2.2) является Утверждение 2.4. Если решётка дистрибутивна, то каждый её элемент имеет не более одного дополнения.
Доказательство. Допустим, что элемент x решётки имеет два дополнения y1 и y2.
Тогда x y1 = x y2 = Abbr y1 = y2.
x y1 = x y2 = o Из теоремы Биркгофа 2.16 следует, что каждая дистрибутивная решётка вложима в дистрибутивную решётку с единственными дополнениями.
Вопрос о связи свойств дистрибутивности и наличия единственного дополнения у решёток является, как оказалось, достаточно глубоким и трудным. В начале XX века при формулировке систем аксиом для булевой алгебры естественной была попытка определить её как решётку, имеющую единственное дополнение. Это оказалось бы возможным, если единственность дополнения у элементов решётки влекло бы её дистрибутивность.
В связи с этим Э. Хантингтоном (см. с. 5) было высказано предположение о том, что все решётки с единственными дополнениями дистрибутивны. Вопрос о том, верна ли эта гипотеза и составлял знаменитую проблему Хантингтона.
К концу 30-х годов XX в. было исследовано значительное количество конкретных решёток с единственными дополнениями, все они оказались дистрибутивными, в силу чего справедливость данного предположения практически не вызывала сомнений у математиков. Поэтому большой неожиданностью было опубликование в 1945 г. работы американского математика Р. Дилуорса16 в которой была доказана Теорема 2.18 (Дилуорса). Всякая решётка может быть вложена в подходящую решётку с единственными дополнениями.
В частности, можно взять пятиугольник N5, и тогда теорема Дилуорса даст немодулярную и, тем более, недистрибутивную решётку с единственными дополнениями.
Таким образом было доказано, что существуют недистрибутивные решётки с единственными дополнениями.17 Отметим однако, что данный объект в доказательстве теоремы Дилуорса появляется лишь в результате некоторого предельного перехода, и до сих Dilworth R.P. Lattices with unique complements. Trans. Amer. Math. Soc., 1945, 57, p. 123-154.
Современное доказательство данной теоремы имеется в [12].
пор нет ни одного явного примера недистрибутивной решётки с единственными дополнениями.
Решётка называется полной, если любое подмножество её элементов имеет точные верхнюю и нижнюю грани (ср. с определением полной булевой алгебры на с. 12). Например, отрезок [ 0, 1 ] с обычным порядком и произвольная алгебра множеств являются полными решётками. В классе полных решёток проблема Хантингтона до сих пор не имеет разрешения.
Определение 2.19. Если [ a, b ] интервал решётки L, x [ a, b ], и элемент y решётки L таков, что x y = a и x y = b, то y называется относительным дополнением элемента x в интервале [ a, b ].
Если в некоторой решётке все интервалы суть решётки с дополнениями, то она называется решёткой с относительными дополнениями.
Легко видеть, что если y относительное дополнение элемента x в интервале [ a, b ], то y [ a, b ] и x, в свою очередь, также будет относительным дополнением элемента y в интервале [ a, b ].
Пример 33. На рис. 19 изображена диаграмма Хассе решётка с относительными дополнениями. Дополнениями элемента b в интервале [e, ] являются элементы c и d, а элементы a и e служат друг для друга единственными дополнениями в интервале [0, b].
c b d a e o Рис. 19: Решётка с относительными дополнениями 2.4 Булевы алгебры (продолжение) 2.4.1 Безатомные булевы алгебры. Булевы гомоморфизмы, кольца и структуры Определение 2.20. Дистрибутивная решётка с дополнениями называется булевой алгеброй.
Согласно утверждению 2.4 в булевой алгебре каждый элемент имеет одно и только одно дополнение. Нетрудно видеть, что оба определения данное выше и на с. 4 эквивалентны.
До сих пор мы рассматривали только атомные булевы алгебры. Приведём примеры булевых алгебр, не имеющих атомов.
Пример 34. Рассмотрим множество A, элементами которого являются подмножества действительных чисел, представимые в виде объединения конечного числа полуинтервалов вида (x, y], содержащихся в промежутке (0, 1]. Это множество, очевидно, устойчиво относительно теоретико-множественных операций объединения, пересечения и дополнения до (0, 1], т.е. представляет собой булеву алгебру. Единицей в ней будет интервал (0, 1], а нулём пустое множество, представляемое в виде (x, x]. Легко видеть, что эта алгебра не имеет атомов: любой интервал (x, y] при 0 < x < y 1 содержит в себе ненулевой подынтервал такого же вида.
Пример 35. Рассмотрим P(Z),,,,, Z тотальную алгебру над множеством целых чисел Z. Определим отношение над элементами P(Z): будем считать, что A B, если симметрическая разность множеств A и B конечна.
Ясно, что есть отношение эквивалентности. Поэтому можно образовать фактормножество P(Z)/. Все конечные (включая пустое) подмножества P(Z) будут, очевидно, эквивалентныж обозначим этот класс эквивалентности []. Также будут эквивалентными все подмножества целых чисел, имеющих конечные дополнения до Z, включая само Z; этот класс эквивалентности обозначим [Z].
Далее, легко проверить, что введенное отношение является также и стабильным относительно теоретико-множественных операций, т.е. для любых A, B P(Z) из A A и B B следует A B A B, A B A B и A A. Это означает, что к элементам фактор-множества P(Z)/ применимы операции сигнатуры алгебры множеств, и АС B = P(Z)/,,,, [], [Z] будет являться булевой алгеброй.
Легко убедиться, что данная булева алгебра не имеет атомов. Действительно, любой отличный от o элемент B класс бесконечных множеств. Атом элемент, непосредственно следующий за o, а таковые отсутствуют в B.
Приведём без доказательства следующий критерий для атомных булевых алгебр.
Теорема 2.19. Булева алгебра будет атомной если и только если её единичный элемент представляет собой точную верхнюю грань всех её атомов.
В п. 1.1.3 было введено понятие изоморфизма булевых алгебр. Дадим теперь определение булева гомоморфизма и его ядра.
Определение 2.21. Пусть B1 и B2 две булевы алгебры. Решёточный гомоморфизм : B1 B2 называется булевым гомоморфизмом, если для всех x из B1 справедливо (x ) = (x).
def Множество Ker = { x B1 | (x) = o }, связанное с булевым гомоморфизмом называют его ядром.Инъективные булевы гомоморфизмы называют булевыми мономорфизмами.
Таким образом, булев гомоморфизм сохраняет все операции булевой алгебры и её выделенные элементы. Для того, чтобы булев гомоморфизм был булевым изоморфизмом необходима биективность отображения. Ясно, что произвольный гомоморфизм одной булевой алгебры в другую может не быть булевым гомоморфизмом.
Пример 36. Если A B, то естественное вложение P(A) в P(B) является решёточным мономорфизмом, но не булевым гомоморфизмом.
Здесь не надо путать ядро отображения (подмножество множества) с раннее рассмотренным ядерным отношением (подмножество декартова квадрата множества).
Определение 2.22. Булева алгебра B называется подалгеброй булевой алгебры B, если B B как решётки, имеют общие нули, единицы и дополнение элемента в B совпадает с его дополнением в B.
n Пример 37. 1. Булева алгебра P2 логических функций от n переменных является подалгеброй алгебры P2 всех логических функций (см. пример 3).
2. Пусть A B. Тогда P(A) P(B), поскольку эти булевы алгебры имеют, например, разные единичные элементы (что влечёт и несовпадение дополнений данного подмножества A в P(A) и в P(B) ).
Непосредственно из определений следует простое Утверждение 2.5. Пусть : B1 B2 булев гомоморфизм. Тогда 1. (o) = o, () = ;
2. x y (x) (y) для любых x и y из B1;
3. (B1) булева подалгебра в B2.
В булевой алгебре B,,,, o, можно ввести производные операции взаимного дополнения или вычитания ( ) и симметрической разности ( ):
def def x y = x y, x y = (x y) (y x).
При этом оказывается, что x = x и x y = x y xy.
Рассмотрим булеву алгебру B = B,,,, o,. Образуем на её основе АС B = B,, ·, o,, где симметрическая разность, а · новое обозначение операции пересечения. Тогда B является ассоциативно-коммутативным кольцом с единицей и нулём o, операциями сложения и умножения ·, в котором для любого элемента x имеет место свойство Id булевой алгебры или, в другой записи, x2 = x.
Ассоциативно-коммутативное кольцо, обладающие свойством x2 = x называется булевым кольцом. Основным примером булева кольца является кольцо P(A),,,, A, получаемое указанным способом из тотальной алгебры множеств.
Таким образом, построенная выше АС B есть булево кольцо с единицей. Если же в некотором булевом кольце R = R, +, ·, 0, 1 с единицей 1 и нулём 0 положить x y = x + y + xy, x y = xy и x = x + 1, то получим булеву алгебру R = R,,,, 0, 1. Таким образом, любое булево кольцо с единицей может быть задано с помощью булевой алгебры и наоборот. При этом, как легко видеть, B = B и R = R. Тем самым устанавливается т.н. стоуновская двойственность между булевыми алгебрами и булевыми кольцами.
Из теоремы 2.6 следует, что в булевой алгебре можно ввести отношение порядка по правилу def def x y = x y = x или x y = x y = y.
Легко показать, что тогда из x y будут следовать соотношения x y = o, x y = и x y (последнее соотношение есть закон антиизотонности дополнения).
Теперь можно определить булеву структуру B,,,,, o,, где её редукт B,,,, o, булева алгебра. Для многих приложений удобнее рассматривать не булевы алгебры, а сразу булевы структуры. Аналогично можно ввести булеву структуру множеств P(A),,,,,, A, дополнив тотальную алгебру множеств отношением включения. Очевидно также, что любая булева структура множеств есть и булева структура.
Теорема 2.20. Булева структура есть решётка с относительными дополнениями.
Доказательство. Пусть B булева структура, a x b, и x дополнение для x.
Определим элемент def Mod y = a (b x ) = b (a x ) (2.3) и покажем, что y относительное дополнение элемента x в интервале [ a, b ]. Действительно, x y = x (b (x a)) = (x b) (x a) = = x (x a) = (x x ) (x a) = a, и, двойственно, x y = x (b (x a)) = (x b) (x x a) = b = b.
Таким образом, в булевой алгебре относительные дополнения определяются легко по формуле (2.3). Если на интервале [ a, b ] по (2.3) определить операцию взятия дополнения, то АС [ a, b ],,,, a, b оказывается булевой алгеброй. Отметим, что полученная булева алгебра не будет (за исключением “собственного” случая a = o, b = ), являться подалгеброй исходной алгебры т.к.эти алгебры имеют, например, различные выделенные элементы.
2.4.2 Булевы идеалы и фильтры Решётчатые идеалы [фильтры] в булевой алгебре B называют булевыми идеалами [фильтрами] в B. Для булева идеала в B используют обозначение I B.
Пример 38. Рассмотрим тотальную алгебру множеств P(M) над множеством M.
1. Пусть A M. Тогда совокупность всех подмножеств множества M, содержащихся в A есть идеал в P(M), а содержащих A есть фильтр в P(M).
