Бинарное отношение $\rho$ — подмножество декартова произведения множеств:
$\rho \subseteq A \times B$ — бинарное отношение.
Бинарное отношение называется однородным, если оно является подмножеством декартова квадрата:
$\rho \subseteq A \times A = A^2 $ — однородное бинарное отношение.
Свойства однородных бинарных отношений
- Рефлексивность $\forall a \in A \Rightarrow (a, a) \in \rho$
- Симметричность $\forall a, b \in A (a, b) \in \rho \Rightarrow (b, a) \in \rho$
- Транзитивность $\forall a, b, c \in A (a, b) \in \rho \land (b, c) \in \rho \Rightarrow (a, c) \in \rho$
- Антисимметричность $\forall a, b \in A (a, b) \in \rho \Rightarrow (b, a) \notin (b, a)$
- Антирефлексивность $\forall a \in A \Rightarrow (a, a) \notin \rho$
- Связность $\forall a, b \in \rho \Rightarrow (a, b) \in \rho \lor (b, a) \in \rho \lor a = b$
Отношения эквивалентности
Отношение эквивалентности $R$ — однородное бинарное отношение со свойствами рефлексивности, симметричности и транзитивности. Обозначение:
$ aRb \Leftrightarrow (a, b) \in R \Leftrightarrow a, b $ эквивалентны по отношению $R$
Классы эквивалентности
$R(a) = \{ \forall b \in A (a, b) \in R \}$ — класс эквивалентности, включающий в себя все пары однородного бинарного отношения $R$ с элементом $a$. $a$ называется образующим элементом.
Свойства классов эквивалентности
- Класс эквивалентности всегда имеет хотя бы один элемент — сам $a$, так как $\exists (a,a) \in R$.
- $b \in R(a) \Rightarrow R(a) = R(b) $
- Классы эквивалентности не пересекаются
- Объединение всех классов эквивалентности даёт множество $A$.
Теорема о разбиении множества заданным отношением эквивалентности
Любое отношение эквивалентности задаёт разбиение множества $A$ на классы эквивалентности.
Доказательство
$]K_a, K_b$ — классы эквивалентности, образованные элементами $a$ и $b$ соответственно. Докажем, что $\forall K_a, K_b$ или $K_a = K_b$, или $\lnot \exists c: c \in K_a \land c \in K_b $ от противного.
$] K_a \neq K_b$ и $\exists c : c \in K_a \land c \in K_b$ $\Rightarrow$ в силу транзитивности $c ~ a \land c ~ b$ $\Rightarrow$ $a \in K_b, b \in K_a$ $\Rightarrow$ $K_a = K_b$ $\Rightarrow$ противоречие.
Теорема доказана.
Теорема, обратная теореме о разбиении множества заданным отношением эквивалентности
Любое разбиение множества $A$ задаёт отношение эквивалентности.
Доказательство
$] (B_i)$, где $i \in I$ — разбиение множества $A$. Рассмотрим отношение $\rho$:
$x ~_\rho y$ $\Leftrightarrow$ $\exists i \in I (x \in B_i \land y \in B_i)$. Очевидно, что $\rho$ рефлексивно и симметрично. $\forall x, y, z x ~_\rho z \land z ~_\rho y$ $\Leftrightarrow$ $\exists i \in I x \in B_i \land z \in B_i \land y \in B_i$ $\Rightarrow$ $x ~_\rho y$, то есть $\rho$ транзитивно $\Rightarrow$ $\rho$ — отношение эквивалентности.
Теорема доказана.
Примеры отношений эквивалентности
Свободный вектор
Любой свободный вектор образует класс эквивалентности отношения конгруэнтности на множестве связанных векторов евклидова пространства, в который входят все векторы, конгруэнтные (с теми же длиной и направлением) заданному.
$$R(\vec{a}) = \{ \forall \vec{b} : \vec{a} \cong \vec{b} \}$$
Вычет
Отношение сравнимости по модулю — это отношение эквивалентности, а классы вычетов есть классы эквивалентности, причём их можно занумеровать таким образом, что $r$-й класс состоит из всех целых чисел, дающих при делении остаток $r$:
$$\mathbb{Z}_n = \{ [0]_n, [1]_n, \dots, [n-1]_n \}$$
$$R(a) = \{ \forall b \in \mathbb{N}: a \equiv b \, (mod \, n) \}$$