Виды бинарных отношений

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

Пример. «=»на множестве ℝ.

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

Пример. «<»на множестве ℝ.

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

Пример. «∥» на множестве всех прямых в пространстве, «=» на множестве ℝ.

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

Пример. Отношения ,=,<,> на множестве ℝ.

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

Пример. «∥» на множестве всех прямых в пространстве, отношения ,=,<,> на множестве ℝ

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

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

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

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

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

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

1) а) Необходимость. Пусть R рефлексивно. Покажем, что R. Действительно, = (а,а) |а А R по определению 20, т.к. ∀ a А: (а;a) R 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 симметрично, то, по определению 22, из (n,m) R следует (m,n) R
R^-1 R.

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

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

2) а) Необходимость. Пусть R антисимметрично. Покажем, что 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 и a ≠ b (по определению R^-1) (a,b) R и (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.