Отношения эквивалентности и толерантности и их свойства
Условие,
при котором
произведение
двух отношений
эквивалентности
и
само является
эквивалентностью,
было получено
чешским математиком
Шиком в 1954 г.
Для
того чтобы
произведение
отношений
эквивалентности
и
было эквивалентностью,
необходимо
и достаточно,
чтобы
и
коммутировали.
Доказательство. Пусть сначала
26
рефлексивно.
симметрично.
Транзитивность
произведения
доказывается
так:
– здесь мы
использовали
ассоциативный
закон для
произведения
отношений,
условие Error: Reference source not found,
а также транзитивность
и рефлексивность
отношений
и
.
Итак
,
но это и означает
транзитивность
отношения
,
поскольку
рефлексивно.
Пусть теперь
произведение
есть эквивалентность.
Тогда
.
Легко
проверить, что
если
и
– эквивалентности,
то
и
также будут
эквивалентностями.
Оказывается,
операция
(ее иногда называют,
объединением
эквивалентностей,
имея в виду,
что обычное
объединение
эквивалентностей
может не быть
эквивалентностью)
ассоциативна,
т.е. является
"хорошей"
алгебраической
операцией.
Для
любых транзитивных
отношений
,
и
справедлив
ассоциативный
закон:
26
Докажем сначала две леммы.
1.3.5 Лемма
Для
любых отношений
,
![]()
26
26
Error: Reference source not found вытекает
из
.
Error: Reference source not found доказывается
аналогично.
1.3.5 Лемма
Для
любых транзитивных
отношений
,
,
из
и
вытекает
.
Доказательство теоремы 1.3.4. Из леммы 1.3.5
26
26
Из Error: Reference source not found и Error: Reference source not found
26
Из леммы 1.3.5
26
Из
Error: Reference source not found, Error: Reference source not found,
леммы 1.3.5 и того,
что любое отношение
вида
транзитивно,
26
Подобно тому как доказывается Error: Reference source not found, доказывается
26
Подобно тому как мы из Error: Reference source not found и Error: Reference source not found вывели Error: Reference source not found, из Error: Reference source not found и Error: Reference source not found выводится
26
Из Error: Reference source not found и аналогично доказываемого "обратного" включения вытекает Error: Reference source not found. Теорема доказана.
Нетрудно
убедиться, что
для любой
эквивалентности
![]()
26
где
– диагональное
отношение.
Покажем
теперь, что
операция
не дает ничего
нового:
Если
и
– эквивалентности,
то
26
Доказательство.
Заметим сначала,
что, учитывая
лемму 1.3.4,
Применяя транзитивное
замыкание к
обеим частям,
ввиду свойства
монотонности
транзитивного
замыкания имеем
26
Далее, применяя распределительный закон получим
26
Мы
использовали
здесь тот факт,
что для рефлексивного
выполнено
включение
,
а следовательно,
.
Запишем теперь
выражение для
транзитивного
замыкания,
используя Error: Reference source not found:
![]()
Отсюда
ясно, что
,
т.е.
26
Сравнивая включения Error: Reference source not found и Error: Reference source not found получим искомое соотношение Error: Reference source not found.
Отсюда вытекает следующий результат, также принадлежащий Шику:
1.3.6 Теорема
Если
и
– эквивалентности
и
,
то
26
В
самом деле, по
теореме 1.3.3 произведение
является
эквивалентностью,
а стало быть
отношение
совпадает со
своим транзитивным
замыканием
.
Но тогда из
теоремы 1.3.5 следует
Error: Reference source not found.
1.4 Отношения эквивалентности на числовой прямой
Пусть
задано отношение
на множестве
.
В случае, когда
– числовая
прямая, отношение
отождествляется
с некоторым
подмножеством
числовой плоскости,
т.е. прямого
произведения
.
В этом параграфе
будут рассмотрены
геометрические
свойства множества
на плоскости
в случае, когда
отношение
есть эквивалентность.
Согласно
определению
1.2.1 отношение
называется
эквивалентностью,
если оно рефлексивно,
симметрично
и транзитивно.
Каждое из этих
свойств порождает
некоторое
геометрическое
свойство множества
.
Координаты
точки на плоскости
будем обозначать
.
1.
Рефлексивность.
Из того, что
для всех
,
следует, что
множество
содержит главную
диагональ
(свойство
).
2.
Симметричность.
Симметричность
означает, что
если
,
то и
,
т.е. что множество
симметрично
относительно
главной диагонали
(свойство
).
3.
Транзитивность.
Транзитивность
означает, что
если
и
,
то и
.
Точка
является четвертой
вершиной
прямоугольника,
три вершины
которого находятся
в точках
и
.
Заметим, что
вершина
лежит на биссектрисе
координатного
угла – главной
диагонали
координатной
плоскости.
Поэтому геометрически
свойство
транзитивности
можно сформулировать
следующим
образом:
Множество
на плоскости
определяет
транзитивное
отношение тогда
и только тогда,
когда для любого
прямоугольника,
одна вершина
которого
лежит на главной
диагонали, а
две соседние
с
вершины принадлежат
,
вершина
,
противоположная
,
также принадлежит
(свойство
).
Замечание.
Если отношение
является
симметричным,
то геометрическая
формулировка
транзитивности
несколько
упрощается.
А именно:
Множество
на плоскости,
симметричное
относительно
главной диагонали,
определяет
транзитивное
отношение тогда
и только тогда,
когда для любого
прямоугольника,
одна вершина
которого лежит
на главной
диагонали, а
две другие
принадлежат
,
четвертая
вершина также
принадлежит
(свойство
).
Разница
с предыдущим
утверждением
состоит в том,
что вершины,
принадлежащие