§ 7. Составные отношения

Подобно тому как мы устанавливали внутренние связи в файлах, для выделения некоторых данных из информации (например, ПОСТАВЩИК и МЕСТО РАС­ПОЛОЖЕНИЯ 3 посредством файлов DEL и SUP4 в примере 6.3) часто приходится связывать бинарные от­ношения друг с другом. Руководствуясь предыдущими рассуждениями, можно определить это понятие следую­щим образом.

Определение. Пусть заданы множества А, В и С и отношения между А и В и между В и С. Опреде­лим отношение между А и С следующим образом: оно действует из А в B посредством , а затем из B в C по­средством . Такое отношение называют составным и обозначают ° , т. е.

( ° )(a)= ( (a)). //

Следовательно, (х,y) ( ° ), если существует z B такое, что (х,z) и (z,y) .Отсюда следует, что _° = ^-1 . Чтобы проиллюстрировать ситуацию, рас­смотрим рис. 2.11.

Области определения и значений и заштрихованы в разных направлениях. Следовательно, сегменты с двойной штриховкой на A, B и C представ­ляют собой _° , и _° соответственно. Замечание. Из записи отношений и следует, что они применяются справа налево. Следовательно, ( ° ) (a) означает, что вначале берется a и преобразу­ется посредством , а затем

Р ис. 2.11

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

Рис. 2.12

Пример 7.1. Пусть и — отношения на N такие, что

= {(x, x+1):x N}, = {(x², х): х N}.

Тогда = {x²: x N}, = {x: x, x+1 N} = N,

_° = ^-1 = {x: x N и x+1=y², где y N}={3, 8, 15, 24,…}

(рис. 2.12). //

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

° = {(х, х + 2): x N} и ° = {(x⁴, x): х N}.

Эти отношения можно также обозначать соответственно ² и ². В общем-то эти обозначения не совсем законны для множеств, однако их легко можно обосновать, по­скольку если (х, y) ° , то ((х, z), (z, y)) x при некотором z; никакого недоразумения при этом не возникает, поскольку известна структура получаемого результата.

Используя это обозначение, мы можем определить ⁿ для любого n N, n > 1, следующим образом:

ⁿ = {(х, у): x z и z ^n-1y для некоторого z}.

Если мы вновь возьмем отношения и из примера 7.1, то получим

ⁿ = {(x, x + n), x N}и ^п={(х²ⁿ,х):x N}.

Хотелось бы рассмотреть вопрос о том, насколько в этих случаях применима аналогия с умножением. Пусть A — множество, a R— отношение на А. Тогда отношения I_a°R,R и R°I_А эквивалентны; поэтому I_А является тождественным отношением на А, которое ведет себя подобно числу 1 по отношению к умножению чисел. Чтобы дополнить аналогию, желательно было бы иметь возможность писать R^-1°R=I_A=R°R^-1. Однако в об­щем случае этого делать нельзя. Для того чтобы иметь такую возможность, необходимо наложить дополни­тельные условия, которые мы рассмотрим в сле­дующей главе.

Рассмотрим теперь несколько упражнений. Они изо­бражают ситуации, которые «легко описать» в математи­ческих терминах, однако следует заботиться о том, что­бы в отношение включались только те пары, которые ему принадлежат. Мы обнаружим, что иногда полезно воспользоваться диаграммами.

Упражнение 2.6.

1. Пусть R и S определены на P, где P — множест­во всех людей, следующим образом:

R = {(x, y): x, y P и x является отцом y},

S = {(x, y): x, y P и x - дочь y}.

Описать явно следующие отношения:

а) R²; б) S²; в) R ° S; г) S ° R;

д) S ° R^-1; е) R^-1 ° S; ж) R^-1 ° S^-1;

з) S^-1 ° R; и) S^-1 ° S^-1; к) S^-1 ° R^-1.