bitterharvest’s diary

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

極限-例:最大公約数

1.3 最大公約数

前回の記事では、集合を利用して、圏論での積を説明した。また、積の普遍性についても説明した。これらをさらに進めると、極限になる。しかし、もう少し例を挙げて、極限の説明をするための準備をすることにしよう。

ここでは、集合から離れることにする。極限という言葉は使わないが、類似した概念は中学校の数学でも現れる。そう、最大公約数(GCD: greatest common divider)だ。二つの整数が与えられた時に、共通の約数で最大のものが最大公約数だ。

今、二つの整数360と420を選んだとしよう。このとき、二つの整数の共通の素数は、(2,2,3,5)である。従って、これらの中からいくつかを取り出して掛け合わせたものは公約数となる。例えば、(2,2,3)からの12、あるいは、(2,3,5)からの30などはこの二つの数の共通の約数である。また、全てを取り出した(2,2,3,5)からの60は最大公約数である。これらを\(X,X’,A \times B\)とし、360と420を\(A\),\(B\)で表すと、以下のような可換図を得る。
f:id:bitterharvest:20171204143050p:plain
この図は、前回の記事で積の極限を説明したときの図と同じものである。この図より、\(A \times B\)が、\(A \)と\(B \)の積の極限、すなわち最大公約数、になっていて、\(X\)や\(X’ \)などが、\(A \)と\(B \)の積の候補、すなわち公約数、であることが分かる。従って、候補の中でもっともよいものが極限、すなわち、公約数の中で最も優れたもの、この場合には大きいものが最大公約数となっている。

即ち、上記の図において、\(A\)と\(B\)に対する任意の公約数\(X\)は、最大公約数\(A \times B\)に対して、一意的な射\(m\)が存在し、
\begin{eqnarray}
fst \circ m = p \\
snd \circ m =q
\end{eqnarray}
である。ここで、\(fst:A \times B \rightarrow A \),\(snd:A \times B\)である。これにより、最大公約数は圏での積である。

上記の図は、公約数で表したが、これを、それぞれを構成する素数で表すと次のようになる。
f:id:bitterharvest:20171204143115p:plain
この図で、公約数を、すなわち最大公約数の候補を、それを構成している素数の集合と見なすと、候補は、極限即ち最大公約数の部分集合となっていることが分かる。

これは、前回、集合と説明したときと同じで、その時も候補は極限の部分集合になっていた。このようにみていくと、最大公約数の場合も、前の例題と同じだということが分かる。

このため、個別に定義するのではなく、共通な概念として極限を考えたほうがよいということが分かる。

問題:最大公約数が作る圏をHaskellで作成しなさい。