double arrow

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


Бинарное отношение r, заданное на множестве М, называется отношением эквивалентности или просто эквивалентностью, если оно рефлексивно, транзитивно и симметрично. Для обозначения этого отношения чаще используется запись a~b без указания r.

Значение этого отношения заключается в том, что с помощью него множество разбивается в объединение попарно непересекающихся подмножеств (классов эквивалентности).

Пусть «~» – эквивалентность на множестве М. Подмножество Ка Í М, состоящее из всех элементов М, эквивалентных элементу аÎМ, называется классом эквивалентности элемента а по отношению «~», т.е. Ка={ х: х~а, где а, х Î М }.

Утверждения:

1) Два класса эквивалентности множества М либо совпадают, либо не пересекаются.

Действительно, если два класса эквивалентности КаÍМ и Кb ÍМ имеют общий элемент сÎМ, то для любого элемента хÎКа следует: х~а и а~с и с~b и по транзитивности x~b. Значит, xÎКb и наоборот. Следовательно, Ка=Кb. Теперь предположим, что классы Ка и Кb пересекаются, тогда они имеют общий элемент сÎМ, такой что сÎКа и сÎКb. Но тогда, как было доказано, Ка=Кb.

2) Любой элемент множества М попадает в один и только один класс эквивалентности. Поэтому множество М разбивается на попарно непересекающиеся классы эквивалентных между собой элементов.




Множество всех классов эквивалентности для М по отношению «~» называется фактор–множеством и обозначается М/~. А процесс разбиения М на классы эквивалентности называется факторизацией.

Примеры:

1) Отношение равенства на любом множестве является эквивалентностью. Соответствующее ему разбиение на классы есть объединение всех одноэлементных подмножеств данного множества.

2) На множестве всех целых чисел рассмотрим отношение r, согласно которому (x,yr, если х и у имеют одинаковые знаки. Ясно, что это отношение рефлексивно, транзитивно и симметрично, следовательно, r – эквивалентность. Тогда соответствующая факторизация множества ℤ /~=ℤ∪ℤ+∪{0}, т.к. число 0 эквивалентно только себе.

3) На множестве всех натуральных чисел рассмотрим отношение r, согласно которому (x,yr, если они имеют одинаковый остаток при делении на одно и то же фиксированное натуральное число m, или как говорят, сравнимы по модулю m: (x mod m) = (y mod m). Заданное отношение – эквивалентность. По этому отношению множество ℕ разбивается на классы чисел, сравнимых по модулю m. Это следующие классы:
K0 – числа, делящиеся на m без остатка, т.е. К0={xÎℕ: x mod m =0};
K1 – числа, дающие при делении на m остаток 1, т.е. К1={xÎℕ: x mod m =1};
K2 – числа, дающие при делении на m остаток 2, т.е. К2={xÎℕ: x mod m =2};
………
Km–1 – числа, дающие остаток m–1, т.е. Кm–1={xÎℕ: x mod m =m–1}.

Тогда факторизация множества ℕ /~(mod m) =K0∪K1∪K2∪…∪Km-1. Классы Кi называются также классами вычетов.







Сейчас читают про: