読者です 読者をやめる 読者になる 読者になる

bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

Haskellで学ぶ圏論・ウォームアップ編 最小公倍数の構造

1.デザート

二人の男女が食事をした後、デザートを食べることになった。デザートに対する二人の好みはあまりにも違いすぎていて、お互いが共に好きなものはあまりにも少ない。さらに、この二人はとても気まぐれで、その日に食べたいと思うものがお気に入りの中で頻繁に変わる。とても、扱いにくいお客さんなのだが、あなたがシェフだとしたら、どうする。

考えられる一つのケースはケチ型である。二人が最大限の満足をする可能性はまずないのだが、最小限の満足をしてもらうために、二人が共に好きなデザートを用意する。

考えられる二つ目のケースはゴージャス型である。二人に最大限に喜んでもらうために、二人が共に好きなデザートだけでなく、どちらか一方が好きなデザートも含めて、沢山のデザートを用意する。

上の例を数学的なモデルで表すことにする。

男性\(A\)が好きなデザートを\(\{a_1..a_m, c_1..c_t\}\)とする。
女性\(B\)が好きなデザートを\(\{b_1..b_n, c_1..c_t\}\)とする。
ここで、\(\{c_1..c_t\}\)は\(A,B\)ともに好きなデザートで、\(\{a_1..a_m\}\)は\(A\)だけが好きなデザートであり、\(\{b_1..b_n\}\)は\(B\)だけが好きなデザートである。

ケチ型の場合に用意するデザート\(K\)は\(K \subset \{c_1..c_t\}\)となる。
ゴージャス型の場合に用意するデザート\(G\)は\(\{a_1..a_m, b_1..b_n,c_1..c_t\} \subset G \)となる。

ケチ型の可換図は下図のようになる。これは、前回の記事で見た積集合と同じである。即ち、対象\(\{c_1..c_t\}\)は、\(\{a_1..a_m, c_1..c_t\}\)と\(\{b_1..b_n, c_1..c_t\}\)の積となっている。
f:id:bitterharvest:20150205140923p:plain

次にゴージャス型の可換図を考えてみる。これは、矢印を全て反対にすると得られることが分かる。
f:id:bitterharvest:20150205175858p:plain

2.最小公倍数の構造

最大公約数と最小公倍数についても同じように考えることができる。二つの自然数\(A,B\)があったとする。それぞれを素数で分解し、定通の素数を\(\{c_1..c_t\}\)とする。\(A\)の方にしかない素数を\(\{a_1..a_m\}\)とし、\(B\)の方にしかない素数を\(\{b_1..b_n\}\)とする。なお、\(A,B\)が同じ素数を有し、その個数が異なるときは、少ないほうの個数を共通の部分とし、沢山の個数を持つ方にはその残りを置くものとする。

このようにした時、\(\{c_1..c_t\}\)の各要素の積が最大公約数であり、\(\{a_1..a_m, b_1..b_n,c_1..c_t\}\)の各要素の積が最小公倍数となる。また、約数は\(K \subset \{c_1..c_t\}\)となるような\(K\)の各要素の積となり、倍数は\(\{a_1..a_m, b_1..b_n,c_1..c_t\} \subset G \)となるような\(G\)の各要素の積となる。

例えば、36と48の場合は次のようになる。それぞれを素数に分解してその集まりを求めると36:{2,2,3,3}であり、48:{2,2,2,2,3}である。従って、最大公約数を構成する素数は12:{2,2,3}となり、最小公倍数を構成する素数は144:{2,2,2,2,3,3}となる。最小公倍数と倍数の関係を可換図で表すと次のようになる(なお、図で\(a,b\)は任意の自然数である)。
f:id:bitterharvest:20150205175909p:plain

3.対象の和

最大公約数はケチ型であり、最小公倍数はゴージャス型と構造が同じであることが分かったと思う。ケチ型については対象の積として定義したので、ゴージャス型も対象の和(余積という場合もある)として次のように定義する。

対象\(Y, B_1, B_2\)と射
\begin{eqnarray*}
f_1 & : & B_1 \rightarrow Y, \\
f_2 & : & B_2 \rightarrow Y, \\
q_1 & : & B_1 \rightarrow B_1 + B_2, \\
q_2 & : & B_2 \rightarrow B_1 + B_2, \\
u' & : & B_1 + B_2 \rightarrow Y
\end{eqnarray*}
が下図において可換図である時、
f:id:bitterharvest:20150205175922p:plain

即ち、
\begin{eqnarray*}
q_1 \circ u' & = & f_1 \\
q_2 \circ u' & = & f_2
\end{eqnarray*}
のとき、対象\(B_1 + B_2\)は、対象\(B_1\)と\(B_2\)(および射\(q_1\)と\(q_2\))による和(余積)と呼ばれる(なお、もう少し一般的にするためには、対象\(B_1 + B_2\)を対象\(Q\)で置き換えるとよい)。

4.Haskellでの対象の和の定義

対象の和をHaskellのデータ型として定義することを考える。対象の和を定義した下図を利用して
f:id:bitterharvest:20150205175922p:plain

和のデータ型Sum b1 b2を、関数q1,q2,u'とともに作成すると次のようになる(和のデータ型は、\(B_1 + B_2\)をHaskellのデータ型として表すことである。そこで、+は二つを合わせたもの、即ち、論理和と概念的には同一であるので、対象の和をデータ型で表現するときは、「左側と右側にあるものを一緒にしたもの」として表現する。そこで、データ型では|を用いて、論理和の概念が含まれるようにする)。

module Sum where

data Sum b1 b2 = L b1 | R b2 deriving (Eq, Show, Read)
q1 b1 = L b1
q2 b2 = R b2
u' f1 f2 y = case y of L b1 -> f1 b1; R b2 -> f2 b2

これを最小公倍数のときの例で確認してみる。最小公倍数の構造は次のようになっていた。
f:id:bitterharvest:20150205175909p:plain

そこで、36と48の和を作成し、関数q1,q2,u'を次のように利用する。期待する結果を得ることができる。

Prelude> :load "Sum.hs"
[1 of 1] Compiling Sum              ( Sum.hs, interpreted )
Ok, modules loaded: Sum.
*Sum> let s1 = L 36
*Sum> let s2 = R 48
*Sum> q1 36
L 36
*Sum> q2 48
R 48
*Sum> u' (*12) (*9) s1
432
*Sum> u' (*12) (*9) s2
432