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

Отношение называется отношением эквивалентности (или просто эквивалентностью), если оно рефлексивно, симметрично и транзитивно. Если элементы a и b связаны отношением эквивалентности, то применяется запись: a~b.

Примеры.

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

2. Отношение “иметь один и тот же остаток от деления на 4” является эквивалентностью на NÈ{0}. Это отношение выполняется, например, для пар (19,43), (12,20) и не выполняется для пар (18,43), (12,21).

3. Отношение “быть параллельными”, заданное на множестве всех прямых на плоскости, также представляет собой эквивалентность.

Пусть на множестве М задано отношение эквивалентности R. Выполним следующее построение. Выберем элемент a₁ÎМ и образуем класс (подмножество М) C₁, состоящий из a₁ и всех элементов, эквивалентных a₁; затем выберем из М элемент a₂ÏC₁ и образуем класс C₂, состоящий из a₂ и всех элементов, эквивалентных a₂, и т.д. Получится система (возможно, бесконечная) классов C₁, C₂,..., в которой каждый элемент из М входит хотя бы в один класс, т.е. =M.

Эта система классов имеет следующие свойства:

1) она образует разбиение (классы попарно не пересекаются);

2) любые два элемента из одного класса эквивалентны;

3) любые два элемента из разных классов не эквивалентны.

Свойства 2, 3 непосредственно следуют из способа построения классов эквивалентности, поэтому ограничимся доказательством свойства 1.

ÿ Предположим, что два класса, например C₁ и C₂, пересекаются. Это значит, что они имеют хотя бы один общий элемент b, причём, по построению, b~ a₁ и b~ a₂. Тогда, в силу транзитивности отношения эквивалентности, a₁~a₂. Полученный результат противоречит построению C₂. Остаётся утверждать, что C₁ и C₂ не пересекаются. ÿ

Построенное разбиение называется системой классов эквивалентности по отношению к R. Мощность этой системы называется индексом разбиения.

Примеры.

1. Все классы эквивалентности для отношения равенства Е состоят из одного элемента (“а” равно только себе самому).

2. Разбиение на NÈ{0} для отношения “иметь один и тот же остаток от деления на 4” имеет конечный индекс 4 и состоит из четырёх классов:

C₁={0,4,8,12,...}={c / c=4k-4, kÎN}, C₂={1,5,9,13,...}= {c / c=4k-3, kÎN},

C₃={2,6,10,14,...}= {c / c=4k-2, kÎN}, C₄={3,7,11,15, ...}= {c / c=4k-1, kÎN}.