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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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


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

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: