Отношение эквивалентности. 
Математика: логика, теория множеств и комбинаторика

Рассмотрим еще один важный вид отношения, которое используется в математике для построения новых множеств.

Определение. Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности.

Пример 8.2.1. Рассмотрим множество А точек плоскости. Пусть О некоторая фиксированная точка. Определим отношение р: ЛрТ «Точки Xи Y равноудалены от точки О». Нетрудно проверить, что отношение р рефлексивно, симметрично и транзитивно (убедитесь в этом). Итак, р есть отношение эквивалентности. •.

Введем понятие класса эквивалентности.

Пусть на множестве А задано отношение эквивалентности р. Класс эквивалентности, порожденный элементом а, - это множество всех элементов х из А, таких, что * находится в отношении р с элементом а.

Класс эквивалентности обозначают по-разному, например [я]_р, или р(а). Также для краткости используют обозначение а. Часто произвольное отношение эквивалентности обозначают символом Вернемся к примеру 8.2.1. Возьмем произвольную точку М на плоскости. Тогда класс эквивалентности, порожденный точкой Л/, — это множество всех точек плоскости X, таких, что ОХ=ОМ. Имеем окружность с центром О радиуса ОМ. Любая другая точка этой окружности порождает тот же самый класс эквивалентности. Чтобы получить другой класс эквивалентности, нужно взять точку Ми такую, что ОМ*ОМ. Класс эквивалентности, порожденный точкой М₉ — это окружность с центром О радиуса ОМ.

Пример 8.2.2. Рассмотрим отношение р на множестве А = {2, 3,4, 5}, заданное перечислением пар:

Нетрудно видеть, что р — отношение эквивалентности.

Тогда 3 = {3,4,5}, аналогично, 4 = {3,4,5} и 5 ={3,4,5}. Класс 2 = {2} есть одноэлементное множество.

Таким образом, существует два различных класса эквивалентности: {2} и {3,4,5}. Дадим следующую интерпретацию рассмотренной задачи. Можно сказать, что данное отношение разбивает множество школьных оценок на два класса: неудовлетворительная оценка и множество положительных оценок. •.

Вообще, термин «класс эквивалентности» оправдан гем, что множество всех классов образует разбиение исходного множества. Ото важное утверждение легко получить, используя критерий равенства классов: классы [г/]_(> и [/?]р совпадают тогда и только тогда, когда apb (см. задачи № 160 и № 161).

Это обстоятельство позволяет из исходного множества А сконструировать новое множество, элементами которого являются классы разбиения (то есть классы эквивалентности р). Полученное множество классов называется фактор-множеством множества А но эквивалентности р и обозначается А / р. Все элементы, лежащие в одном классе «старого» множества, мысленно «склеиваются» в один элемент нового множества (фактор-множества). В примере 8.2.2 каждая из отметок 3, 4, 5 в новом множестве сливается в одну положительную оценку. В примере 8.2.1 множество всех точек класса эквивалентности определяет новый единый объект — окружность.

Мы кратко описали процесс абстрагирования в математике, то есть отвлечение от тех свойств, которыми различаются первоначальные объекты.

Таким образом, с помощью отношения эквивалентности можно описать новое свойство, характеризующее различие элементов множества.

Пример 8.2.3. Рассмотрим координатную плоскость, представляющую собой множество точек прямою произведения R = {(х, у) |jceR, yeR}.

Зададим отрезок АВ, представляющий собой множество точек {(д;2) | 2CD, являющийся множеством {(дг;1) | 1<�т<3}. Ясно, что эти множества различны; например, точка С=(1;1) нс принадлежит отрезку АВ.

Определим на множестве всех отрезков плоскости следующее отношение р: хру о «Отрезки ди у можно совместить наложением». Это отношение является отношением эквивалентности. Теперь мы можем назвать отрезки равными⁴, если они лежат в одном классе эквивалентности (то есть находятся в отношении р). В этом случае отрезок АВ равен отрезку CD (они совмещаются параллельным переносом). Именно так мы и понимаем равенство отрезков. Однако, строго говоря, это уже другое равенство, а именно равенство классов эквивалентное гей, но не равенство множеств точек (ни одна точка отрезка АВ не принадлежит отрезку CD). Итак, мы отвлеклись от нс существенных с геометрической точки зрения различий двух отрезков и признали отрезки равными.

Аналогичным образом обстоит дело с понятием равенства треугольников. На рисунке треугольник ACD равен треугольнику ABD, однако это равенство опять-таки является новым отношением. Изначально треугольники различны, если рассматривать их как подмножества точек в R. Только после того как на множестве треугольников ввести отношение эквивалентности (два треугольника находятся в этом отношении, если их можно совместить наложением), мы имеем право отвлечься от того, что треугольники состоят из различных множеств точек. В геометрии мы всегда считаем треугольники, которые находятся в описанном отношении, равными. •.

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

Пример 8.2.4. Рассмотрим множество А всех уравнений вида f (x) = g (х) от одной переменной.

¹ Иногда отрезки (и любые фигуры), находящиеся в данном отношении, называют конгруэнтными.

На множестве Л можно рассмотреть так называемое формальное равенство уравнений, понимая под уравнением последовательность символов математического языка. В этом случае равные уравнения — это равные упорядоченные л-ки символов. Например, уравнения х = 3 и х + 1 = 4 различны.

С другой стороны, с математической точки зрения любое уравнение определяет некоторый предикат, который характеризуется главным образом тем множеством, в точках которого предикат принимает истинное значение. В каком именно виде задан предикат, для математической теории неважно.

Отсюда возникает следующее отношение, которое отождествляет уравнения с одинаковым множеством решений. Уравнения f (x) = g (x) и /, (x) = g (х) называются равносильными, если совпадают множества их решений. Нетрудно видеть, что отношение равносильности является отношением эквивалентности. Например, уравнения х² = 4 и (х-2)(г+2) = О равносильны, то сеть лежат в одном классе эквивалентности. В математической практике непринято вместо фразы «Уравнения равносильны» говорить, что уравнения равны, однако это не меняет суть дела, и равносильные уравнения, но крайней мере в уме, можно называть равными. •.

Подведем некоторые итоги. Если в контексте изучаемой теории нас не интересуют различия между объектами, связанными отношением эквивалентности ~, то элементы а и Ь, такие, что а~Ь_у мы считаем равными.

Итак, понятие равенства объектов а и b множества Л можно понимать в двух аспектах:

• -а и Ь- это один и тот же элемент множества Л;
• -а и b находятся в некотором заранее определенном отношении эквивалентности.

Более детальное изучение приложений отношения эквивалентности будет проведено в курсе алгебры. Один из первых новых примеров отношения эквивалентности, которое вы подробно рассмотрите, позволит разбить множество всех целых чисел на конечное число классов.

В заключение пункта заметим, что любое разбиение множества Л на классы эквивалентности однозначно определяет отношение эквивалентности следующим правилом: элементы а и b являются эквивалентными тогда и только тогда, когда они лежат в одном классе.