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

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

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

На языке кванторов мы будем записывать эту операцию следующим образом:

Пример.  Рассмотрим множества A = {1, 2, 3, 4},  B = {1,3,5}, C = {5,6}. Тогда, согласно введенному определению получаем:

Аналогично определяется объединение (сумма)  множеств A1,A2, ..., An. Объединением этих множеств называется множество, обозначаемое , состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из этих множеств.

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

Определение. Пересечением (произведением) двух множеств A и B называется множество (его принято обозначать ) состоящее из всех тех и только тех элементов, которые принадлежат каждому из множеств A и B.

На языке кванторов мы будем записывать эту операцию следующим образом:

Пример.  В рамках введенных в предыдущем примере определений множеств A, B, C мы получаем:

Также как мы делали раньше, можно определить пересечение (произведение) конечного числа множеств.

На кругах Эйлера пересечение множеств выглядит следующим образом:

Бывает удобно ввести понятие "универсального" множества U, которое по предположению содержит все используемые нами множества.
Введенные операции над множествами обладают свойствами коммутативности:

и свойством ассоциативности:

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

Перейдем к новой операции над множествами. Эта операция определяется только для двух множеств.

Определение. Разностью двух множеств A и B называется множество (его обычно обозначают A\B или A-B), состоящее из тех и только тех элементов, которые принадлежат множеству A и не принадлежат множеству B.

На кругах Эйлера

Пример. В рамках введенных в предыдущем примере определений множеств A, B, C справедливы следующие результаты

Почти очевидно следующее свойство, которое также можно принять за определение разности двух множеств:

Определение. Симметрической разностью множеств A и B называется множество обозначаемое через A B и определяемое следующим образом:

На кругах Эйлера эта операция выглядит вот как

Пример.

a)    ;

Кроме того, справедливо следующее свойство:

.

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

Перейдем к доказательству. Пусть , что по определению симметрической разности означает, что . Здесь возможны два варианта: либо , либо . В первом случае мы получаем: откуда очевидно следует, что . Ситуация, когда  рассматривается аналогично.   

Итак, мы доказали, что если некоторый элемент x принадлежит множеству из левой части равенства, то из этого следует, что он принадлежит множеству, стоящему в правой части равенства. Теперь нам необходимо доказать обратное включение.
Пусть . Здесь возможны 2 ситуации: либо . Давайте, рассмотрим первый случай: пусть . Второй случай доказывается аналогично.     

Итак, мы полностью доказали заявленное свойство. При доказательстве подобных утверждений огромную роль играет то свойство, что если некоторый элемент x принадлежит некоторому множеству X, то он очевидно будет принадлежать и объединению множества X с произвольным другим множеством.
Достаточно часто оказывается удобным ввести понятие "универсального" множества U, которое содержит все рассматриваемые нами множества.

Определение. Множество U\A называется дополнением множества A (до универсального множества) и обозначается через `.

Принцип двойственности. Пусть Ak, k = 1,...,n - некоторые подмножества универсального множества U, тогда имеют место следующие равенства:

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

Докажем первое соотношение:

Заметим, что в приведенном доказательстве все утверждения об элементе x соединены знаками , что позволяет одновременно строить доказательство утверждения в обе стороны.

Справедливость второго соотношения доказывается аналогично.

Пример.  Определим следующие множества: A - множество четных натуральных чисел; B - множество нечетных натуральных чисел; C - множество натуральных чисел, не больше 10. В качестве "универсального" множества мы будем рассматривать множество натуральных чисел . Наша задача состоит в том, чтобы описать следующие множества:

- это множество нечетных натуральных чисел, т.е. множество B
2) Каждое натуральное число является либо четным, либо нечетным, поэтому . Следовательно,

Если теперь считать, что в нашем распоряжении имеется универсальное множество U, то операции  можно определять друг через друга и фактически ввести некоторый базис операций в алгебре множеств.

Примеры.
1)  
2)
3)