Смекни!
smekni.com

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

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

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

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

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

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

Отношение

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

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

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

на множестве
рефлексивно, симметрично и транзитивно, то существует разбиение
множества
такое, что соотношение
выполнено в тех и только тех случаях, когда
и
принадлежат общему классу разбиения.

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

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

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

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

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

и
либо
, либо
.

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

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

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

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

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

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