圏論の問題

余等化子の具体形. $\mathbf{FinSet}$ において $f,g:B\rightrightarrows B$ の余等化子は、$B$ 上の関係 $\{(f(x),g(x))\mid x\in B\}$ が生成する同値関係（これを含む最小の同値関係）$\sim$ による商集合 $B/\sim$ と、商写像 $q:B\to B/\sim$ で与えられる。実際、写像 $h:B\to C$ が $h\circ f=h\circ g$ を満たすことは、すべての $x$ で $h(f(x))=h(g(x))$ となること、つまり「$h(y)=h(z)$」という同値関係が $\sim$ を含むこと、すなわち $h$ が $\sim$ の各同値類の上で一定であることと同値である。そのとき $u([y])=h(y)$ で $u$ がただ 1 つ定まり $h=u\circ q$ となる。$B/\sim$ は有限集合なので $\mathbf{FinSet}$ の対象でもある。

よって $|Q|$ は、$B$ の元を頂点とし、各 $x\in B$ について $f(x)$ と $g(x)$ を辺で結んだグラフの連結成分の個数に等しい。

関係を列挙する. $x=0,1,\dots ,19$ について $(f(x),g(x))$ を書き出すと
$$x=0\text{–}9:0\sim 0,2\sim 3,4\sim 6,6\sim 9,8\sim 12,10\sim 15,12\sim 18,14\sim 1,16\sim 4,18\sim 7,$$
$$x=10\text{–}19:0\sim 10,2\sim 13,4\sim 16,6\sim 19,8\sim 2,10\sim 5,12\sim 8,14\sim 11,16\sim 14,18\sim 17.$$
（$3$ と $20$ は互いに素なので $g$ は全単射であり、$B$ のすべての元が関係に現れる。）

連結成分を求める.
- $0$ を含む成分: $0\sim 10$, $10\sim 15$, $10\sim 5$ より $\{0,5,10,15\}$（$4$ 個）。
- $2$ を含む成分: $2\sim 3$, $2\sim 13$, $8\sim 2$, $8\sim 12$, $12\sim 18$, $18\sim 7$, $18\sim 17$ より $\{2,3,7,8,12,13,17,18\}$（$8$ 個）。
- $4$ を含む成分: $4\sim 6$, $4\sim 16$, $6\sim 9$, $6\sim 19$, $16\sim 14$, $14\sim 1$, $14\sim 11$ より $\{1,4,6,9,11,14,16,19\}$（$8$ 個）。

$4+8+8=20$ なので、$B$ のすべての元がこの 3 つのどれかに入る。

3 つが互いに別の類であること. $20$ は $5$ の倍数なので、$20$ で割った余りをとっても $5$ を法とした値は変わらず、
$$f(x)\equiv 2x,g(x)\equiv 3x\equiv -2x(\mathrm{mod}5)$$
である。したがって、どの関係 $f(x)\sim g(x)$ でも、両辺の $5$ を法とした値は符号を除いて等しい。よって「$y\mathrm{mod}5$ が $\{0\}$, $\{1,4\}$, $\{2,3\}$ のどれに入るか」は $\sim$ で保たれる。上の 3 つの成分はそれぞれ $\{0\}$, $\{2,3\}$, $\{1,4\}$ に対応するので（例えば $2$ の成分の元 $2,3,7,8,12,13,17,18$ を $5$ で割った余りはすべて $2$ か $3$）、互いに同値にならない。

結論. 同値類の個数は $3$ であり、$|Q|=3$。

FinSet における平行な射 $f,g:B\rightrightarrows B$ の余等化子は、$B$ を同値関係 $\sim$（$f(x)\sim g(x)$ ($x\in B$) から生成される最小の同値関係）で割った商集合 $B/\sim$ である。したがって $\{f(x),g(x)\}$ を辺とするグラフの連結成分の個数を数えればよい。

各 $x$ について $(f(x),g(x))=(2x\mathrm{mod}20,3x\mathrm{mod}20)$ を計算すると
$x=0:(0,0)$, $1:(2,3)$, $2:(4,6)$, $3:(6,9)$, $4:(8,12)$, $5:(10,15)$, $6:(12,18)$, $7:(14,1)$, $8:(16,4)$, $9:(18,7)$, $10:(0,10)$, $11:(2,13)$, $12:(4,16)$, $13:(6,19)$, $14:(8,2)$, $15:(10,5)$, $16:(12,8)$, $17:(14,11)$, $18:(16,14)$, $19:(18,17)$。

これらの辺で併合する。
- $2\sim 3$, $2\sim 13$, $8\sim 2$, $8\sim 12$, $12\sim 18$, $18\sim 7$, $19\sim$ではなく $18\sim 17$ より、$A=\{2,3,7,8,12,13,17,18\}$（8 元）。
- $4\sim 6$, $6\sim 9$, $6\sim 19$, $4\sim 16$, $16\sim 14$, $14\sim 1$, $14\sim 11$ より、$B_2=\{1,4,6,9,11,14,16,19\}$（8 元）。
- $0\sim 10$, $10\sim 15$, $10\sim 5$ より、$C=\{0,5,10,15\}$（4 元）。

$8+8+4=20$ で全元を尽くしており、$A,B_2,C$ の間を結ぶ辺はない（すべての辺を上で使い切っている）。よって連結成分は 3 個。

検算: 偶奇や $\mathrm{mod}5$ で見ると、$2x\equiv 3x(\mathrm{mod}5)$ の差 $x$ は $\mathrm{mod}5$ で保たれず、代わりに $f(x)-g(x)\equiv -x(\mathrm{mod}20)$ なので各辺は $\mathrm{mod}20$ で差 $x$ をもつ。$\gcd$ 的な不変量として $\mathrm{mod}5$ の類 $r$ に対し、$A$ は $\{2,3,2,3,2,3,2,3\}$、$B_2$ は $\{1,4,1,4,1,4,1,4\}$、$C$ は $\{0\}$ の剰余しかもたず、確かに 3 つに分かれている。

答え: $Q$ の元の個数は $3$。