Операции над множествами

Рассмотрим операции над множествами, которые позволяют из уже имеющихся множеств образовывать новые множества.

Для любых двух множеств [cbm]A[/cbm] и [cbm]B[/cbm] определены новые множества, называемые объединением, пересечением, разностью и симметрической разностью:

[cbm]A\cup B=\{x\colon\, x\in A\lor x\in B\}[/cbm] — объединение,
[cbm]A\cap B=\{x\colon\, x\in A\land x\in B\}[/cbm] — пересечение,
[cbm]A\setminus B=\{x\colon\, x\in A\land x\notin B\}[/cbm] — разность,
[cbm]A\,\triangle\, B=(A\setminus B)\cup (B\setminus A)[/cbm] — симметрическая разность,

т.е. объединение [cbm]A[/cbm] и [cbm]B[/cbm] есть множество всех таких [cbm]x[/cbm] , что [cbm]x[/cbm] является элементом хотя бы одного из множеств [cbm]A,B[/cbm] ; пересечение [cbm]A[/cbm] и [cbm]B[/cbm] — множество всех таких [cbm]x[/cbm] , что [cbm]x[/cbm] — одновременно элемент [cbm]A[/cbm] и элемент [cbm]B[/cbm] ; разность [cbm]A \setminus B[/cbm] — множество всех таких [cbm]x[/cbm] , что [cbm]x[/cbm] — элемент [cbm]A[/cbm] , но не элемент [cbm]B[/cbm] ; симметрическая разность [cbm]A\,\triangle\, B[/cbm] — множество всех таких [cbm]x[/cbm] , что [cbm]x[/cbm] — элемент [cbm]A[/cbm] , но не элемент [cbm]B[/cbm] или [cbm]x[/cbm] — элемент [cbm]B[/cbm] , но не элемент [cbm]A[/cbm] .

Кроме того, фиксируя универсальное множество [cbm]U[/cbm] , мы можем определить дополнение [cbm]\overline{A}[/cbm] множества [cbm]A[/cbm] следующим образом: [cbm]\overline{A}=U\setminus A[/cbm] . Итак, дополнение множества [cbm]A[/cbm] — это множество всех элементов универсального множества, не принадлежащих [cbm]A[/cbm] .

Полезно разобраться в том, как операции над множествами, введенные выше, соотносятся с логическими операциями. Пусть [cbm]A=\{x\colon\, P(x)\}[/cbm] и [cbm]B=\{x\colon\, Q(x)\}[/cbm] , т.е. множество [cbm]A[/cbm] задано посредством характеристического предиката [cbm]P[/cbm] , а множество [cbm]B[/cbm] — посредством характеристического предиката [cbm]Q[/cbm] .

Легко показать, что

[cbm]A\cup B=\bigl\{x\colon\, P(x)\lor Q(x)\bigr\},\qquad A\cap B=\bigl\{x\colon\, P(x)\land Q(x)\bigr\},\qquad A\setminus B=\bigl\{x\colon\, P(x)\land\lnot Q(x)\bigr\}.[/cbm]

Следующие процедуры получения новых множеств связаны с понятием подмножества. Говорят, что [cbm]B[/cbm] есть подмножество множества [cbm]A[/cbm] , если всякий элемент [cbm]B[/cbm] есть элемент [cbm]A[/cbm] . Для обозначения используют запись: [cbm]B\subseteq A[/cbm] . Говорят также, что [cbm]B[/cbm] содержится в [cbm]A[/cbm] или [cbm]B[/cbm] включено в [cbm]A[/cbm] , или [cbm]A[/cbm] включает [cbm]B[/cbm] (имеет место включение [cbm]B\subseteq A[/cbm] ). Считают, что пустое множество есть подмножество любого множества и, если фиксировано некоторое универсальное множество, каждое рассматриваемое множество есть его подмножество. Нетрудно проверить, что если [cbm]A=\{x\colon\, P(x)\}[/cbm] и [cbm]B=\{x\colon\, Q(x)\}[/cbm] , то [cbm]B\subseteq A[/cbm] тогда и только тогда, когда высказывание [cbm]Q(x)\Rightarrow P(x)[/cbm] тождественно истинно.

Сопоставляя определение подмножества и определение равенства множеств, мы видим, что множество [cbm]A[/cbm] равно множеству [cbm]B[/cbm] тогда и только тогда, когда [cbm]A[/cbm] есть подмножество [cbm]B[/cbm] и наоборот, т.е.

[cbm]A=B\quad \Leftrightarrow\quad \bigl((A\subseteq B)\land (B\subseteq A)\bigr).[/cbm]
(1.2)

Формула (1.2) является основой для построения доказательств о равенстве множеств. Ее применение состоит в следующем. Чтобы доказать равенство двух множеств [cbm]X[/cbm] и [cbm]Y[/cbm] , т.е. что [cbm]X=Y[/cbm] , достаточно доказать два включения [cbm]X \subseteq Y[/cbm] и [cbm]Y \subseteq X[/cbm] ", т.е. доказать, что из предположения [cbm]x\in X[/cbm] (для произвольного [cbm]x[/cbm] ) следует, что [cbm]x\in Y[/cbm] , и, наоборот, из предположения [cbm]x\in Y[/cbm] следует, что [cbm]x\in Y[/cbm] . Такой метод доказательства теоретико-множественных равенств называют методом двух включений. Примеры применения этого метода мы дадим позже.

Замечание. Равенство множеств [cbm]\{x\colon\,P(x)\}[/cbm] и [cbm]\{x\colon Q(x)\}[/cbm] означает, что предикаты Р(х) и Q(x) эквивалентны, т.е. предикат Р(х) О Q{x) является тождественно истинным.


Собственное подмножество и булеан множества

Если [cbm]B \subseteq A[/cbm] , но [cbm]B\ne A[/cbm] , то пишут [cbm]B \subset A[/cbm] и [cbm]B[/cbm] называют строгим подмножеством (или собственным подмножеством) множества [cbm]A[/cbm] , а символ [cbm]\subset[/cbm] — символом строгого включения.

Для всякого множества [cbm]A[/cbm] может быть образовано множество всех подмножеств множества [cbm]A[/cbm] . Его называют булеаном множества [cbm]A[/cbm] и обозначают [cbm]2^A:[/cbm]

[cbm]2^A=\bigl\{X\colon~ X\subseteq A\bigr\}.[/cbm]

Для булеана используют также обозначения [cbm]\mathcal{P}(A),~\mathcal{B}[/cbm] и [cbm]\exp(A)[/cbm] .


Пример. а. Булеан множества [cbm]\{a,b\}[/cbm] состоит из четырех множеств

[cbm]\varnothing,~ \{a\},~ \{b\},~ \{a,b\}[/cbm] , то есть [cbm]2^{\{a,b\}}=\bigl\{\varnothing,\, \{a\},\, \{b\},\, \{a,b\}\bigr\}.[/cbm] .

б. Булеан [cbm]2^{\mathbb{N}}[/cbm] состоит из всех возможных, конечных или бесконечных, подмножеств множества [cbm]\mathbb{N}[/cbm] . Так, [cbm]\varnothing\in 2^{\mathbb{N}}[/cbm] и [cbm]\{5\}\in 2^{\mathbb{N}}[/cbm] , вообще для любого [cbm]n[/cbm] множество [cbm]\{n\}\in 2^{\mathbb{N}}[/cbm] , множество

[cbm]\{1,2,\ldots,n\}\in 2^{\mathbb{N}},~ \{n\colon\, n=2k,~ k=1,2,\ldots\}\in 2^{\mathbb{N}}[/cbm] и т.д.

Для булеана [cbm]2^A[/cbm] мы можем рассматривать произвольные его подмножества. Таким подмножеством, например, будет Одноэлементное множество [cbm]\{B\}[/cbm] , где [cbm]B[/cbm] — произвольное подмножество [cbm]A[/cbm] . Подчеркнем, что единственным элементом множества [cbm]\{B\}[/cbm] является, в свою очередь, некоторое множество. Вообще же образование булеана открывает путь для построения множеств, элементами которых являются множества, элементами которых, в свою очередь, являются некоторые множества, и т.д. Так можно определить множества [cbm]2^{2^A},~ 2^{2^{2^A}}[/cbm] и т.д.


Свойства операций над множествами

Введенные выше операции над множествами обладают следующими свойствами:

[cbm]\begin{array}{ll} \bold{1)}\quad A\cup B=B\cup A; &\qquad \bold{12)}\quad A\cup U=U;\\[2pt] \bold{2)}\quad A\cap B=B\cap A; &\qquad \bold{13)}\quad A\cup \overline{A}=U;\\[2pt] \bold{3)}\quad A\cup (B\cup C)= (A\cup B)\cup C; &\qquad \bold{14)}\quad A\cap \overline{A}= \varnothing;\\[2pt] \bold{4)}\quad A\cap (B\cap C)= (A\cap B)\cap C; &\qquad \bold{15)}\quad A\cup A=A;\\[2pt] \bold{5)}\quad A\cap (B\cup C)= (A\cap B)\cup (A\cap C); &\qquad \bold{16)}\quad A\cap A=A;\\[2pt] \bold{6)}\quad A\cup (B\cap C)= (A\cup B)\cap (A\cup C); &\qquad \bold{17)}\quad \overline{\overline{A}}=A;\\[2pt] \bold{7)}\quad \overline{A\cup B}= \overline{A}\cap \overline{B}; &\qquad \bold{18)}\quad A \setminus B=A\cap \overline{B};\\[2pt] \bold{8)}\quad \overline{A\cap B}= \overline{A}\cup \overline{B}; &\qquad \bold{19)}\quad A\,\triangle\,B=(A\cup B)\setminus (A\cap B);\\[2pt] \bold{9)}\quad A\cup \varnothing=A; &\qquad \bold{20)}\quad (A\,\triangle\,B)\,\triangle\,C= A\,\triangle\,(B\,\triangle\,C);\\[2pt] \bold{10)}\quad A\cap \varnothing=\varnothing; &\qquad \bold{21)}\quad A\,\triangle\, B=B\,\triangle\,A;\\[2pt] \bold{11)}\quad A\cap U=A; &\qquad \bold{22)}\quad A\cap (B\,\triangle\,C)= (A\cap B)\,\triangle\,(A\cap C). \end{array}[/cbm]

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

Пусть [cbm]x\in A\,\triangle\,B[/cbm] . Тогда, согласно определению симметрической разности, [cbm]x\in (A \setminus B)\cup (B \setminus A)[/cbm] . Это означает, что [cbm]x\in (A \setminus B)[/cbm] или [cbm]x\in(B \setminus A)[/cbm] . Если [cbm]x\in (A \setminus B)[/cbm] , то [cbm]x\in A[/cbm] и [cbm]x\notin B[/cbm] , то есть [cbm]x\in A\cup B[/cbm] и при этом [cbm]x\notin A\cap B[/cbm] . Если же [cbm]x\in (B \setminus A)[/cbm] , то [cbm]x\in B[/cbm] и [cbm]x\notin A[/cbm] , откуда [cbm]x\in A\cup B[/cbm] и [cbm]x\notin A\cap B[/cbm] . Итак, в любом случае из [cbm]x\in (A \setminus B)\cup (B \setminus A)[/cbm] следует [cbm]x\in A\cup B[/cbm] и [cbm]x\notin A\cap B[/cbm] , то есть [cbm]x\in (A\cup B)\setminus (A\cap B)[/cbm] . Таким образом, доказано, что

[cbm]A\,\triangle\,B \subseteq (A\cup B)\setminus (A\cap B).[/cbm]

Покажем обратное включение [cbm](A\cup B)\setminus (A\cap B)\subseteq A\,\triangle\,B[/cbm] .

Пусть [cbm]x\in (A\cup B)\setminus (A\cap B)[/cbm] . Тогда [cbm]x\in A\cup B[/cbm] и [cbm]x\notin A\cap B[/cbm] . Из [cbm]x\in A\cup B[/cbm] следует, что [cbm]x\in A[/cbm] или [cbm]x\in B[/cbm] . Если [cbm]x\in A[/cbm] , то с учетом [cbm]x\notin A\cap B[/cbm] имеем [cbm]x\notin B[/cbm] , и поэтому [cbm]x\in A\setminus B[/cbm] . Если же [cbm]x\in B[/cbm] , то опять-таки в силу [cbm]x\notin A\cap B[/cbm] получаем, что [cbm]x\notin A[/cbm] и [cbm]x\in B\setminus A[/cbm] . Итак, [cbm]x\in A \setminus B[/cbm] или [cbm]x\in B \setminus A[/cbm] , то есть [cbm]x\in (A\setminus B)\cup (B\setminus A)[/cbm] . Следовательно,

[cbm](A\cup B)\setminus (A\cap B)\subseteq A\,\triangle\,B\,.[/cbm]

Оба включения имеют место, и тождество 19 доказано.

Метод двух включений является универсальным и наиболее часто применяемым методом доказательства теоретико-множественных тождеств. Помимо метода двух включений для доказательства теоретико-множественных тождеств могут быть использованы другие методы, например метод характеристических функций.

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

Докажем этим методом тождество 22, пользуясь тождествами 1-19. Преобразуем левую часть к правой:

[cbm]\begin{aligned} (A\cap B)\,\triangle\,(A\cap C)&= \bigl((A\cap B)\cup (A\cap C)\bigr)\cap \overline{(A\cap B)\cap (A\cap C)}=\\[2pt] &= \bigl(A\cap (B\cup C)\bigr)\cap \bigl(\overline{A\cap B}\cup \overline{A\cap C}\bigr)=\\[2pt] &= \bigl(A\cap (B\cup C)\bigr)\cap \bigl(\overline{A}\cup \overline{B}\bigr)\cup \bigl(\overline{A}\cup \overline{C}\bigr)=\\[2pt] &=\bigl(A\cap (B\cup C)\bigr)\cap \bigl(\overline{A}\cup (\overline{B}\cup \overline{C})\bigr)=\\[2pt] &= \bigl(\bigl(A\cap (B\cup C)\bigr)\cap \overline{A}\bigr)\cup \bigl((A\cap (B\cup C))\cap (\overline{B}\cup \overline{C})\bigr)=\\[2pt] &= \varnothing\cup \bigl(\bigl(A\cap (B\cup C)\bigr)\cap \bigl(A\cap (\overline{B}\cup \overline{C})\bigr)\bigr)=\\[2pt] &= \bigl(A\cap (B\cup C)\bigr)\cap \bigl(A\cap \overline{B\cap C}\bigr)=\\[2pt] &=A\cap \bigl((B\cup C)\cap \overline{B\cap C}\bigr)=\\[2pt] &=A\cap \bigl((B\cup C) \setminus (B\cap C)\bigr)=\\[2pt] &= A\cap (B\,\triangle\,C). \end{aligned}[/cbm]

Таким образом, тождество доказано.

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: