Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


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

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


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


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


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

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


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


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


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


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\}.

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


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


A=B\quad \Leftrightarrow\quad \bigl((A\subseteq B)\land (B\subseteq A)\bigr).
(1.2)

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


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




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


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


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


2^A=\bigl\{X\colon~ X\subseteq A\bigr\}.

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




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


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

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


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



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




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


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


\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}


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


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


A\,\triangle\,B \subseteq (A\cup B)\setminus (A\cap B).

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


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


(A\cup B)\setminus (A\cap B)\subseteq A\,\triangle\,B\,.

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


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


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


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


\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}

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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2019 MathHelpPlanet.com. All rights reserved