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

Если хотите быстро ознакомится с содержанием статей, смотрите ниже.
Текст, для быстрого ознакомления (в тексте для быстрого ознакомления формулы могут отображаться не корректно):

Страница переведена на новый сайт https://myeducation.su/ :

страница ФИЗИКО-МАТЕМАТИЧЕСКИЙ ЖУРНАЛ Квант (1972)

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

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

сунке 1, можно разбить на классы
по цвету (рис. 2, о), по форме (рис.
2, б) или по какому-нибудь другому
признаку. Впрочем, для разбиения
множества на классы нам нужны не
столько свойства, присущие
каждому элементу в отдельно-
с т и, сколько правила, указываю-
щие, в один или в раз>1ые классы сле-
дует отнести два произвольно выб-
ранные элемента данного множества.
Например, все прямые плоскости мож-
но разбить на классы, если догово-
риться две прямые относить в один
класс в том и только в том случае,
когда они параллельны. В получен-
ном разбиении любые две (не обяза-
тельно различные *)) прямые одного
класса параллельны, а любые две
прямые из разных классов не парал-
лельны. В этом примере мы пользу-
емся не признаком, которым обладает
или не обладает каждая отдельно
взятая прямая, а свойством, отно-
сящимся к п а р а м прямых (прямые
а и b параллельны или не параллель-
ны). Про построенное разбиение
прямых говорят, что оно и н д у-
цировано отношением парал-
«) Иначе говоря, мы уславливаемся счи-
тать, что кяжд.чя прямая параллельна самой
себе.
лельности. О рассмотренных выше
разбиениях предметов рисунка 1 так-
же можно сказать, что они индуци-
рованы некоторыми отношениями.
Так, разбиение по цвету индуцирова-
но отношением «иметь одинаковый
цвет».
Вместе с тем. не рг« -ое отношение
между элементами л. жества инду-
цирует разбиение этого множества на
классы. Например если бы мы попы-
тались всех л\с чей распределить
по непересекающимся группам так,
чтобы любые два человека одной груп-
пы уважали друг друга, а два челове-
ка из разных групп не уважали бы
или не знали друг друга, то, очевидно,
из этой затеи ничего бы не вышло.
Проверьте, будет ли отношение пер-
пендикулярности индуцировать рязбненне
всех прямых плоскости.
Чтобы выяснить и точно сформу-
лировать условия, при которых от-
ношение между элементами множест-
ва индуцирует разбиение этого мно-
жества на классы, уточним сначала
само понятие отношения.

Что такое отношение?

Начнем с того, что вспомним не-
которые знакомые отношения. Так.
в школьной математике вам часто

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

встречались отношение равенства
( чисел, фигур, функций), отношения
«больше» и «меньше» для чисел, от-
ношение делимости для целых чисел,
отношения параллельности и перпен-
дикулярности для прямых и многие
другие. В повседневной жизни рас-
пространенными отношениями меж-
ду людьми являются отношения стар-
шинства, родства, соседства, това-
рищества, принадлежности к одной
нации, профессии.
Теперь всмотримся внимательнее
в какое-нибудь одно отношение, на-
пример, в отношение равенства чи-
сел. Числовые равенства бывают вер-
ные (истинные) и неверные (ложные).
Например, равенство 5 —- 5 верно, а
5 = 2 неверно. Если же Xi и х2 —
неизвестные числа, то равенство
xi = *г (высказывание «xt равно
х2») не имеет определенного значе-
ния: оно зависит от «неизвестных»
х1э х2, является их функцией: при
каждых конкретных числовых зна-
чениях Xj, хг оно будет истинным
или ложным.
В общем случае отношением би-
нарным (или двуместным *)) на мно-
жестве М мы будем называть выска-
зывание об элементах множества М,
зависящее от двух переменных и прев-
ращающееся в истинное или ложное
высказывание при подстановке в него
вместо переменных любых конкрет-
ных элементов из М. Обычно отно-
шение записывают в виде х,6 х? (хг=
-Х2, X!<X2, Хг || Х2, XjJLXjj И Т. П.).
Часто вместо «отношение *,вх2» гово-
рят просто «отношение в».Например,
вместо «отношение xl=x^> мы гово-
рим «отношение равенства». Анало-
гичный смысл имеют термины «от-
ношение порядка», «отношение па-
раллельности», «отношение соседст-
ва» и т. п. Если отношение aQb истин-
но, то говорят также, что а и b свя-
заны отношением 0 или находятся
в отношении в. Если отношение в
обладает тем свойством, что из ис-
тинности aQb всегда следует истин-
*) В дальнейшем мы будем писать просто
«отношение».

ность ЬВа, то оно называется сим-
метричным. (В дальнейшем мы будем
иногда называть симметричность
«свойством Ь.) Например, отношения
параллельности и перпендикуляр-
ности прямых симметричны, а отно-
шение <; на множестве действитель-
ных чисел не симметрично E < 8 истин-
но, а 8<|5 ложно).
Отношение в на множестве М на-
зывается рефлексивным («свойство 2»).
если а&а истинно для любого элемен-
та а из М, и транзитивным («свойство
3»), если из истинности aQb и Ь0с сле-
дует истинность обе. Например,
отношение равенства чисел рефлек-
сивно и транзитивно, отношение
перпендикулярности прямых не реф-
лексивно и не транзитивно, а отноше-
ние «меньше» для чисел транзитивно,
но не рефлексивно.
Задача. Выясните, какими из свойств
1—3 обладают отношения делимости для це-
лых чисел, отношение «пересекаться» (то есть
иметь хотя бы одну общую точку) для пря-
мых плоскости и отношение соседства для
людей.

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

Вернемся теперь к интересующему
нас вопросу: какие отношения, оп-
ределенные на некотором множестве
М, индуцируют разбиения этого
множества на классы? Иначе говоря,
какими свойствами должно обладать
отношение 0, в соответствии с ко-
торым множество М можно разбить
на такие непересекающиеся классы,
чтобы
1) любые два элемента (различные
или одинаковые) из одного класса
находились в отношении 0,
2) никакие два элемента из разных
классов не находились в отноше-
нии 6?
На этот вопрос отвечает следую-
щая
Теорема. Отношение В на
множестве М тогда и только тогда
индуцирует разбиение множества М,
когда оно рефлексивно, симметрично
и транзитивно.

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

Доказательство. Пусть
отношение в индуцирует разбиение
множества М, то есть множество Л1
можно разбить на классы, удовлетво-
ряющие условиям 1) и 2). Какой бы
элемент а мы ни взяли, он принадле-
жит некоторому классу нашего раз-
биения. Согласно 1), а находится
в отношении 0 с самим собой: aQa
истинно, так что 6 — рефлексивно.
Если, далее, а(-)Ь истинно, то, как
следует из 1)—2), элементы а и b при-
надлежат одному классу разбиения.
Тогда из 1) следует, что истинно
и bQa. Значит, для любых д, b ? М *)
из а&Ь следует /;ва, то есть отноше-
ние 0 симметрично.
Не читайте дальше, пока сами не убеди-
тесь в том, что отношение 6 тракзнтнвно!
Таким образом, если отношение
0 индуцирует разбиение множества
М, то 0 рефлексивно, симметрично
и транзитивно: свойства 1—3 н е-
обходи м ы для того, чтобы 0
индуцировало разбиение множест-
ва М.
Теперь ясно, почему мы не смогли ряз-
делнть человечество на группы уважающих
лруг друга людей и почему отношение пер-
пендикулярности не индуцировало разбиение
прямых плоскости. Отношения «уважения»
и перпендикулярности не транзитивнм (и не
рефлекрнпны).
Докажем теперь достаточ-
ность свойств 1—3. Пусть 0 об-
ладает свойствами 1—3, и а —¦ про-
извольный элемент множества М.
Обозначим через Мв класс (множест-
во) всех таких элементов х из М,
для которых истинно а&х:
Мп = |.v j аВх — истинно:.
Мы получим таким образом некоторое
множество классов. Так
как по свойству I истинно ада.
то а ? /VJ,, (по определению класса
Ма) и. следовательно, каждый эле-
мент множества /VI принадлежит
хотя бы одному из полученных клас-
сов. Покажем, что любые два класса
Ма, Мь или совпадают, или не пересе-
каются. В самом деле, если М. п
Мь имеют хотя бы один общий эле-
мент с, то а0с и ЬВс*). По свойству
2 из b0с следует cBb, a из а0с и с&Ь
по свойству 3 получим аОЬ. Значит,
а&Ь истинно. Возьмем теперь про-
извольный элемент d из класса Мь.
По определению класса Мь истинно
bQd, а по свойству 3 из а06 и bQd
следует aQd; значит, d?Ma. Итак,
если й?Мь, то d?Ma. Аналогично
доказывается, что из d g Ma следует
d ^ Мь (проведите соответствующие
рассуждения сами). Тем самым до-
казано, что Ма = Мь, то есть классы,
имеющие хотя бы один общий элемент,
совпадают. Таким образом, каждый
элемент множества М содержится в
некотором классе и разные классы не
пересекаются. Это и означает, что
мы имеем разбиение множества М.
Покажем, что это разбиение действи-
тельно индуцируется отношением 0,
то есть выполняются условия 1)—2).
Пусть элементы а и b содержатся в
одном классе. Так как а?Мп, то это
означает, что и Ь?Ма (в предыду-
щей фразе оба подлежащих совер-
шенно равноправны!), то есть aQb.
Итак, любые два элемента из одного
класса находятся в отношении в:
выпачняется условие 1). Пусть теперь
а и b — два произвольных элемента
из разных классов, так что МафМь.
Если бы было G0&, то это означало бы,
что Ь~.МЯ, то есть классы Мп и Мь
имели бы общий элемент Ь. Но тогда,
по доказанному выше, было бы Ма —
— М,„ что противоречит условию.
Значит, й0у ложно, ю есть элементы
из разных классов не находятся в от-
ношении 0 (выполняется условие 2)).
Теорема доказана.
При фиксированном разбиении
множества М элементы, содержащие-
ся в одном классе, обычно называют
эквивалентны м и. В связи
с этим всякое рефлексивное, симмет-
ричное и транзитивное отношение на-
зывают отношением эквивалентности,
а сами классы получаемого разбие-
ния — классами эквивалентности.
*) Знак читается «’принадлежит»:
•j ? М означает, что а — элемент и,ч мно-
жества М.
*) В тех местах, где это не приводит к
недоразумениям, мы будем опускать слово

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

Теперь доказанную выше теорему
можно сформулировать короче: от-
ношение 0 на множестве М тогда
и только тогда индуцирует разбиение
множества М, когда оно является
отношением эквивалентности.
Таким образом, еелн нам требует-
ся выяснить, индуцирует ли некото-
рое отношение в разбиение какого-
либо множества М, то нужно прове-
рить, является ли отношение 0 от-
ношением эквивалентности на М.
Например, множество всех ок-
ружностей плоскости распадается на
классы концентрических окружно-
стей, поскольку отношение концент-
ричности окружностей рефлексивно,
симметрично и транзитивно. (При
этом мы, естественно, считаем, что
Рме. Ъ.
всякая окружность концентрична
сама себе.) Весьма просто проверяет-
ся также, что рефлексивно, симмет-
рично и транзитивно отношение подо-
бия треугольников. Следовательно,
множество всех треугольников раз-
бивается на классы подобных тре-
угольников.
Приведем один менее очевидный
пример. Пусть Q—множество всех
дробей вида -—-, где а, Ъ — целые
числа и ЬфО. По каждой дроби ~-
оиределим класс Qab, относя дробь
~ п этот класс в том и только в том
а
случае, когда ad = be. Получится ли
в итоге разбиение всех дробей на
непересекающиеся классы?
Мы определили некоторое отно-
шение в на множестве Q:
~- 0 ~- тогда и только тогда, когда
ad = be.

Выясним, является ли 0 отноше-
нием эквивалентности.
1. Рефлексивность. Для
любой дроби ~- -у в ~, посколь-
ку ab = Ьа.
2. С и м м е т р и ч н о с т ь. Если
-у- fc> ~, то ad —- be, или cb = На.
Последнее равенство означает, что
-?— п а
3. Т р а н з и т и в н о с т ь. Пусть
-г- 0 —т- и -з- 0 -г-, то есть
6 d d f
ad =* be и cf — de. Умножив послед-
ние равенства соответственно на /’ и Ь,
получим:
adf — bef, bef ~ bde.
Отсюда имеем adf = bde и af — be
(на d можно сократить, поскольку
&ф 0!). Но af — be как раз и означает,
а ,, е
ЧТО -J-&-J-.
Таким образом, 0 —• отношение
эквивалентности и потому множест-
во всех дробей распадается на непе-
ресекающиеся классы эквивалентных
(или. как говорят в школе, равных
по величине) дробей. Итак, имея от-
ношение эквивалентности на не-
котором множестве, мы можем раз-
бить это множество на классы. Но
можно поступить к наоборот: снача-
ла разбить множество на классы,
а затем определить отношение эк-
вивалентности, считая по опре-
делению два элемента эквива-
лентными в том и только в том слу-
чае, когда они принадлежат одному
классу рассматриваемого разбиения.
Например, таким образом появляет-
ся отношение «быть одноклассника-
ми»: сначала детей, пришедших впер-
вые в школу, разбивают (почти про-
извольно) на классы, а затем уже
детей,, оказавшихся в одном классе,
называют одноклассниками.

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

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

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

венно возникает вопрос: не является ли ка-
кое-нибудь из указанных свойств I—3 ло-
гическим следствием двух других (в этом
случае нам не пришлось бы делать проверку
всех трех свойств)?
Оказывается, это не так: свойства реф-
лексивности, симметричности и транзитив-
ности независимы. Чтобы доказать,
что некоторое свойство не зависит от двух
других, достаточно привести пример отно-
шения, обладающего двумя последними свой-
ствами, но не обладающего рассматриваемым.
Например, отношение г^ на множестве
действительных чисел рефлексивно и тран-
зитнвно, но не симметрично. Значит, сим-
метричность не является следствием рефлек-
сивности и транзитивности. Свойство тран-
зитивности также не вытекает из двух других.
Например, для прямых плоскости отношение
«прямая *! совпадает с прямой х2 или пер-
пендикулярна к дг5», рефлексивно и симмет-
рично, но не транзнтнвно. (Проверьте!)
Пример, показывающий независимость
рефлексивности от двух других свойств,
постарайтесь привести сами.

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

Мы уже говорили о значении раз-
биений множества на классы (или,
как теперь можно сказать, отноше-
ний эквивалентности) в различных
областях человеческой деятельности.
Очень важную роль играет отноше-
ние эквивалентности в математике.
Кроме упоминавшихся ранее, можно
привести много других примеров от-
ношений эквивалентности, с которы-
ми вы встречались в школьной ма-
тематике. Таковы, например, отно-
шение «иметь одну и ту же абсолют-
ную величину» для чисел, отноше-
ние равенства двух алгебраических
выражений, отношение равновели-
кости многоугольников и многие
другие.
Рассмотрим подробнее два при-
мера, показывающие, как отноше-
ния эквивалентности используются
при образовании важнейших поня-
тий математики.
Натуральные числа.
Понятие натурального числа было
выработано человечеством в процес-
се длительного исторического раз-
вития. Прежде чем человек научился
абстрактно представлять себе число 5,
он научился откладывать 5 камеш-
2*
ков, делать 5 зарубок, завязывать
5 узелков и т. п. и сравнивать эти
«стандартные» множества с другими
встречающимися ему множествами
путем установления взаимно
однозначного соответ-
ствия между ними. Этот процесс
абстрагирования «в ускоренном тем-
пе» каждый на нас проходит в детст-
ве, приучаясь сначала выделять два
глаза, два яблока, две машины и т. д.
и только затем уже представлять себе
число 2. Теперь, когда этот путь аб-
страгирования каждым из нас, надо
полагать, уже давно пройден, попы-
таемся уяснить себе сущность поня-
тия натурального числа. С этой целью
определим следующее отношение G
между конечными множествами: бу-
дем считать, что два конечных мно-
жества М и N находятся в отношении
в тогда и только тогда, когда сущест-
вует взаимно однозначное отображе-
ние множества М на N. (О понятии
отображения множеств можно яро-
честь, например, в статье А. Н. К о л-
могорова «Что такое функция»
в N° 1 «Кванта» за 1970 год.) Легко
проверить, что введенное таким пу-
тем отношение 0 рефлексивно, сим-
метрично и транзитивно. (Проверьте!)
Следовательно, оно является отно-
шением эквивалентности, и потому
все конечные множества разбиваются
в соответствии с ним на классы. Лю-
бые два множества из одного класса
полученного разбиения и называют эк-
вивалентными. Впрочем, чаще,—чтобы
отличить полученное разбиение от
прочих разбиений, индуцируемых про-
извольными рефлексивными, симмет-
ричными и транзитивными отноше-
ниями (напомним, что любое та-
кое отношение есть отношение эк-
вивалентности; примером может слу-
жить хотя бы отношение, отождеств-
ляющее, с одной стороны, все четные
числа, а с другой, — все нечетные) —
эквивалентные в этом смысле мно-
жества называют равномощными,
или равночисленными. Например в
классе, содержащем множество букв
|а, б, в, г, д} будут содержаться
множество пальцев на руке человека,

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

Множество космонавтов космических
кораблей «Восход» и «Восход-2», мно-
жество «частей света» (без Антаркти-
ды!) и т. п. Уже из этого небольшого
перечня видно, что в один класс вхо-
дят множества самой различной при-
роды и общим для всех них является
лишь то, что все они равномошны,
то есть любое одно из них можно вза-
имно однозначно отобразить на любое
другое. Теперь сформулируем опре-
деление натурального числа: на-
туральным числом назовем всякий
класс равномощных конечных мно-
жеств.
Такое определение поначалу мо-
жет немало удивить: такая, вроде бы,
простая штука, как натуральное
число, определяется через что-то
громоздкое и малообозримое — через
целый класс множеств! Од-
нако если в это определение хоро-
шенько вдуматься, свыкнуться с ним,
то придется согласиться, что оно дей-
ствительно отражает «количествен-
ную суть» понятия натурального чис-
ла. В этом определении проявляется
так называемая абстракция отож-
дествления: сначала мы все конечные
множества разбиваем на классы рав-
ночисленных множеств, затем «отож-
дествляем» все множества одного клас-
са и уже результат этого отождествле-
ния мыслим как некоторое натураль-
ное число.
Поскольку каждый класс равно-
мощных множеств вполне определя-
ется любым своим представителем,
то можно говорить о натуральном
числе, определяемом любым множест-
вом данного класса. Число, опреде-
ляемое множеством М, обозначают
через \М\ и называют порядком,
или мощностью, множества М. Для
натуральных чисел можно ввести сис-
тему обозначений, не связанную с
конкретными’ множествами. Конечно,
это можно сделать по-разному. Исто-
рически так и было: у разных наро-
дов были разные системы обозначений
и названий натуральных чисел. (Под-
робнее об этом сказано в статье
И. М. Я г л о м а «Системы счисле-
ния», см. «Квант», № 6, 1970). При-
в
держиваясь общепринятой в настоя-
щее время системы обозначений и
названий, можно сказать, что число 1
(единица) есть класс множеств, рав-
номощных множеству столиц Совет-
ского Союза, число 2 (два) есть класс
множеств, равномощных множеству
глаз человека, и так далее. Добавляя
к любому конечному множеству еще
один элемент, мы получим новое мно-
жество, не равнвмощное исходному.
Осуществляя этот процесс, мы полу-
чим бесконечную последовательность
не равномощных друг другу множеств
и определяемый ими ряд натураль-
ных чисел:
1. 2, 3
Рациональные числа.
Обычно говорят, что рациональным
числом называется дробь вида •— ,
где a, b — целые числа и ЬфО. Однако
такое определение не полно, посколь-
ку из него непосредственно не следует,
равны или нет, например, числа Va
и 3/в- Поэтому приходится сразу же
добавлять: рациональные числа -г- и
Л- равны в том и только в том случае,
когда ad = be. В итоге получается,
что рациональное число это ке просто
дробь, а целый класс дробей.
Таким образом, понятие рациональ-
ного числа более аккуратно вводится
следующим образом.
Рассмотрим множество Q всех дро-
бей и определим на Q отношение в,
положив -?- в-4- тогда и только тог-
о а
да, когда ad = be. Выше мы уже пока-
зали, что такое в есть отношение
эквивалентности и, значит, множест-
во <3 разбивается на непересекающи-
еся классы. Любые две дроби одного
класса указанного разбиения мы и
будем называть эквивалентными.
Теперь можно сформулировать опре-
деление: рациональным числом на-
зывается всякий класс эквивалент-
ных дробей. После всего сказанного
ранее по поводу определения нату-
рального числа мыслить себе раци-
ональное число как класс дробей
совсем просто.

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

Как складывать и ум-
ножать классы? После вве-
денных выше определений натураль-
ного и рационального чисел естествен-
но возникает вопрос: как определить
арифметические опера-
ции над числами-классами? Для
примера покажем, как определить
умножение рациональных чисел, счи-
тая, что все операции над целыми
числами нам уже знакомы.
Пусть а и Р — два рациональных
числа-класса. Возьмем из этих клас-
сов по какой-нибудь одной дроби
¦— и -j- и определим их произведе-
ние, положив
а с _ ас_
Полученная дробь —-, как и всякая
дробь, принадлежит вполне опреде-
ленному классу дробей у. Этот класс
мы и назовем произведением классов
а и Р: «Р = у.
Таким образом, чтобы перемно-
жить классы, нужно выбрать из них
по одному (любому!) представителю,
перемножить эти представители как
дроби и взять класс, содержащий
полученную в итоге дробь.
Сразу же, однако, возникает во-
прос: не может ли получиться при
умножении другой класс, если вы-
брать другие представители из клас-
сов аир? Покажем, что это не так.
а’ с’
Пусть -р~ и -jp какие-нибудь
другие представители классов а и р.
Так как — и -р- принадлежат одно-
му классу а, то-^- 0 -рт-, то есть ab’=
= Ьа’. Аналогично получим cd’ —
= dc’. Перемножая почленно два по-
следних равенства, найдем acb’d’ =
= bda’c’. Но это означает, что
Ш» ® Т^Р» ЗначИ1\ «новое» произве-
дение дробей ~7 принадлежит тому
ас
же классу у, что Итт-.

Упражнения

1. Пусть et и в2 — два отношения эк-
вивалентности на некотором множестве М.
Будут ли отношением эквивалентности на М
отношения в, определенные следующим об-
разом: а) aQb истинно тогда и только тогда,
когда истинно aQtb или аВгЬ; б) aQb истинно
тогда и только тогда, когда истинны ев^
и аЭ2Ь; в) aQb истинно тогда и только тогда,
когда истинно aQxb и ложно а&2Ь.
2. Пусть / (х) — функция на множестве
действительных чисел. Определим отноше-
ние в/, положив aQjb истинным тогда и толь-
ко тогда, когда / (о) = Ь. Что можно сказать
о графике функции [ (дс), если отношение
в/ симметрично? Найти функцию / (дс), для
которой в/ является отношением эквива-
лентности. Каковы в этом случае классы
эквивалентности?

Только ли математика? Что читать
В самом начале этой статьи говорилось
об универсальном характере и применимости
разбираемых в ней понятий. В дальнейшем
же, однако, изложение носило по возмож-
ности счисто математический» характер. Это
не случайно: вопрос об отношениях эквива-
лентности (и связанных с ними разбиениях)
вне рамок математики настолько интересен
и глубок, что вскользь его разбирать не стоит.
Читателю, заинтересовавшемуся этой проб-
лематикой, мы прежде всего хотим пореко-
мендовать две изданные в издательстве «Нау-
ка» книги: «Проблемы узнавания» М. М.
Бонгарда A9С7) и «Равенство. Сход-
ство. Порядок». Ю. А. Шрейдера
A971). Многое в них может показаться вам
(и совершенно справедливо!) довольно труд-
ным и сложным, но то, что вы при внима-
тельном чтении усвоите из этих книг, все
равно послужит лучшей подготовкой к бо-
лее широкому обсуждению понятия эквива-
лентности, которое редакция «Кванта» пред-
полагает провести в будущем. Предлагаем
вам также в связи с этим перечитать статью
В. Р а с к и и а «Еще раз о машинном пе-
реводе» из «Кванта» № 12 за 1971 год и по-
пытаться найти в ней примеры отношений
эквивалентности; это послужит неплохим
самоконтролем усвоения изложенных выше
понятий.

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

 

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