Диаграммы Хассе
Для наглядного представления частично упорядоченного множества используют диаграмму Хассе – граф отношения 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 ” следует - противоречие, что и доказывает теорему.
|