1.5. Алгебра множеств

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

Иначе говоря, то, что ниже будет естественным образом названо «алгеброй множеств» — это не что иное, как дальнейшее развитие основ­ных свойств операций , , ^- и  и связей между ними. Можно ска­зать, что алгебра множеств представляет собой теоретико-множествен­ный аналог обычной алгебры действительных чисел, исходящей из свойств операций +, • и  и их взаимосвязей. Алгебра множеств представ­ляет собой совокупность тождеств — равенств, справедливых независимо от того, каково универсальное множество U и какие именно конкрет­ные подмножества множества U обозначаются входящими в эти равен­ства буквами (отличными от U и ).

Первый наш результат устанавливает основные свойства объединения и пересечения. Ради единообразия все эти свойства будут сформулиро­ваны для подмножеств универсального множества U. Однако для неко­торых из этих свойств упомянутое ограничение является совершенно несущественным, что видно из приводимых ниже доказательств.

Теорема 1.1. Для любых подмножеств А, В и С универсального мно­жества U следующие равенства являются тождествами (А здесь исполь­зуется в качестве сокращения для U — А):

1. А  (В  С) = (А  В)  С.

2. А  В = В  А.

3. А  (В  С) = (А  В)  (А  С).

4. А   = А.

5. А  Ā = U.

1. А  (В  С) = (А  В)  С.

2. А  В = В  А.

3. А  (В  С) = (А  В)  (А  С).

4. А   = А.

5. А  Ā = U.

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

(а) Доказательство того, что А  (В  C)  (А  В)(А  C). Пусть х А  (В  С). Тогда х А или х  В  С. Если х  А, то х  А  В и x  A  C, а, следовательно, х есть элемент пересечения этих множеств. Если х  В  С, то х  В и х  С. Следовательно, х  А  В и х  А  С_г так что и в этом случае х есть элемент их пересечения.

(b) Доказательство того, что (А  В)  (А  С)  А  (В  С). Пусть х  (А  В)  (А  С). Тогда х  А  В и х  А  С. Следовательно, х  А_г, или же х  В и х  С. Из этого и вытекает, что х  А  (В  С).

Тождества 1 и 1 называют ассоциативными законами, соответственно, для объединения и пересечения, а тождества 2 и 2' — коммутативными законами для этих операций. Тождества 3 и 3'—это дистрибутивные законы для этих операций. В этом пункте нарушается аналогия, имею­щая место между свойствами объединения и пересечения множеств, с одной стороны, и, соответственно, сложения и умножения чисел — с другой. 3' в точности соответствует дистрибутивному закону арифме­тики. Расхождение проявляется в тождестве 3, для которого в арифме­тике нет аналога.

Согласно ассоциативному закону (тождество 1), два множества, кото­рые можно образовать с помощью операции объединения, исходя из мно­жеств А, В и С, взятых в определенном порядке, равны. Условимся обозначать это единственное множество через A  В  С. Ассоциативный закон утверждает, что не играет роли, как расставить скобки в этом выражении. При помощи математической индукции этот результат можно обобщить следующим образом. Все множества, получаемые с помощью операции объединения из заданных множеств А₁, А₂, ..., А_п, взятых в фиксированном порядке, равны друг другу. Множество, получаемое таким способом из А₁, А₂, ,..., А_п, мы будем обозначать через

А₁  А₂  ... А_п.

В силу тождества 1 соответствующее обобщение справедливо и для опе­рации пересечения. Эти общие ассоциативные законы позволяют нам уста­новить общие коммутативные законы: если 1, 2', ... , п' суть числа 1, 2, ... , п, взятые в произвольном порядке, то

А₁  А₂  …  А_п = А_1  А_2  …  А_п..

То же можно сказать и об общих дистрибутивных законах:

А  (В₁  В₂  …  В_n) = (А  В₁ ) (А  В₂)  …  (А  В_n),

А  (В₁  В₂  …  В_n) = (А  В₁)  (А  В₂)  …  (А  В_n).

Законы эти также могут быть доказаны по индукции.

Подробные доказательства дальнейших свойств объединения и пере­сечения не требуют никаких ссылок на отношение принадлежности — эти свойства непосредственно следуют из тех, которые устанавливаются в теореме 1.1. Это относится, в частности, и к тем свойствам, которые фигурируют в следующей теореме. Это обстоятельство можно расценивать как источник «аксиоматического подхода» к алгебре множеств, разви­ваемого ниже, в главе IV. Подход этот основан на том, что любая теорема алгебры множеств выводима из 1—5 и 1'—5'.

Указанные десять свойств позволяют сделать и другой интересный вывод. В теореме 1.1 эти свойства фигурируют попарно таким образом, что каждый член любой пары получается из другого члена одновремен­ной взаимной заменой  и ,  и U. Равенство (или выражение, или утверждение) алгебры множеств, полученное из другого равенства (соответ­ственно, выражения или утверждения) заменой всех вхождений  на ,  на ,  на U и U на , называют двойственным исходному. Мы утвер­ждаем, что предложение, двойственное любой теореме алгебры множеств, сформулированной в терминах ,  и -, для доказательства которой можно обойтись лишь тождествами 1—5 и 1'—5', также является теоремой.

В самом деле, допустим, что доказательство исходной теоремы представлено в виде последовательности шагов, а рядом с каждым шагом записано его обоснование. По предположению каждое такое обоснование является одним из тождеств 1—5, 1'—5' или условием теоремы. Заменим теперь каждое тождество и соотношение, встречающееся в доказательстве и обосновании, двойственным ему. Поскольку тождество, двойственное каждому из тождеств 1—5, 1'—5', снова является одним из этих тож­деств, а утверждение, двойственное посылке исходной теоремы, является посылкой новой теоремы, результат замены каждого шага обоснования в доказательстве исходной теоремы может служить обоснованием соот­ветствующего шага новой последовательности, которая, следовательно, будет являться доказательством. Таким образом, последняя строка новой последовательности является теоремой, двойственной исходной теореме.

Согласившись, что любая теорема алгебры множеств может быть выве­дена из условий 1—5 и 1'—5', мы приходим к принципу двойственности для алгебры множеств: для любой теоремы Т, формулируемой в терми­нах ,  и -, двойственное ей предложение также является теоремой. Из этого принципа, например, получается, что если какое-нибудь утверж­дение следующей теоремы непосредственно вытекает из теоремы 1.1, то соответствующее ему (т. е. находящееся в паре с тем же номером) утверж­дение также в силу двойственности вытекает из теоремы 1.1. Читатель сам сможет убедиться, что все утверждения теоремы 1.2 истинны, используя определения для ,  и - в терминах отношения принадлежности. После этого стоило бы попытаться вывести некоторые из этих утвержде­ний прямо из теоремы 1.1, т. е. без какой бы то ни было апелляции к определению отношения принадлежности. Некоторые примеры такого рода читатель найдет ниже, в доказательстве теоремы 4.1.

Теорема 1.2. Для произвольных подмножеств А и В множества U

справедливы следующие утверждения (Ā здесь служит сокращением для U - A):

6. Если для всех А А  В = А, 6'. Если для всех _{А А}  _{В = А,}

то В = . то В = U

7.7'. Если А  B = U и А  В = , то В = Ā.

8.8'. Ā = А

9 .  = U. 9'. U = 

10. А  А = А 10'. А  А = А

11. _А  U = U 11'. _А   = 

12. А  (А  В) = А 12'. А  (А  В) = А

1 3. А  В = А  В. 13'. А  В = А  В

Некоторые из тождеств теоремы 1.2 известны под специальными име­нами. Так, 10 и 10' - это законы идемпотентности, 12 и 12'—законы поглощения, 13 и 13' — законы де Моргана. Каждое из тождеств 7,7' и 8,8' занумеровано дважды, чтобы подчеркнуть, что каждое из них не меняется при преобразовании, переводящем его в двойственное; такие формулы называют самодвойственными. Заметим, что 7,7' утверждает, что каждое множество имеет единственное дополнение.

По поводу следующей теоремы требуется пояснение. Утверждение вида «Предложения R₁ R₂, '..., R_k попарно эквивалентны» означает: «Для любых i и j R_i эквивалентно R_j»; что, в свою очередь, справедливо в том и только в том случае, когда R₁ влечет R₂, R₂ влечет R₃, ..., R_k-1 влечет R_k, R_k влечет R₁. Содержанием теоремы является то, что отно­шение включения множеств может быть определено в терминах объеди­нения, а также в терминах пересечения.

Теорема 1.3. Следующие предложения о произвольных множествах А и В попарно эквивалентны:

(I) А  В;

(II) А  В = А; (III). А  В = В.

Д о к а з а т е л ь с т в о. (I) влечет (II). Пусть A  В. Поскольку для всех А и В А  В  А, нам достаточно доказать, что А  А  В. Но если x  А, то х  В и, следовательно, x  А  В. Значит, А  А  В.

(II) влечет (III). Пусть А  В = А. Тогда А  В = (А  В)  В = = (А  В)  (B  B) = (A  B)  B = B.

(III) влечет (I). Пусть А  В = В. Но из этого тождества и тождества А  А  В следует А  В.

П ринцип двойственности в том виде, как он был сформулирован выше, не приложим непосредственно к выражениям, содержащим знаки – или . На вычитание этот принцип может быть распространен использованием несокращенной формы, а именно А  В вместо А - В. Точно так же в силу теоремы 1.3 А  В можно заменить на А  В = А (или A  В = В). А еще лучше будет сказать, что, поскольку двойственным к А  В = А является соотношение A  B = A, эквивалентное А  В, то принцип двойствен­ности может быть расширен на тот случай, когда в выражение входит символ включения, распоряжением, чтобы при переходе к двойственному выражению все знаки  () заменялись на  (соответственно, ) и обратно.