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

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

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

ОПРЕДЕЛЕНИЕ

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

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

К примеру, в случае если A — множество сотрудников некоего учреждения, то отношение руководить есть отношением порядка на этом множестве. Другими словами, в случае если обозначить данное отношение как r, то соотношение ar 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 в том и лишь в том случае, в то время, когда выполняется условие: ar bи не существует для того чтобы элемента c, хорошего отaиb, что ar c и cr b. Помимо этого, финиши всякой дуги соединяют лишь пары различных вершин.

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

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

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

Упражнение.

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

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

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

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

ОПРЕДЕЛЕНИЕ

Элемент a именуется громаднейшим (мельчайшим) в отношении r, в случае если bI A(ar b) ( aI A(br a)).

Ясно, что всякое упорядоченное множество имеет не более одного громаднейшего (мельчайшего) элемента. К примеру, в случае если A — это множество вероятных обстановок либо вариантов, из которых требуется выбрать оптимальный, и r — отношение предпочтения одних вариантов перед вторыми, воображающее собой отношение порядка, то громаднейший и мельчайший элементы упорядоченного множества (A, r) воображают соответственно наилучший и нехороший варианты.

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

a b

cd

E f g

Рис. 3.2.

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

ОПРЕДЕЛЕНИЕ

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

bI A(b¹a ? (b, a)Ir) ( bIA(b¹a ? (a, b)Ir)).

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

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

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

a,bI A((bra) U (arb)).

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

Следующая теорема характеризует неспециализированный вид диаграмм для взаимоотношений линейного порядка.

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

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

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

2. Индуктивное предположение. Пускай для каждого множества A содержащего не более чем n элементов выполнено утверждение теоремы.

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

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

a I A $bI A (b r a) U $ a I A $bI A ((a, b)I r (b, a)I r). (1)

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

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

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

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

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

Почва НЕ ШАР! Не так долго осталось ждать ДОКАЗАТЕЛЬСТВА!


Также читать:

Понравилась статья? Поделиться с друзьями: