第1講 集合の演算
部分集合
集合 $A$ が集合 $B$ の部分集合であるとは,
$x\in A\Rightarrow x\in B$
が成り立つことをいい,$A\subset B$ と表す($B\supset A$ も可).
また,$A=B$ とは,$A\subset B$ かつ $B\subset A$ が成り立つことをいう.
論理記号の使い方で述べた「$P\Rightarrow Q$ の否定」に注意して,$A\subset B$ の否定 $A\not\subset B$ を論理記号で表すと
$\exists x\,[\ x\in A\ \mathrm{and}\ x\notin B\ ]$
すなわち「$A$ に含まれるが $B$ に含まれない要素が存在する」となる.
空集合 $\emptyset$ は任意の集合の部分集合であると規約する
(任意の集合 $A$ に対して論理的に $x\in \emptyset\Rightarrow x\in A$ が成立すると解釈してもよい).
正しいのはどれか?
(a) $\mathbf{N}\subset\mathbf{Z}\subset\mathbf{Q}\subset\mathbf{R}\subset\mathbf{C}$
(b) $(0,\infty)\subset[0,\infty)$
(c) $\mathbf{R}\subset\mathbf{R}$
(d) $\{\,0,1,2\,\}\subset[0,2]$
すべて正しい.
和,共通部分など
全体集合を $U$ とし,$U$ の部分集合 $A$,$B$ について
$A\cup B\stackrel{\mathrm{def}}{=}\{\,x\in U\,|\,x\in A\ \mathrm{or}\ x\in B\,\}$
$A\cap B\stackrel{\mathrm{def}}{=}\{\,x\in U\,|\,x\in A\ \mathrm{and}\ x\in B\,\}$
$A^c\stackrel{\mathrm{def}}{=}\{\,x\in U\,|\,x\notin A\,\}$
$A\backslash B\stackrel{\mathrm{def}}{=}A\cap B^c$
と定義し,
それぞれ和(合併),共通部分(積),補集合,差などと呼ぶ.
$U^c=\emptyset$,$\emptyset^c=U$である.これも規約と考えてよい.また,
分配法則
$A\cup(B\cup C)=(A\cup B)\cup(A\cup C)$
$A\cap(B\cap C)=(A\cap B)\cap(A\cap C)$
$A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$
$A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$
deMorganの法則
$(A\cup B)^c=A^c\cap B^c$
$(A\cap B)^c=A^c\cup B^c$
が成り立つことはBenn図などで直観的に理解できよう.
直積集合
二つの集合$A,\ B$の直積集合$A\times B$は
$A\times B$ $\stackrel{\mathrm{def}}{=}\{\,(a,b)\,|\,a\in A\ \mathrm{and}\ b\in B\,\}$
で定義される.$n$ 個の集合 $A_1,A_2,\ldots,A_n$ の直積集合は
$\displaystyle \prod_{k=1}^nA_k\stackrel{\mathrm{def}}{=}\{\,(a_1,a_2,\ldots,a_n)\,|\,a_k\in A_k,\ $$\ k=1,2,\ldots,n\,\}$
で定義される.
$A\times A$ のことを $A^2$ と表わす.一般に,$A^n$ は $n$ 個の $A$ の直積集合を表す.
-
$\{\,0,1,2\,\}\times\{\,a,b\,\}$$=\{\,(0,a),(0,b),(1,a),(1,b),(2,a),(2,b)\,\}$
-
$\{\,0\,\}\times\mathbf{N}$$=\{\,(0,1),(0,2),(0,3),\ldots\,\}$
-
$\mathbf{N}^2=\mathbf{N}\times\mathbf{N}=\{\,(m,n)\,|\,m,n\in\mathbf{N}\,\}$
-
$\mathbf{R}^3=\mathbf{R}\times\mathbf{R}\times\mathbf{R}\ $$=\{\,(x,y,z)\,|\,x,y,z\in\mathbf{R}\,\}$
集合族の和と共通部分
全体集合を $U$ とし,$U$の部分集合族 $A_\lambda\ (\lambda\in\Lambda)$ について,次を定義する:
$\displaystyle \bigcup_{\lambda\in\Lambda}A_\lambda\stackrel{\mathrm{def}}{=}\big\{\,x\in U\,\big|\,\exists \lambda\in\Lambda,\ x\in A_\lambda\,\big\}$
$\displaystyle \bigcap_{\lambda\in\Lambda}A_\lambda\stackrel{\mathrm{def}}{=}\big\{\,x\in U\,\big|\,\forall \lambda\in\Lambda,\ x\in A_\lambda\,\big\}$
$\displaystyle \bigcup_{\lambda\in\Lambda}$ は,
$\Lambda=\{\,1,2,\ldots,N\,\}$,$\mathbf{N}$,$\mathbf{Z}$ のときは
それぞれ
$\displaystyle \bigcup_{n=1}^N$,$\displaystyle \bigcup_{n=1}^\infty$,$\displaystyle \bigcup_{n=-\infty}^\infty$
のように書くことが多い.
また,$\Lambda$ が区間のときは
$\displaystyle \bigcup_{a\le t\le b}$
などの表記も用いられる.
$\displaystyle \bigcap_{\lambda\in\Lambda}$ についても同様.
- $\displaystyle \bigcup_{n\in\{1,2,\ldots,10\}}[n,n+1)$$\displaystyle =\bigcup_{n=1}^{10}[n,n+1)$$=[1,2)\cup[2,3)\cup\cdots\cup[10,11)$$=[1,11)$
- $\displaystyle \bigcup_{n\in\mathbf{N}}[n,n+1)$$\displaystyle =\bigcup_{n=1}^{\infty}[n,n+1)$$=[1,\infty)$
- $\displaystyle \bigcup_{n\in\mathbf{Z}}\{\,2^n\,\}$$\displaystyle =\bigcup_{n=-\infty}^{\infty}\big\{\,2^n\,\big\}$$=\{\,\ldots,2^{-2},2^{-1},1,2,2^2,\ldots\,\}$
- $\displaystyle \bigcap_{t\in[0,1]}(t,t+2)$$\displaystyle =\bigcap_{0\le t\le 1}(t,t+2)$$=(1,2)$
$\Lambda$ が $\mathbf{N}$,$\mathbf{R}$ などの無限集合である場合も含め,やはり
分配法則
$\displaystyle A\cup\Big(\ \bigcup_{\lambda\in\Lambda}A_\lambda\ \Big)=\bigcup_{\lambda\in\Lambda}(A\cup A_\lambda)$
$\displaystyle A\cap\Big(\ \bigcap_{\lambda\in\Lambda}A_\lambda\ \Big)=\bigcap_{\lambda\in\Lambda}(A\cap A_\lambda)$
$\displaystyle A\cup\Big(\ \bigcap_{\lambda\in\Lambda}A_\lambda\ \Big)=\bigcap_{\lambda\in\Lambda}(A\cup A_\lambda)$
$\displaystyle A\cap\Big(\ \bigcup_{\lambda\in\Lambda}A_\lambda\ \Big)=\bigcup_{\lambda\in\Lambda}(A\cap A_\lambda)$
deMorganの法則
$\displaystyle \Big(\ \bigcup_{\lambda\in\Lambda}A_\lambda\ \Big)^c=\bigcap_{\lambda\in\Lambda}{A_\lambda}^c$
$\displaystyle \Big(\ \bigcup_{\lambda\in\Lambda}A_\lambda\ \Big)^c=\bigcap_{\lambda\in\Lambda}{A_\lambda}^c$
が成り立つ.