Упражнение. Проверить, является ли отношением эквивалентности отношение синонимии на множестве слов русского языка.
ОТНОШЕНИЯ ПОРЯДКА
ОПРЕДЕЛЕНИЕ
Рефлексивное, антисимметричное и транзитивное отношение на некотором множестве называется отношением порядка.
Отношение порядка на некотором множестве А можно интерпретировать как отношение старшинства или подчиненности между элементами 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, то такая цепочка пустая.
Упражнение.
1. Предложите способ визуального представления симметричных отношений с помощью изображений, подобных диаграммам.
3. Докажите, что если r - транзитивное и рефлексивное отношение на A, то r является отношением порядка тогда и только тогда, когда в диаграмме для этого отношения нет последовательностей дуг, образующих циклы.
2. Докажите, что рефлексивное и транзитивное отношение является отношением эквивалентности, если любые две вершины диаграммы либо не связаны цепочкой дуг, либо лежат на некотором цикле.
Среди элементов упорядоченного множества (A, r) особый интерес представляют элементы, находящиеся в отношении r со всеми элементами A.
ОПРЕДЕЛЕНИЕ
Элемент a называется наибольшим (наименьшим) в отношении r, если " b Î A (a r b) (" a Î A (b r a)).
Понятно, что всякое упорядоченное множество имеет не более одного наибольшего (наименьшего) элемента. Например, если A - это множество возможных ситуаций или вариантов, из которых требуется выбрать оптимальный, и r - отношение предпочтения одних вариантов перед другими, представляющее собой отношение порядка, то наибольший и наименьший элементы упорядоченного множества (A, r) представляют соответственно наилучший и наихудший варианты.
В общем случае упорядоченное множество может не иметь наибольшего или наименьшего элементов. Например, это так для отношения порядка, диаграмма которого приведена на рис 3.2.
a b
cd
E f g
Рис. 3.2.
Здесь элементы a и b не являются наибольшими, обладают свойством максимальности для всех тех элементов A, с которыми они находятся в отношении r.
ОПРЕДЕЛЕНИЕ
Элемент a называется максимальным (минимальным) в упорядоченном множестве (A, r), если
" b Î A (b ¹ a Þ (b, a)Ïr) (" b Î A (b ¹ a Þ (a, b)Ïr)).
Упорядоченное множество может иметь несколько или не иметь вообще максимальных и минимальных элементов. Например, для упорядоченного множества, представленного диаграммой на рис. 3.2., максимальными являются элементы a и b, а минимальными - e, f и g.
Если A - конечное множество, то любое упорядоченное множество (A, r) всегда имеет максимальные и минимальные элементы. Для бесконечных множеств такое свойство может оказаться неверным.
Частным случаем частичного порядка является линейный порядок. Порядок r называется линейным, если:
" a, b Î A ((b r a) Ú (a r b)).
То есть, в линейном порядке любые два элемента множества, на котором определено отношение порядка, являются сравнимыми.
Следующая теорема характеризует общий вид диаграмм для отношений линейного порядка.
Теорема 3.3. Если r является отношением линейного порядка на конечном множестве A, то диаграмма для этого отношения имеет вид последовательности, составленной из всех элементов A, в которой всякий предыдущий элемент связан ориентированной дугой со следующим элементом.
Доказательство. Пусть r является отношением линейного порядка на множестве A = { a 1,..., a n}. Проведем доказательство индукцией по мощности множества A.
1. Базис индукции. Пусть A = { a 1}. Тогда диаграмма отношения r на A имеет вид одноэлементной последовательности a 1.
2. Индуктивное предположение. Пусть для каждого множества A содержащего не более чем n элементов выполнено утверждение теоремы.
3. Индуктивный переход. Пусть A = { a 1,..., a n, a n+1 }.
3.1. Покажем, что r имеет минимальный элемент. Предположим противное. Тогда для отношения r справедливо условие (1):
" a Î A $ b Î A (b r a) Ú $ a Î A $ b Î A ((a, b)Ï r & (b, a)Ï r). (1)
В этом условии левая часть дизъюнкции неверна, поскольку означает существование бесконечной последовательности элементов A, в которой для любых двух соседних элементов a и b выполняется условие b r a, что противоречит условию конечности множества A.
Неверной является и правая часть условия (1). Поскольку в этом случае для отношения линейного порядка найдутся два несравнимых элемента.
Следовательно, r имеет минимальный элемент.
3.2. Покажем что для отношения r выполнено утверждение теоремы. Пусть a Î A является минимальным элементом в отношении r. Тогда часть этого отношения для множестве A \ { a } является линейным порядком. Если бы это было не так, то несравнимые элементы для части r на множестве A \ { a } оказываются несравнимыми и для отношения r на A.
По индуктивному предположению для A \ { a } выполнено утверждаемое в теореме свойство. Пусть b минимальный элемент для части r на A \ { a }. Тогда диаграмма для части r на множестве A получается из диаграммы для части r на множестве A \ { a },добавлением ориентированной дуги, соединяющей вершину a с вершиной b.