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

1. Обратимся теперь к некоторым типам отношений, обладающих свойствами, которые представляют особый интерес.

Рефлексивное отношение – бинарное отношение, обладающее свойством: для любого а выполнено аRa.

Aнтирефлексивное отношение – бинарное отношение, обладающее свойством: для любого а выполнено а a.

Cимметричное отношение – бинарное отношение, обладающее свойством: для любых a, b выполнено aRb  bRa (т.е. из aRb следует bRa).

Антисимметричное отношение – такое бинарное отношение, что для любых выполнено: если a ≠ b, то aRb  b a (т.е. если a и b – в этом порядке(!) – находятся в отношении R, то b и a – нет). Это же свойство выражают иначе: если aRb и bRa, то a = b.

Примеры: 1) отношения равенства рефлексивны и симметричны;

2) отношения между парами чисел «больше», «меньше» – антирефлексивны и антисимметричны;

3) отношение параллельности прямых рефлексивно и симметрично;

4) отношение перпендикулярности прямых антирефлексивно и симметрично;

5) отношение инцидентности точки и прямой симметрично.

Понятие симметрии можно распространить и на отношения большей арности, имея в виду симметрию для отдельных пар в n-наборе. Так, тернарное отношение R(X, Y, Z) симметрично по паре Y, Z, если R(a, b, c) всегда выполняется вместе с R(a, c, b). Например, отношение (X – Y = Z) симметрично по (Y, Z). Действительно, если X – Y = Z, то X – Z = Y, т.е. перестановка Y и Z не изменяет равенства.

2. Транзитивное отношение – бинарное отношение, обладающее свойством: для любых трех элементов a, b, c выполнено: если aRb и bRc, то aRc (если в отношении R находятся a и b, а также b и c, то в этом отношении находятся а и c).

Примеры транзитивности:

1) отношения «больше» и «меньше» (если а > b и b > c, то a > c);

2) отношение параллельности прямых (для прямых l₁, l₂, l₃, если l₁ l₂ и l₂ l₃, то l₁ l₃);

3) отношения равенства чисел;

4) отношения «правее», «левее» между делениями на линейной шкале прибора;

5) отношения «севернее», «южнее» между точками земной поверхности;

6) отношение «быть прямым начальником».

Примеры нетранзитивных отношений:

1) отношение перпендикулярности прямых (для прямых l₁, l₂, l₃, если l₁ l₂ и l₂ l₃, то l₁ не перпендикулярна l₃);

2) известное из истории европейского средневековья отношение между вассалом и сюзере-ном, выражавшееся формулой: «вассал моего вассала – не мой вассал»;

3) отношение между игроками или командами в спортивном турнире: «участник Х выиграл у участника Y»: возможно, что А выиграл у В, В выиграл у С, но А проиграл С;

4) отношения «западнее», «восточнее» между точками земной поверхности: Ярославль (40° восточной долготы) западнее Хабаровска (135° восточной долготы); Хабаровск западнее Торонто (80° западной долготы), но Ярославль восточнее Торонто;

5) отношение «быть непосредственным начальником».

Упражнение. Тернарное отношение примера 5 (в конце п. 4.1) «точки А и В на плоскости находятся по разные стороны от прямой l» превращается в бинарное отношение между двумя точками, если зафиксировать прямую l. Является ли это бинарное отношение транзитивным?

В табл. 4.1 сведены характеристики рассмотренных выше четырех отношений R₁, R₂, R₃, R₄ (пример в п. 4.1).

Таблица 4.1

Для рефлексивного (соответственно, антирефлексивного) отношения все диагональные элементы матрицы равны 1 (соответственно, 0). Матрица симметричного отношения симметрична относительно главной диагонали, т.е. для всех i, j выполнено равенство а_ij = a_ji. Для антисимметричного отношения соответственно выполнено а_ij ≠ a_ji).

Транзитивное замыкание a b бинарного отношения R есть бинарное отношение такое, что элементы a и b находятся в отношении , если существует цепочка c₁, c₂,..., c_k, для которой выполнено aRc₁, c₁Rc₂,..., c_kRb. Например, для отношения «быть сыном» транзитивным замыканием является отношение «быть прямым потомком по мужской линии». Для отношения на множестве квартир дома «иметь общую стену» транзитивное замыкание – это отношение «находиться на одном этаже». Отношение , конечно, транзитивно.

Упражнения. 1. Сравните отношения выражаемые служебными терминами «непосредствен-ный начальник» и «прямой начальник»; например, командир отделения, командир взвода, командир роты и т.д. по отношению к рядовому.

2. Является ли транзитивным бинарное отношение П(X, Y) между реками: «река Х является притоком реки Y»? Сформулируйте, каким географическим термином выражается отношение (X, Y), представляющее транзитивное замыкание бинарного отношения П(X, Y).