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

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

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

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

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


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

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


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


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


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

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


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


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


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


[math]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\}.[/math]

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


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


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

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


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




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


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


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


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

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




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


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

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


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



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




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


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


[math]\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}[/math]


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


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


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

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


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


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

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


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


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


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


[math]\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}[/math]

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


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


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

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