Смекни!
smekni.com

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

Замечание. Понятие когерентности имеет смысл для любых отношений

и
. Но для эквивалентностей когерентность отношений
и
легко формулируется в терминах классов эквивалентности (лемма 1.3.3).

1.3.4 Лемма

Если

и
рефлексивны, то


Доказательство. Если

, то, в силу
, выполнено и соотношение
, т.е.
. Аналогично получается
. Из этих двух включений следует .

Теорема. Для того чтобы объединение

эквивалентностей
и
само было отношением эквивалентности, необходимо и достаточно, чтобы

Доказательство. Пусть

– эквивалентность. По лемме 1.3.4 выполняется . Для доказательства остается доказать

Пусть

. Тогда для некоторого
имеем
и
. Следовательно,
и
. Значит,
и доказано. Пусть теперь выполнено . Отношение
симметрично. По тогда симметрично и ортношение
.
. По теореме 1.3.3 (см. ниже) получаем, что отношение
– эквивалентность. Из вытекает, что и
– эквивалентность. Теорема доказана.

Условие, при котором произведение

двух отношений эквивалентности
и
само является эквивалентностью, было получено чешским математиком Шиком в 1954 г.

Для того чтобы произведение

отношений эквивалентности
и
было эквивалентностью, необходимо и достаточно, чтобы
и
коммутировали.

Доказательство. Пусть сначала


рефлексивно.
симметрично. Транзитивность произведения доказывается так:
– здесь мы использовали ассоциативный закон для произведения отношений, условие , а также транзитивность и рефлексивность отношений
и
. Итак
, но это и означает транзитивность отношения
, поскольку
рефлексивно. Пусть теперь произведение
есть эквивалентность. Тогда
.

Легко проверить, что если

и
– эквивалентности, то
и
также будут эквивалентностями.

Оказывается, операция

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

Для любых транзитивных отношений

,
и
справедлив ассоциативный закон:

Докажем сначала две леммы.

1.3.5 Лемма

Для любых отношений

,


вытекает из

. доказывается аналогично.

1.3.5 Лемма

Для любых транзитивных отношений

,
,
из
и
вытекает
.

Доказательство теоремы 1.3.4. Из леммы 1.3.5

Из и

Из леммы 1.3.5

Из , , леммы 1.3.5 и того, что любое отношение вида

транзитивно,

Подобно тому как доказывается , доказывается


Подобно тому как мы из и вывели , из и выводится

Из и аналогично доказываемого "обратного" включения вытекает . Теорема доказана.

Нетрудно убедиться, что для любой эквивалентности

где

– диагональное отношение.