Произвольную полугруппу обычно обозначают S (semigroup).
Определение. Элемент e
S называется
идемпотентом, если
e
= e, то есть e · e = e. Пример 11.
Полугруппа < N; · > − обладает единственным идемпотентом 1.
Полугруппа < Z; + > − обладает единственным идемпотентом 0.
Полугруппа < N; + > − не имеет идемпотента, т.к. 0
N. Для любого непустого множества X, как обычно, через
обозначается множество всех подмножеств множества X – булеан множества X.
Полугруппа <В
;
> - такова, что каждый ее элемент идемпотентен.
A
В ,
A =
A A.Полугруппа называется идемпотентной полугруппой или связкой, если каждый ее элемент является идемпотентным. Таким образом, примерами связки является всякий булеан относительно объединения.
Пример 12.
Пусть X – произвольное множество.
B
– множество всех подмножеств множества
Х.
B
– называется булеаном на множестве
Х.
Если Х = {1,2,3} , то
B
= {Ø,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}.
Так как пересечение двух подмножеств множества Х вновь является подмножеством в Х, то имеем группоид < В
;
> , более того , это полугруппа и даже связка, так как
А В
и
А =
А А =
А.
Точно также, имеем связку <; В
> .
Коммутативная связка называется полурешеткой.
Пример 13.
Пусть Х = {1,2,3}, построим диаграмму < В
;
>.
Приведем примеры ЧУМ, но не полурешетки.
Пример 14.
ЧУМ с двумя нижними гранями е и d , которые между собой не сравнимы: е||d. Следовательно, inf{a;с} не существует.
Пример 15.
ЧУМ с двумя нижними гранями с и d, которые между собой несравнимы: с||d. Следовательно, inf{a;в} не существует.
Приведем примеры полурешеток.
Пример 16.
Диаграмма:
а
Является полурешеткой , т.к. для любых двух элементов существует точная нижняя грань, т.е.
inf{a;в}=в, inf{a;с}=с, inf{a;d}=d,
inf{в;c}=d, inf{в;d}=d,
inf{c;d}=d.
Пример 17. Является полурешеткой , т.к. для любых двух элементов существует точная нижняя грань, т.е.
inf{a;в}=в, inf{a;с}=с, inf{в;c}=с.
Теорема 1.
Пусть <S ; ≤ > - полурешетка. Тогда <S ;
> коммутативная связка, где a в = inf {a,в} (*).Доказательство:
Нужно доказать, что в <S ;
> выполняются следующие тождества:(1) x
y = y x(2) (x
y) z = x ( y z) (3) x
x = x1) Согласно равенству(*)
x
y = inf (x,y) = inf (y,x) = y x2) Обозначим а = (x
y) z, в = x ( y z)Докажем, что а = в.
Для этого достаточно доказать , что
а ≤ в (4)
в ≤ а (5) (в силу антисимметричности)
Обозначим
с = x
y , d = y zПо смыслу, а точная нижняя грань между с и z
а ≤ с , а ≤ z , c ≤ x, следовательно, в силу транзитивности a ≤ x.
Аналогично, а ≤ y, т.е. а – общая нижняя грань для y и z. А d – их точная нижняя грань .
Следовательно, a ≤ d, но в = inf {x,d}.
Из неравенства a ≤ x , a ≤ d следует , что а – некоторая общая нижняя грань для х и d, а в – их точная нижняя грань, следовательно,
а ≤ в
(4) доказано.Аналогично доказывается (5).
Из (4) и (5) , в виду антисимметричности, заключаем, что
а = в.
Этим мы доказали ассоциативность операции (
).3) Имеем x
х = inf {x,x} = x.Равенство выполняется за счет рефлексивности : х ≤ х.
Т.о. построенная алгебра <S ;
> будет коммутативной идемпотентной полугруппой , т.е. коммутативной связкой.Теорема 2.
Пусть <S ; · > - коммутативная идемпотентная полугруппа, тогда бинарное отношение ≤ на S, определяемое равенство
≤ = {(a,в)
S×S | a·в = а},является частичным порядком. При этом ЧУМ <S ; ≤ > является полурешеткой .
Доказательство:
1) рефлексивность ≤.
По условию <S ; · > удовлетворяет трем тождествам:
(1) х
= х (2) х·y = y·x
(3) (x·y)·z = x·(y·z)
Тогда х·х = х
= х – в силу (1). Поэтому х ≤ х.