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

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

Пусть – отношение эквивалентности, а – такое отношение "быть эталоном", что выполнено в том и только том случае, когда и имеют общий эталон .

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

Рассмотрим в качестве множество всех целых неотрицательных чисел и возьмем его разбиение на множество четных чисел и множество нечетных чисел. Соответствующее отношение эквивалентности на множестве целых чисел обозначается так: и читается: сравнимо с по модулю 2. В качестве эталонов здесь естественно выбрать 0 – для четных чисел и 1 – для нечетных чисел. Аналогично, разбивая то же множество на подмножеств , где состоит из всех чисел, дающих при делении на и остатке , мы придем к отношению эквивалентности: , которое выполняется, если и имеют одинаковый остаток при делении на . В качестве эталона в каждом естественно выбрать соответствующий остаток .

1.2 Формальные свойства эквивалентности

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

1.2.1 Определение

Отношение на множестве называется, эквивалентностью (или отношением эквивалентности ), если оно рефлексивно, симметрично и транзитивно.

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

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

Обратно: если задано разбиение множества и бинарное отношение определено как "принадлежать общему классу разбиения", то рефлексивно, симметрично и транзитивно.

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

Лемма. Для любых и либо , либо .

Доказательство леммы. Пусть пересечение . Покажем, что . Пусть , тогда выполнено и по самому определению множеств и . По симметричности имеем , а по транзитивности из и следует . Возьмем теперь произвольный элемент . По определению . Но из и следует , т.е. . Итак, .

Аналогично показывается, что . Значит . Лемма доказана.

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

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

1.2.2 Теорема

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

Доказательство. Возьмем разбиение множества , соответствующее отношению . В силу конечности множества это разбиение конечно и каждый класс конечен. Перенумеруем элементы каждого класса. Тогда каждому элементу можно сопоставить пару целых чисел: , где – номер класса , в который попал , a – номер элемента в своем классе. Ясно, что если , и , то . Действительно, либо элементы и попали в разные классы – тогда у них различные первые номера; ; либо они различаются номером в классе – тогда . Представим теперь числа и в двоичной системе счисления. Пусть – наибольшее число разрядов у чисел , а – наибольшее число разрядов у чисел . Если некоторое имеет меньше, чем разрядов, то дополним его слева нулями. Так же поступим и со вторыми номерами. Тем самым каждому элементу будет сопоставлен кортеж из двоичных признаков.

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

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

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

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

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

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

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