Курсовая работа: Отношения эквивалентности и толерантности и их свойства

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

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

Пусть – сюръективное отображение множества на некоторое множество . Рассмотрим на множестве отношение "иметь общий образ" и обозначим это отношение . Иначе говоря, , если . Обозначим через множество всех элементов , имеющих данный образ , т.е. таких, что . Ясно, что , так как любой элемент из имеет образ. Далее, при разных и , , так как иначе элемент, попавший в пересечение , имел бы два разных образа: и . Поскольку сюръективно, для любого . Итак, множества образуют разбиение множества , а отношение есть эквивалентность, соответствующая этому разбиению. Последнее следует из того, что тогда и только тогда, когда и принадлежат общему, множеству .

Множество классов эквивалентности по отношению принято обозначать (читается: фактормножество множества по отношению ). Наши рассуждения показывают, что для всякого сюръективного отображения существует отношение эквивалентности на множестве такое, что и могут быть поставлены во взаимно-однозначное соответствие.

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

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

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

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

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

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

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

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

Таким образом, соотношение выполнено в следующих случаях: 1) , и ; 2) , и ;

1.2.3 Теорема

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

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

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

1.2.4 Теорема

Если отношения и рефлексивны и симметричны (в частности, являются эквивалснтиостями), то их прямая сумма также рефлексивна и симметрична.

Замечание. Если , то каждое из отношений и есть сужение отношения на свою область задания.

1.3 Операции над эквивалентностями

Посмотрим, какие операции над отношениями эквивалентности и при каких условиях дают в результате эквивалентность.

Транзитивное замыкание отношения эквивалентности является отношением эквивалентности.

Отношение, обратное к эквивалентности, является эквивалентностью.

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

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

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

Теперь попробуем разобраться, когда объединение эквивалентностей дает в результате эквивалентно