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

Отношение ρ во множестве X называется рефлексивным, если для любого элемента х из X хρх;- симметричным, если хρу влечет уρх; тран­зитивным, если из хρу и yρz следует xρz. Отношения, обладающие всеми этими свойствами, столь часто встречаются в математике, что им при­своили специальное название. Отношение в некотором множестве называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Если отношение ρ в X есть отношение эквивалентности, то, очевидно, D_ρ = X. Вследствие этого отношения эквивалентности в X называют также отношениями эквивалентности на X.

Примеры

Каждое из следующих отношений является отношением эквивалентности на соответствующем множестве:

1. Равенство в произвольной системе множеств.

2. Геометрическое отношение подобия в множестве всех треугольников в евклидовой плоскости.

3. Отношение сравнимости по модулю n в Z. Это отношение определяется для любого не равного нулю целого числа n следующим обра­зом: x сравнимо с у по модулю n, если x — у делится на n;_: обозначение: х = у (mod n).

4. Отношение ~ в множестве всех упорядоченных пар положитель­ных целых чисел, где <x, у>~<и, v>, если xv = yu.

5. Отношение параллельности в множестве прямых в евклидовой плоскости.

6. Отношение равночисленности в произвольной системе конечных множеств.

7. Отношение «проживания в одном доме» в множестве жителей Соединенных Штатов.

Последний из приведенных примеров иллюстрирует на языке повсе­дневной жизни основное свойство любого отношения эквивалентности: это отношение разбивает соответствующее множество на непересекаю­щиеся подмножества, в данном случае — на множества людей, живущих в одном доме. Дадим обоснование этого предложения в общем виде. Если ρ есть отношение эквивалентности на множестве X, то подмноже­ство А множества X называется классом эквивалентности (ρ-классом эквивалентности), если существует такой элемент x из A, что А совпа­дает с множеством всех у, для которых хρу. Таким образом, А есть класс эквивалентности тогда и только тогда, когда существует такой х из X, что A = ρ [{x}]. Если насчет самого отношения ρ нет никаких не­ясностей, то множество ρ-образов элемента x из X сокращенно обозначается через [x] и называется классом эквивалентности, порожденным элементом х. Вот два основных свойства классов эквивалентности:

(I) x  [x];

(II) если xρy, то [х] = [у].

Первое из этих свойств вытекает из рефлексивности отношения эквивалентности. Чтобы доказать второе свойство, допустим, что хρу; тогда [y]  [х]; в самом деле, из z  [y] (что означает yρz) и хρу в силу транзитивности отношения ρ вытекает xρz, т. е. z  [x]. Симметричность отношения ρ позволяет доказать обратное включение [x]  [y], из чего уже следует равенство классов [х] и [у].

Из свойства (I) вытекает, что каждый элемент множества X принад­лежит некоторому классу эквивалентности, а из (II) — что два класса эквивалентности либо не пересекаются, либо совпадают, так как, если z  [x] и z  [y], то [х] = [z] и [y] = [z]. Следовательно, [x] = [y]. Вспо­миная определение разбиения непустого множества, мы получаем, что совокупность различных ρ-классов эквивалентности является разбиением множества X. Это доказывает первое утверждение следующей теоремы

Т е о р е м а 1.5. Пусть ρ есть отношение эквивалентности на X. Тогда система ρ-классов эквивалентности представляет собой разбиение мно­жества X. Обратно, если  есть некоторое разбиение множества X, а отношение ρ таково, что, по определению, аρb, когда в  существует А, для которого а  А и b  А, то ρ есть отношение эквивалентности на X. Если, далее, какое-либо отношение эквивалентности ρ определяет разбие­ние  множества X, то отношение эквивалентности, определяемое этим разбиением , совпадает с ρ. Обратно, если некоторое разбиение  мно­жества X определяет отношение эквивалентности ρ, то разбиение мно­жества X, определенное этим отношением ρ, совпадает с .

Д о к а з а т е л ь с т в о. Докажем второе утверждение теоремы. Пусть  есть разбиение множества X. Отношение ρ, о котором говорится в условии теоремы, по определению симметрично. Если а  Х, то в  най­дется такое множество А, что а  А, так что ρ рефлексивно. Покажем теперь транзитивность отношения ρ. Пусть aρb и bρc. Тогда в  най­дется такое А, что a, b  А, и такое В, что b, с  В. А раз b  А и b  B, то, значит, А = В. Следовательно, аρc.

Чтобы доказать следующее утверждение, предположим, что на X задано отношение эквивалентности ρ, определяющее разбиение  мно­жества X, и что  определяет отношение эквивалентности ρ*. Покажем, что ρ =ρ*. Пусть <x, у>ρ. Тогда х, у  [х] и [x]  . Из определения отношения ρ* следует, что хρ*у, т. е. <x, у>  ρ*. Обратно, если <x, у>  ρ*, то в  найдется такое А, что х, у  А. Но А есть ρ-класс эквивалент­ности и потому хρу, т. е. <x, у>  ρ. Таким образом, ρ = ρ*.

Заключительная часть теоремы предоставляется читателю в качестве упражнения. В качестве примера, иллюстрирующего только что доказанную тео­рему, рассмотрим отношение сравнимости по модулю n на множестве Z, определенное в третьем из примеров. В этом случае класс эквивалент­ности будет состоять из всех чисел a+kn, где k принадлежит Z. По­этому, очевидно, [0], [1], ..., [п—1] суть различные классы. Других классов нет, так как произвольное целое число а можно записать в виде a=qn+r, 0 ≤ r < n, и следовательно, а [r]. Класс чисел, сравнимых между собой по какому-либо модулю п, часто называют классом вычетов по модулю п. Совокупность классов вычетов по модулю п мы будем обо­значать Z_п. На данном примере мы можем еще раз подчеркнуть то обстоятельство, что для любого отношения эквивалентности ρ каждый класс эквивалентности определяется любым из своих членов, так как если хρу, то [x] = [y]. Таким образом, [0] = [п] = [2п] и т. д., [1] = [n+1] = [1-n] и т. д.

Пусть ρ есть отношение эквивалентности на X, тогда разбиение мно­жества X, определяемое отношением ρ, мы будем обозначать через Х/ρ (читается «X по модулю ρ») и называть фактор множеством множества X по отношению ρ. Значение разбиения множества X, соответствующего произ­вольному отношению эквивалентности ρ на X, легче уяснить путем срав­нения отношения ρ с предельным случаем отношения эквивалентности на X — с отношением тождества. Мы характеризуем тождество как пре­дельный случай отношения эквивалентности, исходя из того, что един­ственный элемент, равный какому-либо данному элементу, есть этот самый элемент. Иначе говоря, разбиение множества X, определяемое отношением тождества, есть самое полное разбиение — класс эквивалент­ности, порождаемый каким-либо элементом х, состоит из одного этого х. С другой стороны, чтобы два элемента были р-эквивалентны, они должны быть сходны между собой лишь в одном-единственном отноше­нии, а именно в отношении, характеризуемом как ρ. ρ-класс эквивалент­ности состоит из всех элементов, которые неразличимы с точки зрения отношения ρ. Таким образом, произвольное отношение эквивалентности на X определяет на X обобщенную форму равенства. Переходя от эле­ментов множества X к р-классам эквивалентности, мы попросту иден­тифицируем любые ρ-эквивалентные между собой элементы. Если ока­зывается, что ρ сохраняет какие-либо структурные особенности множе­ства X (в предположении, что таковые имеются), то в Х/ρ эти струк­турные особенности множества X проявляются в более простой форме благодаря отождествлению элементов, обусловленному переходом от X к Х/ρ. Весьма естественные примеры такого рода встретятся нам ниже.

Среди различных применений отношений эквивалентности укажем на формализацию математических понятий, или, как часто говорят, форму­лировку определений через абстракцию. Суть этой процедуры состоит в том, что понятие определяется как множество всех предметов, дающих каким-либо свойством, характеризующим по предположению это понятие. На первый взгляд, этот метод может показаться противоесте­ственным, но на практике он оказывается весьма удобным. Рассмотрим, например, следующую проблему: как определить положительные рацио­нальные числа в терминах положительных целых чисел. Вместо того чтобы прямо определять отношения целых чисел, мы вводим понятия пар целых чисел, имеющих равные отношения, посредством определения: <x, y> ~ <u, v>, если xv = yu. Определяемое таким путем отношение есть отношение эквивалентности на Z⁺*Z⁺, и мы можем теперь определить рациональное число как класс эквивалентности. Иными словами, поня­тие эквивалентности пар целых чисел позволяет нам не различать между собой эквивалентные пары из Z⁺*Z⁺. Поскольку отношение это явля­ется отношением эквивалентности, мы имеем разбиение универсума рас­суждения¹, а каждый класс эквивалентности представляет собой аб­стракцию свойства, общего для всех элементов этого класса. Именно в виде такого рода классов эквивалентности мы и определяем рацио­нальные числа. Привычный символ х/у оказывается сокращением для класса эквивалентности [<x, y>]. То обстоятельство, что класс эквива­лентности полностью определяется каждым из своих элементов, вле­чет, что в качестве имени для того же самого рационального числа мо­жет быть выбран любой другой символ u/v, обладающий тем свойством, что <u, v>  [<x, у>]. Например, утверждение 2/3 = 4/6 истинно, так 2/3 и 4/6 суть различные имена для одного и того же рационального числа.

Другим примером определения через абстракцию может служить оп­ределение понятия направления, исходящее из отношения параллель­ности, являющегося отношением эквивалентности: направление есть класс эквивалентности, состоящий из параллельных между собой прямых. Так же можно трактовать и понятие (геометрической) формы: подобие гео­метрических фигур есть отношение эквивалентности на множестве фи­гур, расположенных в евклидовой плоскости, и форма может быть опре­делена как класс эквивалентности, связанный с отношением подобия.

Основной результат, касающийся отношений эквивалентности, — то, что система всех различных ρ-классов эквивалентности является расчле­ненной и хρу в том и только в том случае, когда х и у принадлежат одному и тому же классу эквивалентности, — до сих использовался нами исключительно в связи с приложениями отношений эквивалентности. Но он может также быть положен в основу характеристического свойства, выделяющего отношения эквивалентности среди отношений вообще. Такую характеристику и описывает следующая.

Т е о р е м а 1.6. Отношение ρ тогда и только тогда является отно­шением эквивалентности, когда существует расчлененная система та­кая, что

ρ = {<x, y> | для некоторого C из  <x, y>  C*C}.

Д о к а з а т е л ь с т в о. Пусть ρ есть отношение эквивалентности на некотором множестве X. Тогда система различных ρ-классов эквива­лентности является расчлененной. Покажем, что если взять эту систему в качестве , то ρ будет обладать описанным в формулировке теоремы свойством. Покажем прежде всего, что {<x, y> | для некоторого C из  <x, y>  C*C} ρ. Пусть <х, у> принадлежит множеству, стоящему слева от знака включения в предыдущей фразе. Тогда существует такой класс эквивалентности [z], что х, у  [z]. Поэтому zρx и zρy, а следовательно, и хρу, что и означает, что <x, y>  ρ. Чтобы доказать обратное включе­ние, допустим, что <x, y>  ρ. Тогда х, у  [х], а, следовательно, <x, y>  [x]*[x].

¹ См. примечание 2 на стр. 25. — Прим. перев.

Доказательство обратного утверждения совсем просто; предоставляем его читателю.