圏論の問題

引き戻しの構成　$\mathbf{FinSet}$（$\mathbf{Set}$ でも同じ）では、$f:A\to C$ と $g:B\to C$ の引き戻しは
$$P=\{(a,b)\in A\times B:f(a)=g(b)\}$$
で、$p_1,p_2$ は第 1・第 2 成分への射影である。したがって
$$|P|=\sum _{c\in C}|f^{-1}(c)|\cdot |g^{-1}(c)|$$

各ファイバーの大きさを求める。

• $f^{-1}(0)=\{3,6,9\}$, $f^{-1}(1)=\{1,4,7,10\}$, $f^{-1}(2)=\{2,5,8\}$ より、大きさは $3,4,3$。
• $b$ が $3$ の倍数なら $b^2\equiv 0$、そうでなければ $b\equiv \pm 1$ より $b^2\equiv 1(\mathrm{mod}3)$。よって $g^{-1}(0)=\{3,6,9\}$（$3$ 個）、$g^{-1}(1)$ は残りの $7$ 個、$g^{-1}(2)=\varnothing$（$0$ 個）。

したがって
$$|P|=3\cdot 3+4\cdot 7+3\cdot 0=9+28+0=37$$

押し出しの構成　スパン $A\stackrel{p_1}{\leftarrow }P\stackrel{p_2}{\to }B$ の押し出しは、直和 $A\bigsqcup B$ を、各 $(a,b)\in P$ について $a\sim b$ となる最小の同値関係で割った商集合
$$Q=(A\bigsqcup B)/\sim$$
である。$A\bigsqcup B$ の元を頂点とし、$(a,b)\in P$ ごとに $a$ と $b$ を辺で結んだグラフを考えると、$Q$ の元はこのグラフの連結成分と 1 対 1 に対応する。

辺 $(a,b)$ は $f(a)=g(b)$ のときに限り引かれるので、$c\in C$ ごとに $f^{-1}(c)\bigsqcup g^{-1}(c)$ の部分を調べればよい（異なる $c$ の間に辺はない）。

• $c=0$: $f^{-1}(0)$ の $3$ 個と $g^{-1}(0)$ の $3$ 個はすべての組が辺で結ばれる（完全 2 部グラフ）ので、連結成分は $1$ 個。
• $c=1$: 同様に $4$ 個と $7$ 個の完全 2 部グラフで、連結成分は $1$ 個。
• $c=2$: $g^{-1}(2)=\varnothing$ なので $f^{-1}(2)=\{2,5,8\}$ の各元には辺がなく、それぞれが 1 点だけの連結成分となり、$3$ 個。

よって
$$|Q|=1+1+3=5$$

答え: $(|P|,|Q|)=(37,5)$

$P=\{(a,b)\in A\times B\mid f(a)=g(b)\}$。

$f$ のファイバーの大きさ：余り 0 は $\{3,6,9\}$ で 3 個、余り 1 は $\{1,4,7,10\}$ で 4 個、余り 2 は $\{2,5,8\}$ で 3 個。
$g$ のファイバーの大きさ：$b\equiv 0$ なら $b^2\equiv 0$（$b=3,6,9$ の 3 個）、$b\not\equiv 0$ なら $b^2\equiv 1$（残り 7 個）、$b^2\equiv 2$ となる $b$ はない。よって $g^{-1}(0)$ は 3 個、$g^{-1}(1)$ は 7 個、$g^{-1}(2)$ は 0 個。

$|P|=3\cdot 3+4\cdot 7+3\cdot 0=9+28=37$。

$\mathbf{FinSet}$ でのスパンの押し出しは、非交和 $A\bigsqcup B$ を、各 $x\in P$ について $p_1(x)\sim p_2(x)$ で生成される同値関係で割った商集合である。したがって $Q$ の要素数は、$A\bigsqcup B$ を頂点、$P$ の各要素 $(a,b)$ を $a$ と $b$ を結ぶ辺とする二部グラフの連結成分の個数に等しい。

• 余り 0 の部分：$A$ の 3 個と $B$ の 3 個の間に全結合の辺があるので連結成分 1 個。
• 余り 1 の部分：$A$ の 4 個と $B$ の 7 個の間に全結合の辺があるので連結成分 1 個。
• 余り 2 の部分：$B$ 側に要素がないので辺がなく、$A$ の 3 個の要素がそれぞれ単独の成分（3 個）。

異なる余りの部分の間には辺がない。よって $|Q|=1+1+3=5$。

検算：$|A|+|B|=20$ 個の頂点のうち、成分は {6 個}, {11 個}, {1 個}×3 で合計 $6+11+3=20$。一致する。

答えは $(37,5)$。