Отношения эквивалентности и толерантности и их свойства
Итак,
доказано, что
есть отношение
эквивалентности.
Но тогда по
теореме 1.2.1 существует
разбиение
множества
на классы
эквивалентных
друг другу
элементов –
так называемые
классы эквивалентности.
Очевидно,
каждый класс
эквивалентности
состоит из всех
элементов,
имеющих общий
эталон
.
По свойству
2)
и, значит,
.
Таким образом,
отношение
,
определенное
аксиоматически
свойствами
1) – 3), всегда может
быть задано
разбиением
с выбранными
представителями
(эталонами) в
каждом классе.
Пусть
– сюръективное
отображение
множества
на некоторое
множество
.
Рассмотрим
на множестве
отношение
"иметь общий
образ" и обозначим
это отношение
.
Иначе говоря,
,
если
.
Обозначим через
множество всех
элементов
,
имеющих данный
образ
,
т.е. таких, что
.
Ясно, что
,
так как любой
элемент из
имеет образ.
Далее, при разных
и
,
,
так как иначе
элемент, попавший
в пересечение
,
имел бы два
разных образа:
и
.
Поскольку
сюръективно,
для любого
.
Итак, множества
образуют разбиение
множества
,
а отношение
есть эквивалентность,
соответствующая
этому разбиению.
Последнее
следует из
того, что
тогда и только
тогда, когда
и
принадлежат
общему, множеству
.
Множество
классов эквивалентности
по отношению
принято обозначать
(читается:
фактормножество
множества
по отношению
).
Наши рассуждения
показывают,
что для всякого
сюръективного
отображения
существует
отношение
эквивалентности
на множестве
такое, что
и
могут быть
поставлены
во взаимно-однозначное
соответствие.
Наоборот,
если имеется
произвольное
отношение
эквивалентности
на
,
то по нему можно
построить
отображение
,
где
и
есть класс
эквивалентности,
содержащий
.
Легко проверить,
что
сюръективно
и построенное
по этому отображению
отношение
эквивалентности
есть исходное
отношение
.
Рассмотрим
частный случай,
когда
и
.
Пусть, далее,
отображение
обладает тем
свойством, что,
при
,
или, как говорят
в таких случаях,
подмножество
неподвижно
при отображении
.
Отсюда видно,
что
сюръективно.
Действительно,
всякий
есть образ по
крайней мере
самого
:
.
Итак, каждому
однозначно
сопоставлен
некоторый
элемент
.
При этом, если
сопоставлен
какому-то элементу,
то самому
сопоставлен
он же.
Сравнивая
с соответствующими
свойствами,
определяющими
соотношение
"быть эталоном",
мы видим, что
отображение
множества
на неподвижное
подмножество
задает на
отношение
"быть эталоном"
так, что
в том и только
том случае,
когда
.
Посмотрим
теперь, что
получится, если
отказаться
от условии, что
определено
на всем
.
Рассмотрим
функцию
,
которая некоторым
элементам
из
сопоставляет
единственный
образ
из
.
По отображению
можно опять-таки
построить
отношение
по правилу:
,
если
.
Легко проверить,
что
будет симметрично
и транзитивно.
Выберем подмножество
,
состоящее из
тех элементов,
на которых
определено
отображение
.
Тогда если либо
,
либо
не принадлежат
,
то
заведомо не
выполняется.
Значит, если
не входит в
,
то
также не выполнено.
Следовательно,
отношение
теперь уже не
обязано быть
рефлексивным.
Видно,
как построить
пример симметричного
и транзитивного,
но не рефлексивного
отношения.
Пусть
– множество
людей, а отношение
означает "быть
уроженцем
одного города".
Легко видеть,
что
симметрично
и транзитивно,
но если
родился не в
городе, а в деревне,
или, вообще, во
время путешествия
по морю, то
не выполнено.
В этом примере