52. Операции на обычных множествах

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

Произведение двух множеств. В действительности мы уже говорили об этом неявно в § 11, когда вводили понятие графа. Еще раз подробно рассмотрим понятие произведения двух множеств.

Пусть  и  - два множества и  и . Множество упорядоченных пар  называется произведением  и . Это произведение множеств обозначается .

Имеем

, если  - некоммутативность,                (52.1)

 - ассоциативность.                       (52.2)

Пример.

,               (52.3)

,                      (52.4)

,                 (52.5)

.                 (52.6)

Если

,                (52.7)

то

                      (52.8)

Аналогично можно разложить правую сторону равенства (52.2).

Для  множеств  можно определить

.                    (52.9)

Изменяя в этом произведении порядок, можно определить всего  различных произведений, если все исходные множества различны.

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

               (52.10)

Пример. Рассмотрим еще раз (52.3) и (52.4), тогда

.                  (52.11)

В этом примере  и  не имеют общих элементов.

Сумма (52.10) обладает следующими свойствами:

 - коммутативность,                  (52.12)

 - ассоциативность.                   (52.13)

Для операций произведения и дизъюнктивной суммы выполняется свойство дистрибутивности

,                  (52.14)

                   (52.15)

(дистрибутивность слева и справа для ).

Рассмотрим пример.

Пример. Пусть даны (52.3), (52.4) и (52.7) Тогда

,                   (52.16)

,  (52.17)

,                 (52.18)

,                   (52.19)

                   (52.20)

Можно легко проверить, что соотношения (52.17) и (52.20) определяют одно и то же множество.

Отметим, что для произведения дистрибутивность не выполняется ни слева, ни справа. Рассмотрим опять соотношения (52.3), (52.4) и (52.5).

,                 (52.21)

,                    (52.22)

,                    (52.23)

,                  (52.24)

,                       (52.25)

   (52.26)

Множество отображений  в . Множество функциональных отображений  в  обозначается   (как степень).

Пример получим непосредственно, если обратимся к соотношениям (52.3) и (52.4) и используем несколько графовых представлений (см. рис. 52.1).

 

Рис. 52.1.

 

Из рисунка видно, что если

                (52.27)

и

,                      (52.28)

то

  (52.29)

Мощность  равна

.                      (52.30)

Для данного примера

.             (52.31)

Если  или (и)  бесконечно, то  бесконечна.                 (52.32)

Основные операции на множествах. Сведем воедино все полученные выше результаты. Пусть ,  и  - множества; тогда

,               (52.33)

,               (52.34)

,                   (52.35)

,                  (52.36)

,                  (52.37)

,               (52.38)

.             (52.39)