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

Замечание. Из этого доказательства видно, что условие непустоты пересечения работало только при проверке транзитивности. Значит, справедлива.

1.2.4 Теорема

Если отношения

и

рефлексивны и симметричны (в частности, являются эквивалснтиостями), то их прямая сумма

также рефлексивна и симметрична.

Замечание. Если

, то каждое из отношений и есть сужение отношения на свою область задания.

1.3 Операции над эквивалентностями

Посмотрим, какие операции над отношениями эквивалентности и при каких условиях дают в результате эквивалентность.

Транзитивное замыкание

отношения эквивалентности является отношением эквивалентности.

Отношение, обратное к эквивалентности, является эквивалентностью.

Если

и – эквивалентности, то их пересечение также является отношением эквивалентности.

Сложнее обстоит дело с объединением отношений эквивалентности. Вообще говоря, объединение эквивалентностей уже не обязано быть эквивалентностью.

Действительно, отношение

дает разбиение на два класса и , отношению соответствует разбиение , а отношение дает неполный связный граф.

Теперь попробуем разобраться, когда объединение эквивалентностей дает в результате эквивалентность. Пусть

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

Рассмотрим более общий случай, когда множество

можно разбить на два непересекающихся подмножества и (из которых одно может быть пустым) так что

и при этом

В этом случае отношения

и мы назовем когерентными.

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

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

Из следует, что для когерентных отношении эквивалентности

и : и . Используя определение прямой суммы и , получаем . Здесь и – эквивалентности (как сужения эквивалентиостей и ), а , и не пересекаются. По теореме 1.2.3 отсюда следует, что есть отношение эквивалентности.

Оказывается, когерентность отношений

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

1.3.2 Теорема

Для того чтобы объединение

эквивалентностсй

и

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

и

были когерентными.

Нам понадобятся некоторые простые свойства разбиений на классы эквивалентности, которые мы сформулируем в виде самостоятельных лемм. Мы будем далее использовать некоторые словесные сокращения. Если

– эквивалентность и , то мы будем говорить, что и

-эквивалентны. Разбиение, соответствующее эквивалентности , мы будем называть

-разбиением;

-классами и т.п.