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

Отношение эквивалентности является формализацией такой ситуации, когда говорят о сходстве двух элементов множества.

Бинарное отношение R называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Отношение эквивалентности xRy часто обозначается: х ~ у.

Пример 1. Отношение «одного роста» есть отношение эквивалентности на множестве X людей. Рефлексивность. Каждый человек такого же роста, как он сам. Симметричность. Сидоров одного роста с Петровым тогда и только тогда, когда Петров одного роста с Сидоровым. Транзитивность. Если Сидоров одного роста с Петровым, а Петров одного роста с Ивановым, то Сидоров одного роста с Ивановым.

Пример 2. Отношение обычного равенства на множестве целых чисел есть отношение эквивалентности.

Пример 3. Отношение х < у на множестве действительных чисел не есть отношение эквивалентности, так как оно не рефлексивно, не симметрично, а лишь транзитивно.

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

Подмножество [х] = {уX: у ~ х} называетсяклассом эквивалентности, содержащим x (это множество всех элементов X, эквивалентных данному элементу x). Любой элемент у[x] называется представителем этого класса.

Пример. Рассмотрим отношение принадлежности к одной студенческой группе. Классом эквивалентности является все множество студентов одной группы.

Теорема 1. Пусть R — отношение эквивалентности на множестве X. Тогда:

1) для хX имеем х[x];

2) если х, уX и xRy, то [х] = [у].

Другими словами, класс эквивалентности порождается любым своим элементом.

Доказательство. Воспользуемся рефлексивностью отношения эквивалентности R, т. е. xRx. Следовательно, по определению, х[х].

Пусть z[у]. Тогда yRz, и в силу транзитивности отношения эквивалентности имеем: из xRy и yRz справедливо xRz, т. е. z[х]. Отсюда [у][х].

Аналогично в силу симметричности R получаем [х][у]. Следовательно, [х] = [у].

Теорема 2. Всякое отношение эквивалентности R определяет разбиение множества X на классы эквивалентности относительно этого отношения R.

Теорема 3. Пусть задано разбиение множества X на попарно непересекающиеся подмножества. Тогда эти подмножества будут классами эквивалентности по некоторому отношению эквивалентности на X.