02-03_-_kombinatorika_otnoshenia (1)

3.1. Покажем, что в каждом классе из R любые два элемента находятся между собой в отношении .

Пусть выбраны произвольное множество [ x] R и элементы a, b A. Покажем, что a b. Действительно, по определ ению множества [ x] справедливы соотношения: x a и x b. Из соотношения x a и симметричности следует, что a x. Из a x и x b, а также транзитивности следует, что a b.

3.2. Покажем, что элементы из разных классов в R не находятся в отношении . Пусть [ x], [y] R и a[x], b[y] произвольные элементы этих множеств. Покажем, что ( a, b) . Предположим противное. Пусть a b. Тогда из симметричности отношения следует, что b a. Поскольку y b и b a, то из транзитивности следует, что y a. Поэтому a[y]. Последнее противоречит тому, что множества [ x] и [y] не пересекаются.

Следовательно, (a, b) .

Доказательство окончено.

Упражнение. Проверить, является ли отношением эквивалентности отношение синонимии на множестве слов русского языка.

3.6. ОТНОШЕНИЯ ПОРЯДКА

ОПРЕДЕЛЕНИЕ

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

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

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

отношение как , то соотношение a b означает, что сотрудник a

64

руководит сотрудник ом 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, то такая цепочка пустая.

Упражнение.

65

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.

66

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

ОПРЕДЕЛЕНИЕ

Элемент a называется максимальным (минимальным) в упорядоченном множестве ( A, ), если

b A(b a (b, a) ) ( b A(b a (a, b) )).

Упорядоченное множество может иметь несколько или не иметь вообще максимальных и минимальных элементов. Например, для упорядоченного множества, представленного диаграммой на рис. 3.2., максимальными являются элементы a и b, а минимальными e, f и g.

Если A конечное множество, то любое упорядоченное

множество (A, ) всегда имеет максимальные и минимальные элементы. Для бесконечных множеств такое свойство может оказаться неверным.

Частным случаем частичного порядка является линейный порядок. Порядок называется линейным, если:

a, b A((b a) (a b)).

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

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

Доказательство. Пусть является отношением линейного порядка на множестве A = {a1 , . . . , an }. Проведем доказательство индукцией по мощности множества A.

1. Базис индукции. Пусть A = {a1 }. Тогда диаграмма отношенияна A имеет вид одноэл ементной последовательности a1 .

67

2. Индуктивное предположение . Пусть для каждого множества A

содержащего не более чем n элементов выполнено утверждение теоремы.

3. Индуктивный переход. Пусть A = {a1 , . . . , an , an + 1 }.

3.1. Покажем, что имеет минимальный элемент. Предположим противное. Тогда для отношения справедливо условие (1):

a A b A (b a) a A b A ((a, b) (b, a) ). (1)

В этом условии левая часть дизъюнкции неверна, поскольку означает существование бесконечной последов ательности элементов A, в которой для любых двух соседних элементов a и b выполняется условие b a, что противоречит условию конечности множества A.

Неверной является и правая часть условия (1). Поскольку в этом случае для отношения линейного порядка найд утся два несравнимых элемента.

Следовательно, имеет минимальный элемент.

3.2. Покажем что для отношения выполнено утверждение теоремы. Пусть a A является минимальным элементом в отношении . Тогда часть этого отношения для множестве A \ { a } является линейным порядком. Если бы это было не так, то несравнимые элементы для части на множестве A \ { a } оказываются несравнимыми и для отношения на A.

По индуктивному предположению для A \ { a } выполнено утверждаемое в теореме свойство. Пусть b минимальный элемент для части на A \ { a }. Тогда диаграмма для части на множестве A получается из диаграммы для части на множестве A \ { a }, добавлением ориентированной дуги, соединяющей вершину a с вершиной b.

Доказательство окончено.

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

Упражнение.

1. Приведите не менее 5 видов диаграмм для отноше ния линейного порядка на произвольном счетно -бесконечном множестве.

68

2. Приведите пример упорядоченного множества ( A, ), для которого множества максимальных и минимальных элементов являются бесконечными.

3. Докажите или опровергните следующее утверждение: всякое отношение линейного порядка представляется диаграммой в виде бесконечной последовательности без первого и последнего элементов либо только с первым элементом либо только с последним элементом.

4. Пусть 1 и 2 являются отношениями порядка. Являют ся ли 1 – 1 и 1 2 отношениями порядка ?

69