Система представителей

Эквивалентность. Классы эквивалентности

ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ

Отношение эквивалентности удовлетворяет условиям рефлексивности, симметрич-ности, транзитивности и обычно обозначается знаком ~. При этом х ~ у означает, что упорядоченная пара (х, у) принадлежит множеству, являющимся отношением эквивалентностив множестве М.

Свойства эквивалентности записываются следующим образом:

1) х ~ х (рефлексивность);

2) х~у Þ у ~ х (симметричность);

3) х~у Ù у ~ z Þ х ~ z (транзитивность).

Классом эквивалентности [ х ] элемента х называется множество всех эквивалентных ему элементов ([ x ]={ y: y~x }).

Теорема. Классы эквивалентности различных элементов не пересекаются.

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

[ x ]Ç[ y ]¹Æ Þ $ z: z Î[ x ]Ç[ y ] Þ z Î[ x ] Ù z Î[ y ] Þ х ~ z Ù у ~ z Þ х~у – противоречие.

Следовательно, различные классы эквивалентности не пересекаются.

Таким образом, отношение эквивалентности разбивает множество М на непересекающиеся классы эквивалентности. Наоборот, всякое разбиение множества М на непересекающиеся подмножества определяет между элементами этого множества некоторое отношение эквивалентности.

Все элементы, принадлежащие некоторому классу М_i разбиения множества М, свя­заны отношением эквивалентности. Они взаимозаменяемые в том смысле, что любой из этих элементов определяет данный класс, т. е. может служить его представителем (эталоном). Подмножество из М, содержащее по одному и только по одному элементу из каждого класса некоторого разбиения, называют системой представителей соответствующего отношения эквивалентности. Множество всех классов разбиения множества М, определяемого отношением эквивалентности А, образует фактор-множество М/А.

Например, отношение параллельности определяет разбиение множества прямых на плоскости на классы, каждый из которых образован множеством параллельных между собой прямых и харак­теризуется некоторым направлением (следует также считать, что прямая параллельна самой себе). Любая из параллельных прямых может служить представителем данного класса, а само направле­ние есть класс эквивалентности. Множество всех направлений составляет фактор-множество множества всех прямых по отноше­нию параллельности.

4.3. Классы вычетов по модулю т.

Рассмотрим отношение срав­нения но модулю т на множестве натуральных чисел, что записы­вается как х=у (mod т) и означает: х сравнимо с у по модулю т (т - целое положительное число, не равное нулю), если х-у делится на т. Целые числа, сравнимые по модулю т, связаны соотношением х = у + km (k - целое число) и образуют под­множество целых чисел, имеющих одинаковый остаток при деле­нии на т. Так как эти подмножества не пересекаются, они являются классами эквивалентности, а в качестве представителя каждого из них естественно выбрать остаток j = 0, 1, 2,..., т- 1. Таким образом, отношение сравнения по модулю т определяет разбиение множества натуральных чисел на т классов, где — счетное множество, называемое классом вычетов по модулю т.

пример. при т =4 имеем М ₀={0, 4, 8, 12,...}; М ₁={1, 5, 9, 13,...}, M ₂ = {2, 6, 10, 14,...}, М ₃={3, 7, 11, 15,...}. Представителями классов эквивалентности являются числа 0, 1, 2 и 3, так как 0 = 4(mod4) = 8(mod4) =...; 1 = 5(mod4) = 9(mod4) =...; 2 = 6(mod 4) = 10(mod 4) =...и 3=7(mod4) = 11(mod 4) =.... Таким образом, множество целых чисел раз­бивается отношением сравнения по модулю 4 на четыре класса эквивалентности. Внутри каждого класса эти числа неразличимы (4 ~ 0, 5 ~ 1, 6 ~ 2, 7 ~ 3 и т. д.).

При т = 1 разбиение состоит из единственного класса, который совпадает с исходным множеством, т. е. имеем полное отношение эквивалентности, при котором любые два элемента эквивалентны (все целые числа делятся на единицу). Отношение х = у (mod 2) разбивает множество целых чисел на классы четных и нечетных чисел.