Смекни!
smekni.com

Отношения эквивалентности и толерантности и их свойства (стр. 5 из 20)

Сравнивая с соответствующими свойствами, определяющими соотношение "быть эталоном", мы видим, что отображение

множества
на неподвижное подмножество
задает на
отношение
"быть эталоном" так, что
в том и только том случае, когда
.

Посмотрим теперь, что получится, если отказаться от условии, что

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

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

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

Из сказанного видно также, что условие рефлексивности можно в определении эквивалентности заменить более слабым. Достаточно потребовать, чтобы для каждого

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

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

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

Прямой суммой отношений

и
называется отношение
. Прямую сумму отношений
,
мы будем обозначать через
.

Таким образом, соотношение

выполнено в следующих случаях: 1)
,
и
; 2)
,
и
;

1.2.3 Теорема

Если

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

Доказательство. Рефлексивность проверяется просто: если

, то выполнено
и, следовательно,
. Симметричность также очевидна: если выполнено
, то либо
и
входят в
и
, а значит, и
, т.е.
, либо
и
входят в
и
, поэтому
и
. Докажем транзитивность отношения
. Пусть выполнены соотношения
и
. Рассмотрим случай, когда
и
. Так как
, то
не входит в
. Но тогда соотношение
может выполняться только при
и
. Однако, из
и
вытекает
и
. Случай, когда
и
принадлежат
, исследуется аналогично. Теорема доказана.