WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 6 | 7 || 9 | 10 |   ...   | 11 |

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 (Биркгофа). Всякая дистрибутивная решётка вложима в решётку всех подмножеств подходящего множества.

Мы докажем эту теорему для класса конечных решёток, где она допускает следующее усиление.

Теорема 2.17. Всякая конечная дистрибутивная решётка изоморфна решётке порядковых идеалов подходящего ч.у. множества.

Доказательство. Пусть 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).

Pages:     | 1 |   ...   | 6 | 7 || 9 | 10 |   ...   | 11 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.