Пример 1.19

1. Отношение равенства на множестве Z есть отношение эквивалентности.

2. Отношение подобия на множестве треугольников есть отношение эквивалентности.

3. Отношение x < y на множестве R не является эквивалентностью, так как оно не рефлексивно и не симметрично, хотя и транзитивно.

4. Отношение сравнимости по модулю натурального числа n на множестве Z: x  y(mod n) является отношением эквивалентности. Действительно, по определению x сравнимо с y по модулю n тогда и только тогда, когда x – y делится на n без остатка. Так как x – x = 0 делится на n, то x  x(mod n) – рефлексивность. Если  x  y(mod n), то x – y делится на n, тогда и  y – x делится на  n, то есть  y  x(mod n) – симметричность.

Далее, если x – y делится на n, то x – y = t₁n (t₁ – целое), а если y – z делится на n, то  y – z = t₂n. Складывая эти равенства, имеем:  x – y + y – z = t₁n + t₂n,  откуда x – z = (t₁ + t₂)n, то есть x – z делится на n. Таким образом, из x  y(mod n) и y  z(mod n) следует, что x  z(mod n) – транзитивность.

5. Отношение принадлежности к одной студенческой группе на множестве студентов университета – эквивалентность.

6. На множестве N  N определим отношение:   x, y, u, v  xv = yu это отношение есть эквивалентность.

(Доказать самостоятельно).

Пусть  – отношение эквивалентности на .

Классом эквивалентности [x], порожденным элементом x, называется подмножество множества , состоящее из тех элементов y  , для которых x, y  , иначе:  [x] = y  y    и x, y  .

Пример 1.20

1. Для примера 1.19 (1) имеем: [x] = {x}, то есть каждый класс эквивалентности состоит только из одного элемента  –  числа x.

2. Пусть Z множество целых чисел (см. пример 1.19 (4)), тогда любые два числа x, y  Z, сравнимые по модулю n (x   y(mod n)), можно представить в виде:  x = qn + r, y = pn + r,  где  r = 0, 1, 2,..., n-1,  p и q – целые числа (действительно,  x – y = = qn + r – pn – r = (q – p)n – делится на n только в том случае, когда остатки равны). Так как  x – r = qn,   y – r = pn,  то  r  x(mod n)  и  r  y(mod n)  и, следовательно, все числа  r, x, y  принадлежат одному классу эквивалентности [r]. То есть всего может быть n различных классов: [0], [1],...,[n-1]. Эти классы называются классами вычетов по модулю n.

3. Для отношения принадлежности к одной студенческой группе (см. пример 1.19 (5))  классом эквивалентности является множество студентов одной группы.

4. Класс эквивалентности, порожденный парой <x, y>, для отношения  из  примера 1.19 (6) определяется соотношением:

Утверждение 1.5. Пусть  – отношение эквивалентности на множестве . Тогда:

1) если x  , то x  [x];

2) если x, y   и x, y  , то [x] = [y].

Доказательство. Так как  – рефлексивно, то <x, x>   и по определению класса эквивалентности [x], x  [x].

Так как  – транзитивно, то из x, y   и y, z   следует, что x, z  . Отсюда: y  [x],  y  [y],  z  [y],  z  [x] по определению классов эквивалентности, тогда. [y]  [x], из свойства симметричности имеем: [x]  [y], следовательно, [x] = [y].

 

Разбиение множества

Разбиением множества X называется семейство (X_i)_iI непустых, попарно непересекающихся множеств, объединение которых равно X , т.е. = X.

Множества X_i   называют элементами (или членами) разбиения {X_i }_iI .

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

Разбиение {X}, состоящее только из самого X, и разбиение, состоящее из всех одноэлементных подмножеств множества X, называются тривиальными разбиениями множества X.