WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 11 |

Диаграммы Хассе дают удобный способ описания решёток. Однако, если решётка устроена слишком сложно, такие диаграммы становятся мало наглядными. Следующая теорема даёт другие возможности представления решёток.

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

Доказательство. Пусть A произвольная решётка. Рассмотрим отображение, сопоставляющее каждому элементу x A главный идеал J(x) P(A). Необходимо показать, что отображение : (1) взаимнооднозначно, (2) изотонно, (3) обратно изотонно и (4) сохраняет пересечения. Будем устанавливать свойства в указанном порядке.

1) Пусть (x) = (y). Так как (x) = J(x) и всегда, в силу рефлексивности порядка, x J(x), то x J(y) и y J(x). Значит одновременно x y и y x, т.е., в силу антисимметричности, x = y.

c b d a e o Рис. 9: Решётка с неядерным идеалом b 2) Пусть x y или x J(y). В этом случае z J(x) влечёт z x y и, по транзитивности, z J(y). Таким образом (x) = J(x) J(y) = (y).

3) Если (x) (y) или, что то же J(x) J(y), то x J(y) (поскольку x J(x) ), и, значит, x y.

4) Поскольку в тотальной алгебре множеств P(A) точная нижняя грань двух элементов (подмножеств A ) совпадает с их теоретико-множественным пересечением, нам надо показать, что (x y) = (x) (y). В самом деле, z (x y) z J(x y) z (x y) z x z y z J(x) z J(y) z (J(x) J(y)) z ((x) (y)).

Теорема доказана.

Данная теорема позволяет представлять элементы любой решётки подмножествами некоторого множества A, а операцию пересечения отождествить с теоретикомножественным пересечением в A. Это, в свою очередь, даёт возможность пользоваться аналогами диаграмм Эйлера-Венна. При этом наибольшему элементу решётки (если он существует) соответствует само множество A, а наименьшему o (если он есть) договариваются сопоставлять пустое подмножество A (хотя по теореме 2.9 (o) = J(o) = {o}, но точка, соответствующая o, содержится во всех идеалах решётки, и её можно удалить без нарушения отношения включения идеалов).

Отличие от ситуации с булевой алгеброй будет в представлении объединения подмножеств: можно показать, что отображение, описанное в теореме 2.9 обладает свойством включения (x) (y) в (x y), но не их равенства (которое будет иметь место только в случае сравнимости x и y ). Поэтому при обозначении объединения элементов, изображаемых в виде связных выпуклых областей, необходимо рисовать выпуклую область, покрывающую “с запасом” области, соответствующие данным элементам (см. рис. 10).

2.3 Специальные виды решёток Далее мы рассмотрим некоторые специальные типы решёток, представляющие особый интерес.

x y x y Рис. 10: Обозначение объединения элементов решётки 2.3.1 Модулярные решётки Определение 2.16. Решётка L = L,, называется модулярной, если для любых x, y, x L в ней выполняется следующий модулярный закон Mod : x y x (y z) = y (x z).

Ясно, что смысл модулярного закона состоит в выполнении следования, обратного утверждаемому в Mod. Двойственный к модулярному закон x y x (y z) = y (x z) ему эквивалентен. Поэтому для модулярных решёток принцип двойственности остается справедливым.

Пример 26. 1. Модулярными являются все цепи, решётка N, |, булевы алгебры и их подрешётки. Впоследствии мы увидим, что для этих решёток справедливо более сильное условие дистрибутивности.

2. Решётка NSub (G) всех нормальных подгрупп группы G образует модулярную решётку. Действительно, пусть X, Y, Z произвольные нормальные подгруппы группы G и X Y. Известно, что объединение X Z двух нормальных подгрупп def X и Z группы G совпадает с их произведением XZ = { g G | x z ( g = xz ) }, X Z а пересечение подгрупп всегда есть подгруппа. Поэтому нам нужно показать справедливость включения Y XZ X(Z Y ). В самом деле, всегда найдутся такие x X и z Z, что g Y XZ g Y g = xz g = xz z Y Z g X(Z Y ).

Второе следование справедливо, поскольку xz = g влечёт z = x-1g Y.

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

3. Другим важным примером модулярной решётки является решётка всех подпространств векторного пространства. Под объединением подпространств понимается наименьшее подпространство, их содержащее. Доказательство этого факта полностью аналогично доказательству модулярности решётки NSub (G). Точно также доказывают, что решётка всех идеалов любого кольца модулярна.

Решётка всех эквивалентностей на данном множестве в общем случае не модулярна. Действительно, рассмотрим множество M = { 1, 2, 3, 4 }. Среди E(M) имеются эквивалентности a, b и c со смежными классами a = { {1}, {2}, {3, 4} }, b = { {1}, {2, 3}, {4} } и c = { {1, 2}, {3, 4} } соответственно. Вместе с диагональным отношением в качестве o и аморфной эквивалентностью в качестве они образуют решётку N5 (см. рис. 8). Однако, она немодулярна, поскольку a c, но a (c b) = a o = a = c (a b) = c = c.

Таким образом, решётка E(M), содержит немодулярную подрешётку, и, следовательно немодулярна сама.

Немодулярность N5 оказывается ключевой: справедлива Теорема 2.10 (Критерий модулярности решётки). Решётка модулярна, если и только если никакая её подрешётка не изоморфна пятиугольнику N5.

Доказательство. () Поскольку пятиугольник не модулярен, то никакая решётка, содержащая изоморфную ему подрешётку, не может быть модулярной.

() Покажем, что немодулярная решётка L содержит подрешётку, изоморфную пятиугольнику N5.

Немодулярность L означает существование таких её элементов x, y и z, что x y, но x (y z) y (x z). Покажем, что элементы y z, x (y z), y (x z), z, x z образует подрешётку в L, изоморфную N5.

В самом деле, должны иметь место соотношения y z z x z и y z x (y z) y (x z) x z, поскольку, заменив первый, второй третий или пятый знак на =, получим x z или z y, откуда сразу следует модулярный закон.

Далее x y = (x z) z (x (y z)) z (y (x z)) z (x y) z = x z.

Это означает, что элементы x (y z) и y (x z) оба дают в объединении с z элемент x z.

Кроме того, y y = (y z) z (x (y z)) z (y (x z)) z = y ((x z) z) = y z.

Это означает, что элементы x (y z) и y (x z) оба дают в пересечении с z элемент y z.

Данный критерий влечет справедливость условия Жордана-Дедекинда для цепей: если в конечной решётке две максимальные цепи между элементами a b имеют разную длину, то интервал [ a, b ] содержит подрешётку, изоморфную N5, и, следовательно, данная решётка немодулярна.

Пример 27. Решётка, изображённая на рис. 11 немодулярна: длины её максимальных цепей не совпадают и, как следствие, она содержит подрешётку, изоморфную N5 (например, { o, a, b,, g } ).

Теорема 2.11. Решётка L,, модулярна, если и только если для любых её элементов x, y и z имеет место соотношение x ((x y) z)) = (x y) (x z) или эквивалентное двойственное ему x ((x y) z)) = (x y) (x z).

e b g f a d o Рис. 11: Немодулярная решётка Доказательство. Если решётка L модулярна, то первое тождество следует из “неравенства” x x y, если в модулярном законе заменить y на x y. Обратно, при x y, или, что то же, при x y = y, первое тождество превращается в x (y z) = y (x z), что является заключением модулярного закона.

Справедливость второго тождества следует из принципа двойственности.

2.3.2 Дистрибутивные решётки Определение 2.17. Решётка называется дистрибутивной, если в ней выполняется дистрибутивные законы Dtr1 : (x y) z = (x z) (y z) ; Dtr2 : (x y) z = (x z) (y z).

Ясно, что смысл дистрибутивных законов состоит в выполнении следований, обратных утверждаемым в Dtr1 и Dtr2. Так же понятно, что для дистрибутивных решёток принцип двойственности остается справедливым. Более того, легко видеть, дистрибутивные законы для решёток эквивалентны. Действительно, для любых элементов x, y, z решётки имеем Dtr1 Abs1, Dtr(x z) (y z) = (x (y z)) (z (y z)) = Abs= (x y) (x z) z = (x y) z.

т.е. доказано следование Dtr1 Dtr2. Двойственно показывается, что Dtr2 Dtr1.

Так что достаточно было потребовать выполнения лишь одного из дистрибутивных законов (обычно постулируют выполнение Dtr1 ).

В дистрибутивных решётках и только в них справедливо следующее правило.

Утверждение 2.2 (Правило сокращения). Решётка L дистрибутивна, если только если для любых x, y, z L справедливо следующее правило сокращения x y = x z Abbr : y = z.

x y = x z Доказательство. () Пусть в дистрибутивной решетке для некоторых элементов x, y и z справедливы равенства x y = x z и x y = x z. Тогда имеем:

Abs1 Dtry = y (y x) = y (z x) = (y z) (y x) = Dtr1 Abs= (y z) (x z) = (y x) z = (x z) z = z.

Мы видим, что справедливость Abbr есть следствие законов коммутативности, поглощения и дистрибутивности.

() Доказательство достаточности может быть найдено в [13].

Пример 28. 1. Все цепи, булевы алгебры и их подрешётки дистрибутивны.

2. Покажем дистрибутивность решётки N, |, т.е., что для любых натуральных чисел x, y, z справедливо соотношение x (y z) = (x y) (x z), где x y наибольший общий делитель, а x y наименьшее общее кратное x и y. Воспользуемся каноническим представлением натуральных чисел в виде произведений их простых сомножителей s s s i i i x = pi, y = pi, z = pi, i=1 i=1 i=считая, что некоторые показатели могут быть равны 0. Тогда s x (y z) = pimin{ i, max{ i, i } }, i=s (x y) (x z) = pimax{ min{ i, i }, min{ i, i } }, i=и требуемое равенство min { i, max { i, i } } = max { min{ i, i }, min{ i, i } } представляет собой дистрибутивный закон для цепи неотрицательных целых чисел.

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

4. Непустая совокупность подмножеств некоторого множества, содержащая вместе с двумя подмножествами их объединение и пересечение называется решёткой или кольцом множеств (ср. с определением поля множеств на с. 5). Всякая решётка множеств дистрибутивна, поскольку дистрибутивны теоретико-множественные операции объединения и пересечения.

5. Решётка Sub (C) всех подгрупп циклической группы C дистрибутивна. Заметим, что, однако, Sub (C) не является решёткой множеств, поскольку объединение её элементов (в отличие от пересечения) не совпадает с теоретико-множественным.

Пятиугольник N5 недистрибутивен: действительно, (см. рис. 8d) (a b) c = c = c = (a c) (b c) = a o = a.

Поэтому справедливо Утверждение 2.3. Всякая дистрибутивная решётка модулярна.

Это утверждение так же следует из того, что модулярный закон представляет собой ослабленную форму первого дистрибутивного закона: если x y, то x y = y и Dtrx (y z) = (x y) (x z) = y (x z).

V4 = a c b E = o Рис. 12: Решётка Sub (V4).

Решётка NSub (G) всех нормальных подгрупп группы G модулярна (см. пример 26.2) но, в общем случае, не дистрибутивна. Действительно, рассмотрим четверную группу Клейна V4 = x, y, x2 = y2 = e, xy = yx. Собственные её подгруппы суть a = x, b = y и c = xy. Все они нормальны, поскольку V4 абелева. Решётка Sub (V4) её подгрупп (см. рис. 12) изоморфна M3 и модулярна, но не дистрибутивна, т.к. не дистрибутивен ромб M3:

(a b) c = c = c = (a c) (b c) = o o = o.

Недистрибутивность M3, оказывается ключевой: справедлива Теорема 2.12. Модулярная решётка является дистрибутивной, если и только если никакая её подрешётка не изоморфна ромбу M3.

Доказательство. () Поскольку ромб M3 не дистрибутивен, то никакая решётка, содержащая изоморфную ему подрешётку, не может быть дистрибутивной.

() Пусть решётка L модулярна и не содержит M3 в качестве подрешётки. Для произвольных x, y, z L рассмотрим следующие пять элементов a = (z (x y)) (x y), b = (y (x z)) (x z), c = (x (y z)) (y z), u = (x y) (y z) (z x), v = (x y) (y z) (z x).

Покажем сначала, что a b = b c = c a = v и a b = b c = c a = u.

Имеем (z (x y)) (y (x z)) = (x y) ((y (x z)) z) = = (x y) ((x z) (y z)) = v.

Вывод сделан с учётом модулярного закона, а также следований y (x z) x z и z x z для первого и второго равенств соответственно. Отсюда получаем, что a b = v и, в силу симметрии, что b c = c a = v.

Учитывая модулярный закон и очевидное следование x y x z получаем другое, двойственное к исходному, выражение для a:

a = (z (x y)) (x y).

Аналогично b = (y (z x)) (z x), c = (x (y z)) (y z).

Используя теперь принцип двойственности для модулярных решёток и учитывая, что u двойственно v, получим a b = b c = c a = u.

Таким образом, если все элементы a, b и c попарно различны, то подрешётка { u, a, b, c, u } в L изоморфна ромбу M3. Это невозможно, и, значит, u = a = b = c = u, но тогда (x y) z a = u (x z) (y z), и, следовательно, в L выполняется дистрибутивный закон.

Следствие (Критерий дистрибутивности решётки). Решётка дистрибутивна, если и только если никакая её подрешётка не изоморфна ни пятиугольнику N5, ни ромбу M3.

Пусть I идеал дистрибутивной решётки L. Отношение I = { (a, b) L2 | x (a x = b x) } I является, как нетрудно видеть, эквивалентностью на L. Кроме того, легко устанавливается, что (x1 x2)I(y1 y2) x1Ix2 y1Iy2.

(x1 x2)I(y1 y2) Это позволяет корректно определить операции объединения и пересечения классов на фактормножестве L/I (поскольку их результат не будет зависеть от выбранных элементов в соответствующих классах). Таким образом, L/I есть решётка (с нулём). Гомоморфизм : L L/I, определяемый естественным отображением = nat(L, I) имеет своим ядром данный идеал I. Решётка дистрибутивна если и только если каждый её идеал ядерный, т.е. является ядром подходящего гомоморфизма (ср. рис. 9).

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

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

Лемма 2.13. Совокупность J(P ) порядковых идеалов элементов ч.у. множества P есть дистрибутивная решётка.

Доказательство. Пусть P ч.у. множество и J(P ) совокупность порядковых идеалов P. Введём на J(P ) операции объединения и пересечения как соответствующие теоретико-множественные. Поскольку объединение и пересечение порядковых идеалов есть порядковый идеал, а теоретико-множественные операции дистрибутивны, то J(P ) есть дистрибутивная решётка.

В соответствии с данной леммой, решётка J(P ), построенная в примере 20, дистрибутивна.

Укажем алгоритм построения диаграммы Хассе для решётки порядковых идеалов J(P ) по данной диаграмме Хассе конечного ч.у. множества P.

Ненулевой элемент z решётки назовём элемент неразложимым в объединение, если из z = x y следует z = x или z = y. Очевидно, в этом случае элемент z нельзя записать в виде объединения строго содержащихся в нём элементов. Например, атомы любой решётки неразложимы, и в атомной булевой алгебре нет других неразложимых элементов, а в конечной цепи ни один элемент не является разложимым.

Пусть множество I минимальных элементов P имеет мощность m.

1. Построим диаграмму Хассе конечной булевой алгебры, изоморфной J(I).

2. Выберем некоторый минимальный элемент x множества P I и присоединим к J(I) неразложимый в объединение элемент, содержащий порядковый идеал J(x) {x}.

3. Добавим все необходимые объединения элементов, содержащих идеал J(x) {x}, чтобы они образовывали булеву алгебру.

4. Если существуют элементы, содержащие множество J(x) {x} и покрывающие элементы которых не имеют объединений, то изобразим последние так, чтобы образовалась булева алгебра. Продолжая таким образом до тех пор, пока каждое множество элементов, содержащее данный элемент не будет иметь объединения, получим диаграмму Хассе дистрибутивной решётки J(I {x}).

5. Выберем некоторый минимальный элемент y множества (P I) x и присоединим к J(I {x}) неразложимый в объединение элемент, содержащий порядковый идеал J(x) {y}.

6. Повторяя шаги 3 и 4, получим диаграмму Хассе дистрибутивной решётки J(I {x, y}).

7. Продолжаем аналогично, пока не получим диаграмму Хассе решётки J(P ).

Пример 29. Построим по приведённому алгоритму решётку порядковых идеалов ч.у. множества Z5 вида “зигзаг”, изображённого на рис. 13.

e d a c b Рис. 13: Ч.у. множество Z5 вида “зигзаг” Полученная решётка изображена на рис. 14. Известно, что n-элементное ч.у. множество вида “зигзаг” имеет Fn+2 ( (n+2)-е число Фибоначчи) порядковых идеалов. В нашем случае |J(Z5)| = F7 = 13.

Лемма 2.14. В конечной решётке каждый ненулевой элемент может быть представлен в виде объединения неразложимых элементов.

Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 11 |






















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

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