3.5. Отношения эквивалентности определение

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

Если   отношение эквивалентности и a  b, то элементы a и b называются эквивалентными в этом отношении или просто эквивалентными.

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

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

Определение

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

1) iI(A_i  );

2) i,jI(i j  A_i  A_j = );

3) A_i = A .

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

Пусть A₁, ... , A_k, . . .  разбиение множества A. Нетрудно проверить, что отношение  на множестве A, определяемое соотношением: a b , является отношением эквивалентности.

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

ТЕОРЕМА 3.2

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

Доказательство

Разобьем доказательство теоремы на несколько этапов.

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

Пусть   отношение эквивалентности на множестве A.

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

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

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

1) [x]  [y] = ;

2) [x]  [y] .

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

[x] [y]

x z y

a b

Рис.3.1

Здесь z  это элемент, общий для классов [x] и [y], а a и b  произвольные элементы в [x] и [y] соответственно.

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

a) поскольку x  z, то из симметричности  следует, что z  x;

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

c) из y  z и z  a и транзитивности  имеем y  a. Поэтому a [y], а, значит, [x] [y].

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

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

Это означает, система множеств R образует разбиение множества разбиение A.

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

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

Пусть выбраны произвольное множество [x]  R и элементы a, b  A. Покажем, что a  b. Действительно, по определению множества [x] справедливы соотношения: xa и xb. Из соотношения xa и симметричности  следует, что ax. Из ax и xb, а также транзитивности  следует, что ab.

3.2. Покажем, что элементы из разных классов в R не находятся в отношении . Пусть [x], [y]  R и a[x], b[y]  произвольные элементы этих множеств. Покажем, что (a, b)  . Предположим противное. Пусть ab. Тогда из симметричности отношения  следует, что ba. Поскольку yb и ba, то из транзитивности  следует, что ya. Поэтому a[y]. Последнее противоречит тому, что множества [x] и [y] не пересекаются.

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

Доказательство окончено.

Упражнение. Проверить, является ли отношением эквивалентности отношение синонимии на множестве слов русского языка.