自由圏とは (ジユウケンとは) [単語記事]

自由圏とは、自由な圏である。

概要

圏論における自由圏（free category）。
自由主義経済圏を共産主義経済圏と区別するときに略して自由圏と呼ぶ。

1を解説する。

有向グラフ

有向グラフとは、以下の図式のように頂点とそこから延びる向き付きの辺（矢印）からなるものである。

A	→	B	→	C
↓	↙	↓	↗
D		E
↓
F	→	G	→	H

頂点を対象、辺を射と見ると、合成射と恒等射がないことを除けば、各グラフは圏と似たような構造を持つことが分かる。なのでしばしば有向グラフを前圏(prec ategory)と呼んだりする。

グラフGは、頂点の集合をO、辺の集合をA、関数の対A⇉Oで定義される。

A⇉^∂0_∂1O　、∂₀f：fの始点（ドメイン）　∂₁f：fの終点（コドメイン）

つまり、Aの要素である射fに対してOの要素から始点と終点を割り当てる関数∂₀と∂₁で定義されるということ。

グラフ間の写像D：G→G'は、関数の対D_O：O→O'とD_A：A→A'で、任意の辺f∈Aについて、D_O∂₀f=∂₀D_Af　かつ　D_O∂₁f=∂₁D_Af　を満たすものである。

a	→	b		D_Oa		D_Od
↓	↙f	↓g	⇒D⇒	↓	↘	↑D_Ag
c		d		D_Oc	← D_Af	D_Ob

この写像DはD'∘D：G→G'→G''のように、明らかに合成が可能なので、すべての(小さな)グラフを対象とする圏Gr aphの射となる。

全ての圏Cは射の合成と恒等射を忘れ、同じ対象と射を持つグラフU(C)に移す操作により、C→U(C)が決定する。すべての関手F：C→C'は同じ操作によりU(F)：U(C)→U(C')を決定する。この操作から、（小さな）圏の圏Catから（ちいさな）グラフの圏Gr aphへの圏の構造を忘れる写像「忘却関手」U：Cat→Gr aphが定義される。

O-グラフ

Oをある固定した集合とする。O-グラフとは、Oを対象の集合とするグラフである。A,BがO-グラフの射の集合とし、O上の積×OをA×_OB={〈g,f〉｜∂₀g=∂₁f、g∈A、f∈B}で定義する。これは「合成可能対」・→_f・→_g・からなる集合である。∂₀〈g,f〉=∂₀f、∂₁〈g,f〉=∂₁gとすることにより、この集合は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,∂₀f〉。

Oを対象とする圏はO-グラフの集合Aと、O-グラフの2つの写像m：A×_OA→A（合成）とe：O→A（恒等射）で、以下の図式を可換とするものとして記述できる。

(A×_OA)×_OA≅A×_O(A×_OA)	id_A×_Om →	A×_OA
↓m×_Oid_A		↓m
A×_OA	→ m	A

O×_OA	e×id_A →	A×_OA	id_A×_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で結びつけて合成した有限列とする。

a₁→_f1a₂→_f2a₃→_f3…→_fn-1a_n

これを経路と呼ぶ。このような経路をCの射〈a₁,f₁,a₂,f₂,…,f_n-1,a_n〉：a₁→a_nを見なす。合成は共通する端の対象を同一視することで定義する。

〈a_n,f_n,a_n+1,f_n+1,…,f_m-1,a_m〉∘〈a₁,f₁,…,f_n-1,a_n〉=〈a₁,f₁,…,f_n-1,a_n,f_n,…,f_m-1,a_m〉

長さ1の列〈a₁〉は対象a₁の恒等射である。

P：G→U(C)は、与えられたグラフGの各辺f：a₁→a₂を長さ2の経路〈a₁,f,a₂〉に移す。

ここで、与えられたグラフGからある圏Bの基底グラフU(B)への他の写像D：G→U(B)を考える。U(D')∘P=Dとなる関手D'：C→Bが存在するなら、D'は対象についてD'〈a〉=D(a)であり、射についてD'〈a₁,f₁,a₂〉=D(f₁)である。長さ2以上の任意の経路はCにおける上記の射の合成なので、D'〈a₁,f₁,…f_n-1,a_n〉=D(f_n-1)∘D(f_n-2)∘…∘D(f₁)でなければならない。

逆に、このようなDがあれば図式を可換にするような関手D'が定義される。

自由圏の例

∂₀f=∂₁fの射f一つのみからなるグラフから生成された自由圏は恒等射id,および f, f∘f=f², f∘f∘f=f³,…からなる。
∂₀f≠∂₁fの射一つのみからなるグラフから生成された自由圏は恒等射id、およびfのみからなる。
2つの対象a,bとf：a→bとg：b→aからなるグラフから生成された自由圏の射はid_a, id_b, f, g, fg, gf, gfg, fgf, gfgf, fg fg,…からなる。
3つの対象からなるグラフ・→・→・は、以下の可換図式で表される3つの射と3つの恒等射を持つ自由圏となる。

・ ↺	→ f	・ ↺
	g∘f↘	↓g
		・ ↺

1つの対象とn個の射f₁,f₂,…,f_n（∂₀f_i=∂₁f_i）を持つグラフから生成された自由圏の射の集合は文字をn個持つ自由モノイドと一致する。例1は文字が一つの自由モノイドと言える。
ひらがなを対象、単語の集合を射、単語の先頭の文字をドメイン、単語の終わりの文字をコドメインとすると自由圏を成す。これをしりとりの圏という。しりとりは身近な圏の一つである。