Пусть G={p₀=e, p₁, …, p_r} есть некоторая группа подстановок, определенная на множестве X = {1, 2, …, n} с единицей e=p₀ тождественной подстановкой. Определим отношение x~y, положив x~y равносильно, что существует p принадлежащее G(p(x)=y). Введенное отношение есть отношение эквивалентности, то есть оно удовлетворяет трем аксиомам:

1) x~x;
2) x~y→y~x;
3) x~y&y~z→x~z;

Пусть А – произвольное множество.
Определение: Бинарное отношение δ=A*A есть отношение эквивалентности (обозначается a ~ b), если они удовлетворяет следующим аксиомам:
∀ a, b, c ∈ A
1) a ~ a – рефлексивность;
2) a ~ b ⇒ b ~ a – коммутативность;
3) a ~ b & b ~ c → a ~ c — транзитивность

обозначается a ~ b, σ(a,b), (a,b) ∈ σ, a σ b

Определение: Разбиение множества А есть семейство попарно не пресекающихся подмножеств из А, в объединении (в сумме) дающих все А.
А= ∪А_i, А_i∩А_j = ∅, ∀i ≠ j.

Подмножества А_i называются смежными классами разбиения.

Теорема: каждое отношение эквивалентности, определенное на А, соответствует некоторому разбиению множества А. Всякое разбиение множества А соответствует некоторому отношению эквивалентности на множестве А.

Коротко: между классами всех определенных на множестве А отношений эквивалентностей и классом всех разбиений множества А существует взаимнооднозначное соответствие.

Доказательство: пусть σ — есть отношение эквивалентности на множестве А. Пусть а ∈ А.

Построим множество: К_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]_σ, называется каноническим (естественным) отображением.

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

Комментарии запрещены.