Смекни!
smekni.com

Упорядоченные множества (стр. 4 из 8)

Произвольную полугруппу обычно обозначают 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 = x

1) Согласно равенству(*)

x

y = inf (x,y) = inf (y,x) = y
x

2) Обозначим а = (x

y)
z, в = x
( y
z)

Докажем, что а = в.

Для этого достаточно доказать , что

ав (4)

ва (5) (в силу антисимметричности)

Обозначим

с = x

y , d = y
z

По смыслу, а точная нижняя грань между с и z

а с , аz , cx, следовательно, в силу транзитивности ax.

Аналогично, а ≤ y, т.е. а – общая нижняя грань для y и z. А d – их точная нижняя грань .

Следовательно, ad, но в = inf {x,d}.

Из неравенства ax , ad следует , что а – некоторая общая нижняя грань для х и 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·yz = x·(y·z)

Тогда х·х = х

= х – в силу (1). Поэтому х ≤ х.