このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

有限集合と写像の圏もJavaScriptで書いてみた、遊んでみてね

昨日、しりとりの圏のJavaScript版実装を示しました。モニャドセミナーの最後のほうでMapFO(Map category over Finite Ordinals)という例も出したので、これもJavaScriptにしてみました。FirefoxブラウザにFirebugが入っていれば、[F12]キーですぐさまいじれます。

大事なのは実感、イメージ、具体性; ぜひブラウザ上で圏の実例を試してみてください。また同じセリフを繰り返しますが、
目や手を動かしてやってみないとハジマリません。ジッと考えていても、どうせ分かりません。

内容:

  1. 使い方
  2. 有限オーディナル
  3. 写像
  4. 写像を作る
  5. 射(写像)の域と余域
  6. 射(写像)の結合
  7. 恒等射
  8. しりとりの圏の実装との違い
  9. まとめ

使い方

まずは、使い方。Firebugで実行するときは、次のようなHTMLファイルをFirefoxにロードします。このHTMLファイルは、簡単なヘルプになっています。


<html>
<head>
<title>Map Category over Finite Ordinals</title>
<script src="MapFO.js"></script>
</head>
<body>
<h1>Map Category over Finite Ordinals</h1>

<ol>
<li><b>MapFO.isObject(x)</b> ( x は任意 )</li>
<li><b>MapFO.isMorphism(x)</b> ( x は任意 )</li>
<li><b>MapFO.dom(f)</b> ( f は射 )</li>
<li><b>MapFO.cod(f)</b> ( f は射 )</li>
<li><b>MapFO.compose(f, g)</b> ( f, g は射 )</li>
<li><b>MapFO.id(n)</b> ( n は対象 )</li>
<li><b>MapFO.newMorphism(n, m, v)</b> ( n, m は対象, v は値の配列 )</li>
<li><b>MapFO.mor(n, m, v)</b> ( newMorphism の短縮 )</li>
<li><b>MapFO.mor(m, v)</b> ( mor(v.length, m, v) の短縮 )</li>
<li><b>MapFO.eq(f, g)</b> ( f, g は射 )</li>
</ol>

</body>
</html>

JavaScriptファイルMapFO.jsは、メモ編エントリー http://d.hatena.ne.jp/m-hiyama-memo/20090425/1240632392 からコピーして作ってください。[F12]キーを押してFirebugをアクティブにして、FirebugコンソールをJavaScriptインタプリタ・シェルとして使います。

ブラウザ特有の機能は使ってないので、Rhinoなど、他のJavaScriptインタプリタでも大丈夫です。

有限オーディナル

{}, {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}, … のような有限集合を考えます。1からはじまる整数を順番に並べた集合ですね。この形の有限集合を有限オーディナル(finite ordinal)と呼びます。ordinalは順序数と訳しますが、「数」じゃなくて「集合」だからここではカタカナ書きにします。

{1, 2, ..., n}を[n]と略記します。つまり、

  1. [0] = {}
  2. [1] = {1}
  3. [2] = {1, 2}
  4. [3] = {1, 2, 3}
  5. [4] = {1, 2, 3, 4}

[0] = {}, [1] = {0}, [2] = {0, 1} と書く流儀もありますが、ささいな違いだからどっちでもいいでしょう。

写像

[n]と[m]が2つの有限オーディナルだとして(n = m でもかまいません)、[n]から[m]への写像(map, mapping)とは、[n]の要素(n以下の正整数)に[m]の要素(m以下の正整数)を1個だけ割り当てる対応のことです。

例えば、fが[2]={1, 2}から[3]={1, 2, 3}への写像であるとは、f(1)とf(2)がハッキリと決まっているということです。f(1) = 2, f(2) = 1 とかね。この例から分かるように、[n]から[m]への写像は、次の3つの構成要素が分かれば確定します。

  1. 非負整数 n
  2. 非負整数 m
  3. f(1), f(2), ..., f(n) という正整数の並び

条件として、

  • f(1), f(2), ..., f(n) のどの数も1以上m以下

写像を作る

MapFO.jsにおいて、有限オーディナルのあいだの写像を作るには、

  • MapFO.mor(n, m, [f(1), f(2), ..., f(n)])

とします。morはmorphismの略です。morphismは射ですよ。圏論のハナシしてんですから。

対話例:


>>> var f = MapFO.mor(2, 3, [2, 1])
>>> f
[2] --> [3]
1 |--> 2
2 |--> 1
dom=2 cod=3 values=[2]
>>> var g = MapFO.mor(3, 3, [2, 3, 3])
>>> g
[3] --> [3]
1 |--> 2
2 |--> 3
3 |--> 3
dom=3 cod=3 values=[3]

ちょっと細工をして、写像をそれらしく表示するようにしてあります。見りゃわかると思うけど、上のfの例なら:

  • [2] --> [3] : fは、[2] から [3] への写像です
  • 1 |--> 2 : f(1) = 2
  • 2 |--> 1 : f(2) = 1

「dom=2 cod=3 values=[2]」については後の「しりとりの圏の実装との違い」で説明します。とりあえず無視してください。

射(写像)の域と余域

圏の主役は射です。今扱っている例なら、有限オーディナルのあいだの写像が射です。その射に対して、定義域となる集合が域(domain)、値を取るべき集合が余域(codomain)です。この例では域も余域も集合ですが、JavaScriptプログラム内では単なる整数として扱っています。つまり、[n] ←→ n という対応により、[n]の代理にnを使っているのです。「代理」ではなくて、最初から対象の集合は{0, 1, 2, 3, ...}だと定義しても何ら問題はありません*1

対話例:


>>> MapFO.dom(f)
2
>>> MapFO.cod(f)
3
>>> MapFO.cod(f) == MapFO.dom(g)
true

射(写像)の結合

2つの射 f, g が結合可能(composable)であるには、cod(f) = cod(g) である必要があります。上の例で、MapFO.cod(f) == MapFO.dom(g) が true だったので、結合(合成)できます。やってみます。

対話例:


>>> MapFO.compose(f, g)
[2] --> [3]
1 |--> 3
2 |--> 2
dom=2 cod=3 values=[2]

事情は、こんな(↓)の図でわかるかな。この図は左から右へと見てね。


f g
[2]→[3]→[3]

1 1 1
\/ \
/\ \
2 2 2


3ーー3

あるいは:

  1. g(f(1)) = g(2) = 3
  2. g(f(2)) = g(1) = 2

恒等射

有限オーディナル[n]に対して、恒等写像id[n]が対応していて、id[n] は次の性質を持ちます。

  1. 射f:[n]→[m] に対して、id[n];f = f
  2. 射g:[k]→[n] に対して、g:id[n] = g

MapFO.jsでは、id[n] を MapFO.id(n) と表現します。

対話例:


>>> var i = MapFO.id(2)
>>> i
[2] --> [2]
1 |--> 1
2 |--> 2
dom=2 cod=2 values=[2]
>>> var j = MapFO.id(3)
>>> j
[3] --> [3]
1 |--> 1
2 |--> 2
3 |--> 3
dom=3 cod=3 values=[3]
>>> MapFO.compose(i, f)
[2] --> [3]
1 |--> 2
2 |--> 1
dom=2 cod=3 values=[2]
>>> MapFO.eq(MapFO.compose(i, f), f)
true
>>> MapFO.compose(f, j)
[2] --> [3]
1 |--> 2
2 |--> 1
dom=2 cod=3 values=[2]
>>> MapFO.eq(MapFO.compose(f, j), f)
true

MapFO.eq は射が等しいかどうかを判定する述語(ブール値の関数)です。上の対話例で確認したことを通常の等式で書けば次のようですね。


f:[2]→[3]、i = id[2]、j = id[3] のとき:

i;f = f
f;j = f

しりとりの圏の実装との違い

しりとりの圏をJavaScriptで実装したときは、対象は整数、射は文字列でした。整数も文字列もJavaScriptの基本データなので、リテラルで表現できるし、等しさはJavaScriptの「==」で判定できます。

今回の有限オーディナルと写像の圏では、対象は整数なのですが、射はJavaScriptのオブジェクトで表現してます。なので、射をリテラルで書くのは好ましくありません(内部構造が露出するので)。コンストラクタを使うことになります。MapFO.mor(MapFO.newMorphismの短縮形)がコンストラクタ(をラップした関数)です。射の等しさを調べるにも、MapFO.eqという関数を呼ぶ必要があります。

もし、対象もJavaScriptオブジェクトで表現するような状況になると、SomeCat.obj(/*適当な引数*/)、SomeCat.mor(/*適当な引数*/) という2つのコンストラクタと、SomeCat.eqObj(a, b)、SomeCat.eqMor(f, g) という2つの述語が必要になるでしょう。元来圏論は、等式的論理(eqational logic)をベースに定義されるので、「対象のイコール」「射のイコール」という述語が要求されるのは当然なのです。たまたまプログラミング言語のイコールが使えるときもある、ということですね。

MapFOの射の表示に「dom=2 cod=3 values=[2]」のように出るのは、Firebugによるオブジェクトの表示で、「domプロパティの値が2, codプロパティの値が3, valuesプロパティは長さ2の配列」という意味です。

まとめ

しりとりの圏と同じスタイルで表にまとめておきます。

  1. 圏Cの対象の集合を Obj(C)、または |C| と書きます。
  2. 圏Cの射の集合を Mor(C)、または圏全体を表す記号を流用(乱用)して C と書きます。
  3. 対象aの恒等は、id(a) よりは ida と書くのが普通です。
  4. 「圏C内で … が成立する」を「… in C」と(ここでは)書くことにします。
概念を言葉で表現すると 式で表現すると プログラム断片で表現すると
[n]は圏MapFOの対象である [n]∈Obj(MapFO) MapFO.isObject(n)
fは圏MapFOの射である f∈Mor(MapFO) MapFO.isMorphism(f)
射fの域は対象[n]である dom(f) = [n] in MapFO MapFO.dom(f) == n
射fの余域は対象[m]である cod(f) = [m] in MapFO MapFO.cod(f) == m
射fは対象[n]から対象[m]への射である s:[n]→[m] in MapFO MapFO.dom(f) == n && MapFO.cod(f) == m
射fと射gは結合可能である cod(f) = dom(g) in MapFO MapFO.cod(f) == MapFO.dom(g)
射hは、射fと射gの結合(合成)である h = f;g in MapFO h == MapFO.compose(f, g)
射iは、対象[n]に対する恒等射である i = id[n] in MapFO i == MapFO.id(n)

さらに、しりとりの圏HSCatと有限オーディナルと写像の圏MapFOも比較しておきます。

一般概念 HSCat MapFO
対象 ひらがな文字を表す整数 有限オーディナル(JavaScript実装では対応する整数)
空でないひらがな文字列 有限オーディナルのあいだの写像
結合 文字列のしりとり結合 写像の合成(普通の定義)
恒等 ひとつの文字からなる文字列 恒等写像(普通の定義)

APIのネーミングはどちらも次の規則にしてあります。Cは圏の名前です。

役割 関数呼び出しの形式
対象かどうかを判定 C.isObject(x)
射かどうかを判定 C.isMorphism(x)
射の域 C.dom(f)
射の余域 C.cod(f)
2つの射の結合 C.compose(f, g)
恒等 C.id(a)

MapFOの延長線上に、有限オーディナルと部分写像(partial map)の圏PMapFO、有限オーディナルと関係(relation)の圏RelFOがあります。興味と元気がある方はお好みのプログラミング言語で実装してみてください。次回モニャドセミナーでは、ホワイトボードだけじゃなくてプログラムのデモも使うかもしれません。

*1:さらに言えば、整数値nがそもそも集合なんだと考えてもいいのです。そう考えるときは、0 = {}, 1 = {0}, 2 = {0, 1} と定義したほうが好都合です。