Связи между свойствами отношений

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

Доказательство. Пусть R слабо полно и x ¹ y. Рассмотрим три случая.

1) (x, y)ÎR.Тогда, по определению обратного отношения (y, x)ÎR^-1, а по определению двойственного отношения – (y, x)ÏR^d.

2) (y, x)ÎR, тогда (x, y)ÎR^–1 и, следовательно, (x,y)Ï`R^–1 = R^d.

3) (x, y)ÎR и одновременно (y, x)ÎR. Отсюда, (y, х)ÏR^d и (x, y)Ï R^d.

Так как R – слабо полное отношение, то для любых x ¹ y выполняется либо случай а), либо б), либо в). Ни в одном из этих случаев включения (x, y)ÎR^d и (y, x)ÎR^d не могут выполняться одновременно. Следовательно, отношение R^d антисимметрично.

Докажем, обратное, что из антисимметричности R^d следует слабая полнота отношения R. Рассмотрим эквивалентное определение антисимметричности. Если x ¹ y, то либо (x, y)ÎR^d и (y, x)Ï R^d, либо (x, y)ÏR^d и (y, x)ÎR^d, либо (x, y)ÏR^d и (y, x)ÏR^d. В первом случае получим, что (x, y)ÎR, во втором – (y, x)ÎR, в третьем – (x, y)ÎR и (y, x)ÎR. Это утверждение означает, что отношение R слабо полно.

2. Отношение R асимметрично тогда и только тогда, когда R^d полно.

Доказательство. Пусть R – асимметрично. Тогда по определению, RÇ R^–1 = Æ. Рассмотрим два случая.

1) (x, y)ÎR. Тогда (х, y)ÏR^–1, значит, (x, y)ÎR^d.

2) (x, y)ÏR. Тогда (x, y)Î`R и (y, x) Î`R^–1 = R^d.

В любом случае либо (x, y)ÎR^d, либо (y, x)ÎR^d, а это означает, что R^d полно.

Докажем обратное следствие. Пусть R^d полно. Снова рассмотрим два случая:

а) (x, y)ÎR^d, тогда (y, x)ÏR;

б) (y, x)ÎR^d, тогда (x, y)ÏR.

Так как R^d полно, то либо случай а), либо случай б) всегда будет иметь место, а отсюда следует невозможность одновременного выполнения yRx и xRy. Это означает, что R асимметрично.

Задание 1. Доказать, что асимметричное отношение антирефлексивно.

Задание 2. Доказать, что ацикличное отношение асимметрично.

Задание 3. Доказать, что если отношение антирефлексивно и транзитивно, то оно ациклично.

Тема 5. Специальные бинарные отношения.