Отношения эквивалентности и толерантности и их свойства (стр. 2 из 20)

Рассмотрим в качестве

множество всех целых неотрицательных чисел и возьмем его разбиение на множество четных чисел и множество нечетных чисел. Соответствующее отношение эквивалентности на множестве целых чисел обозначается так: и читается: сравнимо с по модулю 2. В качестве эталонов здесь естественно выбрать 0 – для четных чисел и 1 – для нечетных чисел. Аналогично, разбивая то же множество на подмножеств , где состоит из всех чисел, дающих при делении на и остатке , мы придем к отношению эквивалентности: , которое выполняется, если и имеют одинаковый остаток при делении на . В качестве эталона в каждом естественно выбрать соответствующий остаток .

1.2 Формальные свойства эквивалентности

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

1.2.1 Определение

Отношение

на множестве называется, эквивалентностью (или отношением эквивалентности), если оно рефлексивно, симметрично и транзитивно.

Мы сейчас дали два независимых определения одного и того же понятия. Теперь нам следует убедиться, что оба определения эквивалентпости равносильны.

Теорема. Если отношение

на множестве

рефлексивно, симметрично и транзитивно, то существует разбиение

множества

такое, что соотношение

выполнено в тех и только тех случаях, когда

и

принадлежат общему классу разбиения.

Обратно: если задано разбиение

множества

и бинарное отношение

определено как "принадлежать общему классу разбиения", то

рефлексивно, симметрично и транзитивно.

Доказательство первой части. Рассмотрим рефлексивное, симметричное и транзитивное отношение

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

Лемма. Для любых

и

либо

, либо

.

Доказательство леммы. Пусть пересечение

. Покажем, что . Пусть , тогда выполнено и по самому определению множеств и . По симметричности имеем , а по транзитивности из и следует . Возьмем теперь произвольный элемент . По определению . Но из и следует , т.е. . Итак, .

Аналогично показывается, что

. Значит . Лемма доказана.

Из леммы и рефлексивности отношения

следует, что множества вида образуют разбиение множества . Пусть теперь выполнено соотношение . Это значит, что . Но и , в силу . Следовательно, оба элемента и входят в . Итак, если , то и входят в общий класс разбиения. Наоборот, пусть и . Покажем, что выполнено. Действительно, имеем и . Отсюда по симметричности . По транзитивности из и следует . Первая часть теоремы доказана.