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

В этом параграфе будем рассматривать бинарные отношения, определенные на множестве , т.е. подмножества множества .

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

Таким образом, граф отношения эквивалентности характеризуется следующими свойствами: 1) каждый элемент имеет петлю; 2) если есть стрелка от элемента к элементу , то обязательно есть стрелка от к ; 3) если есть стрелка от к и от к , то обязательно есть стрелка от х к .

Отношение эквивалентности будем обозначать символом ~ (тилда). Пусть ~ есть отношение эквивалентности на множестве М. Если и , то будем говорить, что элемент эквивалентен элементу (в отношении ~).

Определение 2. Множество всех элементов из , эквивалентных элементу , т.е.

,

называется классом эквивалентности, порожденным элементом а.

Отметим некоторые свойства классов эквивалентности.

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

□ В самом деле, в силу рефлексивности отношения ~ имеем и поэтому в силу определения 2 .

Любые два элемента из одного класса эквивалентности эквивалентны между собой, т.е. .

□ Действительно,

.

Любые два эквивалентных элемента порождают один и тот же класс эквивалентности, т.е. .

□ В самом деле, пусть . Тогда

.

Отсюда получаем равенство .

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

□ Это свойство вытекает непосредственно из определения 2 и свойства

. Любые два класса эквивалентности либо не пересекаются, либо совпадают, т.е. .

□ Действительно, пусть , т.е. имеет по крайней мере один элемент с. Имеем .

. Любые два элемента из различных классов эквивалентности не эквивалентны между собой, т.е. .

□ Пусть , , и . Если предположить, что , то по свойству получим . С другой стороны, в силу свойства из условия следует равенство , а условие влечет . Но тогда , что противоречит условию . Таким образом, элементы и не эквивалентны.

Заметим, что доказательство свойства проводилось методом от противного по схеме , где , и .

Прежде чем сформулировать следующее свойство, введем понятие разбиения множества.

Определение 3. Говорят, что подмножества множества образуют разбиение множества , если

1. их объединение дает все множество , т.е. ;

2. любые два из них попарно не пересекаются, т.е., если и , то .

Непосредственно из свойств , , и вытекает следующее свойство:

. Классы эквивалентности множества образуют разбиение множества .

Непосредственно из свойств классов эквивалентности вытекает следующее важное утверждение.

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

Определение 4. Множество, элементы которого являются классами эквивалентности ~ на множестве М, называется фактор-множеством множества М относительно эквивалентности ~ и обозначается через .

Заметим, что в графе отношения эквивалентности в один класс войдут те и только те элементы, которые попарно соединены стрелками.

Примеры отношений эквивалентности.

1. Отношение на Z. Фактор-множество имеет 6 элементов , где – множество целых чисел, имеющих при делении на 5 остаток r ( ).

2. Отношение «учиться на одном курсе» на множестве студентов математического факультета. Фактор-множество содержит 5 элементов; в один класс попадают студенты, обучающиеся на одном курсе.

3. Отношение на С. Каждое неотрицательного действительного числа определяет класс эквивалентности . Понятно, что такими множествами исчерпываются все классы эквивалентности, т.е. . Геометрически классы этой эквивалентности изображаются концентрическими окружностями плоскости с центром в начале координат.

4. Отношение равносильности на множестве всех формул алгебры высказываний является отношением эквивалентности.

5. Отношение иметь одинаковую мощность является отношением эквивалентности на булеане .