Отношение эквивалентности: классы и фактор-множество

Отношение эквивалентности - один из самых рабочих инструментов дискретной математики и алгебры. Оно формализует простую идею: иногда разные объекты можно считать «одинаковыми» в каком-то отношении - остатки при делении, направления векторов, дроби с равным значением. Стоит навести такое отношение, и множество само распадается на непересекающиеся группы - классы эквивалентности, а из этих классов собирается новое множество, фактор-множество. Ниже разберём три аксиомы, которые делают отношение эквивалентностью, покажем, как из них рождается разбиение, и доведём конструкцию до фактор-множества на конкретных примерах. Если нужно проверить своё отношение или построить классы для конкретной задачи - соберите запрос в форме ниже.

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

Бинарное отношение $R$ на множестве $X$ - это любое подмножество пар $R \subseteq X \times X$. Если пара $(a, b)$ попадает в $R$, пишут $a \sim b$ и говорят, что $a$ находится в отношении с $b$. Отношений на множестве очень много, но эквивалентностью называют только те, что удовлетворяют сразу трём свойствам.

Отношение $\sim$ на $X$ называется отношением эквивалентности, если для любых элементов оно:

$$\begin{aligned} &\text{рефлексивно:} && a \sim a, \\ &\text{симметрично:} && a \sim b \Rightarrow b \sim a, \\ &\text{транзитивно:} && a \sim b \ \text{и}\ b \sim c \Rightarrow a \sim c. \end{aligned}$$

Эти три условия не случайны: вместе они формализуют интуицию «быть одинаковым в некотором смысле». Рефлексивность говорит, что каждый объект одинаков сам с собой; симметричность - что «одинаковость» не зависит от порядка сравнения; транзитивность - что одинаковость передаётся по цепочке. Уберите любую из аксиом, и отношение перестанет аккуратно делить множество на группы.

Рассчитать для своей задачи

Три аксиомы по отдельности

Чтобы свойства не сливались, разберём каждое на привычном примере - отношении «иметь одинаковый остаток при делении на 3» на множестве целых чисел.

• Рефлексивность. Любое число даёт сам с собой одинаковый остаток: $a$ и $a$ - это одно и то же число, остаток совпадает. Формально $a \sim a$ выполнено всегда.
• Симметричность. Если у $a$ и $b$ остатки совпали, то и у $b$ с $a$ они совпадают - порядок сравнения не важен. Это и значит $a \sim b \Rightarrow b \sim a$.
• Транзитивность. Если $a$ и $b$ дают остаток 2, и $b$ с $c$ дают остаток 2, то и $a$ с $c$ дают остаток 2. Одинаковость «склеивается» по цепочке.

Полезно сразу видеть контрпримеры. Отношение «$a < b$» транзитивно, но не рефлексивно ($a < a$ ложно) и не симметрично - это не эквивалентность, а строгий порядок. Отношение «$a$ и $b$ знакомы лично» рефлексивно и симметрично, но не транзитивно: ваш знакомый знаком с человеком, которого вы не знаете. Чтобы записывать классы и разбиения, пригодится язык операций над множествами - объединения, пересечения и разности.

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

Главное следствие трёх аксиом: множество распадается на группы. Классом эквивалентности элемента $a$ называют множество всех элементов, эквивалентных $a$:

$$[a] = \{\, x \in X : x \sim a \,\}.$$

Элемент $a$ называют представителем своего класса, но представителя можно выбрать любого: если $b \sim a$, то $[a] = [b]$ - это один и тот же класс. Именно поэтому удобно говорить просто «класс», не привязываясь к конкретному представителю.

Для остатков по модулю 3 классов ровно три: числа с остатком 0 (…, −3, 0, 3, 6, …), с остатком 1 (…, −2, 1, 4, 7, …) и с остатком 2 (…, −1, 2, 5, 8, …). Любое целое попадает ровно в один из них. Эти классы в теории чисел обозначают $\overline{0}, \overline{1}, \overline{2}$ и называют классами вычетов.

Ключевое свойство: классы либо совпадают, либо не пересекаются

Это центральная теорема всей конструкции. Для отношения эквивалентности два класса $[a]$ и $[b]$ обладают строгой дихотомией:

$$[a] = [b] \quad \text{или} \quad [a] \cap [b] = \varnothing.$$

Промежуточного «частично пересекаются» быть не может. Доказательство короткое: пусть классы пересекаются, то есть есть элемент $c \in [a] \cap [b]$. Тогда $c \sim a$ и $c \sim b$. По симметричности $a \sim c$, по транзитивности из $a \sim c$ и $c \sim b$ получаем $a \sim b$, а значит $[a] = [b]$. Итог: если есть хоть одна общая точка, классы совпадают целиком.

Отсюда и берётся аккуратное деление множества: классы не накладываются друг на друга и вместе покрывают всё $X$ (каждый элемент лежит хотя бы в своём классе $[a] \ni a$ по рефлексивности). Это и есть разбиение.

Разбиение множества и теорема о соответствии

Разбиением множества $X$ называют семейство непустых подмножеств, которые попарно не пересекаются и в объединении дают всё $X$. Связь с эквивалентностью двусторонняя и точная.

$$\text{отношение эквивалентности на } X \;\longleftrightarrow\; \text{разбиение } X.$$

В одну сторону мы уже прошли: всякое отношение эквивалентности задаёт разбиение на классы. Обратное тоже верно - любое разбиение порождает эквивалентность по правилу «$a \sim b$, если $a$ и $b$ лежат в одном блоке разбиения». Легко проверить, что три аксиомы при этом выполняются. Это взаимно однозначное соответствие - фундаментальный факт: говорить об эквивалентности и говорить о разбиении на классы - это одно и то же, выраженное двумя языками.

Рассчитать для своей задачи

Фактор-множество

Теперь финальный шаг. Если рассматривать каждый класс как единый объект, из классов собирается новое множество. Фактор-множеством (множеством-фактором) $X$ по отношению $\sim$ называют множество всех его классов эквивалентности:

$$X / {\sim} \;=\; \{\, [a] : a \in X \,\}.$$

Запись $X / {\sim}$ читают «$X$ по модулю отношения $\sim$» или «фактор $X$ по $\sim$». Элементами этого множества являются не исходные точки, а целые классы. Происходит огрубление: детали внутри класса забываются, остаётся только принадлежность к классу.

Для остатков по модулю 3 фактор-множество $\mathbb{Z} / {\sim}$ состоит из трёх элементов - $\{\overline{0}, \overline{1}, \overline{2}\}$. Бесконечное множество целых чисел свернулось в трёхэлементное. В алгебре на этом множестве вводят сложение и умножение классов - получается кольцо вычетов $\mathbb{Z}_3$; так же строятся фактор-группы и фактор-пространства.

Канонический пример: дроби как классы

Поучительный пример - само множество рациональных чисел. Пары целых чисел $(p, q)$ с $q \neq 0$ можно считать дробями, но разные пары задают одно число: $(1, 2)$ и $(2, 4)$ - это одна дробь. Введём отношение

$$(p, q) \sim (r, s) \quad \Longleftrightarrow \quad p \cdot s = r \cdot q.$$

Проверка трёх аксиом - стандартное упражнение (симметричность очевидна, транзитивность даёт перемножение равенств). Класс эквивалентности пары $(p, q)$ - это все пары, задающие то же значение, то есть в точности привычная дробь $p/q$ как число. Множество рациональных чисел $\mathbb{Q}$ - это и есть фактор-множество пар по этому отношению. Так формально определяется, что «$\tfrac{1}{2} = \tfrac{2}{4}$»: это не два числа, а один класс.

Как это используют

Конструкция «эквивалентность → классы → фактор» работает по всей математике:

• Теория чисел - классы вычетов и арифметика по модулю (часы, контрольные суммы, криптография).
• Алгебра - фактор-группы по нормальной подгруппе, фактор-кольца по идеалу, фактор-пространства; на этом же языке работает гомоморфизм групп с его ядром и образом.
• Геометрия и топология - склейка точек: лист, склеенный по краям, формально есть фактор-множество по отношению «отождествить эти точки».
• Информатика - минимизация автоматов (эквивалентные состояния сливаются), типобезопасность и канонизация данных.

Везде смысл один: ввести правило «считать одинаковым» и перейти к множеству классов, где это правило стало равенством.

Частые ошибки

• Проверяют не все три аксиомы. Часто забывают рефлексивность или путают симметричность с транзитивностью. Для эквивалентности нужны все три одновременно.
• Считают, что классы могут частично пересекаться. Нет: либо совпадают целиком, либо не пересекаются вовсе. Частичное наложение означает, что отношение не транзитивно.
• Путают элемент и класс. В фактор-множестве элементы - это классы, а не исходные точки. $[a]$ - это множество, а не число.
• Думают, что класс зависит от выбора представителя. $[a]$ и $[b]$ при $a \sim b$ - один и тот же класс; представителя берут любого.
• Берут пустые блоки в разбиении. Блоки разбиения по определению непусты; пустое подмножество в разбиение не входит.

FAQ

Чем отношение эквивалентности отличается от отношения порядка? Эквивалентность симметрична ($a \sim b$ влечёт $b \sim a$) и делит множество на классы. Отношение порядка антисимметрично (если $a \le b$ и $b \le a$, то $a = b$) и выстраивает элементы в иерархию, а не в группы. Это два разных типа бинарных отношений с разными аксиомами.

Сколько классов эквивалентности может быть? Сколько угодно - от одного (если все элементы эквивалентны, отношение «всё связано со всем») до количества элементов множества (если эквивалентны только равные, отношение-равенство). Число классов равно числу блоков разбиения.

Зачем нужно фактор-множество, если есть классы? Класс - это отдельная группа, а фактор-множество - новый объект, собранный из всех классов сразу, с которым можно работать как с единым множеством: вводить на нём операции, отображения, структуру. Именно переход к фактор-множеству даёт фактор-группы, кольца вычетов и фактор-пространства.

Коротко

Отношение эквивалентности - это бинарное отношение, удовлетворяющее трём аксиомам: рефлексивности, симметричности и транзитивности. Из них следует, что множество распадается на классы эквивалентности, которые либо совпадают, либо не пересекаются и вместе покрывают всё множество - то есть задают разбиение. Соответствие «эквивалентность ↔ разбиение» взаимно однозначно. Собрав все классы в одно множество, получают фактор-множество $X / {\sim}$ - новый объект, где «эквивалентные» стали равными. На этой конструкции держатся классы вычетов, дроби как классы пар, фактор-группы и фактор-пространства.