Диаграммы Хассе

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

Пусть . Рассмотрим на множестве X отношения порядка “ £ ” и “ ½ ”. Получим два частично упорядоченных множества (X, £) и (X, ½), различия которых наглядно отражают их диаграммы Хассе (рис.1.9).

Определение. Элемент называется наибольшим элементом частично упорядоченного множества p), если p w. Элемент называется максимальным элементом частично упорядоченного множества p), если в множестве X нет элемента y такого, что u p y.

Элемент является наибольшим и одновременно максимальным для (X, £) (рис. 1.9, а). В частично упорядоченном множестве (X, ½) есть два максимальных и , но нет наибольшего (рис. 1.9, б).

Аналогично определяются понятия наименьшего и минимального элементов частично упорядоченного множества.

Теорема. Всякое частично упорядоченное множество имеет не более одного наибольшего элемента.

Доказательство. Пусть p) – частично упорядоченное множество. Теорема утверждает, что если в множестве p) имеется наибольший элемент, то он единственный. Предположим противное: пусть имеется два различных наибольших элемента и . Тогда по определению наибольшего элемента w p и p w, откуда в силу антисимметричности отношения порядка “ p ” следует - противоречие, что и доказывает теорему.

Дата добавления: 2014-12-07