Бинарные отношения. Отношение эквивалентности, фактор-множество

Пусть G={p0=e, p1, …, pr} есть некоторая группа подстановок, определенная на множестве X = {1, 2, …, n} с единицей e=p0 тождественной подстановкой. Определим отношение 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 принадлежит Ka, то b~a. Покажем, что a~b⇔Ka=Kb. В самом деле, пусть a~b. Возьмем произвольный элемент c принадлежит Ka. Тогда c~a, a~b, c~b, c принадлежит Kb и потому Kb принадлежит Ka. То, что Ka принадлежит Kb, показывается аналогично. Следовательно, Kb=Ka.
Пусть теперь Kb=Ka. Тогда a принадлежит Ka = K b, a принадлежит Kb, a~b. Что и требовалось показать.

Если 2 класса Ka и K b имеют общий элемент с, то Ka = K b. В самом деле, если с принадлежит Ka и K b, то b~c, c~a, b~a => Ka = K b.

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

Обратное: Пусть А = сумма по или Ai – есть разбиение А. Введем на А отношение 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]σ, называется каноническим (естественным) отображением.

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


Оставить комментарий





Статистика

Рейтинг@Mail.ru