§E1.3同値関係と商

証明.(1)同値類の定義により、$a\in[b]$であることは$a\sim b$であることにほかならない。

(2)必要性を示す。$[a]=[b]$とする。反射律により$a\in[a]$であるから$a\in[b]$であり、(1)により$a\sim b$である。十分性を示す。$a\sim b$とする。$y\in[a]$をとると$y\sim a$であり、推移律により$y\sim b$であるから$y\in[b]$である。よって$[a]\subseteq[b]$である。対称律により$b\sim a$であるから、同じ議論により$[b]\subseteq[a]$である。外延性により$[a]=[b]$である。

(3)$c\in[a]\cap[b]$をとる。(1)により$c\sim a$かつ$c\sim b$である。対称律により$a\sim c$であり、推移律により$a\sim b$であるから、(2)により$[a]=[b]$である。したがって、$[a]\neq[b]$である二つの同値類については$[a]\cap[b]=\emptyset$である。▨

証明.$a\in A$をとる。定義 3.1 条件 (c)により$a\in\bigcup_{P\in\mathcal P}P$であるから、$a\in P$を満たす$P\in\mathcal P$が存在する。$P,Q\in\mathcal P$が$P\cap Q\neq\emptyset$を満たすとすると、定義 3.1 条件 (b)の対偶により$P=Q$である。とくに$a\in P$かつ$a\in Q$を満たす$P,Q\in\mathcal P$に対しては$a\in P\cap Q$であるから$P=Q$であり、$a$を含むブロックは一つに限る。▨

証明.(1)$A/R$の元は同値類であり、同値類は$A$の部分集合であるから、$A/R$は$A$の部分集合を元とする集合である。同値類は空でないので定義 3.1 条件 (a)が成り立つ。相異なる二つの同値類は補題 2.2 (3)により互いに素であるから定義 3.1 条件 (b)が成り立つ。各同値類は$A$の部分集合であるから$\bigcup_{C\in A/R}C\subseteq A$であり、任意の$a\in A$に対して$a\in[a]_R\in A/R$であるから$A\subseteq\bigcup_{C\in A/R}C$である。外延性により定義 3.1 条件 (c)が成り立つ。

(2)$a\in A$をとると、命題 3.2により$a\in P$を満たす$P\in\mathcal P$が存在するので$(a,a)\in R_{\mathcal P}$であり、反射律が成り立つ。$R_{\mathcal P}$の定義条件は$a$と$b$について対称であるから、対称律が成り立つ。$(a,b)\in R_{\mathcal P}$かつ$(b,c)\in R_{\mathcal P}$とすると、$a,b\in P$を満たす$P\in\mathcal P$と$b,c\in Q$を満たす$Q\in\mathcal P$が存在する。$b\in P\cap Q$であるから命題 3.2により$P=Q$であり、$a,c\in P$であるから$(a,c)\in R_{\mathcal P}$である。よって推移律が成り立つ。

(3)$R\in\operatorname{Eq}(A)$をとる。$(a,b)\in R_{A/R}$とすると、$a,b\in C$を満たす$C\in A/R$が存在する。$C=[c]_R$を満たす$c\in A$をとると補題 2.2 (1)により$a\mathrel{R}c$かつ$b\mathrel{R}c$であり、対称律と推移律により$a\mathrel{R}b$である。逆に$a\mathrel{R}b$とすると、反射律により$a\in[a]_R$であり、対称律により$b\mathrel{R}a$であるから$b\in[a]_R$である。$[a]_R\in A/R$であるから$(a,b)\in R_{A/R}$である。外延性により$R_{A/R}=R$である。

$\mathcal P\in\operatorname{Part}(A)$をとる。$a\in A$に対して、命題 3.2により$a$を含む唯一のブロックを$P_a\in\mathcal P$と書く。$b\in[a]_{R_{\mathcal P}}$であることは$(b,a)\in R_{\mathcal P}$であること、すなわち$a\in P$かつ$b\in P$を満たす$P\in\mathcal P$が存在することであり、$a$を含むブロックは$P_a$に限るので、これは$b\in P_a$であることと同値である。外延性により$[a]_{R_{\mathcal P}}=P_a$である。したがって$A/R_{\mathcal P}=\{\,P_a\mid a\in A\,\}$であり、各$P_a$は$\mathcal P$の元であるから$A/R_{\mathcal P}\subseteq\mathcal P$である。逆に$P\in\mathcal P$をとると、定義 3.1 条件 (a)により$a\in P$を満たす$a$が存在し、$a$を含むブロックの一意性から$P=P_a=[a]_{R_{\mathcal P}}\in A/R_{\mathcal P}$である。外延性により$A/R_{\mathcal P}=\mathcal P$である。

(4)(1)により$R\mapsto A/R$は$\operatorname{Eq}(A)$から$\operatorname{Part}(A)$への写像であり、(2)により$\mathcal P\mapsto R_{\mathcal P}$は$\operatorname{Part}(A)$から$\operatorname{Eq}(A)$への写像である。(3)により、この二つの写像は両方向の合成がそれぞれの恒等写像に等しい。よって$R\mapsto A/R$は全単射であり、その逆写像が$\mathcal P\mapsto R_{\mathcal P}$である。▨

証明.(1)$C\in X/{\sim}$をとる。商集合の定義により$C=[x]$を満たす$x\in X$が存在する。$C=[x']$を満たす$x'\in X$に対しては、補題 2.2 (2)により$x\sim x'$であるから、仮定により$u(x)=u(x')$である。よって

は、$X/{\sim}$の各元$C$に対してちょうど一つの$z\in Z$を含む。定義域を$X/{\sim}$、終域を$Z$、グラフを$\Gamma$とする写像を$\overline u$と書くと、$\overline u([x])=u(x)$である。$\pi(x)=[x]$であるから、任意の$x\in X$に対して$(\overline u\circ\pi)(x)=u(x)$であり、写像の外延性（§E1.1 命題 1.3 (1)）により$\overline u\circ\pi=u$である。

写像$w\colon X/{\sim}\to Z$も$w\circ\pi=u$を満たすとする。$C\in X/{\sim}$に対して$C=\pi(x)$を満たす$x\in X$をとると

である。二つの写像は定義域も終域も一致するので、写像の外延性により$w=\overline u$である。

(2)$x\sim x'$とする。補題 2.2 (2)により$[x]=[x']$であるから$\pi(x)=\pi(x')$であり、

である。▨

証明.(1)任意の$(x,y)\in X\times Y$に対して$x\sim_X x$かつ$y\sim_Y y$であるから、反射律が成り立つ。$\sim_{X\times Y}$の定義条件は二つの成分についての条件の連言であるから、$\sim_X$と$\sim_Y$の対称律を成分ごとに用いて対称律が、推移律を成分ごとに用いて推移律が従う。

(2)写像$p\colon X\times Y\to(X/{\sim_X})\times(Y/{\sim_Y})$を$p(x,y)=([x],[y])$によって定める。$(x,y)\sim_{X\times Y}(x',y')$とすると$x\sim_X x'$かつ$y\sim_Y y'$であり、補題 2.2 (2)により$[x]=[x']$かつ$[y]=[y']$であるから、$p(x,y)=p(x',y')$である。$\sim_{X\times Y}$による標準全射は$(x,y)\mapsto[(x,y)]$であるから、定理 4.1 (1)により、$\theta([(x,y)])=p(x,y)$を任意の$(x,y)\in X\times Y$に対して満たす写像$\theta$がただ一つ存在する。

$\theta$が単射であることを示す。$\theta([(x,y)])=\theta([(x',y')])$とすると$[x]=[x']$かつ$[y]=[y']$であり、補題 2.2 (2)により$x\sim_X x'$かつ$y\sim_Y y'$であるから$(x,y)\sim_{X\times Y}(x',y')$であり、ふたたび補題 2.2 (2)により$[(x,y)]=[(x',y')]$である。$(X\times Y)/{\sim_{X\times Y}}$の元は$[(x,y)]$の形のものに限るから、$\theta$は単射である。

$\theta$が全射であることを示す。$(C,D)\in(X/{\sim_X})\times(Y/{\sim_Y})$をとると、商集合の定義により$C=[x]$を満たす$x\in X$と$D=[y]$を満たす$y\in Y$が存在し、$\theta([(x,y)])=([x],[y])=(C,D)$である。▨

証明.(1)$\Rightarrow$(2)$\sim_X$と$\sim_Y$の積の同値関係を$\sim_{X\times Y}$と書き、命題 4.3 (2)の全単射を$\theta$と書く。(1)は、$(x,y)\sim_{X\times Y}(x',y')$を満たす任意の$(x,y),(x',y')\in X\times Y$に対して$F(x,y)=F(x',y')$であることにほかならない。よって定理 4.1 (1)により、$F_0([(x,y)])=F(x,y)$を任意の$(x,y)\in X\times Y$に対して満たす写像$F_0\colon(X\times Y)/{\sim_{X\times Y}}\to Z$がただ一つ存在する。$\theta$の逆写像$\theta^{-1}$（§E1.1 命題 3.8）を用いて$\overline F=F_0\circ\theta^{-1}$とおく。$\theta([(x,y)])=([x],[y])$であるから$\theta^{-1}([x],[y])=[(x,y)]$であり、

である。

(2)$\Rightarrow$(3)$\overline F$を(2)の写像とし、$y\in Y$をとり、$x\sim_X x'$を満たす$x,x'\in X$をとる。補題 2.2 (2)により$[x]=[x']$であるから

である。第二変数についても、$y\sim_Y y'$から$[y]=[y']$を得て同じ計算を行う。

(3)$\Rightarrow$(1)$x\sim_X x'$かつ$y\sim_Y y'$とする。(3)の前半を$y$について適用すると$F(x,y)=F(x',y)$であり、後半を$x'$について適用すると$F(x',y)=F(x',y')$である。よって$F(x,y)=F(x',y')$である。

写像$\overline G\colon(X/{\sim_X})\times(Y/{\sim_Y})\to Z$も(2)の等式を満たすとする。$\theta$は命題 4.3 (2)により全射であるから、$(X/{\sim_X})\times(Y/{\sim_Y})$の任意の元は$([x],[y])$の形をもち、そこでの$\overline G$と$\overline F$の値はいずれも$F(x,y)$である。二つの写像は定義域も終域も一致するので、写像の外延性（§E1.1 命題 1.3 (1)）により$\overline G=\overline F$である。▨