Отношения эквивалентности и разбиения. Фактор-множества. Матрица отношения эквивалентности

Отношение Р называется отношением эквивалентности, если Р рефлексивно, симметрично и транзитивно. Обозначается Е и ~ (тильда).

Пусть Е – эквивалентность на множестве А. Классом эквивалентности элемента называется множество E(x)={y | xEy}. Классы эквивалентности Е также называют Е-классами. Множество называется фактор-множеством множества А по отношению к Е.

Утверждение: Множество всех классов эквивалентности образует разбиение множества А (система непересекающихся подмножеств, объединение которых совпадает с А). Если {A_i} – некоторое разбиение множества А, то по этому разбиению можно однозначно определить эквивалентность. Т.е. xEy тогда и только тогда, когда x, y принадлежат А_i для некоторого i.

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

Пусть Е – отношение эквивалентности на множестве А, А/Е – фактор-множество множества А по Е. Т.к. в силу рефлексивности Е выполнимо для любого , то каждое множество из А/Е непустое и . Чтобы установить, что А/Е – разбиение множества А, покажем, что если , то E(x)=E(y).

Пусть и , т.е. . Т.к. Е симметрично, то . Из транзитивности Е следует , т.е. . Таким образом, . Обратное включение доказывается аналогично.

Предположим, что Е – отношение на множестве А, соответствующее разбиению R={A_i}. Рефлексивность и симметричность Е очевидны. Пусть выполняется xEy и yEz. Тогда , где . Поскольку и , то А_i=A_j. Следовательно Е транзитивно. Е – эквивалентность.