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

テンプレート:Pathnav 集合に関した基礎的な事項を簡単にまとめておく．

集合(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\ne j$ ならば $a_i\ne a_j$）からなる集合は，$\{a_1,a_2,\cdots ,a_n\}$ と表す． 要素の順序は任意であり，$\{0,1\}$ と $\{1,0\}$ は同じ集合である．

集合を表す記法として次のような方法もある． $D=\{x|x$ は実数の集合 $𝑅$ に属し，かつ $x^6=1\}$ は， “$x$ は実数の集合の集合 $𝑅$ に属し，かつ $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\in ̸A$

$A\ni ̸a$

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

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

は

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

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

$D=\{x\in 𝑅|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\in ̸B\}$ を，$A$ から $B$ を引いた差集合 (difference) という．これを

$C=A-B$

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

$\mathrm{\Omega }-A$

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

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

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

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

集合族・べき集合

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

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

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

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