Упорядоченные множества и универсальная алгебра (вводный курс). Гуров С.И. - 53 стр.

UptoLike

ВУЗ: 

МГУ | Москва

Составители: 

Рубрика: 

В соответствии с данной леммой, решётка J(P ), построенная в примере 20, дистри-
бутивна.
Укажем алгоритм построения диаграммы Хассе для решётки порядковых идеалов
J(P ) по данной диаграмме Хассе конечного ч.у. множества P .
Ненулевой элемент z решётки назовём элемент неразложимым в объединение, если
из z = x t y следует z = x или z = y. Очевидно, в этом случае элемент z нельзя
записать в виде объединения строго содержащихся в нём элементов. Например, атомы
любой решётки неразложимы, и в атомной булевой алгебре нет других неразложимых
элементов, а в конечной цепи ни один элемент не является разложимым.
Пусть множество I минимальных элементов P имеет мощность m.
1. Построим диаграмму Хассе конечной булевой алгебры, изоморфной J(I).
2. Выберем некоторый минимальный элемент x множества P r I и присоединим
к J(I) неразложимый в объединение элемент, содержащий порядковый идеал
J(x) r {x}.
3. Добавим все необходимые объединения элементов, содержащих идеал J(x) r {x},
чтобы они образовывали булеву алгебру.
4. Если существуют элементы, содержащие множество J(x)r{x} и покрывающие эле-
менты которых не имеют объединений, то изобразим последние так, чтобы образо-
валась булева алгебра. Продолжая таким образом до тех пор, пока каждое множе-
ство элементов, содержащее данный элемент не будет иметь объединения, получим
диаграмму Хассе дистрибутивной решётки J(I ∪ {x}).
5. Выберем некоторый минимальный элемент y множества (P rI)rx и присоединим
к J(I ∪{x}) неразложимый в объединение элемент, содержащий порядковый идеал
J(x) r {y}.
6. Повторяя шаги 3 и 4, получим диаграмму Хассе дистрибутивной решётки
J(I ∪ {x, y}).
7. Продолжаем аналогично, пока не получим диаграмму Хассе решётки J(P ).
Пример 29. Построим по приведённому алгоритму решётку порядковых идеалов ч.у. мно-
жества Z
5
вида “зигзаг”, изображённого на рис. 13.
d
e
a
b
c
Рис. 13: Ч.у. множество Z
5
вида “зигзаг”
Полученная решётка изображена на рис. 14. Известно, что n-элементное ч.у. множе-
ство вида “зигзаг” имеет F
n+2
( (n+2)-е число Фибоначчи) порядковых идеалов. В нашем
случае |J(Z
5
)| = F
7
= 13.
Лемма 2.14. В конечной решётке каждый ненулевой элемент может быть представ-
лен в виде объединения неразложимых элементов.
53
   В соответствии с данной леммой, решётка J(P ), построенная в примере 20, дистри-
бутивна.
   Укажем алгоритм построения диаграммы Хассе для решётки порядковых идеалов
J(P ) по данной диаграмме Хассе конечного ч.у. множества P .
   Ненулевой элемент z решётки назовём элемент неразложимым в объединение, если
из z = x t y следует z = x или z = y. Очевидно, в этом случае элемент z нельзя
записать в виде объединения строго содержащихся в нём элементов. Например, атомы
любой решётки неразложимы, и в атомной булевой алгебре нет других неразложимых
элементов, а в конечной цепи ни один элемент не является разложимым.
   Пусть множество I минимальных элементов P имеет мощность m.

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

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

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

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

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

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

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

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


                                         e [
                                   d[[
                                      [
                             a           b           c


                      Рис. 13: Ч.у. множество Z5 вида “зигзаг”

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

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


                                         53

Страницы