自由圏とは、自由な圏である。
概要
1を解説する。
有向グラフ
有向グラフとは、以下の図式のように頂点とそこから延びる向き付きの辺(矢印)からなるものである。
A | → | B | → | C |
↓ | ↙ | ↓ | ↗ | |
D | E | |||
↓ | ||||
F | → | G | → | H |
頂点を対象、辺を射と見ると、合成射と恒等射がないことを除けば、各グラフは圏と似たような構造を持つことが分かる。なのでしばしば有向グラフを前圏(precategory)と呼んだりする。
グラフGは、頂点の集合をO、辺の集合をA、関数の対A⇉Oで定義される。
A⇉∂0∂1O 、∂0f:fの始点(ドメイン) ∂1f:fの終点(コドメイン)
つまり、Aの要素である射fに対してOの要素から始点と終点を割り当てる関数∂0と∂1で定義されるということ。
グラフ間の写像D:G→G'は、関数の対DO:O→O'とDA:A→A'で、任意の辺f∈Aについて、DO∂0f=∂0DAf かつ DO∂1f=∂1DAf を満たすものである。
a | → | b | DOa | DOd | ||
↓ | ↙f | ↓g | ⇒D⇒ | ↓ | ↘ | ↑DAg |
c | d | DOc | ← DAf |
DOb |
この写像DはD'∘D:G→G'→G''のように、明らかに合成が可能なので、すべての(小さな)グラフを対象とする圏Graphの射となる。
全ての圏Cは射の合成と恒等射を忘れ、同じ対象と射を持つグラフU(C)に移す操作により、C→U(C)が決定する。すべての関手F:C→C'は同じ操作によりU(F):U(C)→U(C')を決定する。この操作から、(小さな)圏の圏Catから(ちいさな)グラフの圏Graphへの圏の構造を忘れる写像「忘却関手」U:Cat→Graphが定義される。
O-グラフ
Oをある固定した集合とする。O-グラフとは、Oを対象の集合とするグラフである。A,BがO-グラフの射の集合とし、O上の積×OをA×OB={〈g,f〉|∂0g=∂1f、g∈A、f∈B}で定義する。これは「合成可能対」・→f・→g・からなる集合である。∂0〈g,f〉=∂0f、∂1〈g,f〉=∂1gとすることにより、この集合はO-グラフとなる。
a |
b |
a |
i → |
b |
a |
b |
||||
↙h | ×O | ↓g | ⇒ | ↓〈i,h〉 | ↙〈g,f〉 | |||||
c | ← f |
d | c | d | c | d |
射の合成が結合的なので、この演算×Oは結合的である。つまり、(A×OB)×OC≅A×O(B×OC)。特別なグラフとして、射を持たないグラフをOと書き、Oは×Oに対して恒等元として働くと決める。つまり、O×OA ≅ A×OO ≅ A、f→〈f,∂0f〉。
Oを対象とする圏はO-グラフの集合Aと、O-グラフの2つの写像m:A×OA→A(合成)とe:O→A(恒等射)で、以下の図式を可換とするものとして記述できる。
(A×OA)×OA≅A×O(A×OA) |
idA×Om → |
A×OA |
↓m×OidA | ↓m | |
A×OA | → m |
A |
O×OA |
e×idA → |
A×OA |
idA×Oe ← |
A×OO |
≅↘ | ↓m | ↙≅ | ||
A |
合成可能対〈g,f〉はm(g,f)で与えられる合成mを持ち、各対象aはe(a)で与えられる恒等射を持つ。始めの図式は結合性を、次の図式は各aに対しe(a)が右恒等元および左恒等元となる事を表している。
この図式から、O-グラフの成す圏はモノイドとよく似ていることがわかる。
自由圏
Oから生成されたO-グラフGは同じ対象の集合を持つ圏Cを生成する事ができる。この圏の射は合成可能対の列となり、bからaへのCの射はGの連続する辺からなるbからaへの経路として図示する事ができる。この圏C(G)はグラフGから生成される自由圏と呼ぶ。
G={A⇉O}を小さなグラフとする。Oを対象とする小さな圏C、および、GからCの基底グラフU(C)への写像P:G→U(C)で、次の普遍性を満たすものが存在する。
C |
U(C) |
P ← |
G |
|
D'↓ | U(D')↓ | ↙D | ||
B | U(B) |
任意の圏Bと任意の写像D:G→U(B)が与えられた時、上記可換図式におけるように、U(D)∘P=Dとなる関手D':C→Bが一意に存在する。特に、BがOを対象とし、DがO-グラフの写像であればD'は対象に関しては恒等写像となる。
証明
Cの対象をGの対象とし、Cの射をGのn個の対象をGのn-1本の辺fi:ai→ai+1で結びつけて合成した有限列とする。
これを経路と呼ぶ。このような経路をCの射〈a1,f1,a2,f2,…,fn-1,an〉:a1→anを見なす。合成は共通する端の対象を同一視することで定義する。
〈an,fn,an+1,fn+1,…,fm-1,am〉∘〈a1,f1,…,fn-1,an〉=〈a1,f1,…,fn-1,an,fn,…,fm-1,am〉
長さ1の列〈a1〉は対象a1の恒等射である。
P:G→U(C)は、与えられたグラフGの各辺f:a1→a2を長さ2の経路〈a1,f,a2〉に移す。
ここで、与えられたグラフGからある圏Bの基底グラフU(B)への他の写像D:G→U(B)を考える。U(D')∘P=Dとなる関手D':C→Bが存在するなら、D'は対象についてD'〈a〉=D(a)であり、射についてD'〈a1,f1,a2〉=D(f1)である。長さ2以上の任意の経路はCにおける上記の射の合成なので、D'〈a1,f1,…fn-1,an〉=D(fn-1)∘D(fn-2)∘…∘D(f1)でなければならない。
逆に、このようなDがあれば図式を可換にするような関手D'が定義される。
自由圏の例
- ∂0f=∂1fの射f一つのみからなるグラフから生成された自由圏は恒等射id,および f, f∘f=f2, f∘f∘f=f3,…からなる。
- ∂0f≠∂1fの射一つのみからなるグラフから生成された自由圏は恒等射id、およびfのみからなる。
- 2つの対象a,bとf:a→bとg:b→aからなるグラフから生成された自由圏の射はida, idb, f, g, fg, gf, gfg, fgf, gfgf, fgfg,…からなる。
- 3つの対象からなるグラフ・→・→・は、以下の可換図式で表される3つの射と3つの恒等射を持つ自由圏となる。
・ ↺ |
→ f |
・ ↺ |
g∘f↘ | ↓g | |
・ ↺ |
- 1つの対象とn個の射f1,f2,…,fn(∂0fi=∂1fi)を持つグラフから生成された自由圏の射の集合は文字をn個持つ自由モノイドと一致する。例1は文字が一つの自由モノイドと言える。
- ひらがなを対象、単語の集合を射、単語の先頭の文字をドメイン、単語の終わりの文字をコドメインとすると自由圏を成す。これをしりとりの圏という。しりとりは身近な圏の一つである。
関連商品
関連項目
- 1
- 0pt