Операции над эквивалентностями
Посмотрим, какие операции над отношениями эквивалентности и при каких условиях дают в результате эквивалентность. Транзитивное замыкание отношения эквивалентности является отношением эквивалентности. Отношение, обратное к эквивалентности, является эквивалентностью. Если и – эквивалентности, то их пересечение также является отношением эквивалентности. Сложнее обстоит дело с объединением отношений эквивалентности. Вообще говоря, объединение эквивалентностей уже не обязано быть эквивалентностью. Действительно, отношение дает разбиение на два класса и , отношению соответствует разбиение , а отношение дает неполный связный граф. Теперь попробуем разобраться, когда объединение эквивалентностей дает в результате эквивалентность. Пусть , тогда из свойств теоретикомножественных операций следует , т.е. есть эквивалентность. Точно так же, если , то является эквивалентностью. Рассмотрим более общий случай, когда множество можно разбить на два непересекающихся подмножества и (из которых одно может быть пустым) так что
и при этом
В этом случае отношения и мы назовем когерентными. Легко видеть, что если или , то отношения и когерентны (надо положить , ). Таким образом, сравнимость относительно "порядка", задаваемого включением, есть частный случай когерентности. Из следует, что для когерентных отношении эквивалентности и : и . Используя определение прямой суммы и , получаем . Здесь и – эквивалентности (как сужения эквивалентиостей и ), а , и не пересекаются. По теореме 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 следует .
Популярное: Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (555)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |