CategoryTheory_圏論勉強会ノート

CategoryTheory:圏論勉強会ノート

宿題の回答など説明が長くなるものをこのページに書きます。

グラフの圏 Graphで、X×X＝Xを満たすXを求める

有限なグラフに限れば、以下の3通り。

• 何もないグラフ
• 点が1つだけのグラフ
• ループが1つだけのグラフ

【証明】

• 関手 A, D: Graph → Set を定める。(Setは集合の圏）
  • 任意の対象 X について、A(X) は X の矢印部分の集合を、D(X)はXの点の部分の集合を指す。
  • 任意の X ∈ Graph に対して、Set内の射 s, t: A(X) → D(X) が常に、たかだか2つだけ存在する。
• Graph の object X, Y について、X × Y が存在する とは、下記2条件がともに成り立つことと同義とみなせる：
  • A(X×Y) ＝ A(X) × A(Y)
  • D(X×Y) ＝ D(X) × D(Y)
• X×X＝X となる object X を仮定すると、
  • A(X×X)＝A(X)×A(X)＝A(X)
  • D(X×X)＝D(X)×D(X)＝D(X)
• A(X), D(X) ∈ Set であり、かつ Set の対象で X × X ＝ X を満たす X は（有限集合なら） 0 と 1しかない。
  • ∴ A(X)、D(X)＝ 0 or 1
• 以上のA(X)とD(X)の組み合わせのうち、正しく s, t が定義できるのは次の3通り
  • (A(X), D(X)) |→ (0, 0)
    • … Xは、何もないグラフ
  • (A(X), D(X)) |→ (0, 1)
    • … Xは、点が1つだけのグラフ
  • (A(X), D(X)) |→ (1, 1)
    • … Xは、ループが1つだけのグラフ

Test 5 の 1 (P.301)

11通り。

• http://www.osk.3web.ne.jp/~usitukai/images/kenron060709/DSCN0151.JPG
• 考え方
  • 2つのarrow A, A’ とそれぞれをドメインとする射 s, t, s’, t’ を考える。
    • s＝t, s’＝t’の場合、それぞれがくっついてるか離れてるかで2通り。
    • s＝t, s’≠t’の場合、s = s’, s = t’, とそのどちらでもないのと3通り。
    • s≠t, s’≠t’の場合、
      • 2つの点を共有する場合、s = s’ と s = t’ の2通り。
      • 1点だけ共有する場合、s = s’ と s = t’ と t = s’ の3通り。
      • 全く共有しない場合、1通り。

Test 5 の 2 (P.301)

D ＝ ［・］ , A ＝ ［・→・］ , I ＝ ［・→・→・］

I × I ＝ 2D + 2A + I

なんでかっていうと、I × I はこんなの

 ・　・　・
 　／　／
 ・　・　・
 　／　／
 ・　・　・

／ は斜め上向きの矢印。

Test 4 の 1 (P.300)

• B×C=1 であることから、任意のobject X と f:X→B に対して B×Cへの射 は!bxc : X → B×C は uniqueに存在する。
• productの性質から、p1: B×C→B は常に unique に存在して、p1 o !bxc = fが常に成り立つ。

以上から、任意のobject XからBへの射 f は必ず存在してunique。

よって B＝1。

Test 4 の 2 (P.300)

• • このcategoryにおいて、1 は loop 1個。
    • 1 → B＋D の数：1個
      • loopが対応するのは B の 先頭のところだけ
    • 1 → C の数：0個
      • loopが対応するのは どこにもない。
• • http://www.osk.3web.ne.jp/~usitukai/images/kenron060709/DSCN0148.JPG
• • http://www.osk.3web.ne.jp/~usitukai/images/kenron060709/DSCN0149.JPG

Test 3 の 3 (P.299)

後で書く。

Session 26 Exercise1 (P.280)

• f: X -> A, g: X -> B から定まる X -> A×B の射を <f,g>（横ベクトルのつもり）
• f: A -> X, g: B -> X から定まる A＋B -> X の射を [f,g]（縦ベクトルのつもり）
• a: A -> A, b: A -> B, c: B -> A, d: B -> B から定まる A＋B -> A×B の射を {a,b,c,d}（２×２行列のつもり）
• identity map {1,0,0,1} を I、その逆射をα（ie. I・α = α・I = id）
• A×B からの projection を p1,p2
• A＋B への injection を j1,j2

とする。

以下 domain,codomain を明記しないので適宜判断してください。

【１】

 [<a,b>,<c,d>] = <[a,c],[b,d]> = {a,b,c,d}

【２】

 {a,b,c,d}・p1 = <a b>
 {a,b,c,d}・p2 = <c d>
 j1・{a,b,c,d} = [a c]
 j2・{a,b,c,d} = [b d]

特に

 I・p1 = <1 0>
 I・p2 = <0 1>
 j1・I = [1 0]
 j2・I = [0 1]

【３】

 <f g>・h = <f・h g・h>
 h・[f g] = [h・f h・g]

【４】

 <f・p1  g・p2>・I = <f・p1・I  g・p2・I>（【３】より）
 = <f・[1 0]  g・[0 1]>（【２】より）
 = <[f・1 f・0]  [g・0 g・1]>（【３】より）
 = <[f 0]  [0 g]>（id と 0-map の性質）
 = {f 0 0 g}（【１】より）

 I・[j1・f  j2・g] = [I・j1・f  I・j2・g]（【３】より）
 = [<1 0>・f  <0 1>・g]（【２】より）
 = [<1・f 0・f>  <0・g 1・g>]（【３】より）
 = [<f 0> <0 g>]（id と 0-map の性質）
 = {f 0 0 g}（【１】より）

まとめて

 <f・p1  g・p2>・I = I・[j1・f  j2・g] = {f 0 0 g}（対角行列）

これは identity map が(×)関手と(＋)関手間の自然変換であることを示している。

【５】

 {f 0 0 1}・α・{1 0 0 g} = {f 0 0 1}・α・I・[j1 j2・g]（【４】より）
 = {f 0 0 1}・[j1 j2・g]（αは I の逆射）
 = [{f 0 0 1}・j1  {f 0 0 1}・j2・g]（【３】より）
 = [<f 0>  <0 1>・g]（【２】より）
 = [<f 0>  <0・g 1・g>]（【３】より）
 = [<f 0> <0 g>]（id と 0-map の性質）
 = {f 0 0 g}（【１】より）

同様に

 {1 0 0 g}・α・{f 0 0 1} = {f 0 0 g}

まとめて

 {f 0 0 1}・α・{1 0 0 g} = {1 0 0 g}・α・{f 0 0 1} = {f 0 0 g}

【６】

 f1: X -> A, g1: A -> C, f1: X -> B, g2: B -> D に対して
 <g1・f1 g2・f2>: X -> C×D を X -> A×B -> C×D で分解して考えると
 
 <g1・f1 g2・f2> = <g1・p1 g2・p2>・<f1 f2>
 = {g1 0 0 g2}・α・<f1 f2>（【４】より）

同様に

 f1: C -> A, g1: A -> X, f1: D -> B, g2: B -> X に対して
 
 [g1・f1 g2・f2] = [g1 g2]・[j1・f1 j2・f2]
 = [g1 g2]・α・{f1 0 0 f2}（【４】より）

【７】

 f + g = [g 1]・α・<1 f>（定義）
 = ([1 1]・α・{g 0 0 1})・α・({1 0 0 f}・α・<1 1>)（【６】より）
 = [1 1]・α・({g 0 0 1}・α・{1 0 0 f})・α・<1 1>（結合律）
 = [1 1]・α・({1 0 0 f}・α・{g 0 0 1})・α・<1 1>（【５】より）
 = ([1 1]・α・{1 0 0 f})・α・({g 0 0 1}・α・<1 1>)（結合律）
 = [1 f]・α・<g 1>（【６】より）
 = [f 1]・α・<1 g>（図式をひっくり返して眺めてみると）
 = g + f（定義）

つまり f+g = g+f

【Exercise1 の証明】

{g1 g2 g3 g4}・α・{f1 f3 f2 f4} の(1,1)成分である [g1 g2]・α・<f1 f2> を変形する。

 [g1 g2]・α・<f1 f2> = ([g1 1]・α・{1 0 0 g2})・α・({f1 0 0 1}・α・<1 f2>)（【６】より）
 = [g1 1]・α・({1 0 0 g2}・α・{f1 0 0 1})・α・<1 f2>（結合律）
 = [g1 1]・α・({f1 0 0 1}・α・{1 0 0 g2})・α・<1 f2>（【５】より）
 = ([g1 1]・α・{f1 0 0 1})・α・({1 0 0 g2}・α・<1 f2>)（結合律）
 = [g1・f1 1]・α・<1 g2・f2>（【６】より）
 = g2・f2 + g1・f1（定義）
 = g1・f1 + g2・f2（【７】より）

Temperley-Lieb Algebraのtrace

U_i1・U_i2・U_i3・… の trace を計算する Haskellプログラム

n はドット数（テキストでは３）、xs は U_i1・U_i2・U_i3・… を表現するリスト [i1,i2,i3,…]

 trace n xs = n' + c  where
   (_,(n',c)) = until (null.fst) f (xs,(n,0))
   f (xs,(m,c)) = ([low..m-2]++xs',(m-1, if low==m then c'+1 else c'))  where
     (xs',low,c') = foldl g ([],m,c) xs
     g (xs,low,c) x
       | x < low-1 = (x:xs,           low, c)
       | x > low+1 = ([low..x-2]++xs, x,   c+1)
       | otherwise = (xs,             x,   if (x==low) then c+1 else c)
 {-
 -- The Ear
 > trace 3 [1,2]
 1
 -- Unit
 > trace 3 []
 3
 -}

Last modified : 2008/06/18 17:21:08 JST