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

Классы эквивалентных элементов и их свойства

Пусть %%R%% — отношение эквивалентности на множестве %%M%% и %%a%% — некоторый элемент из %%M%%. Рассмотрим множество всех элементов из %%M%%, находящихся в отношении %%R%% к элементу %%a%%.

Классом эквивалентности %%M_a%%

называется множество всех элементов %%M%%, находящихся в отношении %%R%% к элементу %%a%%, то есть множество

$$ M_a = \{x \in M : x~R~a\}. $$

Пример

Пусть %%M%% — множество всех жителей России и %%R%% — отношение эквивалентности «проживать в одном городе». Найти классы эквивалентных элементов %%M_a%% для %%a \in M%%.

Класс элементов, эквивалентных элементу %%a%%, имеет вид: $$ M_a = \{x \in M : x \text{ проживает в одном городе с человеком } a\} $$

В зависимости от элемента %%a%% получаем несколько классов эквивалентности. Например, класс эквивалентности жителей Москвы или Санкт-Петербурга.

Свойства классов эквивалентности

Пусть %%R%% — отношение эквивалентности на множестве %%M%% и %%M_a, M_b, \dotsc, M_z, \dotsc%% — все классы эквивалентности для отношения %%R%%. Тогда эти классы имеют следующие свойства.

Свойство 1

Для любого элемента %%a \in M%% выполняется условие $$ a \in M_a $$

Действительно, по определению, класс %%M_a = \{x \in M : x~R~a\}%%. Тогда для элемента %%a%% должно выполняться условие %%a \in M_a \leftrightarrow a~R~a%%, которое выполняется в связи с тем, что отношение %%R%% рефлексивно по определению отношения эквивалентности. Следовательно, %%a \in M_a%%.

Как следствие этого свойства можно сказать, что всякий класс %%M_a%% является непустым множеством.

Свойство 2

Пусть %%M_a%% и %%M_b%% классы эквивалентности для отношения %%R%%. Классы %%M_a%% и %%M_b%% равны тогда и только тогда, когда элемент %%a%% находится в отношении %%R%% к элементу %%b%%. $$ M_a = M_b \leftrightarrow a~R~b. $$

Свойство 3

Пусть %%M_a%% и %%M_b%% классы эквивалентности для отношения %%R%%. Тогда классы %%M_a%% и %%M_b%% не имеют общих элементов. $$ M_a \neq M_b \rightarrow M_a \cap M_b = \varnothing $$

Свойство 4

Объединение всех классов эквивалентности множества %%M%% равно множеству %%M%%. $$ \bigcup_{a\in M}{M_a} = M. $$

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

Совокупностью подмножеств %%M_i%%, где %%i \in I%% (множеству индексов), множества %%M%% называется разбиением множества %%M%% если выполняются следующие условия:

1. Каждое из подмножеств %%M_i%% непусто.
2. Объединение всех подмножеств %%M_i%% равно множеству %%M%%.
3. Два различных подмножества %%M_i%% и %%M_j%%, где %%i \neq j%%, не имеют общих элементов.

Теорема. Пусть %%R%% — отношение эквивалентности на множестве %%M%%. Тогда совокупность классов эквивалентности множества %%M%% образует его разбиение.

Действительно, если в качестве подмножеств %%M_i%% взять классы эквивалентности %%M_a%%, то все три условия выполняются:

1. Каждый класс эквивалентности является непустым множеством, согласно свойству 1.
2. Объединение всех классов эквивалентности есть множество %%M%%, согласно свойству 4.
3. Два различных класса эквивалентности не имеют общих элементов, согласно свойству 3.

Все условия определения разбиения выполнены. Следовательно классы эквивалентности есть разбиение множества %%M%%.

Примеры

Пусть дано множество %%M = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 0 \}%%, тогда разбиением этого множества могут быть следующие совокупности множеств:

1. %%A_1 = \{1, 2, 3\}, A_2 = \{4, 5, 6, 7\}, A_3 = \{8, 9, 0 \}%%.
2. %%B_1 = \{0, 7, 2\}, B_2 = \{1, 3, 5 \}, B_3 = \{4, 6, 8, 9\}%%.

Но следующие совокупности не являются разбиением:

1. %%C_1 = \{1, 2, 3\}, C_2 = \{4, 5, 6, 7\}, C_3 = \{8, 9, 0, 3\}%%.
2. %%D_1 = \{0, 7, 2\}, D_2 = \{1, 3, 5 \}, D_3 = \{4, 6, 8, 9\}, D_4 = \varnothing%%.
3. %%E_1 = \{0, 1, 2\}, E_2 = \{3, 4, 5\}, E_3 = \{6, 7, 8\}%%.

Совокупность множеств %%C_i%% не является разбиением, т.к. оно не удовлетворяет условию 3 разбиения множеств: множества %%C_1%% и %%C_3%% имеют общий элемент %%3%%.

Совокупность множеств %%D_i%% не является разбиением, т.к. оно не удовлетворяет условию 1 разбиения множеств: множество %%D_4%% пусто.

Совокупность множеств %%E_i%% не является разбиением, т.к. оно не удовлетворяет условию 2 разбиения множеств: объединение множеств %%E_1, E_2%% и %%E_3%% не образует множество %%M%%.