85976 (612617), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Для завершении доказательства достаточно заметить, что эквивалентность элементов и означает попадание в общий класс, т.е. совпадение первых номеров (первых признаков).

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

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

Вернемся к обсуждению отношения : " является эталоном для ". Мы уже дали конструктивное определение этого отношения. Из него легко можно получить следующие свойства отношения (быть эталоном):

1) для всякого существует эталон : .

2) Если , то , т.е. любой эталон есть эталон для самого себя.

3) Эталон единствен, т.е. из и следует .

Эти три свойства можно объявить аксиомами отношения "быть эталоном". Покажем, что из них следует определение эталона с помощью разбиения. Для этого сначала по отношению построим новое отношение , определяемое правилом: , если и имеют общий эталон. Иначе говоря, если существует такое , что и . Покажем, что есть отношение эквивалентности. Действительно, по свойству 1) у каждого есть эталон и, стало быть, . Значит, рефлексивно. Симметричность отношения очевидна. Если и , то это значит, что и имеют общий эталон, а не может иметь эталона, отличного от эталона для . Значит, .

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2.3 Теорема

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

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

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

1.2.4 Теорема

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

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

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

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

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

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

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

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

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

Теперь попробуем разобраться, когда объединение эквивалентностей дает в результате эквивалентность. Пусть , тогда из свойств теоретикомножественных операций следует , т.е. есть эквивалентность. Точно так же, если , то является эквивалентностью.

Рассмотрим более общий случай, когда множество можно разбить на два непересекающихся подмножества и (из которых одно может быть пустым) так что

11()

и при этом

22()

В этом случае отношения и мы назовем когерентными.

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

Из 2 следует, что для когерентных отношении эквивалентности и : и . Используя определение прямой суммы и 23, получаем . Здесь и – эквивалентности (как сужения эквивалентиостей и ), а , и не пересекаются. По теореме 1.2.3 отсюда следует, что есть отношение эквивалентности.

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

1.3.2 Теорема

Для того чтобы объединение эквивалентностсй и само было отношением эквивалентности, необходимо и достаточно, чтобы и были когерентными.

Характеристики

Список файлов курсовой работы