檜山正幸のキマイラ飼育記 このページをアンテナに追加 RSSフィード

キマイラ・サイトは http://www.chimaira.org/です。
トラックバック/コメントは日付を気にせずにどうぞ。
連絡は hiyama{at}chimaira{dot}org へ。
蒸し返し歓迎!
ところで、アーカイブってけっこう便利ですよ。タクソノミーも作成中。今は疲れるので作っていません。

2006-08-21 (月)

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

| 09:29 | はじめての圏論 その第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つ紹介しましょう。

内容:

  1. しりとりの圏
  2. 圏の定義を確認する

●しりとりの圏

ひらがな文字全体の集合を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:だから、はてなキーワード「圏論」にこの例を入れてます、イキナリ。

iopotshiroutoiopotshirouto 2010/03/18 20:09 はじめまして。「層・圏・トポス」を独学中(というか、数学そのものがほとんど独学の素人です)の者です。
もしかして、このしりとりの圏は(有向)グラフと関係ないでしょうか?
多重辺や多重ループを許せば、グラフは、頂点の集合V、辺の集合、辺の始点を表す写像dom:E→V、終点を表す写像cod:E→Vの4つ組(V,E,dom,cod)として表せますね。
グラフがあれば、頂点を対象として、頂点から頂点への「道」を射とする圏(各頂点ごとに、長さ0の道(恒等射)があると考える)が必ず作れます(グラフから生成された自由圏で、圏をグラフと見なす操作と随伴関係)。
で、Xを文字集合としたとき、しりとりグラフを(X,X×X、π1、π2)(π1、π2は射影)で定義すれば、しりとりの圏はこのしりとりグラフの自由圏になるのではないでしょうか?
なぜ、グラフにこだわるか、というと、(有向)グラフの圏Graphは「位相空間の知識なしに具体的にイメージ可能なブーリアンでないトポス」のひとつなので独学に非常にお勧めなのです。私も大変お世話になりました。
ええと、グラフの頂点集合を取る操作と、文字集合Xからしりとりグラフを作る操作も随伴関係になるはずですね。(というか、geometric morphism Set→Graphになるはずなのですが、あの本にはgeometric morphismの定義しか書いてなかったので、この概念がどう役に立つのか知らないのですけど。)

m-hiyamam-hiyama 2010/03/19 09:49 iopotshiroutoさん、
> で、Xを文字集合としたとき、しりとりグラフを(X,X×X、π1、π2)(π1、π2は射影)で定義すれば、
> しりとりの圏はこのしりとりグラフの自由圏になるのではないでしょうか?
はい、そのとおりです。
道は、((た, ぬ), (ぬ, き)) とかなので、これを、[た, ぬ, き] と書いてみれば、道の連接 [た, ぬ, き];[き, つ, ね] が [た, ぬ, き, つ, ね] となります。

> (有向)グラフの圏Graphは「位相空間の知識なしに具体的にイメージ可能なブーリアンでないトポス」のひとつ
そういえば、Sebastiano Vigna (http://vigna.dsi.unimi.it/)が、 "A Guided Tour in the Topos of Graphs" なんて解説論文を書いていました。グラフは絵に描いて目で確認できるので、確かに良い素材ですね。

iopotshiroutoiopotshirouto 2010/03/19 20:07 蒸し返しOKとのことでコメントを書かせていただきましたが、まさかこんなに早くレスをいただけるとは。ありがとうございました<(_O_)>。
当該解説論文はネットにpdf文書であるようですね。早速(英語が非常に苦手なのですが)読ませていただきます。
この論文には辺へのラベル付けの話があったようですが、このしりとりグラフは頂点へのラベル付けに使えるのですが(しりとりグラフを作る手続きは、頂点集合を取る忘却関手の右随伴なので、Graph/(Xのしりとりグラフ)を考えればよい)、専門家の方は暗算で簡単にできるでしょうが、自分でこれを発見したときは「おお!随伴ってのはこういうことか」と感動しました。

m-hiyamam-hiyama 2010/03/20 18:15 iopotshiroutoさん、
> しりとりグラフを作る手続きは、頂点集合を取る忘却関手の右随伴なので、
少しだけ一般化して、圏の圏Catと集合圏Setを考えて、圏にその対象集合を対応付ける関手 Obj(C) = |C| : Cat → Set に対して、完全グラフ(を圏とみなしたもの)を作る関手が随伴ですね。

> 「おお!随伴ってのはこういうことか」と感動しました。
自分で見つけるとうれしいですよね :-)

iopotshiroutoiopotshirouto 2010/03/20 19:56 私も暗算に挑戦。|C| : Cat → Set の右随伴・・・だとすると、できる圏(完全グラフのような形)の射はすべて同型射になるかな?一方、しりとりの圏は恒等射以外に同型射はないから、しりとり圏とはまったく別物になる・・・これでよろしいでしょうか。

鈴木盛文鈴木盛文 2011/04/15 16:28

オートポイエーシスと圏論


圏論に関して素人なのですが、質問があります。

単刀直入にいって、
オートポイエーシスを圏論で表現することは可能でしょうか?

システムの閉域や、システムの要素そのものが入れ替わるような条件を圏論は表現できるのだろうか、という疑問から質問させていただきました。

m-hiyamam-hiyama 2011/04/15 16:41 鈴木盛文さん、
> オートポイエーシスと圏論
> 圏論に関して素人なのですが、
僕はオートポイエーシスに関して素人なので、

> 単刀直入にいって、
> オートポイエーシスを圏論で表現することは可能でしょうか?
単刀直入にいって、まったく分かりません。

僕にとっての圏論は、計算(computation)やソフトウェアの記述と分析の道具なので、それ以外の用途や分野は全然知りません。
応用を想定しないプロパーな圏論もよく分かりません。
お役に立てなくて申し訳ないです。

sakurasakura 2016/09/24 18:36 はじめまして。圏論には以前から興味があり、最近学び始めた者です。
しりとりの圏は非常に直観的で分かりやすく大変参考になりました。
圏の定義について一つ質問があります。HatenaKeyWordによると、
>(Obj, Morph, dom, cod, id, comp)からなる系を圏と呼ぶ。
とあり、幾つかの性質を持つObj,Morphなる集合と写像の組とあります。これ自体は理解できるのですが、圏論の基礎p10には、
>メタ圏の対象はその恒等射と正確に対応するので,対象を全く抜きにして射のみを扱うことも技術的には可能である。
(中略)
>Cのデータは射,射の合成可能対と呼ばれる順序対<g,f>,および合成可能対<f,g>にそれらの合成射と呼ばれる射g◌fを割り当てる演算からなる。
とあります。確かに、これらがしっかりと定義されているならば、恒等射全体をObjとした上で、dom,codom,id,compを定義し、二つの定義の同値性が示されるということろまでは分かりました。
このマックレーンの定義に於いては恒等射の定義に合成を用いており、合成可能対が定まっている必要があるために、合成可能対全体が暗に仮定されているように思われます。
しかし合成可能対の定義が明確でなく、合成可能対全体を如何にして定めればよいのかが分かりませんでした。
ですから、私は射のみからなる定義を一旦諦めて読み進めているのですが、どうもこの点が腑に落ちずにいます。
もしよければ、非常に基本的な事柄ではあるのですが、以上の点についてご教授いただければ幸いです。

トラックバック - http://d.hatena.ne.jp/m-hiyama/20060821/1156120185