Одним из самых важных типов отношений является отношение эквивалентности на множестве.
Определение. Рефлексивное, симметричное и транзитивное отношение r на множестве X называется отношением эквивалентности на множестве X.
Пример 1.12.
1. Отношение равенства на множестве целых чисел есть отношение эквивалентности.
2. Пусть A = R2{<0,0>} - множество точек на плоскости за исключением начала координат. Отношение r на A определим так: <a,b> r <c,d> тогда и только тогда, когда точки <a,b> и <c,d> лежат на одной прямой, проходящей через начало координат. Легко показать, что отношение r является отношением эквивалентности.
3. Отношение сравнимости по модулю натурального числа n на множестве целых чисел Z: x є y (mod n) тогда и только тогда, когда x-y делится на n. Это отношение рефлексивно на Z, так как для любого xОZ x - x = 0, и, следовательно, делится на n. Это отношение симметрично, так как если x-y делится на n, то y-x делится на n . Это отношение транзитивно, так как если x - y делится на n, то для некоторого целого t1 имеем x-y= t1n, а если y-z делится на n, то для некоторого целого t2 имеем y-z = t2n. Отсюда x-z = (t1+t2)n, т. е. x-z делится на n.
4. Рассмотрим отношение r, определенное на множестве неотрицательных целых чисел так: n r m, если и только если n - делитель m. Отношение r не является отношением эквивалентности. Чтобы показать это, достаточно убедиться, что хотя бы одно из трех свойств не выполняется для r. Очевидно, что r не является симметричным отношением, так как, например, 2 - делитель 4, но 4 не является делителем 2.
5. На множестве NґN, где N - множество натуральных чисел, определим отношение r : <x, y>r<u, v> уxv = yu. Это отношение рефлексивно: <x,y>r<x, y>, так как xy = yx; симметрично: если <x, y>r<u, v>, то <u,v>r<x, y>, так как из xv = yu следует, что и uy = vx; транзитивно: если <x, y>r<u, v>, <u, v>r<w, z>, то <x, y>r<w, z>, так как, перемножая левые и правые части равенств xv = yu и uz = vw после сокращения получаем xz = yw.
Пусть r - отношение эквивалентности на множестве X.
Определение. Классом эквивалентности, порожденным элементом x, называется подмножество множества X, состоящее из тех элементов yОX, для которых xry. Класс эквивалентности, порожденный элементом x, обозначается [x]:
[x] = {y | yОX и xry}.
Пример 1.13.
1. Отношение равенства на множестве целых чисел порождает следующие классы эквивалентности: для любого элемента xОZ [x] = {x}, т. е. каждый класс эквивалентности состоит только из одного элемента - числа x.
2. Отношение сравнимости по модулю числа n на множестве целых чисел Zпорождает следующие классы эквивалентности: вместе с любым числом aОZ в этом же классе эквивалентности содержатся все числа вида a + kn, где k - целое. Очевидно, что все числа 0, 1, 2,…, n-1 порождают различные классы эквивалентности, которые обозначим [0], [1], [2],…, [n-1]. Они называются классами вычетов по модулю n. Все остальные классы эквивалентности для этого отношения совпадают с ними, так как любое число aОZ можно представить в виде a = qn + r, где 0Ј r <n.
3. Класс эквивалентности, порожденной парой <x, y> для отношения r из примера 1.12 (5) определяется соотношением [<x, y>]={<u, v>| x/y = u/v}. Каждый класс эквивалентности в этом случае определяет одно положительное рациональное число.
Теорема 1.6. Пусть r - отношение эквивалентности на множестве X. Тогда: 1) если xОX, то xО[x]; 2) если x, y О X и xry, то [x] =[y] (т. е. класс эквивалентности порождается любым своим элементом).
Для доказательства первой части утверждения достаточно воспользоваться рефлексивностью отношения r: xrx и, следовательно, xО[x]. Докажем вторую часть утверждения. Пусть zО[y]. Тогда yrz и в силу транзитивности отношения r xrz, т. е. zО[x] . Отсюда [y] Н [x]. Аналогично, в силу симметричности r можно показать, что [x]Н[y], а значит [y] = [x].
Определение. Разбиением множества X называется множество попарно непересекающихся подмножеств X таких, что каждый элемент множества X принадлежит одному и только одному из этих подмножеств.