Бинарные отношения
Областью определения бинарного отношения $\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$.
Любое подмножество множества $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)$.
Функции
Две функции равны, если они состоят из одних и тех же элементов (как и любые множества).
Иногда приходится сталкиваться с трудностями в определении области значений функций. Тогда, если $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$.
Инъективную функцию еще называют 1-1-функцией.
Если указана биективная функция $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$ биективна.
Композиция двух функций есть функция. При этом, если $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$.
Конспект: Дискретная математика