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

Отноше́ние эквивале́нтности, бинарное отношение на множестве, обладающее свойствами рефлексивности, симметричности и транзитивности. Более подробно, бинарное отношение ${\displaystyle \sim }$ на множестве ${\displaystyle X}$ называется отношением эквивалентности, если оно обладает свойствами:

(E1) ${\displaystyle x\sim x}$ для всех ${\displaystyle x\in X}$ (рефлексивность);

(E2) если ${\displaystyle x\sim y}$, то ${\displaystyle y\sim x}$ (симметричность);

(E3) если ${\displaystyle x\sim y}$ и ${\displaystyle y\sim z}$, то ${\displaystyle x\sim z}$ (транзитивность).

При этом если ${\displaystyle x\sim y}$, то говорят, что элементы ${\displaystyle x}$ и ${\displaystyle y}$ эквивалентны (относительно данного отношения эквивалентности ${\displaystyle \sim }$). Отношение эквивалентности часто обозначается символом ${\displaystyle \equiv }$.

Пусть на множестве ${\displaystyle X}$ задано отношение эквивалентности ${\displaystyle \sim }$; для каждого ${\displaystyle x\in X}$ множество ${\displaystyle [x]=\{a\in X:a\sim x\}}$ (т. е. множество элементов, эквивалентных данному элементу ${\displaystyle x}$) называется классом эквивалентности (более точно, классом эквивалентности элемента ${\displaystyle x}$). Два элемента эквивалентны в том и только том случае, если их классы эквивалентности совпадают, т. е. ${\displaystyle x\sim y}$ тогда и только тогда, когда ${\displaystyle [x]=[y]}$. Каждый элемент ${\displaystyle x\in X}$ принадлежит своему классу эквивалентности (${\displaystyle x\in [x]}$), поэтому все классы эквивалентности непусты и их объединение совпадает с множеством ${\displaystyle X}$; кроме того, любые два класса эквивалентности либо не пересекаются, либо совпадают. Множество классов эквивалентности называется фактормножеством множества ${\displaystyle X}$ по отношению эквивалентности ${\displaystyle \sim }$ и обозначается ${\displaystyle X/{\sim }}$.

Семейство ${\displaystyle {\mathcal {P}}}$ подмножеств множества ${\displaystyle X}$ называется разбиением этого множества, если оно а) состоит из непустых множеств; б) покрывает ${\displaystyle X}$ (т. е. если ${\displaystyle \bigcup {\mathcal {P}}=X}$, иначе говоря – если каждый ${\displaystyle x\in X}$ принадлежит некоторому ${\displaystyle A\in {\mathcal {P}}}$); в) состоит из попарно не пересекающихся множеств (т. е. ${\displaystyle A\cap B=\varnothing }$ для любых различных ${\displaystyle A,B\in {\mathcal {P}}}$). Каждому отношению эквивалентности ${\displaystyle \sim }$ на множестве ${\displaystyle X}$ соответствует разбиение ${\displaystyle {\mathcal {P}}=X/{\sim }}$ этого множества на классы эквивалентности, т. е.

${\displaystyle {\mathcal {P}}=\{A\subset X:A=[x]{\text{ для некоторого }}x\in X\}}$.

Обратно, каждому разбиению ${\displaystyle {\mathcal {P}}}$ множества ${\displaystyle X}$ соответствует отношение эквивалентности ${\displaystyle \sim }$ на нём, определённое следующим образом: два элемента эквивалентны, если они оба принадлежат одному и тому же элементу этого разбиения, т. е.

${\displaystyle x\sim y{\text{ тогда и только тогда, когда }}x,y\in A{\text{ для некоторого }}A\in {\mathcal {P}}}$;

при этом оказывается, что разбиение множества ${\displaystyle X}$ на классы эквивалентности относительно так определённого отношения ${\displaystyle \sim }$ совпадает с исходным разбиением ${\displaystyle {\mathcal {P}}}$, т. е. ${\displaystyle X/{\sim }={\mathcal {P}}}$.

Указанные правила определяют обратные друг другу отображения, устанавливающие взаимно однозначное соответствие между множеством всех отношений эквивалентности на ${\displaystyle X}$ и множеством всех разбиений на нём. Это соответствие имеет фундаментальный характер; его существование неформально может быть выражено фразой: «задать отношение эквивалентности на множестве – это то же самое, что задать его разбиение».

Примеры отношений эквивалентности.

1. Отношение равенства на произвольном множестве: ${\displaystyle x\sim y}$ означает ${\displaystyle x=y}$. Классами эквивалентности являются одноэлементные множества.

2. Отношение эквивалентности на произвольном множестве ${\displaystyle X}$, отождествляющее все его элементы, т. е. определённое правилом: ${\displaystyle x\sim y}$ для всех ${\displaystyle x,y\in X}$. Если множество ${\displaystyle X}$ непусто, то оно является единственным классом эквивалентности. (На пустом множестве существует единственное отношение эквивалентности, и множество классов эквивалентности в этом случае пусто.)

3. Отношение параллельности на множестве прямых на плоскости (считается, что каждая прямая параллельна сама себе). Классами эквивалентности являются пучки параллельных прямых, которые могут быть отождествлены с точками «бесконечно удалённой прямой», которая дополняет «обычную» плоскость до проективной плоскости.

4. Отношение сравнимости по модулю ${\displaystyle m}$ на множестве целых чисел, где ${\displaystyle m}$ – натуральное число. Два целых числа ${\displaystyle a}$, ${\displaystyle b}$ эквивалентны, если они дают один и тот же остаток при делении на ${\displaystyle m}$ (или, что равносильно, если разность ${\displaystyle a-b}$ делится на ${\displaystyle m}$). Классами эквивалентности являются классы вычетов по модулю ${\displaystyle m}$.

5. На произвольном топологическом пространстве ${\displaystyle X}$ можно задать следующее отношение эквивалентности: ${\displaystyle x\sim y}$, если существует связное множество ${\displaystyle A\subset X}$, содержащее обе точки ${\displaystyle x}$ и ${\displaystyle y}$. Классы эквивалентности в этом случае называются компонентами связности пространства ${\displaystyle X}$; каждая компонента связности является связным замкнутым множеством.

6. На множестве вещественнозначных функций, определённых на произвольном множестве ${\displaystyle T}$, имеется отношение «равенства с точностью до постоянного слагаемого»: ${\displaystyle f\sim g}$ означает, что существует вещественное число ${\displaystyle C}$, такое, что ${\displaystyle f(t)=g(t)+C}$ для всех ${\displaystyle t\in T}$. Типичная ситуация возникновения такого отношения эквивалентности в математическом анализе – неопределённые интегралы, которые можно рассматривать как соответствующие классы эквивалентности первообразных функций.

7. На множестве функций из примера 6 также можно рассмотреть отношение «равенства с точностью до положительного постоянного множителя»: ${\displaystyle f\sim g}$ означает, что существует вещественное число ${\displaystyle K>0}$, такое, что ${\displaystyle f(t)=Kg(t)}$ для всех ${\displaystyle t\in T}$. Такое отношение эквивалентности возникает, например, в анализе размерностей в физике, когда зависимость физических величин может рассматриваться «с точностью до множителя», что обусловлено возможностью выбора различных единиц измерения.

Понятие отношения эквивалентности имеет фундаментальное значение и является математическим уточнением интуитивной идеи отождествления предметов по какому-либо признаку (и соответствующего разбиения их на классы, в каждый из которых попадают предметы, отождествлённые друг с другом по этому признаку). Описательно говоря, отношение эквивалентности на некотором множестве выражает «равенство» его элементов «с точностью до какого-то условия», а класс эквивалентности представляет собой элемент, «рассмотренный с этой точностью» (ср. примеры 6 и 7 выше, а также понятие высотного класса в теории музыки и музыкальной акустике).

Различные отношения эквивалентности (в частности, отношения параллельности прямых, подобия и конгруэнтности геометрических фигур) и соответствующие классы эквивалентности по существу рассматривались ещё в античной математике, но общая формализация и точные определения этих понятий были даны лишь в первой трети 20 в.