Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


Отношения эквивалентности на множестве

Отношения эквивалентности на множестве


Разбиение множества


Пусть A — произвольное множество. Семейство (B_i)_{i\in I} непустых и попарно не пересекающихся множеств называют разбиением множества A, если объединение множеств семейства (B_i)_{i\in I} равно A, то есть


\bigcup\limits_{i\in I}B_i=A\,.

Сами множества B_i называют элементами (или членами) разбиения (B_i)_{i\in I}.


Например, множества \left[0;\tfrac{1}{3}\right)\!,\, \left[\tfrac{1}{3};\tfrac{2}{3}\right) и \left[\tfrac{2}{3};1\right] образуют разбиение отрезка [0;1]. Тривиальными разбиениями A являются, по определению, разбиение \{A\}, состоящее только из самого A, и разбиение, состоящее из всех одноэлементных подмножеств множества A.


Пусть \rho — эквивалентность на множестве A и x\in A. Множество всех элементов A, эквивалентных x, т.е. множество \{y\colon\, y\,\rho\,x\}, называют классом эквивалентности по отношению \rho и обозначают [x]_{\rho}. Отметим, что в силу рефлексивности для любого элемента x\in A класс эквивалентности не пуст, так как x\in[x]_{\rho}.


Теорема 1.4. Для любого отношения эквивалентности на множестве A множество классов эквивалентности образует разбиение множества A. Обратно, любое разбиение множества A задает на нем отношение эквивалентности, для которого классы эквивалентности совпадают с элементами разбиения.


Покажем, что отношение эквивалентности \rho на множестве A определяет некоторое разбиение этого множества. Убедимся вначале, что любые два класса эквивалентности по отношению \rho либо не пересекаются, либо совпадают.


Пусть два класса эквивалентности [x]_{\rho} и [y]_{\rho} имеют общий элемент z\in[x]_{\rho}\cap[y]_{\rho}. Тогда z\,\rho\,x и z\,\rho\,y. В силу симметричности отношения \rho имеем x\,\rho\,z, и тогда x\,\rho\,z и z\,\rho\,y. В силу транзитивности отношения \rho получим x\,\rho\,y. Пусть h\in[x]_{\rho}, тогда h\,\rho\,x. Так как x\,\rho\,y, то h\,\rho\,y и, следовательно, h\in[y]_{\rho}.


Обратно, если h\in[y]_{\rho}, то в силу симметричности \rho получим h\,\rho\,y,~ y\,\rho\,x и в силу транзитивности — h\,\rho\,x, то есть h\in[x]_{\rho}. Таким образом, [x]_{\rho}=[y]_{\rho}.


Итак, любые два не совпадающих класса эквивалентности не пересекаются. Так как для любого x\in A справедливо x\in[x]_{\rho} (поскольку x\,\rho\,x), т.е. каждый элемент множества A принадлежит некоторому классу эквивалентности по отношению \rho, то множество всех классов эквивалентности по отношению \rho образует разбиение исходного множества A. Таким образом, любое отношение эквивалентности однозначно определяет некоторое разбиение.


Теперь пусть (B_i)_{i\in I} — некоторое разбиение множества A. Рассмотрим отношение \rho, такое, что x\,\rho\,y имеет место тогда и только тогда, когда x и y принадлежат одному и тому же элементу B_i данного разбиения:


x\,\rho\,y~ \Leftrightarrow~ (\exists i\in I)(x\in B_i)~ \land~ (y\in B_i).

Очевидно, что введенное отношение рефлексивно и симметрично. Если для любых x,y и z имеет место x\,\rho\,y и y\,\rho\,z, то x,y и z в силу определения отношения \rho принадлежат одному и тому же элементу B_i разбиения. Следовательно, x\,\rho\,z и отношение \rho транзитивно. Таким образом, \rho — эквивалентность на A.




Фактор-множество


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


Множество всех классов эквивалентности по данному отношению эквивалентности \rho на множестве A называют фактор-множеством множества A по отношению \rho и обозначают A/\rho.


Пример 1.14. а. На множестве целых чисел \mathbb{Z} определим отношение равенства по модулю k, где k\in \mathbb{N}. Положим x=_{(\operatorname{mod}k)}y, если и только если (x-y) делится на A.


Легко проверяется, что это отношение эквивалентности. Действительно, рефлексивность следует из того, что для любо m\in \mathbb{Z}m-m=0 и делится на k; симметричность — из того, что если (m-n) делится на k, то и (n-m) делится на k. Для доказательства транзитивности заметим, что если (m-n) делится на k и (n-p) делится на k, то и их сумма (m-n)+(n-p)=m-p делится на k. Другими словами, для любых целых m,n,p из m=_{(\operatorname{mod}k)}n и n=_{(\operatorname{mod}k)}p следует m=_{(\operatorname{mod}k)}p, что доказывает транзитивность отношения =_{(\operatorname{mod}k)}.


Равенство чисел m и n по модулю k означает, что при делении на k эти числа дают одинаковые остатки. Действительно, для каждого x\in\mathbb{Z} имеем x=m\cdot k+r, где r — остаток от деления x на k. Следовательно, x-r=m\cdot k, то есть x=_{(\operatorname{mod}k)}r. Таким образом, каждое число попадает в тот же класс эквивалентности по отношению =_{(\operatorname{mod}k)}, что и остаток от деления его на k. Поскольку всего различных остатков может быть ровно k\colon\, 0,1,\ldots,k-1, получаем ровно k попарно различных классов эквивалентности по данному отношению:


[0]=_{(\operatorname{mod}k)},\quad [1]=_{(\operatorname{mod}k)},\quad \ldots,\quad [k-1]=_{(\operatorname{mod}k)},

где класс [r]=_{(\operatorname{mod}k)} состоит из всех целых чисел, дающих при делении на k остаток r.


Отметим, что мы установили взаимно однозначное соответствие между фактор-множеством \mathbb{Z}/=_{(\operatorname{mod}k)} и множеством \mathbb{Z}_k, состоящим из чисел 0,1,\ldots,k-1.


Второе множество дает нам как бы wнаглядный образ" построенного фактор-множества. Нельзя считать, что фактор-множество \mathbb{Z}/=_{(\operatorname{mod}k)} равно множеству \{0,1,\ldots,k-1\}. Нет, указанное фактор-множество состоит из k элементов, каждый из которых есть не число, а множество всех целых чисел, при делении на k дающих фиксированный остаток. Но каждому такому классу эквивалентности однозначно сопоставляется целое число от 0 до k-1, и, наоборот, каждому целому числу от 0 до k-1 соответствует единственный класс эквивалентности по отношению =_{(\operatorname{mod}k)}. Заметим, что в математике часто используется прием сопоставления фактор-множеству такого находящегося с ним во взаимно однозначном соответствии множества, которое легко представить и описать.


б. На множестве \mathbb{R} действительных чисел зададим отношение a=_{(\operatorname{mod}1)}b, полагая, что числа a и b равны по модулю 1 тогда и только тогда, когда число a-b является целым. Из определения следует, что каждое число по модулю 1 равно своей дробной части.


Примечание. Под дробной частью <a> числа a понимается число из полуинтервала [0;1), такое, что a=n+<a> для некоторого целого n. Поэтому дробной частью отрицательного числа (-a), где a>0, будет число (1-<a>). Так, Дробной частью (-1,\!23) будет не 0,\!23, а 0,\!77=1-0,\!23.


Так как отношение =_{(\operatorname{mod}1)} определено через равенство, то легко понять, что все свойства отношения эквивалентности для него выполняются. Каждый класс эквивалентности будет содержать числа с равными дробными частями. Это значит, что каждый класс эквивалентности по данному отношению однозначно определяет некоторое число из полуинтервала [0;1) и, наоборот, каждому числу \gamma\in[0;1) однозначно сопоставляется класс эквивалентности, состоящий из всех действительных чисел, дробная часть которых равна \gamma. Таким образом, фактор-множество \mathbb{R}/=_{(\operatorname{mod}1)} и полуинтервал [0;1) на числовой прямой находятся во взаимно однозначном соответствии. Этот полуинтервал можно рассматривать как представление определенного выше фактор-множества.




Связь между понятиями эквивалентности и отображения


Установим теперь связь между понятиями эквивалентности и отображения. Заметим, что для любого отношения эквивалентности \rho на множестве A можно определить отображение f_{\rho}\colon A\to A/\rho, положив f_{\rho}(x)=[x]_{\rho}, т.е. сопоставив каждому x\in A содержащий его класс эквивалентности. Это отображение сюръективно, так как каждый элемент множества A принадлежит некоторому классу эквивалентности, т.е. для каждого [x]_{\rho}\in A/\rho справедливо [x]_{\rho}=f_{\rho}(x).


Отображение f_{\rho} определенное таким образом, называют канонической сюръекцией множества A.


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


Теорема 1.5. Пусть f\colon A\to B — произвольное отображение. Отношение \rho_f на множестве A, для которого x\,\rho_f\,y, если и только если f(x)=f(y), является отношением эквивалентности, причем существует биекция фактор-множества A/\rho_f на множество f(A).


Доказательство. Рефлексивность, симметричность и транзитивность отношения \rho_f следуют непосредственно из его определения, т.е. \rho_f — эквивалентность.


Зададим отображение \varphi фактор-множества A/\rho_f в множество f(A) следующим образом: \varphi([x]_{\rho_f})=f(x). Из способа задания отношения \rho следует, что отображение определено корректно, т.е. каждому классу эквивалентности поставлен в соответствие единственный элемент y\in f(A).


Докажем, что \varphi — биекция, для чего убедимся в том, что это инъекция и сюръекция одновременно. Пусть классы эквивалентности [x]_{\rho_f} и [y]_{\rho_f} не совпадают. В силу теоремы 1.4 это означает, что они не пересекаются, т.е. x не эквивалентно y. Из определения отношения \rho_f следует, что f(x)\ne f(y). Таким образом, \varphi — инъекция. Если элемент u\in f(A), то найдется такой элемент x\in A, что u=f(x)=\varphi([x]_{\rho_f}), то есть \varphi — сюръекция фактор-множества A/\rho_{f} на множество f(A). Итак, \varphi — биекция.




Следовательно, в силу доказанных теорем 1.4 и 1.5 существует связь между тремя понятиями — отображением множества, отношением эквивалентности на множестве и разбиением множества. Но неверно, что существует взаимно однозначное соответствие между отображениями и отношениями эквивалентности (заметим, что теорема 1.5 этого и не утверждает). Два разных отображения могут определять одно и то же разбиение отображаемого множества, тем самым задавая на нем одно и то же отношение эквивалентности. Так, например, любое биективное отображение f\colon A\to B задает на A одно и то же разбиение — тривиальное разбиение на одноэлементные множества.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2019 MathHelpPlanet.com. All rights reserved