Бинарные отношения - История изменений

СВ: /* Функции */

2026-10-24T09:39:23Z

Функции

← Предыдущая		Версия 09:39, 24 октября 2026
Строка 93:		Строка 93:

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

			[[Файл:p10-01-injection-surjection-bijection.svg\|frame\|none\|900px\|alt=Три схемы отображений: инъекция с лишним элементом Y, сюръекция со слиянием двух стрелок и биекция\|Рис. 1. Инъекция: разные <math>x</math> дают разные <math>y</math>, но один <math>y</math> не задействован. Сюръекция: каждый <math>y</math> имеет прообраз, но два <math>x</math> попадают в один. Биекция: соответствие взаимно однозначное.]]


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

СВ в 09:37, 24 октября 2026

2026-10-24T09:37:41Z

← Предыдущая		Версия 09:37, 24 октября 2026
Строка 10:		Строка 10:

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

			[[Файл:p09-01-relation-arrows.svg\|frame\|none\|600px\|alt=Стрелки 1→2, 1→5, 2→3 и 3→3 между множествами X и Y; области определения и значений подписаны\|Рис. 1. Отношение <math>\rho</math> — это четыре пары, изображённые стрелками. Слева область определения <math>D_\rho=\{1,2,3\}</math>, справа область значений <math>R_\rho=\{2,3,5\}</math>; само отношение лежит в <math>X\times Y</math>.]]

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

СВ в 19:18, 9 октября 2026

2026-10-09T19:18:42Z

← Предыдущая		Версия 19:18, 9 октября 2026
Строка 46:		Строка 46:
	Образом множества $A$ относительно бинарного отношения $\rho$ называется множество		Образом множества $A$ относительно бинарного отношения $\rho$ называется множество
	$\rho(A) = \{y \| \exists x\in X: x\rho y\}$. Прообразом множества $A$ относительно $\rho$ называется $\rho^{-1}(A)$.		$\rho(A) = \{y \| \exists x\in X: x\rho y\}$. Прообразом множества $A$ относительно $\rho$ называется $\rho^{-1}(A)$.

			== Функции ==

			{{Определение
			\|definition=
			Бинарное отношение $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$.

			{{Определение
			\|definition=
			Функцию (отображение) $f$ назовем инъективной функцией (инъекцией), если для любых $x_1,x_2\in X$ и любого $y\in Y$ из $y=f(x_1)$ и $y=f(x_2)$ следует, что $x_1=x_2$.
			}}
			Инъективную функцию еще называют 1-1-функцией.
			{{Определение
			\|definition=
			Функция $f$ называется сюръективной функцией (сюръекцией), если для любого элемента $y\in Y$ существует эле\-мент $x\in X$ такой, что $y=f(x)$.
			}}
			{{Определение
			\|definition=
			Функция $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$ биективна.

			Композиция двух функций есть функция. При этом, если $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$.


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

СВ в 19:13, 9 октября 2026

2026-10-09T19:13:30Z

← Предыдущая		Версия 19:13, 9 октября 2026
Строка 46:		Строка 46:
	Образом множества $A$ относительно бинарного отношения $\rho$ называется множество		Образом множества $A$ относительно бинарного отношения $\rho$ называется множество
	$\rho(A) = \{y \| \exists x\in X: x\rho y\}$. Прообразом множества $A$ относительно $\rho$ называется $\rho^{-1}(A)$.		$\rho(A) = \{y \| \exists x\in X: x\rho y\}$. Прообразом множества $A$ относительно $\rho$ называется $\rho^{-1}(A)$.

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

СВ в 19:03, 9 октября 2026

2026-10-09T19:03:57Z

← Предыдущая		Версия 19:03, 9 октября 2026
Строка 5:		Строка 5:
	}}		}}

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

	Областью значений бинарного отношения $\rho$ называется множество $R_\rho = \{y \| \~~textrm~~{существует такое $x$, что }x\rho y\}$		Областью значений бинарного отношения $\rho$ называется множество <math>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) $\rho = \{(1,2), (2,3), (1,5), (3,3)\}$. Тогда $D_\rho = \{1,2,3\}$, $R_\rho = \{2,3,5\}$.

	2) $\{(x,x) \| x \~~textrm~~{ {{---}} вещественное число}\}$. Тогда $D_\rho = R_\rho = \mathbb{R}$.		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}$.		3) $\{(x,y) \| x,y$ {{---}} целые числа и найдется такое целое число $z$, что $x+z=y\}$. Тогда $D_\rho = R_\rho = \mathbb{Z}$.

СВ: Новая страница: «{{Определение |definition= Бинарным (двуместным) отношением $\rho$ называется множество упорядоч...»

2026-10-09T19:00:27Z

Новая страница: «{{Определение |definition= Бинарным (двуместным) отношением $\rho$ называется множество упорядоч...»

Новая страница

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

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

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

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

2) $\{(x,x) | x \textrm{ {{---}} вещественное число}\}$. Тогда $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$.
{{Замечание
|content=$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)$.