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

 

Рассмотрим три отношения: 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 обладает свойствами рефлексивности, симметричности, транзитивности, т.е. является отношением эквивалентности. Теорема доказана.