宿題の回答など説明が長くなるものをこのページに書きます。
有限なグラフに限れば、以下の3通り。
【証明】
11通り。
D ＝ ［・］ , A ＝ ［・→・］ , I ＝ ［・→・→・］
I × I ＝ 2D + 2A + I
なんでかっていうと、I × I はこんなの
・ ・ ・ ／ ／ ・ ・ ・ ／ ／ ・ ・ ・
／ は斜め上向きの矢印。
以上から、任意のobject XからBへの射 f は必ず存在してunique。
よって B＝1。
後で書く。
とする。
以下 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（【７】より）
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
-}