85976 (Отношения эквивалентности и толерантности и их свойства), страница 3

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

Лемма. Для того чтобы , необходимо и достаточно, чтобы каждый -класс содеожался в некотором -классе.

Действительно, если , то из следует . Зчачит, множество всех , -эквивалентных элементу , содержится во множестве всех , -эквивалентных этому . Обратный вывод столь же очевиден.

Для того чтобы необходимо и достаточно, чтобы каждый -класс содержал любой -класс , имеющий с непустое пересечение.

Для доказательства необходимости выберем произвольный элемент . По предыдущей лемме целиком содержится в некотором классе . Но если бы был бы отличен от , то элемент был бы сразу в двух классах -разбиения, что невозможно. Значит, . Для доказательства достаточности нужно только вспомнить, что из по условию вытекает , и применить лемму 1.3.1.

Для того чтобы эквивалентности и были когерентными, необходимо и достаточно, чтобы всякий -класс либо содержался в некотором -классе , либо целиком содержал любой -класс , имеющий с непустое пересечение.

Доказательство. Eсли и когерентны, то , и на , имеем , а на . Тогда по лемме 1.3.1 для каждого класса , содержащегося в , существует такой класс , что . По лемме 1.3.2 каждый класс , содержащийся в , целиком содержит любой класс , имеющий с непустое пересечение. Поскольку и не пересекаются, из 1 вытекает, что всякий класс эквивалентности содержится либо в , либо в ; значит, наше рассуждение охватывает все классы.

Проведем доказательство в обратную сторону. Пусть каждый класс обладает сформулированным в лемме 1.2.3 свойством. Обозначим через объединение всех тех классов , для которых существует такой , что , а через – объединение остальных классов . Ясно, что , и , , где и – сужения отношений и на . Наконец, очевидно, что и , т.е. и когерентны.

Теперь мы подготовили все необходимое для доказательства теоремы 1.3.1. Будем вести доказательство от противного, т.е. предположим, что и не когерентны. Тогда по лемме 1.3.3 существует класс и класс такиее, что , но не один из них не содержит другой. Значит, существуетвует , существует , существует . Имеем следующие соотношения: и , следовательно, и . По транзитивности должно было бы быть также . Однако, соотношения: и – оба не выполнены, так как не лежит с ни в общем -классе, ни в общем -классе. Значит, соотношение не выполнено. Полученное противоречие доказывает теорему.

Замечание. Понятие когерентности имеет смысл для любых отношений и . Но для эквивалентностей когерентность отношений и легко формулируется в терминах классов эквивалентности (лемма 1.3.3).

1.3.4 Лемма

Если и рефлексивны, то

33()

Доказательство. Если , то, в силу , выполнено и соотношение , т.е. . Аналогично получается . Из этих двух включений следует 3.

Теорема. Для того чтобы объединение эквивалентностей и само было отношением эквивалентности, необходимо и достаточно, чтобы

44()

Доказательство. Пусть – эквивалентность. По лемме 1.3.4 выполняется 3. Для доказательства 4 остается доказать

55()

Пусть . Тогда для некоторого имеем и . Следовательно, и . Значит, и 5 доказано. Пусть теперь выполнено 4. Отношение симметрично. По 4 тогда симметрично и ортношение . . По теореме 1.3.3 (см. ниже) получаем, что отношение – эквивалентность. Из 4 вытекает, что и – эквивалентность. Теорема доказана.

Условие, при котором произведение двух отношений эквивалентности и само является эквивалентностью, было получено чешским математиком Шиком в 1954 г.

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

Доказательство. Пусть сначала

66()

рефлексивно. симметрично. Транзитивность произведения доказывается так: – здесь мы использовали ассоциативный закон для произведения отношений, условие 6, а также транзитивность и рефлексивность отношений и . Итак , но это и означает транзитивность отношения , поскольку рефлексивно. Пусть теперь произведение есть эквивалентность. Тогда .

Легко проверить, что если и – эквивалентности, то и также будут эквивалентностями.

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

Для любых транзитивных отношений , и справедлив ассоциативный закон:

77()

Докажем сначала две леммы.

1.3.5 Лемма

Для любых отношений ,

88()

99()

8 вытекает из . 9 доказывается аналогично.

1.3.5 Лемма

Для любых транзитивных отношений , , из и вытекает .

Доказательство теоремы 1.3.4. Из леммы 1.3.5

1010()

1111()

Из 10 и 11

1212()

Из леммы 1.3.5

1313()

Из 12, 13, леммы 1.3.5 и того, что любое отношение вида транзитивно,

1414()

Подобно тому как доказывается 12, доказывается

1515()

Подобно тому как мы из 13 и 13 вывели 14, из 14 и 15 выводится

1616()

Из 16 и аналогично доказываемого "обратного" включения вытекает 7. Теорема доказана.

Нетрудно убедиться, что для любой эквивалентности

1717()

где – диагональное отношение.

Покажем теперь, что операция не дает ничего нового:

Если и – эквивалентности, то

1818()

Доказательство. Заметим сначала, что, учитывая лемму 1.3.4, Применяя транзитивное замыкание к обеим частям, ввиду свойства монотонности транзитивного замыкания имеем

1919()

Далее, применяя распределительный закон получим

2020()

Мы использовали здесь тот факт, что для рефлексивного выполнено включение , а следовательно, . Запишем теперь выражение для транзитивного замыкания, используя 20:

Отсюда ясно, что , т.е.

2121()

Сравнивая включения 19 и 21 получим искомое соотношение 18.

Отсюда вытекает следующий результат, также принадлежащий Шику:

1.3.6 Теорема

Если и – эквивалентности и , то

2222()

В самом деле, по теореме 1.3.3 произведение является эквивалентностью, а стало быть отношение совпадает со своим транзитивным замыканием . Но тогда из теоремы 1.3.5 следует 22.

1.4 Отношения эквивалентности на числовой прямой

Пусть задано отношение на множестве . В случае, когда – числовая прямая, отношение отождествляется с некоторым подмножеством числовой плоскости, т.е. прямого произведения . В этом параграфе будут рассмотрены геометрические свойства множества на плоскости в случае, когда отношение есть эквивалентность.

Согласно определению 1.2.1 отношение называется эквивалентностью, если оно рефлексивно, симметрично и транзитивно. Каждое из этих свойств порождает некоторое геометрическое свойство множества . Координаты точки на плоскости будем обозначать .

1. Рефлексивность. Из того, что для всех , следует, что множество содержит главную диагональ (свойство ).

2. Симметричность. Симметричность означает, что если , то и , т.е. что множество симметрично относительно главной диагонали (свойство ).

3. Транзитивность. Транзитивность означает, что если и , то и . Точка является четвертой вершиной прямоугольника, три вершины которого находятся в точках и . Заметим, что вершина лежит на биссектрисе координатного угла – главной диагонали координатной плоскости. Поэтому геометрически свойство транзитивности можно сформулировать следующим образом:

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

Замечание. Если отношение является симметричным, то геометрическая формулировка транзитивности несколько упрощается. А именно:

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

Разница с предыдущим утверждением состоит в том, что вершины, принадлежащие , не обязаны быть соседними с вершиной, лежащей на диагонали. Покажем, что для симметричного свойство , влечет . Пусть, например, вершина, лежащая на диагонали, имеет координаты и и ; покажем, что . В самом деле, в силу симметрии, вместе с имеем . Если в качестве вершины на диагонали взять теперь , а в качестве соседних с ней вершин, принадлежащих , и , то, в силу свойства получаем .