Бинарные отношения и их свойства

Важное значение в теории выбора и принятия решений имеет понятие бинарного отношения, позволяющее формализовать операции попарного сравнения альтернатив.

Для любых двух множеств X и Y ( различных или нет) существует единственное множество, состоящее из всех упорядоченных пар (x,y), где xX, yY. Оно обозначается символами XY и называется декартовым произведением (или просто произведением) X и Y. При этом XX обозначается как X².

Бинарным отношением на множестве A называется произвольное подмножество R множества A². Имеем, следовательно, RA², в том числе A²A².

Существует наглядный способ задания бинарных отношений на конечных множествах. Изобразим элементы конечного множества A точками на плоскости. Если задано отношение RA² и (a_i, a_j)R, где a_iA, a_jA , то проведем стрелку от a_i к a_j. Если (a_i, a_i)R, то у точки a_i нарисуем петлю-стрелку, выходящую из a_j и входящую в ту же точку. Получившаяся фигура называется ориентированным графом или просто графом, а сами точки - вершинами графа. Заметим, что вместо (a_i, a_j) R можно писать a_i R a_j.

Дополнение отношения R определяется следующим образом: a₁a₂ означает, что (a₁, a₂)R, т.е. неверно, что a₁ находится в отношении R с a₂ .

Бинарное отношение R на множестве A называется:

полным , если любые два элемента из A связаны отношением R;

рефлексивным, если aRa для всех aA;

симметричным , если a₁Ra₂a₂Ra₁ для всех a₁,a₂ A;

антирефлексивным, если a₁Ra₂a₁a₂;

антисимметричным, если для всех a₁,a₂A из a₁Ra₂, a₂Ra₁ следует a₁ =a₂;

асимметричным, если a₁Ra₂a₂a₁ для всех a₁,a₂A;

транзитивным, если для всех a₁,a₂,a₃A: a₁Ra₂, a₂Ra₃a₁Ra₃;

эквивалентностью, если R транзитивно, рефлексивно и симметрично (если R - эквивалентность и (a₁,a₂)R, то этот факт будем обозначать также a₁~ a₂);

квазипорядком , если R транзитивно и рефлексивно;

строгим порядком, если оно антирефлексивно и транзитивно;

порядком, если R транзитивно и антисимметрично.

В случае, если одновременно , альтернативы a₁ и a₂ называются несравнимыми по бинарному отношению R. Если не существует несравнимых альтернатив, то отношение R называется линейным (не путать со свойством полноты).

Упражнения.

а). Докажите, что если отношение R симметрично и транзитивно, то оно и рефлексивно (следовательно, при определении эквивалентности можно было ограничиться только двумя требованиями);

б). Докажите, что из асимметричности следует антирефлексивность;

в). Подумайте, как приведенные свойства бинарных отношений могут быть представлены (проиллюстрированы ) на языке ориентированных графов.

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

Примерами симметричных отношений служат “быть похожим на”, “быть одинаковым с “, “быть родственником”. В соответствующем графе вместе с каждой стрелкой, идущей из вершины a_i в вершину a_j , существует и противоположно направленная стрелка (следовательно, симметричное отношение естественнее изображать неориентированным графом).

Свойство транзитивности также легко интерпретируется на графе. Именно, если точки a_i и a_j соединены путем, проходимым по направлению стрелок, то существует стрелка, непосредственно идущая из вершины a_i в вершину a_j. Примером транзитивного отношения может служить отношение “больше” на множестве вещественных чисел. Ясно также, что граф антирефлексивного (а значит и асимметричного) отношения не может иметь петель.

Примерами строгого порядка могут служить отношение “ < “ для вещественных чисел и отношение строгого включения “ “ для множеств.

Большинство из приведенных свойств бинарных отношений прямо или косвенно будет использовано в дальнейшем изложении.

Предлагаю ознакомиться с аналогичными статьями: