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

ОПРЕДЕЛЕНИЕ

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

В случае если r — отношение эквивалентности и a r b, то элементы a и b именуются эквивалентными в этом отношении либо легко эквивалентными.

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

Для представления основного свойства взаимоотношений эквивалентности введем понятие разбиения множества.

ОПРЕДЕЛЕНИЕ

Разбиением множества A именуется конечное либо нескончаемое семейство множеств Ai, i I I таких, что:

1)iII(Ai ¹ );

2) i,jII(i j ? Ai C Aj = );

3) Ai = A .

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

Пускай A1, … , Ak, . . . — разбиение множества A. Нетрудно проверить, что отношение r на множестве A, определяемое соотношением: ar b , есть отношением эквивалентности.

Следующая теорема говорит о том, что справедливо и обратное свойство.

ТЕОРЕМА 3.2

Всякое отношение эквивалентности на множестве A разбивает это множество на классы эквивалентных элементов.

Подтверждение

Разобьем подтверждение теоремы на пара этапов.

1. Построение разбиения, порождаемого отношением r.

Пускай r — отношение эквивалентности на множестве A.

Для каждого в один раз A обозначим как [x] множество {y½xry}. Потому, что отношение r рефлексивно, то x I [x], а, значит, каждое множество [x] есть непустым и совокупность множеств [x], где x I A, содержит все элементы A. Из семейства множеств {[x]| x IA } удалим кратные вхождения однообразных множеств. В следствии возьмём семейство непустых несовпадающих множеств R, в которых находятся все элементы A.

2. Обоснование того, что R образует разбиение.

Пускай [x] и [y] — произвольные классы из семейства R. Продемонстрируем, что они или не пересекаются, или совпадают, т.е. вероятны лишь два случая:

1) [x] C [y] = ;

2) [x] C [y] .

Предположим, что это свойство есть неверным. Другими словами для некоторых двух элементов x и y множества [x] и [y] пересекаются, но не совпадают (рис 3.1).

[x] [y]

x z y

ab

Рис.3.1

Тут z — это элемент, неспециализированный для классов [x] и [y], аa и b — произвольные элементы в [x] и [y] соответственно.

1. Докажем, что [x] [y]. Пускай x r a. Продемонстрируем, что
справедливо отношение y r a:

a) потому, что x r z, то из симметричности r направляться, что
z r x;

b) потому, что z r x и x r a, то из транзитивности r вытекает, что z r a;

c) из y r z и z r a и транзитивности r имеем y r a. Исходя из этого aI[y], а, значит, [x] [y].

2. Обратное включение [y] [x] возможно доказано, в случае если повторить совершённые рассуждения, поменяв в них местами x и y, и aи b.

Следовательно, справедливо равенство множеств [x] и [y]. Последнее противоречит предположению о том, что эти множества являются различными.

Это указывает, совокупность множеств R образует разбиение множества разбиение A.

3. Обоснование того, что R разбивает A на классы эквивалентных элементов.

3.1. Продемонстрируем, что в каждом классе из R каждые два элемента находятся между собой в отношении r.

Пускай выбраны произвольное множество [x] I R и элементы a, b I A. Продемонстрируем, что ar b. Вправду, по определению множества [x] честны соотношения: xraи xrb. Из соотношения xraи симметричности r направляться, что arx. Из arx и xrb, и транзитивности r направляться, что arb.

3.2. Продемонстрируем, что элементы из различных классов в R не находятся в отношении r. Пускай [x], [y] I R и aI[x], bI[y] — произвольные элементы этих множеств. Продемонстрируем, что (a, b) I r. Предположим неприятное. Пускай arb. Тогда из симметричности отношения r направляться, что bra. Потому, что yrb и bra, то из транзитивности r направляться, что yra. Исходя из этого aI[y]. Последнее противоречит тому, что множества [x] и [y] не пересекаются.

Следовательно, (a, b) I r.

Интуитивная топология | теоретикомнож. вопр. | двоичные отношения | отношение эквивалентности | 1


Также читать:

Понравилась статья? Поделиться с друзьями: