1.3 Отношения между множествами

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

Некоторые из таких бинарных связей вам хорошо известны:

1. На множестве Z задано бинарное отношение – равенство: про любые два целых числа можно сказать, что они либо равны (связь есть), либо не равны (связи нет).

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

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

Обычно бинарное отношение обозначается буквой  (от английского relation – отношение).

Бинарное отношение – понятие весьма широкое. Нас будут интересовать бинарные отношения, подчиненные некоторым дополнительным условиям. Рассмотрим некоторые из них.

Общие свойства отношений. Отношение может быть:

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

а  а

Например, равенство и равновеликость, самообслуживание, «иметь общий делитель» обладают свойством рефлексивности, а перпендикулярность, отношения <, >,»быть братом» не обладают этим свойством или говорят антирефлексивно;

2. симметрично. Бинарное отношение  называется симметричным, если из того, что элемент а связан с элементом b этим отношением, вытекает, что и элемент b связан с элементом а этим же отношением

a  b  b  a

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

3. транзитивно (от латинского transeo –«перехожу»). Бинарное отношение  называется транзитивным, если из того, что элемент а связан с элементом b отношением , а элемент b, в свою очередь, связан с элементом с этим же отношением, вытекает, что и элемент а связан с элементом с отношением 

а  b b  с  а  с.

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

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

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

Если между любыми тремя элементами множества а, b, c установлено отношение a<b, b<c, из которого следует, что a<c, множество называют линейно упорядоченным. Например, линейно упорядоченными являются точки прямой, отрезка, произвольной кривой линии.

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

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

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

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

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

Муха – мура – тура – тара – кара – каре – кафе – кафр – каюр – каюк – крюк – крок – срок – сток – стон – слон.

Отношение может быть определено не только для пары объектов, но и для троек, четверок и т.д. (n-мерное отношение). Примером трехместных (тернарных) отношений являются арифметические операции над числами, отношения между родителями и детьми (отец, мать, ребенок) и т.п.