Бинарные отношения на множестве

Отношение А А называется отношением на A. Такие отношения называются также бинарными отношениями на множестве A. То есть отношение на A - это отношение между элементами одного и того же множества A.

Для таких отношений можно выделить несколько специальных свойств.

1. Рефлексивность

Отношение А А является рефлексивным, если
.

Простейшее рефлексивное отношение на A - это множество, состоящее из всех пар вида (a, a), где a A. Такое отношение называется единичным отношением или диагональю и обозначается как e.

2. Симметричность

Отношение А А - является симметричным, если
" a, bÎ A (ar bÞ br a).

То есть отношение А А симметрично, если для любых a и b из того что (a, b) следует, что пара (b, a) .

Поэтому отношение r несимметрично, если хотя бы для одной пары (a, b) не выполняется указанное свойство. Нетрудно видеть, условие симметричности равносильно условию:

" a, bÎ A (ar bÛ br a).

3. Антисимметричность

Отношение А А- антисимметричное, если

"a,bÎ A(ar b & br a Þa= b).

То есть отношение А А является антисимметричным, если из (a, b) и (b, a) следует, что a = b.

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

4. Транзитивность

Отношение А А- транзитивное, если

"a, b, cÎ A(ar b & br c Þar c).

Отношение А А является транзитивным если из (a, b) r и
(b, c) r следует, что (a, c) r. Содержательно транзитивность состоит в том, что если осуществляется последовательный многократный переход между элементами множества A, по связям отношения r, то между первым и последним элементами такого перехода также выполняется отношение r.

Упражнение. Доказать следующие свойства отношений:

1) - рефлексивное e Í r;

2) r - симметричное r = r^-1;

3) r - антисимметричное r Ç r^-1Í e;

4) r - транзитивное r r Í r.

Упражнение. Является ли транзитивным бинарное отношение, на множестве {a, b, c, d, e, f} заданное диаграммой:

a d

b e

c f

Рассмотрим несколько примеров отношений на множестве.

Пусть A - это множество всех людей.

Отношение r = "дружить". Для этого отношения справедливость условия (a, b) r означает, что a дружит с b. Это отношение симметричное, но оно нетранзитивное и нерефлексивное.

Отношение "любить" - несимметричное и нетранзитивное, но, по-видимому, рефлексивное.

Отношение "быть родственником" - рефлексивное, симметричное и транзитивное.

Отношение "руководить" - антисимметричное, транзитивное и нерефлексивное.

Если А А - некоторое отношение, то рефлексивным, симметричным, транзитивным замыканиями этого отношения называются минимальные отношения на А, которые содержат r и являются соответственно рефлексивными, симметричными и транзитивными.

ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ

ОПРЕДЕЛЕНИЕ

Всякое рефлексивное, симметричное и транзитивное отношение А А, называется отношением эквивалентности.

Если r - отношение эквивалентности и a r b, то элементы a и b называются эквивалентными в этом отношении или просто эквивалентными.

Рассмотренное ранее отношение "быть родственником" является отношением эквивалентности. Аналогично, отношением эквивалентности на множестве всех людей является отношение "быть однофамильцем". Это отношение связывает между собой людей с одинаковыми фамилиями, распределяя их по классам людей, каждый из которых состоит из всех людей, имеющих одну и ту же фамилию.

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

ОПРЕДЕЛЕНИЕ

Разбиением множества A называется конечное или бесконечное семейство множеств A_i, i Î I таких, что:

1)"iÎI(A_i ¹ );

2) "i,jÎI(i j Þ A_i Ç A_j = );

3) A_i = A .

Здесь I это множество значений нижнего индекса множеств разбиения. В разбиениях счетных множеств в качестве множества индексов I обычно применяется все или часть множества натуральных чисел.

Пусть A₁, ... , A_k, . . . - разбиение множества A. Нетрудно проверить, что отношение r на множестве A, определяемое соотношением: ar b , является отношением эквивалентности.

Следующая теорема показывает, что справедливо и обратное свойство.

ТЕОРЕМА 3.2

Всякое отношение эквивалентности на множестве A разбивает это множество на классы эквивалентных элементов.

Доказательство

Разобьем доказательство теоремы на несколько этапов.

1. Построение разбиения, порождаемого отношением r.

Пусть r - отношение эквивалентности на множестве A.

Для каждого x A обозначим как [x] множество {y½xry}. Поскольку отношение r рефлексивно, то x Î [x], а, значит, каждое множество [x] является непустым и система множеств [x], где x Î A, содержит все элементы A. Из семейства множеств {[x]| x ÎA } удалим кратные вхождения одинаковых множеств. В результате получим семейство непустых несовпадающих множеств R, в которых содержатся все элементы A.

2. Обоснование того, что R образует разбиение.

Пусть [x] и [y] - произвольные классы из семейства R. Покажем, что они либо не пересекаются, либо совпадают, т.е. возможны только два случая:

1) [x] Ç [y] = ;

2) [x] Ç [y] .

Предположим, что это свойство является неверным. То есть для некоторых двух элементов x и y множества [x] и [y] пересекаются, но не совпадают (рис 3.1).

[x] [y]

x z y

ab

Рис.3.1

Здесь z - это элемент, общий для классов [x] и [y], аa и b - произвольные элементы в [x] и [y] соответственно.

1. Докажем, что [x] [y]. Пусть x r a. Покажем, что
справедливо отношение y r a:

a) поскольку x r z, то из симметричности r следует, что
z r x;

b) поскольку z r x и x r a, то из транзитивности r вытекает, что z r a;

c) из y r z и z r a и транзитивности r имеем y r a. Поэтому aÎ[y], а, значит, [x] [y].

2. Обратное включение [y] [x] может быть доказано, если повторить проведенные рассуждения, поменяв в них местами x и y, а также aи b.

Следовательно, справедливо равенство множеств [x] и [y]. Последнее противоречит предположению о том, что эти множества являются разными.

Это означает, система множеств R образует разбиение множества разбиение A.

3. Обоснование того, что R разбивает A на классы эквивалентных элементов.

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

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

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

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

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

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

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

ОПРЕДЕЛЕНИЕ

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

Отношение порядка на некотором множестве А можно интерпретировать как отношение старшинства или подчиненности между элементами 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, если " bÎ A(ar b) (" aÎ A(br 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((bra) Ú (arb)).

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

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

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

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

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

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

3. Индуктивный переход. Пусть A = {a₁, . . . , 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.

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

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

Упражнение.

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

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

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

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