ставляя полученные включения AA µ AB µ BB, заключаем:

A2 µ B2. Продолжая подобные действия, для любой степени

k k b b

k получим A µ B и, следовательно, A µ B. £ Приведем без доказательства очевидное свойство:

b

b b

Теорема 2.14 A = A.

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

Пусть заданы конечное множество M мощности jMj = n и отношения A; B; C µ M £M. Через ¢ обозначено, как обычно, диагональное (единичное) отношение.

Определение. Отношение A называется рефлексивным, если

¢µ A : 8x 2 M [xAx].

Крефлексивным относятся отношения типа 6; >, “быть похожим на”, “быть равным”, т.е. ¢ – также рефлексивное отношение.

Матрица, представляющая рефлексивное отношение, имеет все единицы на главной диагонали. В графе, представляющем рефлексивное отношение, при каждой вершине имеется петля.

Определение. Отношение A называется антирефлексивным, если

¢ \ A = ? : 8x; y 2 M[xAy ) x =6 y] или 8x[:xAx] .

К антирефлексивным относятся отношения типа <, >, "быть моложе”, “быть предком”, "быть потомком”.

Главная диагональ матрицы, представляющей антирефлексивное отношение, содержит только нули, а в соответствующем графе отсутствуют петли.

Определение. Отношение A называется симметричным, если

A µ A¡1 : 8x; y 2 M[xAy ) yAx].

Симметричные отношения – это отношения типа =, “быть одинаковым с”, “быть похожим на”, “быть родственником с”.

Элементы матрицы, представляющей симметричное отношение, расположенные симметрично относительно главной диагонали, равны между собой: aij = aji. В соответствующем графе, если существует дуга, идущая из из вершины x в вершину y, то существует и дуга, идущая из y в x. Часто граф симметричного отношения изображают как неориентированный – пара симметричных дуг заменяется звеном.

Определение. Отношение A называется антисимметричным, если

A \ A¡1 µ ¢; т.е. xAy и yAx выполняются одновременно только тогда, когда x = y :

(8x; y 2 M [xAy ^ xA¡1y ) x = y]).

Примерами антисимметричных отношений могут служить 6, >. Для элементов матрицы, представляющей антисимметричное отношение, aijaji = 0, если i =6 j. В соответствующем графе любую пару вершин соединяет не более одной дуги, но могут быть и петли.

Определение. Отношение A называется асимметричным, если

A \ A¡1 = ?; т.е. из двух соотношений xAy, xA¡1y (yAx) по крайней мере одно не выполняется.

Примерами асимметричных отношений могут служить <, >. В матрице, представляющей асимметричное отношение,

aijaji = 0, т.е. если элемент aij = 1, то aji = 0, но возможно aij = aji = 0. В соответствующем графе любую пару вершин

соединяет не более одной дуги, петли отсутствуют.

Определение. Отношение A называется транзитивным, если

A2 µ A , т.е. если выполнены соотношения xAz и zAy, выполнится и xAy :

(8x; y; z 2 M [xAz ^ zAy ) xAy):

Из определения по индукции следует такое свойство: если выполнены соотношения xAz1; z1Az2; : : : ; zn¡1Ay, выполнится и xAy. На графе, представляющем транзитивное отношение, любая ориентированная цепочка из x в y замыкается дугой

(x; y). Примеры транзитивного отношения: “быть предком”, отношения <, > на числовой оси и т.д.

Определение. Отношение A называется антитранзитивным, если

A \ Ak = ? при всех k > 1,

т.е. если выполнена цепочка соотношений x = z0Az1 ^ z1Az2 ^ ¢ ¢ ¢ ^ zk¡1Azk = y,

то xAy невозможно, и наоборот, если выполнено соотноше-

ние xAy, то цепочка x = z0Az1 ^ z1Az2 ^ ¢ ¢ ¢ ^ zn¡1Azk = y невозможна.

Пример: отношение непосредственного следования.

Теорема 2.15 Отношение A симметрично тогда и только тогда, когда

A= A¡1:

До к а з а т е л ь с т в о . 1. °) По определению симметричного отношения A µ A¡1.

2.°( Используя теорему (2.10) (A µ B ) A¡1 µ B¡1),

для включения A µ A¡1 получим A¡1 µ (A¡1)¡1 = A (последнее включение следует из теоремы 2.9). £

Теорема 2.16 Если отношение A асимметрично, то оно антирефлексивно.

Д о к а з а т е л ь с т в о (от противного). Предположим, что 9x[xAx]; тогда выполнится и xA¡1x, а это значит, что A\A¡1 =6 ?, что противоречит определению асимметричности. £

Теорема 2.17 Если отношение A транзитивно, то

b

A = A:

2. °(