§ 6. Отношения и их свойства

Подмножество RMⁿ называется n-местным отношением на множестве М. Говорят, что a₁,a₂,...,a_n находятся в отношении R, если (a₁,a₂,...,a_n)R.

Одноместное отношение - это просто подмножество множества М. Такие отношения называют признаками: а обладает признаком R, если аR и RM. Вообще, для случая n=1 термин “отношение” употребляется редко.

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

Наиболее часто встречающимися и хорошо изученными являются двухместные (или бинарные) отношения. Именно о них пойдет речь в дальнейшем, поэтому слово “бинарные” будем опускать.

Если a, b находятся в отношении R, это часто записывается как aRb.

Примеры 1.3.

1. Пусть M = {3,8,24}.

Тогда M² = {(3,3), (3,8), (3,24), (8,3), (8,8), (8,24), (24,3), (24,8), (24,24)}.

а). Отношение “<“, т.е. a<b, на множестве М: R₁ = {(3,8), (3,24), (8,24)}.

б). Отношение “быть делителем”, т.е. a - делитель b, на множестве М:

R₂ = {(3,3), (3,24), (8,8), (8,24), (24,24)}.

2. Пусть M²- множество точек действительной плоскости.

а). Отношение “находиться на одинаковом расстоянии от начала координат” выполняется, например, для пары точек (3,4) и (0,5), но не выполняется для пары точек (3,4) и (1,-6).

б). Отношение “быть симметричными относительно оси (ОХ)” выполняется для всех пар точек (x₁,y₁) и (x₂,y₂), удовлетворяющих условию: x₁=x₂; y₁=-y₂.

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

а). “жить в одном городе”;

б). “быть дочерью”;

в). “быть старше” .

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

Матрица бинарного отношения на множестве M={a₁,a₂,...,a_n} - это квадратная матрица C_nn, в которой элемент c_ij, стоящий на пересечении i-й строки и j-го столбца, равен единице, если a_iRa_j, и нулю в противном случае.

В табл. 1.1 и 1.2 приведены соответственно матрицы отношений 1,а и 1,б примера 1.3.

Таблица 1.1 Таблица 1.2

	3	8	24			3	8	24
3	0	1	1		3	1	0	1
8	0	0	1		8	0	1	1
24	0	0	0		24	0	0	1

Для каждого множества М отношение Е, заданное единичной матрицей, в которой на главной диагонали стоят единицы, а в остальных местах - нули, называется отношением равенства на М.

Поскольку отношения являются множествами, для них можно определить те же операции, что и над множествами.

Определим ещё одну операцию над отношениями. Отношение R^-1 называется обратным к отношению R, если a_jR^-1a_i тогда и только тогда, когда a_iRa_j. Из определения непосредственно следует, что (R^-1)^-1=R.

Пример. Для отношения ““ обратным является отношение ““.

Свойства отношений

Отношение R называется рефлексивным, если для любого аМ имеет место аRа. Главная диагональ матрицы такого отношения содержит только единицы.

Примеры. В примере 1.3 рефлексивными являются отношения 1, б; 2, а; 3, а.

Отношение R называется симметричным, если для любой пары (а,b)M² из аRb следует bRa (иначе говоря, для любой пары отношение R выполняется либо в обе стороны, либо не выполняется вообще). Матрица этого отношения симметрична относительно главной диагонали: c_ij=c_ji для любых i и j.

Примеры. В примере 1.3 симметричными являются отношения 2, а; 2, б; 3, а.

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

Отношение R называется антисимметричным, если из аRb и bRa следует, что a=b.

Пример. В примере 1.3 антисиметричным является отношение 1, б.

Рассмотрим отношение R_S, которое является симметричным и антисимметричным одновременно. В силу его симметричности если выполняется аR_Sb,то выполняется и bR_Sa. Но из аR_Sb и bR_Sa следует, что a=b (в силу антисимметричности этого отношения). Значит, матрица отношения R_S может содержать единицы только на главной диагонали. Примером такого отношения является отношение равенства Е.

Отношение R называется транзитивным, если для любых аМ, bМ, cМ из аRb и bRc следует аRc.

Примеры.

1. В примере 1.3 транзитивными являются отношения 1, а; 1, б; 2, а; 3, а; 3, в.

2. Симметричное и антисимметричное одновременно отношение R_S транзитивно.

Для каждого отношения R отношение, называемое транзитивным замыканием R, определяется следующим образом: ab, если в М существует цепочка из n элементов

a=a₁,a₂,...,a_n-1,a_n=b, в которой между соседними элементами выполнено отношение R, т.е.

aRa₂, a₂Ra₃,...,a_n-1Rb.

Примеры.

1. Транзитивным замыканием отношения “быть дочерью” служит отношение “быть прямым потомком”, являющееся объединением отношений “быть дочерью”, “быть внучкой”, “быть правнучкой” и т.д.

2. Транзитивным замыканием отношения “иметь общую стену” для жильцов дома является отношение “жить на одном этаже”.

Теорема 1.8. Отношение R транзитивно тогда и только тогда, когда оно совпадает со своим транзитивным замыканием: R =.

 Необходимость. Любое отношение, в том числе и не транзитивное, можно рассматривать как частный случай его транзитивного замыкания, когда длина цепочки n=2. Следовательно, всегда R .

С другой стороны, так как R транзитивно, из aRa₂, a₂Ra₃,...,a_n-1Rb следует aRb, т.е. если ab, то aRb. Значит, для транзитивного отношения выполняется  R.

Из этих двух включений следует R =.

Достаточность. По определению транзитивного замыкания и так как по условию R=, из aRb следует существование цепочки aRa₂, a₂Ra₃,...,a_n-1Rb, аналогично bRс означает наличие цепочки bRb₂, b₂Rb₃,...,b_m-1Rc. Значит, существует цепочка

aRa₂, a₂Ra₃,...,a_n-1Rb, bRb₂, b₂Rb₃,...,b_m-1Rc.

Тогда, по определению транзитивного замыкания, aс или, по условию R =, aRс. Таким образом, из aRb, bRс следует aRс, а это и доказывает транзитивность отношения R. 