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

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

Если R является отношением эквивалентности, то часто вместо ARb пишут A~Rb, или просто A ~ b, если ясно, о каком отношении эквивалентности R идет речь.

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

1. Отношения подобия треугольников.

2. Отношение тождества на множестве алгебраических выражений.

3. Отношение параллельности на множестве прямых.

4. Отношение учиться в одной группе на множестве студентов.

5. Отношение получить одну и ту же оценку по математике на экзамене.

6. Отношение иметь одинаковый остаток при делении на 7 на множестве

целых чисел Z.

7. На множестве комплексных чисел С отношение иметь одинаковый модуль: z1~z2, если | z1 | = | z2 |.

Контрпримеры (отношения, не являющиеся отношениями эквивалентности).

1. на множестве чисел (не выполняется свойство симметричности).

2. на множестве прямых (нерефлексивно и нетранзитивно).

3. Отношение на Z (несимметрично).

Определение. Пусть на множестве А задано отношение эквивалентности ~ и AA. Множество всех элементов таких, что X~A , называется Смежным классом множества А, или Классом эквивалентности, и обозначается [A].

Свойства классов смежности.

1. ( очевидно, так как A ~ a, ввиду рефлективности).

2. Если A~b, то [ a ] = [ b ].

Доказательство. Проверим, что [A] [B]. Пусть X[A]. Тогда X ~ a. Но так как A~b, то по свойству транзитивности X~b И, следовательно, X[B]. В силу симметричности, имеем: B~a. Далее, поменяв местами A и B и все повторив, получим [B][A].

Замечание. Свойство 2 означает, что любой класс смежности однозначно определяется любым своим представителем. Тем самым, все представители класса равноправны при определении этого класса.

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

Доказательство. Пусть C A, C[A][B]. Так как C[A], То [C] = [A]. А так как

[C] b, то [C] = [B]. Поэтому [A] = [B].

Определение. Совокупность всех различных смежных классов множества А по отношению эквивалентности ~ называется Фактор -- множеством Множества А и обозначается A/~.

Замечание. Свойство 3 показывает, что такая совокупность всех различных смежных классов (фактор—множество) представляет собой некоторое разбиение множества А.

Обратно, всякое разбиение множества А=А1А2… Аn ( где АiAj = Ø ) определяет соответствующее отношение эквивалентности на множестве А.

Действительно, если задано разбиение множества A (такое, как выше), то положим A~b, если a и B принадлежат одному и тому же подмножеству Ai (рефлексивность и симметричность очевидны, транзитивность легко следует из того, что AiAj = Ø ).

< Предыдущая		Следующая >