Бинарные отношения

Определение:

Бинарным (двуместным) отношением $\rho$ называется множество упорядоченных пар. Если некоторая пара $(x,y)$ принадлежит отношению $\rho$, наряду с записью $(x,y)\in \rho$ пишут $x\rho y$.

Областью определения бинарного отношения $\rho$ называется множество [math]\displaystyle{ D_\rho = \{x | \text{ существует такое } y, \text{ что } x\rho y\} }[/math].

Областью значений бинарного отношения $\rho$ называется множество [math]\displaystyle{ R_\rho = \{y | \text{существует такое } x, \text{ что } x\rho y\} }[/math]

1) $\rho = \{(1,2), (2,3), (1,5), (3,3)\}$. Тогда $D_\rho = \{1,2,3\}$, $R_\rho = \{2,3,5\}$.

2) $\{(x,x) | x \text{ — вещественное число}\}$. Тогда $D_\rho = R_\rho = \mathbb{R}$.

3) $\{(x,y) | x,y$ — целые числа и найдется такое целое число $z$, что $x+z=y\}$. Тогда $D_\rho = R_\rho = \mathbb{Z}$.

Каждое бинарное отношение является подмножеством прямого произведения множеств $X$ и $Y$ таких, что $D_\rho\subseteq X$ и $R_\rho\subseteq Y$. Говорят, что $\rho$ — бинарное отношение на множестве $X$, если $\rho\subseteq X\times X$. Для произвольного бинарного отношения $\rho$ можно сказать, что оно явяется отношением на множестве $X = D_\rho \cup R_\rho$.

Замечание

$n$-арным отношением называют множество упорядоченных $n$-ок. То есть, $n$-арное отношение — это подмножество прямого произведения некоторых $n$ множеств.

Любое подмножество множества $X$ можно назвать унарным отношением на множестве $X$.

Тождественным отношением на множестве $X$ называется $e_X = \{(x,x) | x\in X\}$.

Универсальным отношением на множестве $X$ называется $U_X = X\times X$.

Дополнение бинарного отношения, как и для множеств, определяется как разность универсального и данного множеств. То есть, если $\rho$ — бинарное отношение на множестве $X$, то $\overline\rho = U_X \setminus \rho$.

Обратным отношением для отношения $\rho$ называют отношение $\rho^{-1}=\{(x,y) | (y,x)\in\rho\}$.

Композицией отношений $\rho_1$ и $\rho_2$ называется отношение $\rho_2 \circ \rho_1 = \{(x,z) | \textrm{существует такое $y$, что $x\rho_1 y$ и $y\rho_2 z$}\}.$

Для любых бинарных отношений $\rho$, $\rho_1$, $\rho_2$ выполняются следующие свойства:

1. $(\rho^{-1})^{-1} = \rho$;

2. $(\rho_2\circ\rho_1)^{-1} = \rho_1^{-1}\circ \rho_2^{-1}$

Пункт 1 непосредственно следует из определения обратного отношения. Покажем истинность пункта 2: $(\rho_2 \circ \rho_1)^{-1} = \{(z,x) | \exists y: x\rho_1 y, y\rho_2 z\} = \{(z,x) | \exists y: y\rho_1^{-1} x, z\rho_2^{-1} y\} = \rho_1^{-1}\circ \rho_2^{-1}$

Образом множества $A$ относительно бинарного отношения $\rho$ называется множество $\rho(A) = \{y | \exists x\in X: x\rho y\}$. Прообразом множества $A$ относительно $\rho$ называется $\rho^{-1}(A)$.

Конспект: Дискретная математика