Эквивалентность

Теорема: каждое отношение эквивалентности, определенное на А, соответствует некоторому разбиению множества А. Всякое разбиение множества А соответствует некоторому отношению эквивалентности на множестве А.Коротко: между классами всех определенных на множестве А отношений эквивалентностей и классом всех разбиений множества А существует взаимнооднозначное соответствие.Доказательство: пусть ? – есть отношение эквивалентности на множестве А. Пусть а принадлежит А. Построим множество: К _a={x принадлежит A,: x~a } – всех элементов, эквивалентных а. Множество (обозначение) называется классом эквивалентности относительно эквивалентности ?. Заметим, что если b принадлежит K_a, то b~a. Покажем, что a~b?K_a=K_b. В самом деле, пусть a~b. Возьмем произвольный элемент c принадлежитK_a . Тогда c~a, a~b, c~b, c принадлежит K_b и потому K_b принадлежит K_a. То, что K_a принадлежит K_b, показывается аналогично. Следовательно, K_b=K_a.
Пусть теперь K_b=K_a. Тогда a принадлежит K_a = K _b, a принадлежит K_b, a~b. Что и требовалось показать.Если 2 класса K_a и K _b имеют общий элемент с, то K_a = K _b. В самом деле, если с принадлежитK_a и K _b, то b~c, c~a, b~a =>K_a = K _b.
Поэтому различные классы эквивалентности либо не пересекаются, либо пересекаются и тогда совпадают. Всякий элемент с из А принадлежит только одному классу эквивалентности К_с. Поэтому система непересекающихся классов эквивалентности в пересечении дает все множество А. И потому эта система есть разбиение множества А на классы эквивалентности.Обратное: Пусть А = сумма по или A_i – есть разбиение А. Введем на А отношение a~b, как a~b ?a,b принадлежат одному и тому же классу разбиения. Это отношение удовлетворяет следующим аксиомам:1) a ~ a (лежат в одном классе);
2) a ~ b ? b ~ a;
3) a ~ b & b ~ c ? a ~ c, т.е. введенное отношение ~ есть отношение эквивалентности.Замечание:
1) разбиение множества А на одноэлементные подмножества и разбиение А, состоящие только из множества А, называется тривиальными (несобственным) разбиением.2) Разбиение А на одноэлементные подмножества соответствует отношению эквивалентности которое есть равенство.3) Разбиение А, состоящие из одного класса А, соответствует отношению эквивалентности, содержащему A x A.4) a ? b ? [a]_? = [b]_? – всякое отношение эквивалентности определенное на некотором множестве разбивает это множество на попарно не пересекающиеся классы называемые классами эквивалентности.Определение: Совокупность классов эквивалентности множества А называется фактор-множеством A/? множества А по эквивалентности ?.Определение: Отображение p:A?A/?, при котором p(A)=[a]_?, называется каноническим (естественным) отображением.Всякое отношение эквивалентности, определенное на некотором множестве, разбивает это множество на попарно не пересекающиеся классы, называемые классами эквивалентности.