Рассмотрим в качестве
множество всех целых неотрицательных чисел и возьмем его разбиение на множество четных чисел и множество нечетных чисел. Соответствующее отношение эквивалентности на множестве целых чисел обозначается так: и читается: сравнимо с по модулю 2. В качестве эталонов здесь естественно выбрать 0 – для четных чисел и 1 – для нечетных чисел. Аналогично, разбивая то же множество на подмножеств , где состоит из всех чисел, дающих при делении на и остатке , мы придем к отношению эквивалентности: , которое выполняется, если и имеют одинаковый остаток при делении на . В качестве эталона в каждом естественно выбрать соответствующий остаток .1.2 Формальные свойства эквивалентности
Мы определили выше отношении эквивалентности с помощью разбиений, т.е. фактически задали их некоторой конструкцией. Можно было бы и по-другому определить эквивалентности: можно сформулировать свойства (аксиомы), которые выделяют отношения эквивалентности среди прочих бинарных отношений.
1.2.1 Определение
Отношение
на множестве называется, эквивалентностью (или отношением эквивалентности), если оно рефлексивно, симметрично и транзитивно.Мы сейчас дали два независимых определения одного и того же понятия. Теперь нам следует убедиться, что оба определения эквивалентпости равносильны.
Теорема. Если отношение на множестве рефлексивно, симметрично и транзитивно, то существует разбиение множества такое, что соотношение выполнено в тех и только тех случаях, когда и принадлежат общему классу разбиения.
Обратно: если задано разбиение множества и бинарное отношение определено как "принадлежать общему классу разбиения", то рефлексивно, симметрично и транзитивно.
Доказательство первой части. Рассмотрим рефлексивное, симметричное и транзитивное отношение
на . Пусть для любого множество состоит из всех таких элементов , для которых .Лемма. Для любых и либо , либо .
Доказательство леммы. Пусть пересечение
. Покажем, что . Пусть , тогда выполнено и по самому определению множеств и . По симметричности имеем , а по транзитивности из и следует . Возьмем теперь произвольный элемент . По определению . Но из и следует , т.е. . Итак, .Аналогично показывается, что
. Значит . Лемма доказана.Из леммы и рефлексивности отношения
следует, что множества вида образуют разбиение множества . Пусть теперь выполнено соотношение . Это значит, что . Но и , в силу . Следовательно, оба элемента и входят в . Итак, если , то и входят в общий класс разбиения. Наоборот, пусть и . Покажем, что выполнено. Действительно, имеем и . Отсюда по симметричности . По транзитивности из и следует . Первая часть теоремы доказана.