１０．２ 集合と冪集合
数学は全く異なるものの間の中に共通する性質を見出し新しい概念を引き出すことを得意とする学問だ。ここでも、後でまさかと思うことを説明するのだが、その準備のために集合について少し説明しておこう。
集合は要素の集まりと最初は教わる。例えば、集合\(S\)が要素\(a,b,c\)の集まりである時は、\(S=\{a,b,c\}\)と記す。
次に集合の部分集合を学ぶ。これは、ある集合を構成する要素の一部分を集めて作った集合である。例えば、要素\(a,b\)で構成される集合\(S'=\{a,b\}\)は\(S\)の部分集合である。これは、\(S' \subset S\)と記す。部分集合には要素が皆無である物もすべて含んでいるものも含まれる。
そこで、部分集合を集めたものもまた集合である。例えば、\(S''=\{a,c\}\)としたとき\(T=\{S',S''\}=\{\{a,b\},\{a,c\}\}\)は集合である。そこで、部分集合で構成される集合の全てを集めたものを考えることにしよう。これを冪集合と呼ぶことにしよう。先に説明した集合\(S=\{a,b,c\}\)の冪集合\(P(S)\)は
\begin{equation}
P(S)=\{\{\},\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}
\end{equation}
となる。
冪集合も集合なのでその冪集合を取ることができる。そこで、\(P(S)\)の冪集合\(Q(P(S))\)は、
それぞれの要素を部分集合にしたもの：\(\{\{\}\},\{\{a\}\},\{\{b\}\},\{\{c\}\},\{\{a,b\}\},\{\{a,c\}\},\{\{b,c\}\}\},\{\{a,b,c\}\}\)
\(\{\}\)と残りの要素のそれぞれを組み合わせて部分集合にしたもの：\(\{\{\},\{a\}\},\{\{\},\{b\}\},\{\{\},\{c\}\},\{\{\},\{a,b\}\},\{\{\},\{a,c\}\},\{\{\},\{b,c\}\},\{\{\},\{a,b,c\}\}\)
\(\{a\}\)と残りの要素のそれぞれを組み合わせて部分集合にしたもの：\(\{\{a\},\{b\}\},\{\{a\},\{c\}\},\{\{a\},\{a,b\}\},\{\{a\},\{a,c\}\},\{\{a\},\{b,c\}\},\{\{a\},\{a,b,c\}\}\)
\(\{b\}\)と残りの要素のそれぞれを組み合わせて部分集合にしたもの：\(\{\{b\},\{c\}\},\{\{b\},\{a,b\}\},\{\{b\},\{a,c\}\},\{\{b\},\{b,c\}\},\{\{b\},\{a,b,c\}\}\)
\(\{c\}\)と残りの要素のそれぞれを組み合わせて部分集合にしたもの：\(\{\{c\},\{a,b\}\},\{\{c\},\{a,c\}\},\{\{c\},\{b,c\}\},\{\{c\},\{a,b,c\}\}\)
\(\{a,b\}\)と残りの要素のそれぞれを組み合わせて部分集合にしたもの：\(\{\{a,b\},\{a,c\}\},\{\{a,b\},\{b,c\}\},\{\{a,b\},\{a,b,c\}\}\)
\(\{a,c\}\)と残りの要素のそれぞれを組み合わせて部分集合にしたもの：\(\{\{a,c\},\{b,c\}\},\{\{a,c\},\{a,b,c\}\}\)
\(\{b,c\}\)と残りの要素のそれぞれを組み合わせて部分集合にしたもの：\(\{\{b,c\},\{a,b,c\}\}\)
これらを集めたものである。この関係を図に表したのが下図である。
しかし、上記の記述では、それぞれの部分集合は部分集合を集めたものとなっている。例えば最後の部分集合\(\{\{b,c\},\{a,b,c\}\}\)である。しかし、これは実は\(\{a,b,c\}\)と同じである。即ち、冪集合から作られた冪集合を構成する部分集合は、内側にある\(\{\}\)をはずし同じ要素を一つにまとめたもの(和集合)と同じである。また、要素が一つだけの部分集合のカッコも外すと、次のようになる。
\begin{equation}
Q(P(S))=\{\{\},a,b,c,\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}
\end{equation}
同じように\(P(S)\)の方も要素が一つだけの部分集合のカッコを外すと、次のようになる。
\begin{equation}
P(S)=\{\{\},a,b,c,\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}
\end{equation}
これより、
\begin{equation}
Q(P(S))=P(S)
\end{equation}
であることが分かる。
そこでこれを図で表すと次のようになる。
上図で\(P(S)\)は\(S\)を含んでいるので、集合を冪集合の部分集合にして図を書き直すと次のようになる。
さて、\(S\)と\(P(S)\)をHaskellでの型と思って、それぞれを型変数\(a\)と\(m \ a\)で書き換え、冪集合をモナドで書き換えると下図を得る。
ここで、\(m \ (m \ a)=m \ a\)である。
上記では、集合と冪集合を型変数で書き換えることで抽象化をおこなった。ここで得られたものがモナドと呼ばれるものである。モナドと言われたら、集合と冪集合の関係を思い出すか、あるいは、前回の記事で述べたようにCやJavaのような命令型の言語で書かれたプログラムを思い出すと分かりやすいと思う。
