Отношение

Бинарным отношением между множествами $A$ и $B$ называется любое подмножество $\rho$ декартова произведения $A \times B$ .

Если $A$ = $B$ $\rho \subset {A^2}$ , тогда $\rho$ бинарное отношение на множестве $A$ .

Часто, чтобы обозначить принадлежность упорядоченной пары $({a,b})$ к бинарному отношению $\rho$ вместо $\left( {a,b} \right) \in \rho$ используют обозначения $\rho ({a,b})$ или $a\rho b$ . При этом говорят, что $a$ находится в отношении $\rho$ к $b$ .

$\left( {a,b} \right) \in \rho \Leftrightarrow a\rho b$

Аналогно, $\left( {a,b} \right) \notin \Leftrightarrow \neg \left( {a\rho b} \right)$

Свойства бинарного отношения $\rho$ на множестве $A$

$R$ (рефлексивность) $\Leftrightarrow$ $(\forall a \in А)(a \rho a)$
$AR$ (анитрефлексивность) $\Leftrightarrow$ $(\forall a \in А) \neg (a \rho a)$
$S$ (симметричность) $\Leftrightarrow$ ${\text{(}}\forall a,b \in A){\text{ }}a\rho a \Rightarrow b\rho a$
$AS$ (асимметричность) $\Leftrightarrow$ ${\text{(}}\forall a,b \in A){\text{ (}}a\rho b \wedge b\rho a) \Rightarrow a = b$
$Т$ (транзитивность) $\Leftrightarrow$ ${\text{(}}\forall a,b,c \in A){\text{ }}(a\rho b \wedge b\rho c) \Rightarrow {\text{ }}a\rho c$

Виды отношений

Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности
Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка
Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка

Класс эквивалентности

Классом эквивалентности, порождённым элементом $a$ , называется множество: $\left\{ {x\backslash x \in A \wedge x\rho a} \right\}.$

Фактор-множество — множество всех классов эквивалентности заданного множества $А$ по заданному отношению $\rho$ .

Отношение порядка на множестве $А$ называется отношением линейного порядка или линейным порядком на $А$ , если $a\rho b \vee a = b \vee b\rho a$ , для $a$ и $b \in A$ .

Упорядоченное множество

Пусть $\rho$ произвольное отношение порядка на непустом множестве $А$ .

Упорядоченное множество — множество $А$ с заданным отношением порядка $\rho$ , обозначается $(A,\rho )$ .

Если порядок $\rho$ на $А$ линейный, то пара $(A,\rho )$ называется линейно упорядоченным множеством.

Операция порядка обозначается $\leqslant$ , а операция строгого порядка $<$ .

Пусть $(A, \leqslant)$ — упорядоченное множество,

$a \in A$	минимальный элемент	$\Leftrightarrow \neg {\text{(}}\exists x \in A)(x \ne a \wedge x \leqslant a)$
$a \in A$	наименьший элемент	$\Leftrightarrow {\text{(}}\forall x \in A)(a \leqslant x)$
$a \in A$	максимальный элемент	$\neg (\exists x \in A)(x \ne a \wedge a \leqslant x)$
$a \in A$	наибольший элемент	$\left( {\forall x \in A} \right)\left( {x \leqslant a} \right)$

Обратное отношение

Обратным отношением отношения $\rho$ называется отношение:

${\rho ^{ - 1}} = \left\{ {\left( {b,a} \right)\backslash \left( {a,b} \right) \in \rho } \right\}$

Композиция

Композицией (произведнием) двух бинарных отношений ${\rho _1} \subset A \times B$ и ${\rho _2} \subset B \times C$ называется отношение:

${\rho _1}^\circ {\rho _2} = \left\{ {\left( {x,y} \right)\backslash \left( {\exists z} \right)\left( {x{\rho _1}z \wedge z{\rho _2}y} \right)} \right\}$

Бинарное отношение $\rho$ на множестве $A$ — любое подмножество $A^2 = A \times A$ ; пишут $a \rho b$ , если $(a, b) \in \rho$ . Отношение рефлексивно, если $a \rho a$ для всех $a \in A$ , симметрично, если из $a \rho b$ следует $b \rho a$ , антисимметрично, если из $a \rho b$ и $b \rho a$ следует $a = b$ , и транзитивно, если из $a \rho b$ и $b \rho c$ следует $a \rho c$ .

Отношение эквивалентности рефлексивно, симметрично и транзитивно и разбивает множество на непересекающиеся классы эквивалентности. Отношение порядка рефлексивно, антисимметрично и транзитивно, как $\leq$ или делимость в $\mathbb{N}$ . Внимание: «антисимметрично» не значит «не симметрично» (равенство — и то и другое), а чтобы показать, что отношение не транзитивно, достаточно одного контрпримера.

Таблица отношения ρ: Одинаковый остаток при делении на 3
ρ	1	2	3	4	5	6	7	8
1
2
3
4
5
6
7
8

Отношение эквивалентности

Классы: {1, 4, 7}, {2, 5, 8}, {3, 6}

Рефлексивно: да
Симметрично: да
Антисимметрично: нет1 ρ 4 и 4 ρ 1, а 1 ≠ 4
Транзитивно: да

Одинаковый остаток при делении на 3 разбивает числа на классы, как день недели разбивает даты в примере: вся диагональ отмечена, а таблица симметрична относительно неё. Делимость — отношение порядка, а у соседних чисел один контрпример,

1 \rho 2

2 \rho 3

, но не

1 \rho 3

, показывает, что отношение не транзитивно.

Когда библиотека распределяет книги по жанрам, а календарь — даты по дням недели, это разбиение на классы эквивалентности. Отношение порядка задаёт очерёдность работ на стройке, где одна работа должна закончиться раньше другой.

Дни недели

На множестве дат октября 2026 года, $A = \{1, 2, \ldots, 31\}$ , рассмотрите отношение $a \rho b$ , если $a - b$ делится на 7. Покажите, что это отношение эквивалентности, найдите классы и назовите даты, которые приходятся на тот же день недели, что и 1 октября — четверг.

Решение

Рефлексивность: $a - a = 0$ делится на 7. Симметричность: если $7 \mid a - b$ , то $7 \mid b - a$ , так как $b - a = -(a - b)$ .
Транзитивность: если $7 \mid a - b$ и $7 \mid b - c$ , то 7 делит и сумму $(a - b) + (b - c) = a - c$ .
Класс даты 1: $[1] = \{1, 8, 15, 22, 29\}$ , остальные — $[2], [3], \ldots, [7]$ , например $[7] = \{7, 14, 21, 28\}$ . Их 7, по одному на каждый день недели.
В классах $[1]$ , $[2]$ и $[3]$ по 5 дат, в остальных по 4. Классы не пересекаются и вместе дают всё множество: $3 \cdot 5 + 4 \cdot 4 = 31$ .

Ответ: Это отношение эквивалентности с 7 классами, а четверги — 1, 8, 15, 22 и 29 октября 2026 года.

Задача для тренировки

Является ли на множестве $\{1, 2, \ldots, 10\}$ отношение « $a$ и $b$ дают одинаковый остаток при делении на 3» отношением эквивалентности? Если да, назовите классы.

Показать решение

Да: отношение рефлексивно (число даёт тот же остаток, что и оно само), симметрично (если остатки $a$ и $b$ равны, то равны и остатки $b$ и $a$ ) и транзитивно (если равны остатки $a$ и $b$ , а также $b$ и $c$ , то равны и остатки $a$ и $c$ ). Классы: $\{3, 6, 9\}$ , $\{1, 4, 7, 10\}$ и $\{2, 5, 8\}$ .

Отношение

Кратко

Выберите отношение

Пример из жизни

Дни недели

Решение

Задача для тренировки