3.6. Отношения порядка

ОПРЕДЕЛЕНИЕ

Рефлексивное, антисимметричное и транзитивное отношение на некотором множестве называется отношением порядка.

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

Например, если A  множество сотрудников некоторого учреждения, то отношение "руководить" является отношением порядка на этом множестве. То есть, если обозначить данное отношение как , то соотношение a  b означает, что сотрудник a руководит сотрудником b, или, что то же самое, a является начальником b.

Упражнение. Показать, что если   это отношение порядка, то отношение ^1 также отношение порядка.

Множество A, на котором задано отношение порядка, называется упорядоченным. Для обозначения множества A с заданным на нем отношением порядка  применяется запись (A, ).

Элементы a и b упорядоченного множества (A, ) называются сравнимыми, если выполняется одно из двух соотношений: a  b или b  a.

Если (A, )  это упорядоченное множество и множество A  конечное, то возможно наглядное представление отношения  в виде специальной диаграммы. На таких диаграммах элементы A изображаются точками. Из точки, соответствующей a, проводится дуга в точку, соответствующую b в том и только в том случае, когда выполняется условие: a  b и не существует такого элемента c, отличного от a и b, что a  c и c  b. Кроме того, концы всякой дуги соединяют только пары разных вершин.

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

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

Действительно, справедливость соотношения a  b означает, что в диаграмме существует цепочка ребер, ведущая из a в b. Если a = b, то такая цепочка пустая.

Упражнение.

1. Предложите способ визуального представления симметричных отношений с помощью изображений, подобных диаграммам.

3. Докажите, что если   транзитивное и рефлексивное отношение на A, то  является отношением порядка тогда и только тогда, когда в диаграмме для этого отношения нет последовательностей дуг, образующих циклы.

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

Среди элементов упорядоченного множества (A, ) особый интерес представляют элементы, находящиеся в отношении  со всеми элементами A.

Определение

Элемент a называется наибольшим (наименьшим) в отношении , если  b  A(a  b) ( a  A(b  a)).

Понятно, что всякое упорядоченное множество имеет не более одного наибольшего (наименьшего) элемента. Например, если A  это множество возможных ситуаций или вариантов, из которых требуется выбрать оптимальный, и   отношение предпочтения одних вариантов перед другими, представляющее собой отношение порядка, то наибольший и наименьший элементы упорядоченного множества (A, ) представляют соответственно наилучший и наихудший варианты.

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

a b

c d

e f g

Рис. 3.2.

Здесь элементы a и b не являются наибольшими, обладают свойством максимальности для всех тех элементов A, с которыми они находятся в отношении .