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

Доказательство второй части. Пусть дано разбиение

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

1.2.2 Теорема

Если

– конечное множество и

– отношение эквивалентности на нем, то существуют такие

и

, что каждому элементу

можно сопоставить кортеж (упорядоченный набор) из

двоичных признаков (нулей или единиц):

,

и т.д., так что 1) разным элементам соответствуют разные кортежи признаков и 2) для того, чтобы было

, необходимо и достаточно, чтобы первые

признаков этих элементов совпадали:

.

Доказательство. Возьмем разбиение

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

Для завершении доказательства достаточно заметить, что эквивалентность элементов

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

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

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

Вернемся к обсуждению отношения

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