Главная | Обратная связь

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

Отношение 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} и r = {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}. Отношение R антисимметрично.

Отношение s = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 3)} не является антисимметричным. Например, (1, 2) Îs, и (2, 1) Îs, но 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.