Свойства бинарных отношений

Определение 20. Бинарное отношение R на множестве А называется рефлексивным, если для любого a А: (а;a) R (т.е. aRa).

Пример. //, =.

Определение 21. Бинарное отношение R на множестве А называется антирефлексивным, если для любого а А: (a;a) R .

Определение 22.Бинарное отношение R на множестве А называется симметричным, если из (а,b) R (b,a) R, a,b A.

Пример. //,=

Определение 23.Бинарное отношение R на множестве А называется антисимметричным, если из (а,b) R и (b,a) R a=b, a,b A.

Пример. ,=,<,> .

Определение 24.Бинарное отношение R на множестве А называется транзитивным, если из (а,b) R и (b,с) R (а,с) R, a,b,с A.

Пример.//,<,>,=.

Пусть = (a,a)|a A - диагональ декартова квадрата A²=A A.

Лемма 1. Пусть R - бинарное отношение на множестве A. Тогда

1) R рефлексивно R;

2) R антирефлексивно R = .

Доказательство.

1) а) Необходимость. Пусть R рефлексивно. Покажем, что R. Действительно, = (а,а) |а А R (по определению 20) R.

б) Достаточность. Пусть R. Покажем, что R рефлексивно. Пусть а А. Покажем, что (а,а) R. Так как (а,а) R, т.е. (а,а) R по определению 20 R рефлексивно.

2) а) Необходимость. Пусть R антирефлексивно. Покажем, что R = . Допустим, что R (x,y) R (x,y) R и (x,y) x=y, т.е. (x,x) R – противоречие с определением 21 допущение неверно R = .

б) Достаточность. Пусть R = . Покажем, что R антирефлексивно. Для этого достаточно показать, что R удовлетворяет определению 21. Пусть а А. Покажем, что (а,а) R. Пусть (а,а) R (a,a) R = - противоречие (а,а) R. Лемма доказана.

Определение 25. Пусть R – бинарное отношение между множествами A и B.

Множество R^-1 = (m,n) | (n,m) R называется бинарным отношением, обратным бинарному отношению R.

Лемма 2. Пусть R - бинарное отношение на множестве A. Тогда

1) R симметрично R^-1=R;

2) R антисимметрично R R^-1 .

Доказательство. 1) а) Необходимость. Пусть R симметрично. Покажем, что

R^-1=R. Докажем, что R^-1 R . Действительно, R^-1 = (m,n) | (n,m) R

(так как R симметрично) R^-1 R.

Доказательство включения R R^-1 проводится аналогично.

б) Достаточность. Пусть R^-1=R. Покажем, что R симметрично. Пусть (n,m) R. Покажем, что (m,n) R. Так как (n,m) R= R^-1 (m,n) R R симметрично.

2) а) Необходимость. Покажем, что R R^-1 . Пусть (x,y) R R ^-1 (x,y) R ^-1 и (x,y) R (x,y) R и (y,x) R (так как R симметрично) x=y.

б) Достаточность. Пусть R - бинарное отношение на А и R R^-1 . Докажем, что R антисимметрично. Предположим, что это не так. Тогда найдётся хотя бы одна пара (a,b) R такая, что (b,a) R (по определению R^-1) (a,b) R^-1 и (a,b) R^-1. Таким образом, (a,b) R R^-1 a=b, что не соответствует условию предположение неверно. Лемма доказана.

Определение 26. Пусть R, S - бинарные отношения на множестве А.

Множество R^.S={(x,y) | y A: (x,y) S и (y,z) R} называется произведением бинарных отношений R и S.

Лемма 3. Пусть R - бинарное отношение на множестве A. Тогда R транзитивно R^.R R.

Отношение эквивалентности.