而して

ノートとかメモとか。

Setsのcoequalizer (Awodey, 3.5.11)

Reference. Awodey, S. (2010) Category Theory, Oxford: Oxford University Press, 2nd ed. 2011.

概要

集合 R から生成する最小の同値関係を \langle R \rangle とかく. f, g:A \rightrightarrows B のcoequalizerが, R \triangleq \{ x \in A; f(x) = g(x) \} とするとき B \overset{\pi}{\twoheadrightarrow} B / \langle R \rangle であることを示せ.

R を包む最小の同値関係 \langle R \rangle

問にはさらに, この \langle R \rangle を

\langle R \rangle \triangleq \bigcap \{ C \in B \times B; C\text{ is eq.rel. on }B\,\&\,C \supseteq R \}

と定めよ, とある. これは確かに, R を包む B 上の同値関係であって, かつそのなかで最小の集合である. このことを示しておく.

同値関係であること.

反射律. 任意に x \in B をとる. いま任意に, R を包む B 上の同値関係 C をとると, C の反射律から (x,x) \in C となるから (x,x) \in \langle R \rangle.

対称律. (x,y) \in \langle R \rangle をとれば, 任意の C について (x,y) \in C となって, C の対称律から (y,x) \in C となる. C は任意だったから (y,x) \in \langle R \rangle.

推移律. 対称律と同様.

R を包むこと. x \in R とすれば, 任意の C について x \in R \subseteq C より x \in C. C は任意だったから x \in \langle R \rangle.

最小であること. 任意に C をとれば, \langle R \rangle の定義から \langle R \rangle \subseteq C.

よって示せた. しかしこの定義は今回の問で使いにくいと思うので, より構造の分かりやすいやり方でこの「最小の同値関係」を定めるのがよいだろう. すなわち, \Delta_B \triangleq \{ (b,b); b\in B \}, かつ

F(X) \triangleq \underline{\{ (y,x); (x,y) \in X \}}_{(1)} \cup \underline{\{ (x,z); (x,y), (y,z) \in X \}}_{(2)}

として \langle R \rangle' \triangleq \bigcup _ {n \in \omega} F^n (R \cup \Delta_B) とする.

同値関係であること.

反射律. 任意に x \in B をとれば (x,x) \in R \cup \Delta_B \subseteq \langle R \rangle'.

対称律. (x,y) \in \langle R \rangle' をとれば, ある n があって (x,y) \in F^n (R \cup \Delta_B) となるので, (1)より (y,x) \in F^{n+1} (R \cup \Delta_B) \subseteq \langle R \rangle'.

推移律. 対称律と同様.

R を包むこと. R \subseteq R \cup \Delta_B \subseteq \langle R \rangle' 故.

最小であること. いま任意に R を包む B 上の同値関係 C をとるとき, 任意の n について

F^n(R \cup \Delta_B) \subseteq C

となることを示せば十分. 帰納法で示す. n = 0 なら明らか. (x,y) \in F^{n+1}(R \cup \Delta_B) をとるとき,

(x,y) が F(F^n(R \cup \Delta_B)) の (1)由来なら (y,x) \in F^n(R\cup\Delta_B) \subseteq C で, C の対称律から (x,y) \in C.

(x,y) が (2)由来としても同様.

よって示せた. なお, \langle R \rangle と \langle R \rangle' は同じ集合となる（最小性から, \langle R \rangle は \langle R \rangle' よりも小さいので \langle R \rangle \subseteq \langle R \rangle', 逆も同様）. 以下, \langle R \rangle' を \langle R \rangle とかく.

（ところで,

F(X) \triangleq \Delta_B \cup \{ (y,x); (x,y) \in X \} \cup \{ (x,z); (x,y), (y,z) \in X \}

として \langle R \rangle' \triangleq \bigcup _ {n \in \omega} F^n (R) としてもよい. Why?）

解答

\pi f = \pi g はたやすい（こうなるように作ったのだから）. あとは A \rightrightarrows B \overset{\varphi}{\rightarrow} S, \varphi f = \varphi g なる \varphi をとるとき \varphi = \psi \pi と一意に分解できることを示せばよい. これには, \psi: \lbrack z \rbrack \mapsto \varphi z と定めればよいが, この \psi がwell-definedであることを示す部分が問題である. すなわち, x, y \in \lbrack z \rbrack について x \neq y でも \varphi(x) = \varphi(y) か？

ここで先の \langle R \rangle の帰納的な定義が活きてくる. (x,y) \in \langle R \rangle \Longrightarrow \varphi(x) = \varphi(y) をいうのに, \forall n \in \omega. (x,y) \in F^n (R \cup \Delta_B) \Longrightarrow \varphi(x) = \varphi(y) をいえば十分だからである.

n の帰納法. n = 0 のとき, (x,y) \in \Delta_B なら自明で, (x,y) \in R なら, 定義からある a \in A がとれて x = f(a), y = g(a) となって, \varphi(x) = \varphi(f(a)) = \varphi(g(a)) = \varphi(y) を得る. (x,y) \in F^{n+1}(R \cup \Delta_B) をとる. (x,y) が (1)由来なら (y,x) \in F^n(R\cup \Delta_B) ゆえ \varphi(y) = \varphi(x). (2)由来なら, ある z がとれて (x,z), (z,y) \in F^n(R \cup \Delta_B) となり \varphi(x) = \varphi(z) = \varphi(y).

一意性は, かかる分解 \varphi = \psi \pi = \psi' \pi があれば \psi(\lbrack z \rbrack) = \psi\pi(z) = \psi' \pi(z) = \psi' (\lbrack z \rbrack) ゆえ \psi = \psi', と示せる.