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

 

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

Транзитивное замыкание  отношения эквивалентности  является отношением эквивалентности.

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

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

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

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

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

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


   

 

и при этом

 

                       

 

В этом случае отношения  и  мы назовем когерентными.

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

Из следует, что для когерентных отношении эквивалентности  и :  и . Используя определение прямой суммы и , получаем . Здесь  и  – эквивалентности (как сужения эквивалентиостей  и ), а , и  не пересекаются. По теореме 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, просмотров: 106.