Лекции_по_ДМ

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

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

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

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

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

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

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

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

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

Примеры:

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

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

3) На множестве всех натуральных чисел рассмотрим отношение , согласно которому (x,y), если они имеют одинаковый остаток при делении на одно и то же фиксированное натуральное число m, или как говорят, сравнимы по модулю m: (x mod m) = (y mod m). Заданное отношение – эквивалентность. По этому отношению множество ℕ разбивается на классы чисел, сравнимых по модулю m. Это следующие классы: K₀ – числа, делящиеся на m без остатка, т.е. К₀={xℕ: x mod m =0}; K₁ – числа, дающие при делении на m остаток 1, т.е. К₁={xℕ: x mod m =1}; K₂ – числа, дающие при делении на m остаток 2, т.е. К₂={xℕ: x mod m =2}; ……… K_m_–1 – числа, дающие остаток m–1, т.е. К_m_–1={xℕ: x mod m =m–1}.

Тогда факторизация множества ℕ /(mod m) =K₀∪K₁∪K₂∪…∪K_m_-1. Классы К_i называются также классами вычетов.

Содержание