Отношения эквивалентности и толерантности и их свойства (стр. 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 и того, что любое отношение вида

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

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

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

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

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

где

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