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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2.3 Теорема

Если

, а отношения

и

– эквивалентности, то их прямая сумма

также является эквивалентностью.

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

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