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

Бинарным отношением R на непустом множестве А называется подмножество декартова произведения , т.е. . Например, отношение «меньше, чем», на множестве Z задается подмножеством . В более общем случае -арным отношением R на непустом множестве А называется подмножество декартовой степени Отношение называется обратным (инверсным) к R. Очевидно, что Например, обратным является

Определение 2.1.3. Отношением эквивалентности Е на множестве А называется бинарное отношение , удовлетворяющее следующим трем условиям:

a. для всех (рефлексивность).

b. влечет за собой (симметричность).

c. влечет за собой (транзитивность).

Будем писать у (или просто когда понятно, о каком Е идет речь), если это читается так: эквивалентно у». Для каждого элемента образуем множество эквивалентных ему элементов которое называется классом эквивалентности элемента . В силу рефлексивности Элемент называется представителем этого класса эквивалентности. Если то из симметричности и транзитивности следует, что поэтому любые представители некоторого класса эквивалентности определяют один и тот же класс эквивалентности. Образуем множество всех возможных (различных) классов эквивалентности, Оно называется фактормножеством множества А по этому отношению эквивалентности и, как мы увидим ниже, является разбиением множества А.

Пример. На определим отношение эквивалентности если Например, Проверьте, что это действительно отношение эквивалентности. Мы утверждаем, что фактормножество может быть отождествлено с множеством рациональных чисел Q. Действительно, элементы из Q представляются дробями когда . Таким образом, элементы из Q — это в точности классы эквивалентности.

Покажем, что между отношениями эквивалентности на множестве А и разбиениями этого множества существует тесная связь.

Предложение 2.1.4. Если Е — отношение эквивалентности на множестве А, то фактормножество является разбиением множества А. Обратно, если — разбиение множества А, то его можно представить как фактормножество для некоторого отношения эквивалентности Е на множестве А.

Доказательство. доказательства первой части предложения нужно показать, что различные классы эквивалентности не пересекаются и что их объединение совпадает с А.

Так как Е рефлексивно, для всякого выполняется а а. Отсюда следует, что каждый класс а непуст и что их объединение совпадает с А.

Докажем, что различные классы не пересекаются. Предположим, что b для некоторого ; покажем, что По определению а и b имеем ; в силу симметричности что по транзитивности влечет за собой

Для доказательства второй части предложения определим отношение ЕТ на А, такое, что ЕТ тогда и только тогда, когда a и b лежат в одном и том же блоке разбиения (Покажите, что это отношение эквивалентности.) Мы покажем, что ниже обозначает единственный блок содержащий элемент

Докажем включение Пусть непусто; покажем, что Рассмотрим ; по определению а имеем откуда получаем по определению что доказывает включение . Для доказательства обратного включения рассмотрим тогда по определению откуда получаем по определению а, что доказывает включение . Таким образом, каждый блок разбиения совпадает с некоторым классом эквивалентности а, принадлежащим

Доказательство обратного включения предоставляется читателю.

На практике значение отношений эквивалентности связано с идеей игнорирования подробностей; а именно, когда мы имеем дело с классами эквивалентности, мы как бы не замечаем различий между эквивалентными элементами множества А.

Пример. Зафиксируем целое число . Зададим такое отношение эквивалентности на , если для некоторого иначе говоря, , если их разность есть целое кратное . Несколько примеров: Класс эквивалентности элемента а — это множество которое мы также будем обозначать . Если , то и так далее; таким образом, мы разбили Z на непересекающиеся подмножества 0,1,2,3,4, и фактормножество есть Заметим, что, хотя каждый из классов эквивалентности содержит бесконечно много элементов, множество классов эквивалентности содержит всего пять элементов. В общем случае содержит элементов.