ОПРЕДЕЛЕНИЕ. Рефлексивное, антисимметричное и транзитивное отношение на некотором множестве называется отношением порядка

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

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

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

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

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

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

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

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

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

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