Глава 3. Отношения множеств

В главе 1 речь шла о том, что элементы множества могут находиться в некоторых отношениях между собой или с элементами других множеств. Были рассмотрены два таких отношения: принадлежность и включение . Первое из них определяет связь между множеством и его элементами, а второе – между двумя множествами.

В самом общем смысле отношение означает какую-либо связь между предметами или понятиями. Отношения между парами объектов называют бинарными. Примерами бинарных отношений являются равенство (=), неравенства ( или <), а также такие выражения как «быть братом», «делиться на какое-то число», «входить в состав чего-либо» и т. п.

Для любого бинарного отношения можно записать соответствующее ему соотношение (для отношения неравенства соотношением будет , для отношения «быть братом» соотношение запишется )

В общем виде бинарные отношения устанавливают соответствие элементов одного множества элементам другого множества . Ясно, что такое отношение может быть задано некоторой совокупностью упорядоченных пар ( ), которые являются элементами множества . Это вовсе не значит, что всегда нужно перечислять все такие пары. Часто отношение задается некоторым свойством, выраженным в словесной или символической форме.

Если – отношение, то соотношение можно записать также в виде , где . Например, выражения и обозначают одно и тоже, но первое из них привычнее В то же время означало бы , что неверно. Таким образом, в общем случае переставлять элементы в паре ( ) нельзя, что и подчеркивается названием этой пары – упорядоченной. Элемент называют первой координатой, а элемент – второй координатой упорядоченной пары.

Множество первых координат является областью определения (левой областью) , а множество вторых координат – областью значений (правой областью) отношения . Если и , то и . В таких случаях говорят, что есть отношение от к . Его называют также соответствием и обозначают . Если , то любое отношение является подмножеством множества и называется отношением в .

Пусть, например, и . Произведение этих множеств . Отношение = есть множество , а отношение > есть пустое множество . Области определения и значений отношения – это соответственно множества и . Если область определения отношения совпадает с некоторым множеством , то говорят, что отношение определено на .

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

Заслуживают внимания три частных случая отношений в :

1) полное (универсальное) отношение , которое имеет место для каждой пары ( ) элементов из (например, отношение «работать в одном отделе» на множестве сотрудников данного отдела);

2) тождественное (диагональное) отношение , равносильное (например, равенство на множестве действительных чисел);

3) пустое отношение, которому не удовлетворяет ни одна пара элементов из (например, отношение «быть братом» на множестве женщин).

Очевидно, для любого отношения в справедливо .

Рассмотрим отношение . Если , то сечение по , отношения , обозначаемое , есть множество таких, что . Множество всех сечений отношения называют фактор-множеством множества по отношению и обозначают . Оно полностью определяет отношение .

Пусть, например, ; и

.Очевидно, ; и т. д. Если записать под каждым элементом из соответствующее сечение отношения , то элементы второй строки образуют фактор-множество :

Объединение сечений по элементам некоторого подмножества является сечением этого подмножества, т. е. . Так для рассмотренного примера,

Так как отношение – это множества, то над ними можно выполнять все рассмотренные ранее теоретико-множественные операции. Кроме этого, определяются специфические для отношений операции: обращение и композиция.

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

Пусть даны три множества и два отношения и . Композиция отношений и есть отношение , состоящее из всех тех пар , для которых существует такое , что и . Сечение отношения по совпадает с сечением отношения по подмножеству , т. е. . Рассмотрим, например, два отношения:

и

.

Очевидно,

. Сечение . С другой стороны,

.

Композицию отношений и обычно записывают как , тогда .

Композиция отношений обладает ассоциативным законом, т. е. , но не коммутативна ( ). Можно также показать, что .

Пусть – бинарное отношение в множестве . Определим общие свойства таких отношений, которые должны выполняться для всех . Говорят, что :

1) рефлексивно, если ( – тождественное отношение), т. е. оно всегда выполняется между объектом и им самим: (равенство, самообслуживание);

2) антирефлексивно, если , т. е. может выполняться только для несовпадающих объектов: из следует (строгое неравенство);

3) симметрично, если , т. е. при выполнении соотношения выполняется и соотношение (расстояние между двумя точками);

4) асимметрично, если , т. е. из двух соотношений и по меньшей мере одно не выполняется (строгое включение); если отношение асимметрично, то оно и антирефлексивно;

5) антисимметрично, если , т. е. оба соотношения и выполняются одновременно только тогда, когда (нестрогое неравенство);

6) транзитивно, если , т. е. из и следует («быть родственником»).

Кроме рассмотренных ранее отношений принадлежности и включения рассмотрим отношения эквивалентности, порядка и толерантности.

Отношение эквивалентности представляет собой замену таких обыденных слов как «одинаковость», «неразличимость», «взаимозаменяемость». Эквивалентность обозначается знаком ~. При этом означает, что упорядоченная пара принадлежит множеству , являющимся отношением эквивалентности в множестве . Эквивалентность удовлетворяет условиям рефлексивности, симметричности, транзитивности, что записываются следующим образом:
1) (рефлексивность); 2) если , то (симметричность); 3) из и следует (транзитивность).

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

Например, отношение «проживать в одном доме» в множестве жителей города является эквивалентностью и разбивает это множество на непересекающиеся подмножества людей, являющихся соседями по дому. Примерами отношений эквивалентности могут служить подобие или равенство треугольников на плоскости, параллельность прямых, утверждение «быть таким же» и т. п.

Все элементы, принадлежащие некоторому классу разбиения множества , связаны отношением эквивалентности. Они взаимозаменяемые в том смысле, что любой из этих элементов определяет данный класс, т. е. может служить его представителем (эталоном). Подмножество из , содержащее по одному и только по одному элементу из каждого класса некоторого разбиения, называют системой представителей соответствующего отношения эквивалентности. Множество всех классов разбиения множества , определяемого отношением эквивалентности , образует фактор-множество . Например, отношение параллельности определяет разбиение множества прямых на плоскости на классы, каждый из которых образован множеством параллельных между собой прямых и характеризуется некоторым направлением (следует также считать, что прямая параллельна самой себе). Любая из параллельных прямых может служить представителем данного класса, а само направление есть класс эквивалентности. Множество всех направлений составляет фактор-множество множества всех прямых по отношению параллельности.

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

Предельным случаем отношения эквивалентности является тождественное равенство. Единственный элемент, равный какому-либо данному элементу, есть этот самый элемент. Следовательно, имеем самое полное разбиение, при котором классы эквивалентности содержат только по одному элементу исходного множества.

Отношение порядка принято обозначать символом . Запись означает, что пара ( ) принадлежит множеству , являющемуся отношением порядка в множестве , причем предшествует (или следует за ). Отношение порядка обладает свойствами рефлексивности, транзитивности и антисимметричности, которые в принятых обозначениях записываются следующим образом: 1) (рефлексивность); 2) если и то (транзитивность); 3) из и следует (антисимметричность).

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

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

Отношение, наделенное свойствами транзитивности и антирефлексивности (следствиями этих двух свойств являются также асимметричность и антисимметричность), называют отношением строгого порядка и обозначают символом <. Свойство антирефлексивности означает, что элемент множества не может сравниваться сам с собой (как в случае строгого неравенства или строгого включения). В отличие от него отношение называют нестрогим порядком. Между отношениями строгого и нестрогого порядка имеют место соотношения ( )= и , где – тождественное отношение.

Отношение строгого порядка характерно для различного рода иерархий с подчинением одного объекта другому (или другим). Если для некоторой совокупности элементов из справедливо соотношение , то в соответствии со свойством транзитивности , т. е. отношение строгого порядка обусловливает как прямое, так и косвенное подчинение по старшинству.

Элементы любого конечного множества можно пронумеровать порядковыми числами . Для счетного множества нумерацию следует понимать как взаимнооднозначное отображение множества натуральных чисел на М, которое каждому числу ставит в соответствие некоторый элемент из . Упорядоченное таким отображением множество называется последовательностью (конечной или бесконечной). Элемент из называют членом последовательности с индексом .

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

Отношение толерантности на множестве , обозначаемое символом , удовлетворяет свойствам рефлексивности и симметричности. Упорядоченная пара принадлежит множеству , если: 1) и 2) из следует . Для этого отношения, в отличие от эквивалентности, транзитивность не обязательна, и значит эквивалентность есть частный случай толерантности.

Отношение толерантности представляет собой перевод интуитивных представлений о сходстве и неразличимости в ранг математических понятий. Каждый объект неразличим сам с собой (рефлексивность), а сходство двух объектов не зависит от того, в каком порядке они сравниваются (симметричность). В то же время, если один объект сходен с другим, а другой сходен с третьим, то это вовсе не означает, что все они обязательно сходны между собой, т. е. свойство транзитивности может не выполняться.

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

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

Пусть множество объектов и множество признаков. Каждому элементу из соответствует некоторое подмножество признаков ( ). Следовательно, сходство между объектами и определяется толерантностью соответствующих им подмножеств и из , т. е. условием .

Если рассматривать соответствие между объектами и признаками как бинарное отношение между множеством объектов и множеством признаков , то элементами будут упорядоченные пары , в каждой из которых первая координата является объектом, а вторая – признаком. Очевидно, множество признаков объекта является сечением этого отношения, т. е. . Все такие сечения полностью определяют бинарное отношение .

Итак, толерантность на множестве объектов можно задать с помощью некоторого всюду определенного бинарного отношения от к следующим образом: для любой пары объектов и из имеет место , если и только если .