10. Отношение эквивалентности. Фактор-множество множества по отношению.

Если R —  эквивалентность, то множество A распадается на непересекающиеся классы эквивалентных элементов, или на классы эквивалентности. Множество классов эквивалентности называется фактор-множеством множества A по отношению R. Число классов эквивалентности отношения эквивалентности R называют индексом множества A.

Подмножество называется местным ( мерным) отношением на множестве А. Говорят, что элементы находятся в отношении , если .

Наиболее часто встречающимися и хорошо изученными являются двухместные или бинарные отношения.

Отношение называется отношением эквивалентности (или просто эквивалентностью), если оно рефлексивно, симметрично и транзитивно.

Отношение называется рефлексивным, если для любого элемента имеет место .

Главная диагональ матрицы рефлексивного отношения содержит только единицы.

Отношение называется симметричным, если для любой пары из отношения следует . Иными словами, отношение является симметричным тогда и только тогда, когда для любой пары оно выполняется в обе стороны (или вовсе не выполняется).

Матрица симметричного отношения симметрична относительно главной диагонали: для любых .

Отношение называется транзитивным, если для любых из отношений и следует (R²  R)

Пусть на множестве задано отношение эквивалентности . Осуществим следующее построение. Выберем элемент и образуем класс (подмножество ), состоящий из элемента и всех элементов, эквивалентных ему в рамках данного отношения. Затем выберем элемент и образуем класс , состоящий из и эквивалентных ему элементов. Продолжая эти действия, получим систему классов (возможно, бесконечную) такую, что любой элемент из множества входит хотя бы в один класс, то есть .

Эта система обладает следующими свойствами: она образует разбиение множества , то есть классы попарно не пересекаются; любые два элемента из одного класса эквивалентны; любые два элемента из разных классов не эквивалентны.

Все эти свойства прямо следуют из определения отношения эквивалентности. Действительно, если бы, например, классы и пресекались, то они имели бы хотя бы один общий элемент. Этот элемент был бы, очевидно, эквивалентен и . Тогда, в силу транзитивности отношения выполнялось бы . Однако, по способу построения классов, это не возможно. Аналогично можно доказать другие два свойства.