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

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

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

参照用 記事

はじめての圏論 その第1歩:しりとりの圏

全体目次:

  1. 第1歩:しりとりの圏 (このエントリー)
  2. 第2歩:行列の圏
  3. 第3歩:極端な圏達
  4. 第4歩:部分圏
  5. 第5歩:変換キューの圏
  6. 第6歩:有限変換キューと半圏
  7. 第7歩:アミダの圏
  8. 第8歩:順序集合の埋め込み表現
  9. 第9歩:基本に戻って、圏論感覚を養うハナシとか

付録/番外など:

  1. 中間付録A:絵を描いてみた
  2. 番外:同期/非同期の結合
  3. 中間付録B:アミダとブレイド
  4. 番外:米田の補題に向けてのオシャベリ


一部のプログラミング言語の背景として、圏論(カテゴリー論)が使われたりするせいか、以前に比べれば多少は圏論に興味を持つ人が増えたような気がしなくもないような。でも、安直な入門的文書はあまり見かけないですね。もちろん、シッカリした教科書や論説はあるんですが、どうもシッカリし過ぎているような。例えば、圏の例として「コンパクト・ハウスドルフ空間連続写像の圏」とか言われてもねぇ(この例はいい例なんですけど*1)。かといって、空な圏0とか、単一元からなる圏1とか出されても「へっ? それがなにか」つう感じだし。

そんなわけで、予備知識なしで理解できる圏の具体例を1つ紹介しましょう。

内容:

しりとりの圏

ひらがな文字全体の集合をHとします。つまり、H={ぁ, あ, ぃ, い, ..., ん, ー}。点々(「...」)でごまかしちゃったけど、ひらがなって何文字あるんでしょう? http://www.unicode.org/charts/PDF/U3040.pdf を眺めると93文字あるようです。が、文字番号3090から始まる16文字は、「を」「ん」以外は使う機会が少ないので除外すると81文字、これに長音記号「ー」(番号は30FC)を加えて82文字としておきます。

ひらがなを並べて出来る文字列全体の集合をHStr(Hiragana Stringのつもり)とします。例えば、"きゅーり", "なす", "ぴーまん" とかがHStrのメンバーです。野菜の名前じゃなくてもいいですよ。それどころか、日本語になっている必要もありません。"はれまけろ", "んじゃびー", "ーょょっん" もHStrに含まれます。ここで大事な注意、空文字列""はHStrに入れません。HStrは1文字以上を含む文字列の集合です。

ひらがな文字列を引数として、ひらがな文字を値とする関数first, lastを次のように定義します。

  • first(s) = 文字列sの最初の文字
  • last(s) = 文字列sの最後の文字

例えば:

 first("きゅーり") = き
 last("きゅーり") = り
 first("らん") = ら
 last("らん") = ん
 first("あ") = あ
 last("あ") = あ

HStrに""は含まれてなかったので、firstもlastもちゃんと定義できます。

さて、ここで“しりとり”をしましょう。「こぶた、たぬき、きつね、ねこ」ってやつです。文字列sとtが(この順で)しりとりになっているのは、last(s) = first(t) のときです。sとtがしりとりになっているときに限り、しりとり結合という演算を定義します。しりとり結合をセミコロン「;」で表すとして、実例を以下に:

 "こぶた";"たぬき" = "こぶたぬき"
 "すいか";"からす" = "すいからす"
 "らいおん";"んじゃびー" = "らいおんじゃびー"
 "あ";"あか" = "あか"

簡単ですね。s;tは、sとtを(この順で)並べるのですが、sの最後とtの最初が同じ文字なので、その並んだ2文字を1文字にするのです。

「"あ";"あか" = "あか"」の例から分かるように、1文字だけからなる文字列(長さ1の列)は単位のような働きを持ちます。そこで、unit = "あ" のような書き方をすることにします。

以上に出てきた、H, HStr, first, last, unit, ; を合わせるとになっています。名付けて「しりとりの圏」。

圏の定義を確認する

圏の定義は、http://d.hatena.ne.jp/keyword/%B7%F7%CF%C0に書いておきましたが、形式的定義だけでは実感が湧かないですよね。で、しりとりの圏が確かに圏であることを確認しましょう。

まず、次の2種類の集合がありました。

  • H -- ひらがな文字全体の集合
  • HStr -- ひらがな文字列全体の集合(ただし空な列は除く)

それと2つの関数。

  • first, last : HStr → H (最初と最後の文字)

もうひとつ関数。

  • unit : H → HStr (1文字からなる文字列)

そして一番重要なのは、しりとり結合演算「;」です。

  • s;t は last(s) = first(t) のときだけ定義される2項演算

算数が足し算や掛け算を扱うのと同様に、圏論は結合演算(今の例ではしりとり結合演算)を扱います。圏論の結合演算(composition; 合成とも呼ぶ)は、いつでも定義できるわけではなくて、条件付きで定義されます。その条件を正確に述べるために、(しりとりの例では)first, lastが必要でした。足し算の0、掛け算の1の役割を演じるのはunitxです。ここで、xは任意のひらがな文字でいいので、単位はたくさん(この例では82個)あります。

次は、定義からすぐにわかるでしょう。

  • first(unitx) = last(unitx) = x (x∈H)
  • first(s;t) = first(s)、last(s;t) = last(t) (s, t∈HStr、sとtが結合可能)

例を挙げれば:

 first(unit) = first("あ") = あ
 last(unit) = last("あ") = あ

 first("こぶた";"たぬき") = first("こぶたぬき") = first("こぶた") = こ
 last("こぶた";"たぬき") = last("こぶたぬき") = last("たぬき") = き

たいていの演算で成立している法則である結合(associative)法則と単位法則は、しりとり結合演算でもやはり成立しています。

  • (s;t);u = s;(t;u)
  • x = first(s), y = last(s) なら、unitx;s = s;unity = s

これも例を挙げれば:

 ("たぬき";"きつね");"ねこ"  = "たぬきつね";"ねこ"  = "たぬきつねこ"
 "たぬき";("きつね";"ねこ") = "たぬき";"きつねこ" = "たぬきつねこ"

 unit;"きゅーり" = "き";"きゅーり" = "きゅーり"
 "きゅーり";unit = "きゅーり";"り" = "きゅーり"

もうこれで、圏の定義は全部述べきってしまったのですが、圏論で一般的に使われる用語/記法と、しりとりの例で使った用語/記法を並べておきます。

圏論一般 しりとりの例
対象 ひらがな文字
ひらがな文字列
恒等射 長さ1の文字列
結合(合成) しりとり結合
対象の集合 ひらがな文字の集合H
射の集合 ひらがな文字列の集合HStr
dom (域) first
cod (余域) last
id (恒等射) unit

*1:だから、はてなキーワード圏論」にこの例を入れてます、イキナリ。