🔀 Дискретка

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

Q: Что такое класс эквивалентности элемента a?

Это множество всех элементов, эквивалентных $a$: $[a] = \{x : x \sim a\}$. Любой элемент класса можно взять представителем — класс от этого не изменится благодаря транзитивности. Два класса либо совпадают, либо не пересекаются, поэтому классы всегда образуют разбиение множества. Верно и обратное: всякое разбиение порождает эквивалентность («лежать в одном куске») — на этом основаны задачи о подсчёте классов.

англ. Equivalence relation

Бинарное отношение, которое одновременно рефлексивно, симметрично и транзитивно; разбивает множество на непересекающиеся классы «одинаковостей».

Отношение эквивалентности — бинарное отношение, которое ведёт себя как равенство, не будучи им. Требования три: рефлексивность ( $a \sim a$ для всех), симметричность (из $a \sim b$ следует $b \sim a$ ) и транзитивность (из $a \sim b$ и $b \sim c$ следует $a \sim c$ ). Классические примеры: равенство чисел, сравнение по модулю $m$ , совпадение дня рождения у людей, параллельность прямых на плоскости. Систематика всех типов бинарных отношений — в уроке отношения, логическая сторона — в материале логика предикатов.

Главное следствие: эквивалентность режет множество на непересекающиеся куски — классы эквивалентности; внутри каждого элементы «одинаковы», между классами связей нет. Совокупность всех классов называют фактор-множеством $X / \sim$ . Так, сравнение целых по модулю $5$ даёт пять классов — по остаткам $0, 1, 2, 3, 4$ . Приём универсален: рациональные числа — классы пар целых с одинаковым отношением, в топологии так склеивают точки границы. Проверка трёх свойств занимает пару строк и всегда идёт в одном порядке.

a \sim a; a \sim b \Rightarrow b \sim a; a \sim b, b \sim c \Rightarrow a \sim c

рефлексивность, симметричность, транзитивность — трёх аксиом достаточно, чтобы множество распалось на непересекающиеся классы

Частые вопросы

Почему именно эти три свойства, а не другие?

Они в точности повторяют поведение знака равенства, поэтому всё доказанное для одного объекта переносится на любой эквивалентный ему. Симметричность запрещает «очередь»: если $a$ связан с $b$ , обратная связь есть автоматически. Транзитивность склеивает цепочки — классы обязаны совпасть целиком. Убери транзитивность, и классы перестанут существовать как неделимые куски; убери рефлексивность — отдельные элементы останутся ни с чем не связанными.

Что такое класс эквивалентности элемента a?

Это множество всех элементов, эквивалентных $a$ : $[a] = {x : x \sim a}$ . Любой элемент класса можно взять представителем — класс от этого не изменится благодаря транзитивности. Два класса либо совпадают, либо не пересекаются, поэтому классы всегда образуют разбиение множества. Верно и обратное: всякое разбиение порождает эквивалентность («лежать в одном куске») — на этом основаны задачи о подсчёте классов.