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

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

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

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

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


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

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


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


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


[math]\bigcup\limits_{i\in I}B_i=A\,.[/math]

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


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


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


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


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


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


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


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


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


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

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




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


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


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


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


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


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


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

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


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


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


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


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


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




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


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


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


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


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


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


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


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




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


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


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

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