オートマトン/第一類/数学的準備/集合

メインページ > 自然科学 > 理学 > 数学 > 理論計算機科学 > オートマトン > オートマトン/第一類/数学的準備/集合

集合に関した基礎的な事項を簡単にまとめておく．

集合(set)とは，要素(element)の集まりである．対象となる要素はなんであってもいいし，特に集合を要素とする集合も通常は許容される． ある集合 $A$ があるとき，どんな要素が $A$ に属するかは明瞭に記述されなければならない． 例えば「0 と 1 からなる文字列」の集まりは集合である． 一つの集合には，同じ要素が重複して含まれることはない． 有限個の要素よりなる集合を有限集合(finite set)，無限個の要素より成る集合を無限集合(infinite set)という．

集合の記法

要素 0, 1 の二つからなる集合は $\{0,1\}$ と表す． $n$ 個の要素 $a_{1},a_{2},a_{3},\cdots ,a_{n}$（$i\neq j$ ならば $a_{i}\neq a_{j}$）からなる集合は，$\{a_{1},a_{2},\cdots ,a_{n}\}$ と表す． 要素の順序は任意であり，$\{0,1\}$ と $\{1,0\}$ は同じ集合である．

集合を表す記法として次のような方法もある． $D=\{x\ |\ x$ は実数の集合 ${\mathit {R}}$ に属し，かつ $x^{6}=1\}$ は， “$x$ は実数の集合の集合 ${\mathit {R}}$ に属し，かつ $x^{6}=1$” という性質を満足するような $x$ をすべて集めた集合であり， 要素を列挙する記法で表せば，$D=\{-1,1\}$ である．

一般に，$x$ に関する性質を $P(x)$ としたとき，性質 $P(x)$ を満足するような $x$ をすべて集めた集合を

$\{x\ |\ P(x)\}$

と表す．さらに性質 $P(y)$ と性質 $Q(x)$ をともに満足するような $y$ をすべて集めた集合を

$\{y\ |\ P(y),$ かつ $Q(y)\}$

$\{y\ |\ P(y),Q(y)\}$

と表す．

特に要素を一つも持たない集合は空集合(empty set) という．空集合は記号 $\varnothing$ で表す．

要素と集合

集合 $A$ が要素として $a$ を持つとき，$a$ は $A$ に属する，あるいは $A$ は $a$ を含むといい，

$a\in A$

$A\ni a$

と表す．$a$ が $A$ の要素ではないときは，

$a\not \in A$

$A\not \ni a$

と表す．前提としてのすでに明らかな集合 $S$ があって，今は性質 $P(x)$ に論述の力点があるときに

$\{x\ |\ x\in S$ かつ $P(x)\}$

は

$\{x\in S\ |\ P(x)\}$

のように表示されることもある．例えば実数の集合を ${\mathit {R}}$ としたとき，先にあげた集合 $D$ を

$D=\{x\in {\mathit {R}}\ |\ x^{6}=1\}$

とも表すことができる．

部分集合

集合 $A,B$ において，集合 $A$ の要素は必ず集合 $B$ であるとき， $A$ は $B$ の部分集合(subset) であるという．またこのとき，$A$ は $B$ に含まれる， あるいは，$B$ は $A$ を含むといい，

$A\subseteq B$

$B\supseteq A$

と表す．例えば $\{0\}\subseteq \{0,1\}$． 定義より $A$ 自身は $A$ の部分集合である．

$A\subseteq A$

また，空集合 $\varnothing$ はすべての集合の部分集合である，と定義する．

集合 $A,B$ において $A\subseteq B$ かつ $B\subseteq A$ であるとき，集合 $A$ と $B$ は等しいといい，

$A=B$

と表す．

集合に対する演算

和集合

集合 $A,B$ に対し，そのいずれかに属する要素をすべて集めた集合 $C=\{c\ |\ c\in A$ または $c\in B\}$ を，$A$ と $B$ を $A$ と $B$ の和集合 (union) という．これを

$C=A\cup B$

と表す．一般に集合 $S_{1},S_{2},\cdots ,S_{n}(n\geqq 2)$ に対して $S=\{a\ |\ a\in S_{1}$ あるいは $a\in S_{2},\cdots ,$ あるいは $a\in S_{n}\}$ を $S_{1},S_{2},\cdots ,S_{n}$ の和集合といい，

$S=S_{1}\cup S_{2}\cup \cdots \cup S_{n}$

$=\bigcup _{i=1}^{n}S_{i}$

と表す．

積集合

集合 $A$ と $B$ とに共通して含まれる要素を集めた集合 $C=\{c\ |\ c\in A$ かつ $c\in B\}$ を $A$ と $B$ の積集合 (intersection, product) という．これを

$C=A\cap B$

と表す．一般に集合 $S_{1},S_{2},\cdots ,S_{n}(n\geqq 2)$ に対して $S=\{a\ |\ a\in S_{1}$ かつ $a\in S_{2},\cdots ,$ かつ $a\in S_{n}\}$ を $S_{1},S_{2},\cdots ,S_{n}$ の積集合といい，

$S=S_{1}\cap S_{2}\cap \cdots \cap S_{n}$

$=\bigcap _{i=1}^{n}S_{i}$

と表す．

差集合・補集合

集合 $A$ の要素の中から，集合 $B$ にも属する共通要素をすべて除いて得られる集合 $C=\{c\ |\ c\in A,$ かつ $c\not \in B\}$ を，$A$ から $B$ を引いた差集合 (difference) という．これを

$C=A-B$

と表す．考察の前提または対象となる全要素が先に提示されていて，これを集合 $\Omega$（omega; これを全体集合あるいは普遍集合(universal set)という）とし， $\Omega$ の部分集合 $A$ が与えられたときの $\Omega$ と $A$ の差集合

$\Omega -A$

を $A$ の（$\Omega$ に関する）補集合 (complement) という．これを ${\overline {A}}$ または $A^{C}$ と表す． 定義より ${\overline {\overline {A}}}=A$ が成り立つ．

次の公式はド・モルガン則と呼ばれている．

${\overline {A\cup B}}={\overline {A}}\cap {\overline {B}}$

${\overline {A\cap B}}={\overline {A}}\cup {\overline {B}}$

集合族・べき集合

集合を要素とする集合を，特に集合族 (family)，あるいは集合のクラス (class) という．

集合 $A$ のすべての部分集合全体を考えたとき，これは集合の集合すなわち集合族である．すなわち $\{B\ |\ B\subseteq A\}$ は集合族をなす． この集合を $A$ のべき集合 (power set) といい，$2^{A}$ あるいは $\wp (A)$ と記す.

例： $A=\{a,b,c\}$ のとき，

$\wp (A)=\{\varnothing ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$ である．