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

Отношение — это множество пар

Определение выглядит неожиданно скупо:

$R \subseteq A \times B$

Отношение — это просто подмножество декартова произведения. Никакой отдельной сущности «отношение» нет: есть набор пар, которые мы объявили связанными.

Вместо $(a, b) \in R$ обычно пишут $a \mathbin{R} b$. Именно поэтому $\le$, $=$ и $\subseteq$ — это отношения: $\le$ на $\N$ есть множество пар $\{(0,0), (0,1), (1,1), (0,2), \dots\}$.

В коде отношение — это либо set[tuple], либо предикат f(a, b) -> bool, либо матрица смежности. Три представления одного и того же.

Свойства

Для отношения на одном множестве ($R \subseteq A \times A$) важны три свойства:

Свойство	Формально	Словами
рефлексивность	$\forall a,\; a \mathbin{R} a$	каждый связан сам с собой
симметричность	$a \mathbin{R} b \Rightarrow b \mathbin{R} a$	связь не имеет направления
транзитивность	$a \mathbin{R} b \wedge b \mathbin{R} c \Rightarrow a \mathbin{R} c$	связь передаётся по цепочке

Проверьте на знакомых примерах:

• $=$ обладает всеми тремя
• $\le$ рефлексивно и транзитивно, но не симметрично
• $<$ транзитивно, но не рефлексивно и не симметрично
• «быть другом» симметрично, но обычно не транзитивно

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

Отношение, обладающее всеми тремя свойствами, называется эквивалентностью и обозначается $\sim$.

Смысл прост: эквивалентность — это «равенство с точностью до чего-то». Мы объявляем неразличимыми объекты, которые различаются только тем, что нас сейчас не интересует.

Примеры, которые пригодятся позже:

• сравнение по модулю: $a \sim b \iff a \equiv b \pmod n$
• векторы, отличающиеся положительным множителем: $x \sim y \iff x = \lambda y,\; \lambda > 0$ — направления, а не векторы
• матрицы, подобные друг другу — один и тот же оператор в разных базисах (блок 1)

Классы и разбиения

Класс эквивалентности элемента $a$ — это все объекты, ему эквивалентные:

$[a] = \{x \in A : x \sim a\}$

Дальше происходит вещь, которую стоит один раз осознать и потом использовать как факт:

Классы эквивалентности образуют разбиение. И наоборот: любое разбиение задаёт отношение эквивалентности («лежать в одной группе»).

Это два описания одной структуры. Транзитивность и симметричность — ровно то, что не даёт классам частично перекрываться: если у двух классов есть общий элемент, они совпадают целиком.

Практическое следствие: когда вы видите $\sim$, можно сразу думать «groupby по какому-то ключу». Множество классов обозначается $A/{\sim}$ и называется фактормножеством.

Порядок — второй важный тип

Если отношение рефлексивно, транзитивно и антисимметрично ($a \mathbin{R} b \wedge b \mathbin{R} a \Rightarrow a = b$), оно называется частичным порядком. Пример — $\subseteq$ на подмножествах: два множества могут быть несравнимы, ни одно не включено в другое.

Частичный порядок понадобится, чтобы аккуратно говорить про sup и inf в следующем уроке.

Чего здесь нет

Решёток, вполне упорядоченных множеств, теоремы Цермело. Для чтения статей достаточно узнавать $\sim$ и понимать, что за ним стоит группировка.