3.3. Основные типы отношений

Рассмотрим наиболее употребительные типы отношений.

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

Данное отношение удовлетворяет следующим трем аксиомам: 1) рефлексивности, 2) симметричности и 3) транзитивности.

Практический смысл отношения эквивалентности заключается в том, что оно разбивает множество, на котором определено, на классы.

Определение. Пусть множество Х разбито на подмножества Х₁,Х₂,..., Х_n таким образом, что все они попарно не пересекаются и объединение их равно Х:

1)  Х_i = Х, (i = 1,...,n);

2) Х _i Х, Х _j Х , (ij)  Х _i  Х _j =.

В этом случае говорят, что произведено разбиение Х на классы Х₁, ... , Х_n. Элементы х_i и х_j множества Х эквивалентны по отношению к его разбиению, если они принадлежат одному и тому же классу Х_k.

Замечание.

1. Мощность множества классов эквивалентности может быть как конечной, так и бесконечной (счетной, континуум и т.д.).

2. Смысл понятия эквивалентности в том, что с точки зрения разбиения множества Х элементы х_i и х_j неразличимы, если попадают в один класс. Обычно отношение эквивалентности обозначают символом «  ».

Определение. Поэлементным будем называть такое разбиение множества на классы эквивалентности, где каждый класс Х_i содержит ровно один элемент из Х.

Фиктивным будем называть разбиение в котором выделен один класс Х₁, совпадающий со всем Х, (Х₁ = Х).

Пример 1. Рассмотрим в качестве Х множество натуральных чисел N. Его можно разбить отношением эквивалентности на два непересекающихся класса, дающих в сумме все N: множество четных (делящихся на 2 без остатка) чисел N₂ и множество нечетных (делящихся на 2 с остатком 1) чисел N_2. При этом само множество пар отношения будет образовано: а) всеми парами четных чисел; б) всеми парами нечетных чисел. Смешанные пары (четное число с нечетным и наоборот) в него не войдут.

Данное отношение эквивалентности можно задать при помощи предиката Р(х, у) = «х - у кратно 2».

Пример 2. Х = N. Х₁ = {1}, Х₂ = {2, 3}, Х₃ = {4, 5, 6, 7},…, Х_i = {множество целых чисел от 2^i-1 до 2ⁱ–1}. Выделенные множества Х₁,Х₂, ... не пересекаются, объединение их равно N. Следовательно, они разбивают N на классы. Их число бесконечно. Несложно показать, что { Х_i }=₀. Множество пар, составляющих отношение, будет следующим: {(1, 1); (2, 2); (2, 3); (3, 2); (3, 3); (4, 4); (4, 5); (4, 6); (4, 7); (5, 4); (5, 5); (5, 6)…}.

Отношение можно задать при помощи предиката, непосредственно задающего структуру классов эквивалентности: Р(х,у)= «2^i-1 ≤ х, у ≤ 2ⁱ-1, i N».

Пример 3. Х = {1, 2, 3, 4, 5, 6}. Ниже приведены при помощи матриц примеры отношений, реализующих следующие разбиения Х на классы: 1) разбиение: Х₁= {1,2}, Х₂= {3}, Х₃= {4, 5, 6}; 2) фиктивное: Х₁= Х ; 3) поэлементное: Х₁ = {1}, Х₂ = {2}, Х₃ = {3}, Х₄ = {4}, Х₅ = {5}, Х₆ = {6}.

	1	2	3	4	5	6
1	+	+	-	-	-	-
2	+	+	-	-	-	-
3	-	-	+	-	-	-
4	-	-	-	+	+	+
5	-	-	-	+	+	+
6	-	-	-	+	+	+

	1	2	3	4	5	6
1	+	+	+	+	+	+
2	+	+	+	+	+	+
3	+	+	+	+	+	+
4	+	+	+	+	+	+
5	+	+	+	+	+	+
6	+	+	+	+	+	+

	1	2	3	4	5	6
1	+	-	-	-	-	-
2	-	+	-	-	-	-
3	-	-	+	-	-	-
4	-	-	-	+	-	-
5	-	-	-	-	+	-
6	-	-	-	-	-	+