Отношения эквивалентности и толерантности и их свойства
Из
сказанного
видно также,
что условие
рефлексивности
можно в определении
эквивалентности
заменить более
слабым. Достаточно
потребовать,
чтобы для каждого
существовал
такой элемент
,
что выполнено
либо
,
либо
.
Тогда из этого
свойства, а
также симметричности
и транзитивности
можно получить
рефлексивность
отношения
.
Граф,
изображающий
отношение
эквивалентности,
выглядит следующим
образом. Пусть
– множество
его вершин.
Тогда
,
где
– классы эквивалентности.
Ясно, что в каждом
подмножестве
все вершины
соединены друг
с другом. Но
никакая из них
не соединена
с вершинами,
не входящими
в
.
Итак, граф,
изображающий
отношение
эквивалентности,
состоит из
отдельных, не
связанных друг
с другом полных
подграфов.
Прямой
суммой отношений
и
называется
отношение
.
Прямую сумму
отношений
,
мы будем обозначать
через
.
Таким
образом, соотношение
выполнено в
следующих
случаях: 1)
,
и
;
2)
,
и
;
1.2.3 Теорема
Если
,
а отношения
и
– эквивалентности,
то их прямая
сумма
также является
эквивалентностью.
Доказательство.
Рефлексивность
проверяется
просто: если
,
то выполнено
и, следовательно,
.
Симметричность
также очевидна:
если выполнено
,
то либо
и
входят в
и
,
а значит, и
,
т.е.
,
либо
и
входят в
и
,
поэтому
и
.
Докажем транзитивность
отношения
.
Пусть выполнены
соотношения
и
.
Рассмотрим
случай, когда
и
.
Так как
,
то
не входит в
.
Но тогда соотношение
может выполняться
только при
и
.
Однако, из
и
вытекает
и
.
Случай, когда
и
принадлежат
,
исследуется
аналогично.
Теорема доказана.
Замечание. Из этого доказательства видно, что условие непустоты пересечения работало только при проверке транзитивности. Значит, справедлива.
1.2.4 Теорема
Если
отношения
и
рефлексивны
и симметричны
(в частности,
являются
эквивалснтиостями),
то их прямая
сумма
также рефлексивна
и симметрична.
Замечание.
Если
,
то каждое из
отношений
и
есть сужение
отношения
на свою область
задания.
1.3 Операции над эквивалентностями
Посмотрим, какие операции над отношениями эквивалентности и при каких условиях дают в результате эквивалентность.
Транзитивное
замыкание
отношения
эквивалентности
является отношением
эквивалентности.
Отношение, обратное к эквивалентности, является эквивалентностью.
Если
и
– эквивалентности,
то их пересечение
также является
отношением
эквивалентности.
Сложнее обстоит дело с объединением отношений эквивалентности. Вообще говоря, объединение эквивалентностей уже не обязано быть эквивалентностью.
Действительно,
отношение
дает разбиение
на два класса
и
,
отношению
соответствует
разбиение
,
а отношение
дает неполный
связный граф.
Теперь
попробуем
разобраться,
когда объединение
эквивалентностей
дает в результате
эквивалентность.
Пусть
,
тогда из свойств
теоретикомножественных
операций следует
,
т.е.
есть эквивалентность.
Точно так же,
если
,
то
является
эквивалентностью.
Рассмотрим
более общий
случай, когда
множество
можно разбить
на два непересекающихся
подмножества
и
(из которых
одно может быть
пустым) так что
26
и при этом
26
В
этом случае
отношения
и
мы назовем
когерентными.
Легко
видеть, что
если
или
,
то отношения
и
когерентны
(надо положить
,
).
Таким образом,
сравнимость
относительно
"порядка",
задаваемого
включением,
есть частный
случай когерентности.
Из
Error: Reference source not found следует,
что для когерентных
отношении
эквивалентности
и
:
и
.
Используя
определение
прямой суммы
и Error: Reference source not found, получаем
.
Здесь
и
– эквивалентности
(как сужения
эквивалентиостей
и
),
а
,
и
не пересекаются.
По теореме
1.2.3 отсюда следует,
что
есть отношение
эквивалентности.
Оказывается,
когерентность
отношений
,
является не
только достаточным,
но и необходимым
условием для
того, чтобы
объединение
эквивалентностей
и
было эквивалентностью.
1.3.2 Теорема
Для
того чтобы
объединение
эквивалентностсй
и
само было отношением
эквивалентности,
необходимо
и достаточно,
чтобы
и
были когерентными.
Нам
понадобятся
некоторые
простые свойства
разбиений на
классы эквивалентности,
которые мы
сформулируем
в виде самостоятельных
лемм. Мы будем
далее использовать
некоторые
словесные
сокращения.
Если
– эквивалентность
и
,
то мы будем
говорить, что