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

Некоторые элементы множества можно рассматривать как эквивалентные в том случае, когда любой из этих эле­ментов при некотором рассмотрении может быть заменен другим. В этом случае говорят, что данные элементы на­ходятся в отношении эквивалентности. Примерами отно­шений эквивалентности являются: отношение «быть на одном курсе» на множестве студентов факультета; отно­шение «иметь одинаковый остаток при делении на 3» на множестве натуральных чисел; отношение параллельности на множестве прямых плоскости; отношение подобия на множестве треугольников и т. п.

Для того чтобы дать четкую формулировку отноше­ния эквивалентности, будем считать, что термин «отно­шение эквивалентности» применяется только в случае, ес­ли выполняются следующие три условия:

каждый элемент эквивалентен самому себе;

высказывание, что два элемента являются эквивалент­ными, не требует уточнения, какой из элементов рассмат­ривается первым и какой вторым;

два элемента, эквивалентные третьему, эквивалентны между собой.

Примем для обозначения эквивалентности символ . Тогда общее определение эквивалентности получим, запи­сав три вышеприведенных условия в виде следующих со­отношений:

хх(рефлексивность);

xуyx (симметричность);

ху _и yxхz (транзитивность).

Таким образом, отношение Г называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Отношение эквивалентности находится в тесной связи с разбиением множества. Пусть X — множество, на котором определено отношение экви­валентности. Например, X — множество студентов курса, а отношением эквивалентности является отношение «быть в одной группе». Подмножество элементов, эквивалентных некоторому элементу хХ, будем называть классом эк­вивалентности. Так, группа, в которой учится студент Иванов, будет классом эквивалентности, эквивалентным студенту Иванову.

Пусть J — некоторое множество индексов. Обозначим через {} множество классов эквивалентности для множества X. Очевидно, что все элементы одного класса эквивалентности эквивалентны между собой (свой­ство транзитивности) и всякий элемент хХможет на­ходиться в одном и только в одном классе. Но в таком случае X является объединением непересекающихся мно­жеств , так что полная система классов {} является разбиением множества X. Таким образом, каж­дому отношению эквивалентности на множестве X соот­ветствует некоторое разбиение множества на классы .

В качестве общего символа отношения эквивалентно­сти используют знак (иногда ~). Однако для отдель­ных частных отношений эквивалентности применяют дру­гие знаки: = - для обозначения равенства, || - парал­лельности, - логической эквивалентности.