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

2

М. М. Шухоль

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

Попробуйте представить себе все многообразие смысловых отношений слова «класс»: «работый класс», «ученик 10-го класса», «кαιota 1-го класса», «класс млекопитающих» … Сколько различных ни казались бы эти отношения, слово «класс» во всех случаях имеет одно и то же происхождение — оно всегда связано с классификацией, или разбиением, какого-либо множества на непересекающийся классы. Понятие «класс» и его многочисленные сордини (семейство, тип, категория, вид, сорт, род, разряд и другие) ширококо использовется буквально во всех областях человека действияности. Например, когда нам требуется изучить объекты какого-нибудь множества в связи с какими-нибудь их свойствами, мы стремимся разбить это множество на классы так, чтобы все элементы одного класса были себя одинаковым образом по отношению к интерсуцишим насвойством, и тогда появляется возможность изучать целый класс объектов по одному его представителю.

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

Для разбиения множества, то есть для такого распределения его элементов по классам, при котором каждый элемент попадает в один и только один класс, обычно использует различные признаки, присущие элементам данного множества. Например, предметы, изображенные на рис. 1.

4

встречались отношения равенства (чисел, фигур, функций), отношения «больше» и «меньше» для чисел, отношения делимости для целых чисел, отношения параллельности и перpendикularности для прямых и многоугольные. В повседневной жизни распространялись отношения между людьми являются отношениями старшинства, родства, соседства, товарищества, принадежности к одной нашии, профессии.

Тепер вмотрися внимательнее в какое-нибудь одно отношение, например, в отношение равенства чисел. Числовые равенства былиют верные (истинные) и неверные (ложные). Например, равенство 5 = 5 верно, а 5 = 2 неверно. Если же $x_1$ и $x_2$ — неизвестные числа, то равенство $x_1 = x_2$ (высказывание «$x_1$ равно $x_2$») не имеет определенного значения: оно зависит от «неизвестных» $x_1, x_2$, является их функцией: при каждых конкретных числовых значениях $x_1, x_2$ оно будет истинным или ложным.

В обшем случае отношением биарным (или двуместным *) на множество $M$ мы будем называть высказывание об элементах множества $M$, зависимости от двух переменных и превращаются в истинное или ложное высказывание при подстановке в него вместе переменных любых конкретных элементов из $M$. Общно отношение записывается в виде $x_1\Theta x_2$ ($x_1 = x_2, x_1 < x_2, x_1 \parallel x_2, x_1 \perp x_2$ и т. п.). Часто вместе «отношение $x_1\Theta x_2$» говорят просто «отношение $\Theta$». Например, вместе «отношение $x_1 = x_2$» мы говорим «отношение равенства». Аналогичный смысл имеет термин «отношение порядка», «отношение соседства» и т. п. Если отношение $a\Theta b$ истинно, то говорят также, что $a$ и $b$ связаны отношением $\Theta$ или находится в отношении $\Theta$. Если отношение $\Theta$ обладает тем свойством, что из истинности $a\Theta b$ всегда следует истинность $b\Theta a$, то оно называется «симметриным». (В дальнейшем мы будем иногда называть симметрично «свойством 1».) Например, отношения параллельности и перpendикularности прямых симметрины, а отношение < на множестве действительных чисел не симметрично (5 < 8 истинно, а 8 < 5 ложно).

Отношение $\Theta$ на множестве $M$ называется рефлексиным («свойство 2»). если $a\Theta a$ истинно для любого элемента $a$ из $M$, и трансимивным («свойство 3»), если истинности $a\Theta b$ и $b\Theta c$ следует истинность $a\Theta c$. Например, отношения равенства чисел рефлексино и транситивно, отношения перpendикularности прямых не рефлексино и не транситивно, а отношение «меньше» для чисел транситивно, но не рефлексино.

Заддача. Выясните, какими из свойства 1—3 обладают отношения делимости для целых чисел, отношение «пересекаться» (то есть имеет бы одну общую точку) для прямых плоскости и отношение соседства для людей.

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

Вернемся теперь к интерсующему нас вопросу: какие отношения, определяемые на некотором множестве $M$, индуцируют разбения этого множества на классы? Иначе говоря, какими свойствами должны обладать отношения $\Theta$, в соответствии с которым множество $M$ можно разбить на такие непересекающиеся классы, чтобы

1. любые два элемента (различные или одинаковые) из одного класса находится в отношении $\Theta$,
2. никакие два элемента из разных классов не находится в отношении $\Theta$?

На этот вопрос ответа следуетющая

Теорема. Отношение $\Theta$ на множестве $M$ может и только может индуцирует разбение множества $M$, когда оно рефлексино, симметрично и трансимивно.

5

Доказательство. Пусть отношение $\Theta$ индуцирует разбиение множества $M$, то есть множества $M$ можно разбит на классы, удовлетворяющие условиям 1) и 2). Какой элемент $a$ мы ни взяли, он принадлежит некоторому классу нашего разбиения. Согласно 1), $a$ находится в отношении $\Theta$ с самим собой: $a\Theta a$ истинно, так что $\Theta$ — рефлексивно. Если, далее, $a\Theta b$ истинно, то, как следует из 1)—2), элементы $a$ и $b$ принадлежат одному классу разбиения. Тогда из 1) следует, что истинно и $b\Theta a$. Значит, для любых $a, b \in M^*$) из $a\Theta b$ следует $b\Theta a$, то есть отношение $\Theta$ симметрично.

Не читайте данные, пока сами не убедитесь в том, что отношение $\Theta$ транситивно!

Таким образом, если отношение $\Theta$ индуцирует разбиение множества $M$, то $\Theta$ рефлексивно, симметрично и транситивно: свойства 1—3 не обходимы для того, чтобы $\Theta$ индуцировало разбиение множества $M$.

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

Докажем теперь достаточно свойств 1—3. Пусть $\Theta$ обладает свойствами 1—3, и $a$ — произвольный элемент множества $M$. Обозначим через $M_a$ класс (множество) всех таких элементов $x$ из $M$, для которых истинно $a\Theta x$:

$$M_a = \{x \mid a\Theta x \text{ — истинно}\}.$$

Мы получим таким образом некоторое множество классов. Так как по свойству 1 истинно $a\Theta a$, то $a \in M_a$ (по определению класса $M_a$) и, следовательно, каждый элемент множества $M$ принадлежит хотя бы одному из полученных классов. Покажем, что любые два класса $M_a, M_b$ или совпадают, или не пересекаются. В самом деле, если $M_a$ и $M_b$ имеют хотя бы один общий элемент $c$, то $a\Theta c$ и $b\Theta c^*$. По свойству 2 из $b\Theta c$ следует $c\Theta b$, а из $a\Theta c$ и $c\Theta b$ по свойству 3 получим $a\Theta b$. Значит, $a\Theta b$ истинно. Возьмем теперь произвольный элемент $d$ из класса $M_b$. По определению класса $M_b$ истинно $b\Theta d$, а по свойству 3 из $a\Theta b$ и $b\Theta d$ следует $a\Theta d$; значит, $d \in M_a$. Итак, если $d \in M_b$, то $d \in M_a$. Аналогично доказывается, что из $d \in M_a$ следует $d \in M_b$ (проведите соответствующие рассуждания сам). Тем самым доказано, что $M_a = M_b$, то есть классы, имеющие хотя бы один общий элемент, совпадают. Таким образом, каждый элемент множества $M$ содержится в некотором классе и разные классы не пересекаются. Это и означает, что мы имеем разбиение множества $M$. Покажем, что это разбиение действительное и индуцирует отношением $\Theta$, то есть выполняются условия 1)—2). Пусть элементы $a$ и $b$ содержятся в одном классе. Так как $a \in M_a$, то это означает, что и $b \in M_a$ (в предыдущей форме оба подлежащих совершению равноправны!), то есть $a\Theta b$. Итак, любые два элемента из одного класса находится в отношении $\Theta$: выполняется условия 1). Пусть теперь $a$ и $b$ — два произвольных элемента из разных классов, так что $M_a \neq M_b$. Если бы было $a\Theta b$, то это означает, что $b \in M_a$, то есть классы $M_a$ и $M_b$ имеющие хотя бы один элемент $b$. Но тогда, по доказанному выше, было бы $M_a = M_b$, что противоречит условия. Значит, $a\Theta b$ ложно, то есть элементы из разных классов не находятся в отношении $\Theta$ (выполняется условия 2)). Теорема доказана.

При фиксировании множества $M$ элементы, содержащие в одном классе, обычно называются отношение эквивалентности, а сами классы получаемого разбиения — классами эквивалентности.

*) Знак ∈ читается «принадлежит»: $u \in M$ означает, что $a$ — элемент из множества $M$.

6

Теперь доказанную выше теорему можно сформировать короче: отношение $\Theta$ на множестве $M$ может и только моеда индуцируем разбиение множества $M$, когда оно является отношением эквивалентности.

Таким образом, если нам требуется выяснить, индуцирует ли некоторое отношение $\Theta$ разбиение какого-либо множества $M$, то нужно проверить, является ли отношение $\Theta$ отношением эквивалентности на $M$.

Например, множество всех окружностей плоскости распадается на классы концентрических окружностей, поскольку отношение концентриности окружностей рефлексировно, симметрично и транситивно. (При этом мы, естественно, считаем, что

Рис. 3.

всякая окружность концентрина сама себе.) Весьма просто проверяется также, что рефлексировно, симметрично и транситивно отношение подобия треугольников. Следовательно, множество всех треугольников разбиается на классы подобных треугольников.

Приведем один менее очевидный пример. Пусть $Q$ — множество всех дробей вида $\frac{a}{b}$, где $a, b$ — целые числа и $b \neq 0$. По каждой дроби $\frac{a}{b}$ определяем класс $Q_{a,b}$, относая дробь $\frac{c}{d}$ в этот класс в том и только в том случае, когда $ad = bc$. Получится ли в итоге разбиение всех дробей на непересекающийся классы?

Мы определили некоторое отношение $\Theta$ на множестве $Q$:

$$\frac{a}{b} \Theta \frac{c}{d}$$ тогда и только тогда, когда $ad = bc.$

Выясним, является ли $\Theta$ отношением эквивалентности.

1. Рефлексировать. Для любой дроби $\frac{a}{b} \frac{a}{b} \Theta \frac{a}{b}$, поскольку $ab = ba$.

2. Симметрировать. Если $\frac{a}{b} \Theta \frac{c}{d}$, то $ad = bc$, или $cb = da$. Последнее равенство означает, что $\frac{c}{d} \Theta \frac{a}{b}$.

3. Транзитивность. Пусть $\frac{a}{b} \Theta \frac{c}{d}$ и $\frac{c}{d} \Theta \frac{e}{f}$, то есть $ad = bc$ и $cf = de$. Умножив последнее равенство соответственно на $f$ и $b$, получим:

$$adf = bcf, \ bcf = bde.$$

Отсюда имеем $adf = bde$ и $af = be$ (на $d$ можно сократить, поскольку $d \neq 0$!). Но $af = be$ как раз и означает, что $\frac{a}{f} \Theta \frac{e}{f}$.

Таким образом, $\Theta$ — отношение эквивалентности и потому множество всех дробей распадается на непересекающийся классы эквивалентных (или, как говорят в школе, равных по величины) дробей. Итак, имея отношение эквивалентности на некотором множестве, мы можем разбить это множество на классы. Но можно поступить и наоборот: сначала разбить множество на классы, а затем определить отношение эквивалентности, считая по определению два элемента эквивалентными в том и только в том случае, когда они принадлежат одному классу рассматриваемого разбиения.

Например, таким образом появляется отношение «быть одноклассниками»: сначала детей, пришеших впервы в школе, разбиают (почти произвольно) на классы, а затем уже детей, оказавшихся в одном классе, называют одноклассниками.

Нельзя ли экономить?

Если нам часто приходится проверять, будет ли заданное отношение рефлексировным, симметриным и транситивным, то есте-

8

множество космонавтов космических кораблей «Восход» и «Восход-2», множество «части света» (без Антарктиды!) и т. п. Уже из этого небольшего перечня видно, что в один класс входят множества самой различной природы и общим для всех них является лишь то, что все они равномощны, то есть любое одно из них можно взимно однозначно отобразить на любое другое. Теперь сформирует определение натурального числа: натуральным числом называем изовем всякий класс равномощных конечных множества.

Такое определение поначалу может немало удивить: такая, вроде бы, простая штука, как натуральное число, определяется через что-то громоздкое и малообозримое — через целый класс множества! Однако если в это определение хорошо шенЬко вдуматься, свыкнуть с ним, то придется согласно, что оно действительно отражает «количественной суть» поняття натурального числа. В этом определении проявляется так называемая абстракция отохдествления: сначала мы все конечные множества разбиаем на классы равночисленных множества, затем «отождествляем» все множества одного класса и уже результат этого отождествления мыслим как неокоторое натуральное число.

Поскольку каждый класс равномощных множества вполне определяется любым своим представителем, то можно говорить о натуральном числе, определяемом любым множестром данного класса. Число, определяемое множестром $M$, обозначает через $|M|$ и называют порядком, или мощность, множества $M$. Для натуральных чисел можно ввести систему обозначений, не связанную с конкретным множествами. Конечно, это можно сделать по-разному. Исторически так и было: у разных народов были разные системы обозначений и названный натуральных чисел. (Подробнее об этом сказано в статье И. М. Яглома «Системы чисел», см. «Квант», № 6, 1970). Придерживаясь общепризнанной в настоящее время системы обозначений и названный, можно сказать, что число 1 (единица) есть класс множества, равномощных множеству столц Советского Союза, число 2 (два) есть класс множества, равномощных множеству глаз человека, и так далее. Добавляя к любому конечному множеству еще один элемент, мы получим новое множество, не равнымштою исходному. Осуществляя этот процесс, мы получим бесконечную последовательность не равномощных друг другу множества и определяемый им при натуральных чисел:

1, 2, 3, …

Ращиной говорят, что рациональный числом называется дробь вида $\frac{a}{b}$, где $a, b$ — целые числа и $b \neq 0$. Однако такое определение не полно, поскольку из него неосредственно не следует, равны или нет, например, числа $1/2$ и $3/6$. Поэтому приходит сразу же добавлять: рациональные числа $\frac{a}{b}$ и $\frac{c}{d}$ равны в том и только в том случае, когда $ad = bc$. В итоге получается, что рациональный число это не просто дробь, а целый класс дробей. Таким образом, понятие рационального числа более аккуратно вводится следующим образом.

Рассмотрим множество $Q$ всех дробей и определим на $Q$ относение $\Theta$, положив $\frac{a}{b} \Theta \frac{c}{d}$ тогда и только тогда, когда $ad = bc$. Выше мы уже показали, что такое $\Theta$ есть относение эквивалентности и, значит, множество $Q$ развиется на непересекающийся классы. Любые две дроби одного класса указанного разбиения мы и будем назвать аккуватнымми. Теперь можно сформировать определение: рациональный числом называется всякий класс эквивалентных дробей. После всего сказаного ранее по поводу определения натурального числа мы сcribe рациональный число как класс дробейсовсем просто.