空から毛がはえた

グラフの圏における冪対象

グラフの圏の対象はグラフである。 $A$ をエッジ1つの対象、 $D$ をノード1つの対象とする。この圏における冪対象 $A^{A}$ , $A^{D}$ , $D^{A}$ , $D^{D}$ はそれぞれどんなグラフだろうか?

$A^{A}$ の形

グラフ $X$ がどんな形をしているかを調べるためには、まず、射 $D \to X$ , 射 $A \to X$ がそれぞれ何個あるかを調べる。また、グラフの圏における終対象 $1$ はノード1つエッジ(ループ)1つのグラフなので、射 $1 \to X$ の個数が $X$ が持つループの個数になる。

冪対象の定義から、以下の一対一対応が成り立つ。

$\frac{D \to A^{A}}{A \times D \to A}$ , $\frac{A \to A^{A}}{A \times A \to A}$

下側の射のdomainは以下のようになる。

$A \times D \simeq 2D$ , $A \times A \simeq 2D + A$

$2D \to A$ は4個ある。 $2D+A \to A$ も4個ある。また $A \to A$ は1個あるので、ループ $1 \to A^{A}$ は1個ある。よって、 $A^{A}$ は4個のノード、4個のエッジ(そのうち1つはループ)のグラフであることがわかる。

$A^{A}$ の4個のエッジ(射 $A \times A \to A$ )を $a1$ , $a2$ , $a3$ , $a4$ と書こう。

以下のように、 $A$ のsourceを0, targetを1と書く。 f:id:yabaniyatun:20190211185547p:plain

$A \times A$ は以下のようになる。

f:id:yabaniyatun:20190211185733p:plain

4個のエッジを以下のように定義する。

$ai(0, 0) = 0 (i=1, 2, 3, 4)$

$ai(1, 1) = 1 (i=1, 2, 3, 4)$

$a1(0, 1) = 0$

$a1(0, 1) = 0$

$a2(0, 1) = 0$

$a2(1, 0) = 1$

$a3(0, 1) = 1$

$a3(1, 0) = 0$

$a4(0, 1) = 1$

$a4(1, 0) = 1$

ここで以下の2つの射を考える。

$1_{A} \times s: A \times D \to A \times A$

$1_{A} \times t: A \times D \to A \times A$

$s$ はノードをエッジのsourceに移す射であり、 $t$ はノードをエッジのtargetに移す射とする。

$A \times D \simeq 2D = \{0, 1\}$ と書くと、以下が成り立つ。

$1_{A} \times s (0) = (0, 0)$

$1{_A} \times s (1) = (1, 0)$

$1_{A} \times t (0) = (0, 1)$

$1_{A} \times t (1) = (1, 1)$

これらと $a1$ , $a2$ , $a3$ $a4$ を合成することで、 $A^{A}$ の形を調べる。

まず、 $a1$ と合成する。

$a1 \circ (1_{A} \times s) (0) = 0$

$a1 \circ (1_{A} \times s) (1) = 0$

$a1 \circ (1_{A} \times t) (0) = 0$

$a1 \circ (1_{A} \times t) (1) = 1$

よって、エッジ $a1$ は以下のような形をしている。

f:id:yabaniyatun:20190211191853p:plain

次に $a2$ と合成する。

$a2 \circ (1_{A} \times s) (0) = 0$

$a2 \circ (1_{A} \times s) (1) = 1$

$a2 \circ (1_{A} \times t) (0) = 0$

$a2 \circ (1_{A} \times t) (1) = 1$

よって、エッジ $a2$ は以下のような形をしている。

f:id:yabaniyatun:20190211192239p:plain

続いて $a3$ と合成する。

$a3 \circ (1_{A} \times s) (0) = 0$

$a3 \circ (1_{A} \times s) (1) = 0$

$a3 \circ (1_{A} \times t) (0) = 1$

$a3 \circ (1_{A} \times t) (1) = 1$

よって、エッジ $a3$ は以下のような形をしている。

f:id:yabaniyatun:20190211192522p:plain

最後に $a4$ と合成する。

$a4 \circ (1_{A} \times s) (0) = 0$

$a4 \circ (1_{A} \times s) (1) = 1$

$a4 \circ (1_{A} \times t) (0) = 1$

$a4 \circ (1_{A} \times t) (1) = 1$

よって、エッジ $a4$ は以下のような形をしている。

f:id:yabaniyatun:20190211192737p:plain

以上より、グラフ $A^{A}$ は以下の形をしていることがわかった。

f:id:yabaniyatun:20190211193340p:plain

同様にして他のグラフの形もわかる。

$A^{D}$ の形

f:id:yabaniyatun:20190211193904p:plain

$D^{A}$ の形

f:id:yabaniyatun:20190211194041p:plain

$D^{D}$ の形

f:id:yabaniyatun:20190211194153p:plain