Посмотрим, какие операции над отношениями эквивалентности и при каких условиях дают в результате эквивалентность.
Транзитивное замыкание 
отношения эквивалентности 
является отношением эквивалентности.
Отношение, обратное к эквивалентности, является эквивалентностью.
Если 
и 
– эквивалентности, то их пересечение 
также является отношением эквивалентности.
Сложнее обстоит дело с объединением отношений эквивалентности. Вообще говоря, объединение эквивалентностей уже не обязано быть эквивалентностью.
Действительно, отношение дает разбиение на два класса 
и 
, отношению соответствует разбиение 
, а отношение дает неполный связный граф.
Теперь попробуем разобраться, когда объединение эквивалентностей дает в результате эквивалентность. Пусть 
, тогда из свойств теоретикомножественных операций следует 
, т.е. 
есть эквивалентность. Точно так же, если 
, то является эквивалентностью.
Рассмотрим более общий случай, когда множество 
можно разбить на два непересекающихся подмножества 
и 
(из которых одно может быть пустым) так что
и при этом
В этом случае отношения и мы назовем когерентными.
Легко видеть, что если или 
, то отношения и 
когерентны (надо положить 
, 
). Таким образом, сравнимость относительно "порядка", задаваемого включением, есть частный случай когерентности.
Из следует, что для когерентных отношении эквивалентности и : 
и 
. Используя определение прямой суммы и , получаем 
. Здесь 
и 
– эквивалентности (как сужения эквивалентиостей 
и 
), а 
, и 
не пересекаются. По теореме 1.2.3 отсюда следует, что 
есть отношение эквивалентности.
Оказывается, когерентность отношений , является не только достаточным, но и необходимым условием для того, чтобы объединение эквивалентностей и было эквивалентностью.
Теорема
Для того чтобы объединение 
эквивалентностсй и само было отношением эквивалентности, необходимо и достаточно, чтобы и были когерентными.
Нам понадобятся некоторые простые свойства разбиений на классы эквивалентности, которые мы сформулируем в виде самостоятельных лемм. Мы будем далее использовать некоторые словесные сокращения. Если – эквивалентность и 
, то мы будем говорить, что 
и 
-эквивалентны. Разбиение, соответствующее эквивалентности , мы будем называть -разбиением; -классами и т.п.
Лемма. Для того чтобы 
, необходимо и достаточно, чтобы каждый -класс содеожался в некотором -классе.
Действительно, если , то из следует 
. Зчачит, множество всех , -эквивалентных элементу , содержится во множестве всех , -эквивалентных этому . Обратный вывод столь же очевиден.
Для того чтобы 
необходимо и достаточно, чтобы каждый -класс 
содержал любой -класс 
, имеющий с 
непустое пересечение.
Для доказательства необходимости выберем произвольный элемент 
. По предыдущей лемме целиком содержится в некотором классе 
. Но если бы 
был бы отличен от , то элемент был бы сразу в двух классах -разбиения, что невозможно. Значит, 
. Для доказательства достаточности нужно только вспомнить, что из 
по условию вытекает , и применить лемму 1.3.1.
Для того чтобы эквивалентности и были когерентными, необходимо и достаточно, чтобы всякий -класс либо содержался в некотором -классе 
, либо целиком содержал любой -класс , имеющий с непустое пересечение.
Доказательство. Eсли и когерентны, то 
, 
и на , имеем , а на 
. Тогда по лемме 1.3.1 для каждого класса , содержащегося в , существует такой класс 
, что 
. По лемме 1.3.2 каждый класс , содержащийся в , целиком содержит любой класс , имеющий с непустое пересечение. Поскольку и не пересекаются, из вытекает, что всякий класс эквивалентности содержится либо в , либо в ; значит, наше рассуждение охватывает все классы.
Проведем доказательство в обратную сторону. Пусть каждый класс обладает сформулированным в лемме 1.2.3 свойством. Обозначим через объединение всех тех классов 
, для которых существует такой , что 
, а через – объединение остальных классов . Ясно, что , 
и 
, 
, где 
и 
– сужения отношений и на 
. Наконец, очевидно, что 
и 
, т.е. и когерентны.
Теперь мы подготовили все необходимое для доказательства теоремы 1.3.1. Будем вести доказательство от противного, т.е. предположим, что и не когерентны. Тогда по лемме 1.3.3 существует класс и класс такиее, что 
, но не один из них не содержит другой. Значит, существуетвует 
, существует 
, существует 
. Имеем следующие соотношения: 
и 
, следовательно, 
и 
. По транзитивности должно было бы быть также 
. Однако, соотношения: 
и 
– оба не выполнены, так как не лежит с 
ни в общем -классе, ни в общем -классе. Значит, соотношение не выполнено. Полученное противоречие доказывает теорему.
Замечание. Понятие когерентности имеет смысл для любых отношений и . Но для эквивалентностей когерентность отношений и легко формулируется в терминах классов эквивалентности (лемма 1.3.3).
Лемма
Если и рефлексивны, то
Доказательство. Если , то, в силу 
, выполнено и соотношение 
, т.е. 
. Аналогично получается 
. Из этих двух включений следует .
Теорема. Для того чтобы объединение эквивалентностей и само было отношением эквивалентности, необходимо и достаточно, чтобы
Доказательство. Пусть – эквивалентность. По лемме 1.3.4 выполняется . Для доказательства остается доказать
Пусть 
. Тогда для некоторого имеем и 
. Следовательно, 
и 
. Значит, 
и доказано. Пусть теперь выполнено . Отношение симметрично. По тогда симметрично и ортношение 
. 
. По теореме 1.3.3 (см. ниже) получаем, что отношение – эквивалентность. Из вытекает, что и – эквивалентность. Теорема доказана.
Условие, при котором произведение двух отношений эквивалентности и само является эквивалентностью, было получено чешским математиком Шиком в 1954 г.
Для того чтобы произведение отношений эквивалентности и было эквивалентностью, необходимо и достаточно, чтобы и коммутировали.
Доказательство. Пусть сначала
рефлексивно. симметрично. Транзитивность произведения доказывается так: 
– здесь мы использовали ассоциативный закон для произведения отношений, условие , а также транзитивность и рефлексивность отношений и . Итак 
, но это и означает транзитивность отношения , поскольку рефлексивно. Пусть теперь произведение есть эквивалентность. Тогда 
.
Легко проверить, что если и – эквивалентности, то 
и 
также будут эквивалентностями.
Оказывается, операция (ее иногда называют, объединением эквивалентностей, имея в виду, что обычное объединение эквивалентностей может не быть эквивалентностью) ассоциативна, т.е. является "хорошей" алгебраической операцией.
Для любых транзитивных отношений , и 
справедлив ассоциативный закон:
Докажем сначала две леммы.
Лемма
Для любых отношений 
, 
вытекает из 
. доказывается аналогично.
Лемма
Для любых транзитивных отношений 
, 
, 
из 
и 
вытекает 
.
Доказательство теоремы 1.3.4. Из леммы 1.3.5
Из и
Из леммы 1.3.5
Из , , леммы 1.3.5 и того, что любое отношение вида 
транзитивно,
Подобно тому как доказывается , доказывается
Подобно тому как мы из и вывели , из и выводится
Из и аналогично доказываемого "обратного" включения вытекает . Теорема доказана.
Нетрудно убедиться, что для любой эквивалентности 
где 
– диагональное отношение.
Покажем теперь, что операция 
не дает ничего нового:
Если 
и 
– эквивалентности, то
Доказательство. Заметим сначала, что, учитывая лемму 1.3.4, 
Применяя транзитивное замыкание к обеим частям, ввиду свойства монотонности транзитивного замыкания имеем
Далее, применяя распределительный закон получим
Мы использовали здесь тот факт, что для рефлексивного выполнено включение 
, а следовательно, 
. Запишем теперь выражение для транзитивного замыкания, используя :
Отсюда ясно, что 
, т.е.
Сравнивая включения и получим искомое соотношение .
Отсюда вытекает следующий результат, также принадлежащий Шику:
Теорема
Если и – эквивалентности и 
, то
В самом деле, по теореме 1.3.3 произведение 
является эквивалентностью, а стало быть отношение 
совпадает со своим транзитивным замыканием 
. Но тогда из теоремы 1.3.5 следует .
Дата: 2019-07-30, просмотров: 241.
