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

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

Бинарным (двуместным) отношением $\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\}$.

Рис. 1. Отношение [math]\displaystyle{ \rho }[/math] — это четыре пары, изображённые стрелками. Слева область определения [math]\displaystyle{ D_\rho=\{1,2,3\} }[/math], справа область значений [math]\displaystyle{ R_\rho=\{2,3,5\} }[/math]; само отношение лежит в [math]\displaystyle{ X\times Y }[/math].

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)$.

Функции

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

Бинарное отношение $f$ называется функцией, если из $(x,y)\in f$ и $(x,z)\in f$ следует, что $y=z$.

Две функции равны, если они состоят из одних и тех же элементов (как и любые множества).

Иногда приходится сталкиваться с трудностями в определении области значений функций. Тогда, если $D_f = X$ и $R_f\subseteq Y$, то говорят, что функция $f$ задана на множестве $X$ со значениями в множестве $Y$ (осуществляет отображение множества $X$ в множество $Y$), и пишут $f: X\rightarrow Y$.

Если $f$ — функция, вместо $(x,y)\in f$ пишут $f(x)=y$ и говорят, что $y$ — значение, соответствующее аргументу $x$ (образ элемента $x$). $x$ называют прообразом элемента $y$.

1) $\{(1,2),(2,3), (48,\star), (\square, \bigtriangleup)\}$ — функция;

2) $\{(1,2), (1,3), (2,4)\}$ — не функция;

3) $\rho=\{(x, x^2+2x+1) | x \textrm{ — вещественное число}\}$ — функция. % $y=x^2+2x+1$. Обратное бинарное отношение $\rho^{-1}$ в этом случае функцией не является.

Пусть, $f: X\rightarrow Y$.

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

Функцию (отображение) $f$ назовем инъективной функцией (инъекцией), если для любых $x_1,x_2\in X$ и любого $y\in Y$ из $y=f(x_1)$ и $y=f(x_2)$ следует, что $x_1=x_2$.

Инъективную функцию еще называют 1-1-функцией.

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

Функция $f$ называется сюръективной функцией (сюръекцией), если для любого элемента $y\in Y$ существует эле\-мент $x\in X$ такой, что $y=f(x)$.

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

Функция $f$ называется биективной функцией (биекцией), если она и сюръективна, и инъективна.

Если указана биективная функция $f: X\rightarrow Y$, говорят, что осуществляется взаимно-однозначное соответствие между множествами $X$ и $Y$.

Рассмотрим функции $f: \mathbb{R}\rightarrow \mathbb{R}$.

1) $f(x)=e^x$ инъективна, но не сюръективна;

2) $f(x)=x^3-x$ сюръективна, но не инъективна;

3) $f(x) = 2x+1$ биективна.

Рис. 1. Инъекция: разные [math]\displaystyle{ x }[/math] дают разные [math]\displaystyle{ y }[/math], но один [math]\displaystyle{ y }[/math] не задействован. Сюръекция: каждый [math]\displaystyle{ y }[/math] имеет прообраз, но два [math]\displaystyle{ x }[/math] попадают в один. Биекция: соответствие взаимно однозначное.

Композиция двух функций есть функция. При этом, если $f: X\rightarrow Y$ и $g: Y\rightarrow Z$, то $g\circ f: X\rightarrow Z$.

Пусть, $(x, z_1)\in g\circ f$ и $(x, z_2)\in g\circ f$. Тогда существуют $y_1$ и $y_2$: $z_1 = g(y_1)$ и $z_2 = g(y_2)$. При этом $y_1 = f(x)$ и $y_2 = f(x)$. Поскольку $f$ — функция, то $y_1 = y_2$. Поскольку $g$ — функция, то $z_1 = g(y_1) = g(y_2) = z_2$. Таким образом, $g\circ f$ — функция.

Покажем, что $g\circ f: X\rightarrow Z$. Так как $f: X\rightarrow Y$, для любого $x\in X$ существует $y\in R_f\subseteq Y$: $f(x)=y$. Так как $g: Y\rightarrow Z$, существует $z\in R_g\subseteq Z$: $z=g(y) = g(f(x)) = (g\circ f)(x)$. Таким образом, для любого $x\in X$ мы нашли такой $z\in Z$, что $(x,z)\in g\circ f$. Следовательно, $D_{g\circ f}=X$.

С другой стороны, $R_{g\circ f}\subseteq R_g\subseteq Z$, что и требовалось доказать.

Композиция двух биективных функций есть биективная функция.

Пусть, $f: X\rightarrow Y$ и $g: Y\rightarrow Z$ — биекции. Пусть, для некоторых $x_1,x_2\in X$ и $z\in Z$ верно $z = g\circ f (x_1)$ и $z = g\circ f(x_2)$. Пусть, $y_1, y_2\in Y$ те элементы, для которых $y_1 = f(x_1)$ и $y_2 = f(x_2)$. Тогда, $z = g(y_1) = g(y_2)$. Поскольку $g$ инъективна, $y_1 = y_2$ и, поскольку $f$ инъективна, $x_1=x_2$. Следовательно, $g\circ f$ — инъективна.

Пусть, $z\in Z$. Тогда, поскольку $g$ сюръективна, существует $y\in Y$: $g(y) = z$. Поскольку $f$ сюръективна, существует $x\in X$: $f(x) = y$. Следовательно, $g\circ f(x) = z$ и $g\circ f$ сюръективна. Таким образом, $g\circ f$ — биекция.

Пусть, $f^{-1}$ — отношение, обратное к $f$. Если $f^{-1}$ осуществляет отображение множества $Y$ в множество $X$, говорят, что $f^{-1}$ — обратное отображение.

Отображение $f: X\rightarrow Y$ имеет обратное отображение $f^{-1}: Y\rightarrow X$ тогда и только тогда, когда $f$ — биекция. При этом $f^{-1}$ тоже будет биекцией.

Достаточность. Пусть, $(y, x_1)\in f^{-1}$ и $(y,x_2)\in f^{-1}$. Тогда, $f(x_1) = f(x_2) = y$. Из инъективности функции $f$ следует, что $x_1=x_2$ и, следовательно, $f^{-1}$ — функция.

Из сюръективности функции $f$ следует, что для любого $y\in Y$ существует $x\in X$: $f(x) = y$. Другими словами, для любого $y\in Y$ существует $x\in X$: $f^{-1}(y) = x$. Следовательно, $D_{f^{-1}} = Y$ и $f^{-1}$ осуществляет отображение из $Y$ в $X$.

Покажем, что $f^{-1}$ — биекция. Поскольку $f$ определена на всем множестве $X$, $f^{-1}$ — сюръекция. Пусть, существуют такие $y_1, y_2\in Y$ и $x\in X$, что $x=f^{-1}(y_1) = f^{-1}(y_2)$. Тогда, $(x,y_1)\in f$ и $(x, y_2)\in f$ и, поскольку $f$ функция, $y_1 = y_2$. Следовательно, $f^{-1}$ — инъекция.

Необходимость доказывается из тех же соображений, рассмотренных в обратном порядке: если $f^{-1}$ функция, то $f$ — инъективна; если $f^{-1}$ осуществляет отображение из $Y$ в $X$, $f$ — сюръективна.

Замечание. Из доказательства видно, что чтобы обратное отношение $f^{-1}$ было функцией, необходимо и достаточно, чтобы функция $f$ была инъективна.

Тождественным отображением множества $X$ на себя называется отображение $e_X: X\rightarrow X$ такое, что для любого $x\in X$ верно $e_X(x)=x$. Если $f: X\rightarrow Y$, тогда верно, что $e_Y\circ f = f$ и $f\circ e_X = f$.

Если $f: X\rightarrow Y$ — биекция, то

1) $(f^{-1}\circ f) = e_X$;

2) $(f\circ f^{-1}) = e_Y$.

Для любого $x\in X$, $(f^{-1}\circ f)(x) = f^{-1}(f(x)) = x$. Для любого $y\in Y$, $(f\circ f^{-1})(y) = f(f^{-1}(y)) = y$.

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