Отношения

Подмножество RÍ Mⁿ называется n- местным отношением на множество М. Говорят, что а₁, …., а_n находится в отношении R, если (а₁,…..,а_n)ÎR. Одноместное отношение это просто подмножество М. Такие отношения называют признаками: а обладает признаком R, если аÎR и RÍМ. Свойства одноместных отношений это свойства подмножеств М; поэтому для случая n=1 термин отношение употребляется редко. Примером трехместного отношения является множество троек нападающих в хоккейной команде. Каждый из нападающих находится в этом отношении со всеми теми игроками, с которыми он играет в тройке.

Наиболее часто встречаются и лучше всего изучены двухмерные или бинарные отношения. Записывают, что если а и в находятся в бинарном отношении R ® а R в.

Пример. Отношение на N (где N – множество положительных чисел):

1) отношение £ выполняется для пар (7, 9) и (7, 7), но не выполняется для пар (9, 7).

2) отношение “иметь общий делитель, отличный от единицы” выполняется для пар (6, 9), (4, 2), (2, 4), (4, 4), но не выполняется для пар (7, 9) и (9, 7).

3) Отношение “быть делителем” а R в - а- делитель- в – выполняется для пар (2, 4) и (4, 4), но не выполняется для пар (4, 2) и(7, 9).

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

1) отношение “находиться на одинаковом расстоянии от начала координат” выполняется для пар точек находящихся на одной и той же окружности с центром в начале координат.

2) отношение “находиться на разном расстоянии от начала координат” выполняется для тех и только тех пар точек, для которых не выполняется предыдущее отношение.

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

Пример. Отношения на множестве людей “жить в одном городе”, “быть моложе”, “быть сыном”, “быть знаменитым”.

Пусть дано отношение R и М. Для любого подмножества М₁ Í М естественно определяется отношение R^’, называемое сужением R на М₁, которое получается из R удалением всех пар, содержащих элементы, не принадлежащие множеству М₁. Другими словами, R’=R Ç M₁². Строго говоря, R и R’ - это разные отношения с разными областями определения. Однако, если не возникает разночтений этот педантизм не соблюдается; например, вполне можно говорить “быть делителем” не уточняя, задано оно на N или каком-либо его подмножестве.

Для задания бинарных отношений можно использовать любые способы, задания множеств, например, список пар, для которых данное отношение выполняется. Отношение на конечных множествах обычно задаются списком или матрицей. Матрица, задающая бинарные отношения на множестве M={a₁, ….,a_m} – это квадратная матрица с порядком m, в которой элемент c_ij, стоящий на пересечении i-й строки и j-го столбца определяется следующим образом:

i j

ì 1, если a_i R a_j;

c_ij = í

î 0 – в противном случае.

Например, для конечного множества {1, 2, …,6} матрицы отношений £ , “имеет общий делитель”, “быть делителем” имеют вид:

1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6

1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1

2 0 1 1 1 1 1 2 0 1 0 1 0 1 2 0 1 0 1 0 1

3 0 0 1 1 1 1 3 0 0 1 0 0 1 3 0 0 1 0 0 1

4 0 0 0 1 1 1 4 0 1 0 1 0 1 4 0 0 0 1 0 0

5 0 0 0 0 1 1 5 0 0 0 0 1 0 5 0 0 0 0 1 0

6 0 0 0 0 0 1 6 0 1 1 1 0 1 6 0 0 0 0 0 1

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

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

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