Смекни!
smekni.com

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

Далее отыскиваем минимальные элементы ЧУМа

, изображаем их точками “третьего ряда” и соединяем точками “второго ряда” указанным выше спо­собом. Продолжаем процесс до тех пор , пока не будут исчерпаны все эле­менты данного ЧУМа S. Процесс конечен в силу конечности множества S. Полученную совокупность точек и отрезков называют диаграммой ЧУМа S. При этом a < в тогда и только тогда, когда от “точки” а можно перейти к “точки” в по некоторой “восходящей” ломаной. В силу этого обстоятельства , любое конечное ЧУМ можно отождествить с его диаграммой.

Пример 5.


Здесь задано диаграммой ЧУМ S = {m

, m
,

,
,
,
},в кото­рой m
<
, m
<
, m
<
m
<
, m
<
m
<
, m
<
.

Элемент m называется наименьшим элементом ЧУМа, если для лю­бого x

A всегда mx.

Понятно, что наименьший элемент является мини­мальным, но обратное не верно: не всякий минимальный элемент является наименьшим. Наименьший элемент (если такой имеется) только один. Аналогично определяется наибольший элемент.

Пример 6.

· · · ·

Это ЧУМ , элементы которого попарно несравнимы. Такие частично

упорядоченные множества называются антицепями.

Пример 7.

·

0

Эта цепь с наименьшим и наибольшим элементом. Где 0 - наименьший эле­мент , а 1 – наибольший элемент.

Пусть М – подмножество частичного упорядоченного множества А. Элемент а

A называют нижней гранью множества М, если а ≤ х для лю­бого x
М.

Наибольшая из всех нижних граней множества М, если она существует, называется точной нижней гранью множества М и обозначают inf M.

Пусть < А, ≤ > - произвольный ЧУМ. Элемент с

A называется точной нижней гранью элементов a,в
A, если с = inf{a}.

Замечание 1.

Не во всяком ЧУМ для любых двух элементов существует точная нижняя грань.

Покажем это на примере.

Пример 8.

Для {a;c},{d;e} нет нижней грани,

inf{a;в}=d, inf{в;c}=e.

Пример 9.


Приведем пример ЧУМ, у которого для любых элементов существует точная нижняя грань.

inf{a;в}=d, inf{a;d}=d, inf{a;0}=0, inf{a;c}=0, inf{a;e}=0,

inf{в;c}=e, inf{в;e}=e, inf{в;d}=d,

inf{c;e}=c, inf{c;0}=0, inf{c;d}=0,

inf{d;e}=0, inf{d;0}=0,

inf{e;0}=0.

Определение: Частично упорядоченное множество, в котором для лю­бых двух элементов существует точная нижняя грань, называется полуре­шеткой.

Пример 10.

Приведем пример ЧУМ, которое не является полурешеткой.

Пусть < N, ≤ > - линейно - упорядоченное множество натуральных чисел и e

,e
N. На множестве N
=N
{ e

,e
} определим бинарное отношение ≤ , пологая что xy, если x,y
N, где xy, или если x
N, y
{ e
,e
}. Также счи­таем по определению : e
e
,e
e
.

Диаграмма этого ЧУМ следующая:


Любое натуральное число n e

и n ≤ e
, но в N нет наибольшего эле­мента, следовательно, N
- ЧУМ, но не полурешетка.

Итак, по самому определению, полурешетка есть модель (как множе­ство с отношением ≤ ). Как мы сейчас увидим к понятию полурешетки воз­можен и другой подход, а именно, полурешетку можно определить как неко­торую алгебру.

Для этого введем некоторые дополнительные алгебраические понятия. Как известно, полугруппой называется непустое множество с заданной на нем ассоциативной бинарной алгебраической операцией.