1.2.5. Отношения эквивалентности

Рассмотрим три отношения: M, S, H. ОтношениеМописано в 1.2.4. ОтношениеS введем на множествеXвсех треугольников следующим образом: этому отношению принадлежат пары треугольников такие, что площадь треугольникаx равна площади треугольникаy.

Отношение Ндействует на множестве жителей г. Томска и содержит парытакие, чтохиуносят шляпы одинакового размера.

Свойства этих трех отношений приведены в таблице 1.3, где Розначает рефлексивность,АР– антирефлексивность,С– симметричность, АС - антисимметричность,НС– несимметричность,Т– транзитивность отношения. В качестве упражнения проверьте правильность заполнения таблицы, пользуясь определениями свойств бинарных отношений.

Таблица 1.3

Свойства отношений

Отношение	Р	АР	С	АС	НС	Т
М	+	-	+	-	-	+
S	+	-	+	-	-	+
H	+	-	+	-	-	+

Мы видим, что отношения обладают одинаковыми свойствами, поэтому их относят к одному типу.

Определение. ОтношениеRна множествеХ называется отношениемэквивалентности,если оно обладает свойствами рефлексивности, симметричности, транзитивности.

Таким образом, отношения M, S, H являются отношениями эквивалентности на соответствующих множествахХ. Важной особенностью отношений эквивалентности является то, что они разбивают все множествоХна непересекающиеся подмножества – классы эквивалентности.

Определение.Классом эквивалентности, порожденным элементом, называется подмножество множестваХ, для элементов которого выполняется условие. Таким образом, класс эквивалентности .

Так, отношение Мразбивает множествона три класса эквивалентности:. Класс, порожденный элементом 4, совпадает с классом [1]; [5] = [2], [3] = [6], [7] = [1].

Классы эквивалентности образуют систему непустых непересекающихся подмножеств множества Х, в объединении дающую все множествоХ– т.е. образуют разбиение множестваХ(см. 1.1.6).

Отношение эквивалентности обозначают “ “, поэтому определение класса эквивалентности можно записать так: .

Множество различных классов эквивалентности множества Xпо отношениюRназываетсяфактор-множествоми обозначается. Так, для отношенияMфактор-множество состоит из трех элементов:

.

Теорема 1.ПустьR– отношение эквивалентности на множествеX и - совокупность всех различных классов эквивалентности по отношениюR. Тогда- разбиение множестваX.

Доказательство. По условию теоремыR– отношение эквивалентности, т.е. рефлексивно, симметрично и транзитивно. Покажем, что- разбиение множестваX, т.е.

а) ;

б) ;

в) ,.

Условие авыполняется по определению класса эквивалентности и по свойству рефлексивности, т.к.для любого.

Условие бвыполняется, так как каждый элемент множестваXпопадает в какой-либо класс эквивалентности и.

Условие вдокажем методом “от противного”. Пустьи- разные классы эквивалентности (т.е.иотличаются хотя бы одним элементом). Покажем, что они не пересекаются. Предположим противное: найдется элементтакой, чтои. По определению класса эквивалентностии. По свойствам симметричности и транзитивности отношенияRимеем:и- отсюда следует равенство множестви.

Действительно, возьмем произвольный элемент

в силу произвольностиaследует. Возьмем произвольный элемент:- в силу произвольностиbследует. По определению равенства множеств.

Условие вдоказано: если классы эквивалентности не совпадают, то они не пересекаются.

Следовательно, фактор-множество является разбиением множестваX.

Теорема 2. Всякое разбиение множестваX порождает наXотношение эквивалентности.

Доказательство. Пусть- разбиение множестваX. Рассмотрим наXотношениенайдетсяи.

Покажем, что R– отношение эквивалентности.

Рефлексивность отношения Rследует из условия. Каждый элемент множестваXпопадает в одно из множеств, поэтому.

Покажем, что отношение Rсимметрично. Пусть. Это означает, что

ии.

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

Отношение Rобладает свойствами рефлексивности, симметричности, транзитивности, т.е. является отношением эквивалентности. Теорема доказана.