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

Пусть А — произвольное множество. Семейство (B_i)_i∈I непустых и попарно не пересекающихся множеств называют разбиением множества А, если объединение множеств семейства (B_i)_i∈I равно А, т.е.

Сами множества B_i называют элементами (или членами) разбиения (B_i)_i∈I.

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

Пусть р — эквивалентность на множестве А и х ∈ А. Множество всех элементов А, эквивалентных х, т.е. множество {у: у р x}, называют классом эквивалентности по отношению р и обозначают [х]_p. Отметим, что в силу рефлексивности для любого элемента х ∈ А класс эквивалентности не пуст, так как х ∈ [х]_p.

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

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

Пусть два класса эквивалентности [х]_p и [у]_p имеют общий элемент z ∈ [х]_p ∩ [у]_p. Тогда zpx и zpy. В силу симметричности отношения р имеем хрz, и тогда хрz и zpy. В силу транзитивности отношения р получим хру. Пусть h ∈ [х]_p, тогда h р х. Так как х р у, то h р у и, следовательно, h ∈ [у]_p.

Обратно, если h ∈ [у]_p, то в силу симметричности р получим hру, ypx и в силу транзитивности — hрх, т.е. h ∈ [х]_p. Таким образом, [х]р = [у]р.

Итак, любые два не совпадающих класса эквивалентности не пересекаются. Так как для любого х ∈ А справедливо х ∈ [х]_p (поскольку хрх), т.е. каждый элемент множества А принадлежит некоторому классу эквивалентности по отношению р, то множество всех классов эквивалентности по отношению р образует разбиение исходного множества А. Таким образом, любое отношение эквивалентности однозначно определяет некоторое разбиение.

Теперь пусть B_i)_i∈I — некоторое разбиение множества А. Рассмотрим отношение р, такое, что хру имеет место тогда и только тогда, когда х и у принадлежат одному и тому же элементу В_i данного разбиения:

х р у ⇔ (∃_i ∈ I)(х ∈ В_i) ∧ (у ∈ В_i).

Очевидно, что введенное отношение рефлексивно и симметрично. Если для любых х,у,z имеет место хру и уpz, то x, у и z в силу определения отношения р принадлежат одному и тому же элементу В_i разбиения. Следовательно, хpz и отношение р транзитивно. Таким образом, р — эквивалентность на А. ▶

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

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

Пример 1.14. а. На множестве целых чисел ℤ определим отношение равенства по модулю л, где k ∈ ℕ. Положим* x=_(modk)У, если и только если х — у делится на k.

* Традиционное обозначение: т = n(mod&).

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

Равенство чисел m и n по модулю k означает, что при делении на k эти числа дают одинаковые остатки. Действительно, для каждого х∈ℤ имеем x = m ⋅ k + r, где r — остаток от деления х на k. Следовательно, х — r = m ⋅ k, т.е. x=(_(modk))r. Таким образом, каждое число попадает в тот же класс эквивалентности по отношению =(_(modk)), что и остаток от деления его на k. Поскольку всего различных остатков может быть ровно k: 0, 1, ..., k — 1, получаем ровно кk попарно различных классов эквивалентности по данному отношению: [0]=_(modk), [1]=_(modk), ..., [k-1]=_(modk)' где класс [r]=_(modk) состоит из всех целых чисел, дающих при делении на л остаток к.

Отметим, что мы установили взаимно однозначное соответствие между фактор-множеством ℤ/=_(modk) и множеством ℤ_k, состоящим из чисел 0, 1, ..., k — 1.

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

б. На множестве ℝ действительных чисел зададим отношение а=_(mod1)b, полагая, что числа а и b равны по модулю 1 тогда и только тогда, когда число a — b является целым. Из определения следует, что каждое число по модулю 1 равно своей дробной части*.

Так как отношение _(mod1) определено через равенство, то легко понять, что все свойства отношения эквивалентности для него выполняются. Каждый класс эквивалентности будет содержать числа с равными дробными частями. Это значит, что каждый класс эквивалентности по данному отношению однозначно определяет некоторое число из полуинтервала [0,1) и, наоборот, каждому числу γ[0,1) однозначно сопоставляется класс эквивалентности, состоящий из всех действительных чисел, дробная часть которых равна γ. Таким образом, фактормножество ℝ/=_(mod1) и полуинтервал [0,1) на числовой прямой находятся во взаимно однозначном соответствии. Этот полуинтервал можно рассматривать как представление определенного выше фактор-множества. #

Установим теперь связь между понятиями эквивалентности и отображения. Заметим, что для любого отношения эквивалентности р на множестве А можно определить отображение f_р: А → А/р, положив f_р(x) = [x]_р, т.е. сопоставив каждому х ∈ А содержащий его класс эквивалентности. Это отображение сюръективно, так как каждый элемент множества А принадлежит некоторому классу эквивалентности, т.е. для - каждого [х]_р ∈ А/р справедливо [х]_р = f_р(x).

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

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

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

Теорема 1.5. Пусть f: А → В — произвольное отображение. Отношение р_f на множестве А, для которого х р_f у, если и только если f(x) = f(у), является отношением эквивалентности, причем существует биекция фактор-множества А/р_f на множество f(A).

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

Зададим отображение φ фактор-множества A/р_f в множество f(A) следующим образом: φ([x]_рf) = f(x).Из способа задания отношения р следует, что отображение определено кор- корректно, т.е. каждому классу эквивалентности поставлен в со- соответствие единственный элемент у ∈ f(A).

Докажем, что φ — биекция, для чего убедимся в том, что это инъекция и сюръекция одновременно. Пусть классы эквивалентности [x]_рf и [y]_рf не совпадают. В силу теоремы 1.4 это означает, что они не пересекаются, т.е. х не эквивалентно у. Из определения отношения р_f следует, что f(x) ≠ f(у). Таким образом, φ — инъекция. Если элемент u ∈ f(А), то найдется такой элемент х ∈ А, что u = f(x) = φ([x]_рf), т.е. φ — сюръекция фактор-множества А/р_f на множество f(A). Итак, φ — биекция. >

Следовательно, в силу доказанных теорем 1.4 и 1.5 существует связь между тремя понятиями — отображением множества, отношением эквивалентности на множестве и разбиением множества. Но неверно, что существует взаимно однозначное соответствие между отображениями и отношениями эквивалентности*. Два разных отображения могут определять одно и то же разбиение отображаемого множества, тем самым задавая на нем одно и то же отношение эквивалентности. Так, например, любое биективное отображение f: А → В задает на A одно и то же разбиение — тривиальное разбиение на одноэлементные множества.

*Заметим, что теорема 1.5 этого и не утверждает.