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

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

Пусть X — произвольное непустое множество и   X². Тогда пару (X; Г)=R, где (X; Г) = (X; X; Г), называют бинарным отношением R на множестве X, а Г_R =Г — графиком отношения R. Если (х; у)  Г_R, то говорят, что элемент x находится в отношении R к элементу у и пишут xRy. Итак, _R = {(x;y)/x, y  X  xRy}.

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

Пример.

1. R = {(1, 2), (2, 1), (2, 3)} – отношение задано перечислением упорядоченных пар;

2. R = {(x, y) x+ y = 7, x, y – действительные числа} – отношение задано указанием свойства x+ y = 7.

Рассмотрим некоторые бинарные отношения.

1. Отношения на множестве натуральных чисел.

а) отношение  выполняется для пар (1, 2), (5, 5), но не выполняется для пары (4, 3);

б) отношение «иметь общий делитель, отличный от единицы» выполняется для пар (3, 6), (7, 42), (21, 15), но не выполняется для пары (3, 28).

2. Отношения на множестве точек действительной плоскости.

а) отношение «находиться на одинаковом расстоянии от точки (0, 0)» выполняется для точек (3, 4) и (–2, 21), но не выполняется для точек (1, 2) и (5, 3);

б) отношение «быть симметричным относительно оси OY» выполняется для всех точек (x, y) и (–x, –y).

3. Отношения на множестве людей.

а) отношение «жить в одном городе»;

б) отношение «учиться в одной группе»;

в) отношение «быть старше».

Свойства бинарных отношений.

Отношение R = (X; Г_R) может обладать рядом свойств. Перечислим некоторые из них.

1. Отношение R называется рефлексивным на множестве X, если для любого x X выполняется xRx: xX/xRx. Из определения следует, что всякий элемент (x, x)  R.

Пример.

а) Пусть X – конечное множество, X = {1, 2, 3} и R = {(1, 1), (1, 2), (2, 2), (3, 1), (3, 3) }. Отношение R рефлексивно.

б) Пусть X – множество действительных чисел и R отношение равенства. Это отношение рефлексивно, т.к. каждое число равно самому себе.

в) Пусть X – множество людей и R отношение "жить в одном городе". Это отношение рефлексивно, т.к. каждый живет в одном городе сам с собой.

2. Отношение R называется антирефлексивным на множестве X, если для любого x X неверно, что выполняется xRx: .

3. Отношение R называется симметричным на множестве X, если для любых x, y  X из xRy следует yRx: x,yX/xRyyRx.

Очевидно, что R симметрично тогда и только тогда, когда R = R^–1.

Пример.

а) Пусть X – конечное множество, X = {1, 2, 3} и R = {(1, 1), (1, 2), (1, 3), (2, 1), (3, 1), (3, 3)}. Отношение R симметрично.

б) Пусть X – множество действительных чисел и R отношение равенства. Это отношение симметрично, т.к. если x равно y, то и y равно x.

в) Пусть X – множество студентов и R отношение "учиться в одной группе". Это отношение симметрично, т.к. если x учится в одной группе с y, то и y учится в одной группе с x.

4. Отношение R называется асимметричным на множестве X, если для любых x, y  X одновременно не выполняется xRy и yRx: x,yX/ .

5. Отношение R называется антисимметричным на множестве X, если для любых x, y  X из того, что одновременно выполняются xRy и yRx следует равенство x и y: x,yX/ .

Из определения антисимметричности следует, что всякий раз, когда пара (x, y) принадлежит одновременно R и R^–1, должно выполняться равенство x = y. Другими словами, R  R^–1 состоит только из пар вида ( x, x).

Пример.

а) Пусть X – конечное множество, X = {1, 2, 3} и  = {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}. Отношение R антисимметрично.

Отношение  = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 3)} не является антисимметричным. Например, (1, 2) , и (2, 1) , но 1 2.

б) Пусть X – множество действительных чисел и R отношение  (меньше или равно). Это отношение антисимметрично, т.к. если x  y, и y  x, то x = y.

6. Отношение R называется транзитивным на множестве X, если для любых x, y, z  X из xRy и yR z следует xR z: x, y, zX / (xRy  yRz)xRz.

Пример.

а) Пусть X – конечное множество, X = {1, 2, 3} и R = {(1, 1), (1, 2), (2, 3), (1, 3)}. Отношение R транзитивно, т. к. наряду с парами (x, y) и (y, z) имеется пара (x, z). Например, наряду с парами (1, 2), и (2, 3) имеется пара (1, 3).

б) Пусть X – множество действительных чисел и R отношение  (меньше или равно). Это отношение транзитивно, т.к. если x y и y z , то x z.

в) Пусть X – множество людей и R отношение "быть старше". Это отношение транзитивно, т.к. если x старше y и y старше z , то x старше z.