関係としての写像
関係
集合$X,Y$に対して，直積$X\times Y$の部分集合を$X$から$Y$への（$2$項）関係という．また，$X$から$Y$への関係全体のなす集合を$\rel(X,Y)$で表わす：
$$
\rel(X,Y) \coloneqq \mathcal{P}(X \times Y).$$
集合$X$に対して，関係
$$
\Delta_{X} \coloneqq \{(x,x') \in X \times X \mid x=x'\} \in \rel(X,X)$$
を$X$上の等号関係という．
関係$R \in \rel(X,Y)$に対して，関係
$$
R^{\top} \coloneqq \{(y,x) \in Y \times X \mid (x,y) \in R\} \in \rel(Y,X)$$
を$R$の転置という．
明らかに$(R^{\top})^{\top} = R$が成り立つ．
関係$R \in \rel(X,Y),\, S \in \rel(Y,Z)$に対して，関係
$$
RS \coloneqq \{(x,z) \in X \times Z \mid \exists\,y \in Y,\ (x,y) \in R,\ (y,z) \in S\} \in \rel(X,Z)$$
を$R$と$S$との合成という．
明らかに$\Delta_{X}R = R = R\Delta_{Y}$が成り立つ．
任意の関係$R \in \rel(X,Y),\, S \in \rel(Y,Z)$に対して
$$
(RS)^{\top} = S^{\top}R^{\top} \in \rel(Z,X)$$
が成り立つ：
\begin{align}
(z,x) \in (RS)^{\top}
&\iff (x,z) \in RS \\
&\iff \exists\,y \in Y,\ (x,y) \in R,\ (y,z) \in S \\
&\iff \exists\,y \in Y,\ (z,y) \in S^{\top},\ (y,x) \in R^{\top} \\
&\iff (z,x) \in S^{\top}R^{\top}.
\end{align}
$R,R' \in \rel(X,Y),\,S,S' \in \rel(Y,Z)$とする．このとき，
$$
R \subset R',\ S \subset S' \implies RS \subset R'S'$$
が成り立つ：
$$
(x,z) \in RS \iff \exists\,y \in Y,\ (x,y) \in R,\ (y,z) \in S \implies \exists\,y \in Y,\ (x,y) \in R',\ (y,z) \in S' \iff (x,z) \in R'S'.$$
任意の関係$R \in \rel(X,Y),\, S \in \rel(Y,Z),\, T \in \rel(Z,W)$に対して
$$
R(ST) = (RS)T \in \rel(X,W)$$
が成り立つ：
\begin{align}
(x,w) \in R(ST)
&\iff \exists\, y \in Y,\ (x,y) \in R,\ (y,w) \in ST \\
&\iff \exists\,y \in Y,\ \exists\,z \in Z,\ (x,y) \in R,\ (y,z) \in S,\ (z,w) \in T \\
&\iff \exists\, z \in Z,\ (x,z) \in RS,\ (z,w) \in T \\
&\iff (x,w) \in (RS)T.
\end{align}
写像
写像の定義
$X,Y$を集合とする．関係$F \in \rel(X,Y)$が
$$
\Delta_{X} \subset FF^{\top},\ F^{\top}F \subset \Delta_{Y}$$
を満たすとき，組$f=(F,X,Y)$を始域$X$から終域$Y$への写像といい，$F$をそのグラフという．写像$f$の始域が$X$であり終域が$Y$であることを$f \colon X \to Y$で表わす．また，$X$から$Y$への写像全体のなす集合を$\map(X,Y)$で表わす．
$f = (F,X,Y)$を写像とする．このとき，任意の$x \in X$に対して，$y\in Y$であって$(x,y) \in F$なるものがただ一つ存在する：実際，
- 任意の$x \in X$に対して，$(x,x) \in FF^{\top}$より，$y \in Y$であって$(x,y) \in F$なるものが存在する．
- $(x,y),(x,y') \in F$とすると，
$$ (y,x) \in F^{\top},\ (x,y) \in F \quad\leadsto\quad (y,y') \in F^{\top}F \subset \Delta_{Y}$$
より，$y=y'$を得る．
そこで，この$y$を$f(x)$で表わす：
$$
f(x)=y \iff (x,y) \in F.$$
また，$f(x)=y$であることを$f\colon x \mapsto y$で表わす．
写像$\id_{X} \coloneqq (\Delta_{X},X,X)$を$X$上の恒等写像という：
$$
\id_{X}(x)=x.$$
写像$\varnothing_{Y} \coloneqq (\varnothing,\varnothing,Y)$を空写像という．
部分集合$A \subset X$に対して，写像
$$
\chi_{A} \coloneqq ((A \times \{1\}) \cup ((X \smallsetminus A) \times \{0\}),X,\{0,1\})$$
を$A$の指示函数という：
$$
\chi_{A}(x) = \begin{dcases}
1 & x \in A,\\
0 & x \notin A.
\end{dcases}$$
$f=(F,X,Y),\,g=(G,X,Y)$を写像とする．このとき次は同値である：
- $f=g;$
- $\forall\,x \in X,\ f(x)=g(x).$
(i)$\implies$(ii)
$$ f(x)=y \iff (x,y) \in F \iff (x,y) \in G \iff g(x)=y.$$
(ii)$\implies$(i)
$$ (x,y) \in F \iff f(x)=y \iff g(x)=y \iff (x,y) \in G.$$
写像の合成
$f=(F,X,Y),\, g=(G,Y,Z)$を写像とする．このとき，合成$FG$は$X$から$Z$への写像を定める（cf. id，compo-inv，compo-monotone，compo-assc）：
- $$ \Delta_{X} \subset FF^{\top} = (F\Delta_{Y})F^{\top} \subset (F(GG^{\top}))F^{\top} = ((FG)G^{\top})F^{\top} = (FG)(G^{\top}F^{\top}) = (FG)(FG)^{\top};$$
- $$ (FG)^{\top}(FG) = (G^{\top}F^{\top})(FG) = G^{\top}(F^{\top}(FG)) = G^{\top}((F^{\top}F)G) \subset G^{\top}(\Delta_{Y}G) = G^{\top}G \subset \Delta_{Z}.$$
写像$g \circ f \coloneqq (FG,X,Z)$を$f$と$g$との合成写像という．任意の$x \in X$に対して，
$$
\exists\,z \in Z,\ (x,z) \in FG \quad\leadsto\quad \exists\,y \in Y,\ (x,y) \in F,\ (y,z) \in G$$
より，
$$
(g \circ f)(x) = z = g(y) = g(f(x))$$
が成り立つ．
任意の写像$f \colon X \to Y$に対して
$$
f \circ \id_{X} = f = \id_{Y} \circ f$$
が成り立つ（cf. id）．
任意の写像$f \colon X \to Y,\, g \colon Y \to Z,\, h \colon Z \to W$に対して
$$
h \circ (g \circ f) = (h \circ g) \circ f$$
が成り立つ（cf. compo-assc）．
写像$f \colon X \to Y$に対して，写像$g \colon Y \to X$であって
$$
g \circ f = \id_{X},\ f \circ g = \id_{Y}$$
を満たすものが存在するとき，$f$を可逆写像といい，$g$を$f$の逆写像という．
逆写像は存在すれば一意である：実際，$g,h$が$f$の逆写像であるとすると，
$$
g = g \circ \id_{Y} = g \circ (f \circ h) = (g \circ f) \circ h = \id_{X} \circ h = h$$
が成り立つ．そこで可逆写像$f$に対してその逆写像を$f^{-1}$で表わす：
$$
f(x)=y \iff x=f^{-1}(y).$$
可逆写像$f$の逆写像もまた可逆であり
$$
(f^{-1})^{-1}=f$$
が成り立つ．
写像$f \colon X \to Y,\,g \colon Y \to Z$が可逆ならば，合成写像$g \circ f \colon X \to Z$も可逆であって
$$
(g \circ f)^{-1} = f^{-1} \circ g^{-1}$$
が成り立つ：実際，$h \coloneqq f^{-1} \circ g^{-1}$とおくと，
\begin{align}
h \circ (g \circ f) &= (h \circ g) \circ f = (f^{-1} \circ (g^{-1} \circ g)) \circ f = (f^{-1} \circ \id_{Y}) \circ f = f^{-1} \circ f = \id_{X};\\
(g \circ f) \circ h &= g \circ (f \circ h) = g \circ ((f \circ f^{-1}) \circ g^{-1}) = g \circ (\id_{Y} \circ g^{-1}) = g \circ g^{-1} = \id_{Z};
\end{align}
が成り立つので，逆写像の一意性より結論を得る．
写像の制限
$f=(F,X,Y)$を写像とし，$A \subset X$とする．このとき，関係
$$
F|_{A} \coloneqq F \cap (A \times Y)$$
は$A$から$Y$への写像を定める：
- $$ \Delta_{A} = \Delta_{X} \cap (A \times A) \subset (FF^{\top}) \cap (A \times A) = (F|_{A})(F|_{A})^{\top};$$
- $$ (F|_{A})^{\top}(F|_{A}) \subset F^{\top}F \subset \Delta_{Y}.$$
写像$f|_{A} \coloneqq (F|_{A},A,Y)$を$f$の$A$への制限という．
$f=(F,X,Y)$を写像とし，$B \subset Y$とする．このとき，
$$
f_{*}(X) \coloneqq \{y \in Y \mid (y,y) \in F^{\top}F\}=\{y \in Y \mid \exists\,x \in X,\ f(x)=y\} \subset B$$
が成り立つならば，$F \subset X \times B$であるから，関係$F \in \rel(X,B)$は$X$から$B$への写像を定める：
- $$ \Delta_{X} \subset FF^{\top};$$
- $$ F^{\top}F \subset \Delta_{Y} \cap (B \times B) = \Delta_{B}.$$
写像$f|^{B} \coloneqq (F,X,B)$を$f$の$B$への（余）制限という．
終域を重視しない立場では，$f|^{B}$と$f$とを区別しない（cf. eq）．
$A \subset X, B \subset Y$とする．写像$f \colon X \to Y$が$(f|_{A})_{*}(A) \subset B$を満たすとき，
$$
f|_{A}^{B} \coloneqq (f|_{A})|^{B} \colon A \to B$$
とおく．
全射・単射・双射
$f=(F,X,Y)$を写像とする．
- $\Delta_{Y} \subset F^{\top}F$が成り立つとき，$f$を全射という．
- $FF^{\top} \subset \Delta_{X}$が成り立つとき，$f$を単射という．
- $f^{\top} \coloneqq (F^{\top},Y,X)$が写像であるとき，$f$を双射という．
- $f$が全射であるためには，$Y \subset f_{*}(X)$，すなわち
$$ \forall\,y \in Y,\ \exists\, x\in X,\ f(x)=y$$
が成り立つことが必要かつ十分である． - $$
(x,x') \in FF^{\top} \iff \exists\, y \in Y,\ (x,y),(x',y) \in F \iff f(x)=f(x')$$
より，$f$が単射であるためには，
$$ f(x)=f(x') \implies x=x'$$
が成り立つことが必要かつ十分である． - $f$が双射であるためには，$f$が全射かつ単射であることが必要かつ十分である（cf. tt）．
任意の写像$f \colon X \to Y$に対して，$f_{*}(X) \subset Y$への余制限
$$
f|^{f_{*}(X)} \colon X \to f_{*}(X)$$
は全射である．
空写像$\varnothing_{Y} \colon \varnothing \to Y$は単射であり，$Y=\varnothing$ならば全射でもある．
全射の特徴づけ
写像$f=(F,X,Y)$が全射であるためには，任意の写像$g=(G,Y,Z),\, h=(H,Y,Z)$に対して
$$
g \circ f = h \circ f \implies g=h$$
が成り立つことが必要かつ十分である．
必要性
$$ FG=FH \implies G = \Delta_{Y}G = (F^{\top}F)G = F^{\top}(FG) = F^{\top}(FH) = (F^{\top}F)H = \Delta_{Y}H = H.$$
十分性
対偶を示す．そこで$f$が全射でないとして$b \in Y \smallsetminus f_{*}(X)$を取る．このとき，
$$
\forall\,x \in X,\ (\chi_{f_{*}(X)} \circ f)(x) = 1 = (\chi_{Y} \circ f)(x) \quad\leadsto\quad \chi_{f_{*}(X)} \circ f = \chi_{Y} \circ f$$
が成り立つが，
$$
\chi_{f_{*}(X)}(b) = 0 \neq 1 = \chi_{Y}(b) \quad\leadsto\quad \chi_{f_{*}(X)} \neq \chi_{Y}$$
となる．
任意の写像$f \colon X \to Y,\,g \colon Y \to Z$に対して，次が成り立つ：
- $f,g$が全射ならば，$g \circ f$も全射である；
- $g \circ f$が全射ならば，$g$は全射である．
- $$ h \circ (g \circ f) = k \circ (g \circ f) \implies (h \circ g) \circ f = (k \circ g) \circ f \implies h \circ g = k \circ g \implies h=k.$$
- $$ h \circ g = k \circ g \implies h \circ (g \circ f) = (h \circ g) \circ f = (k \circ g) \circ f = k \circ (g \circ f) \implies h=k.$$
写像$f \colon X \to Y$について，次は同値である：
- $f$は全射である；
- 写像$s \colon Y \to X$であって，$f\circ s = \id_{Y}$なるものが存在する．
(i)$\implies$(ii)
$f$の全射性より
$$
\forall\,y \in Y,\ f^{*}(y) \coloneqq \{x \in X \mid f(x)=y\} \neq \varnothing$$
であるから，写像$c \colon Y \to X$であって$c(y) \in f^{*}(y)$なるものが存在する（cf. ac）．そこで$s \coloneqq c$とおけば，任意の$y \in Y$に対して
$$
(f \circ s)(y) = f(c(y)) = y = \id_{Y}(y)$$
が成り立つ．
(ii)$\implies$(i)
$f \circ s = \id_{Y}$が全射なので，$f$は全射である．
単射の特徴づけ
写像$f=(F,X,Y)$が単射であるためには，任意の写像$g=(G,Z,X),\, h=(H,Z,X)$に対して
$$
f \circ g =f \circ h \implies g=h$$
が成り立つことが必要かつ十分である．
必要性
$$ GF=HF \implies G = G\Delta_{X} = G(FF^{\top}) = (GF)F^{\top} = (HF)F^{\top} = H(FF^{\top}) = H\Delta_{X} = H.$$
十分性
$X \neq \varnothing$としてよい（cf. empty-map）．
$f(x)=f(x')$とする．このとき，写像
$$
g \coloneqq (\{0\} \times \{x\},\{0\},X),\ h \coloneqq (\{0\} \times \{x'\},\{0\},X)$$
について
$$
(f \circ g)(0) = f(x) = f(x') = (f \circ h)(0)$$
より$g=h$が成り立つので，
$$
x=g(0)=h(0)=x'$$
を得る．
任意の写像$f \colon X \to Y,\,g \colon Y \to Z$に対して，次が成り立つ：
- $f,g$が単射ならば，$g \circ f$も単射である；
- $g \circ f$が単射ならば，$f$は単射である．
- $$ (g \circ f) \circ h = (g \circ f) \circ k \implies g \circ (f \circ h) = g \circ (f \circ k) \implies f \circ h = f \circ k \implies h=k.$$
- $$ f \circ h = f \circ k \implies (g \circ f) \circ h = g \circ (f \circ h) = g \circ (f \circ k) = (g \circ f) \circ k \implies h=k.$$
$X \neq \varnothing$のとき，写像$f=(F,X,Y)$について，次は同値である：
- $f$は単射である；
- 写像$r \colon Y \to X$であって，$r\circ f = \id_{X}$なるものが存在する．
(i)$\implies$(ii)
$a \in X$を取り
$$
R \coloneqq F^{\top} \sqcup ((Y \smallsetminus f_{*}(X)) \times \{a\}) \in \rel(Y,X)$$
とおく．
- まづ$r \coloneqq (R,Y,X)$が写像であることを示す：
- $y \in Y$とする．$x \in X$であって$f(x)=y$なるものが存在するときは$(y,x) \in F^{\top} \subset R$が成り立ち，そのような$x \in X$が存在しないときは$(y,a) \in R$が成り立つ．
- $(y,x),(y,x') \in R$とする．$y \in f_{*}(X)$のときは$f$の単射性より
$$ (y,x),(y,x') \in F^{\top} \quad\leadsto\quad (x,x') \in FF^{\top} \subset \Delta_{X}$$
が成り立ち，$y \notin f_{*}(X)$のときは$x=a=x'$が成り立つ．
- 任意の$x \in X$に対して，$(f(x),x) \in F^{\top} \subset R$より
$$ (r \circ f)(x) = r(f(x)) = x = \id_{X}(x)$$
が成り立つ．
(ii)$\implies$(i)
$r \circ f = \id_{X}$が単射なので，$f$は単射である．
双射の特徴づけ
写像$f=(F,X,Y)$が双射であるためには，$f$が可逆写像であることが必要かつ十分である：実際，
- $f$が双射ならば，写像$f^{\top}=(F^{\top},Y,X)$が$f$の逆写像を与える：
$$ \Delta_{X}=FF^{\top},\ F^{\top}F=\Delta_{Y} \quad\leadsto\quad f^{\top} \circ f = \id_{X},\ f \circ f^{\top} = \id_{Y}.$$ - $f$が可逆ならば，その逆写像$f^{-1} \coloneqq (F^{-1},Y,X)$について
$$ (y,x) \in F^{\top} \iff (x,y) \in F \iff f(x)=y \iff x=f^{-1}(y) \iff (y,x) \in F^{-1}$$
が成り立つので，$f^{\top}=f^{-1}$は写像である．
写像$f \colon X \to Y$について，次は同値である：
- $f$は双射である；
- 写像$r \colon Y \to X,\,s \colon Y \to X$であって
$$ r \circ f = \id_{X},\ f \circ s = \id_{Y}$$
を満たすものが存在する．
(i)$\implies$(ii)
$r \coloneqq s \coloneqq f^{\top}$とおけばよい．
(ii)$\implies$(i)
$$ r = r \circ \id_{Y} = r \circ (f \circ s) = (r \circ f) \circ s = \id_{X} \circ s = s \quad\leadsto\quad r=s=f^{-1}.$$
商写像
関係と写像との関係
任意の集合$X,Y$に対して，$\rel(X,Y)$から$\map(X,\mathcal{P}(Y))$への双射が存在する．
関係$R \in \rel(X,Y)$に対して，関係$M_{R} \in \rel(X,\mathcal{P}(Y))$を
$$
M_{R} \coloneqq \{(x,B) \in X \times \mathcal{P}(Y) \mid (x,y) \in R \iff y \in B\}$$
で定める．
- 任意の$x \in X$に対して，
$$ B \coloneqq \{y \in Y \mid (x,y) \in R\} \in \mathcal{P}(Y)$$
とおくと，
$$ (x,y) \in R \iff y \in B \quad\leadsto\quad (x,B) \in M_{R}$$
が成り立つ． - $(x,B),(x,B') \in M_{R}$とすると，任意の$y \in Y$に対して
$$ y \in B \iff (x,y) \in R \iff y \in B'$$
が成り立つので，$B=B'$を得る．
よって$\mu_{R} \coloneqq (M_{R},X,\mathcal{P}(Y))$は写像であるから，写像$\mu \colon \rel(X,Y) \to \map(X,\mathcal{P}(Y))$が
$$
\mu \colon R \mapsto \mu_{R}$$
により定まる：
$$
y \in \mu_{R}(x) \iff (x,y) \in R.$$
また，写像$\rho \colon \map(X,\mathcal{P}(Y)) \to \rel(X,Y)$を
$$
\rho \colon f \mapsto \{(x,y) \mid y \in f(x)\}$$
で定める．あとは
$$
\rho\circ\mu = \id_{\rel(X,Y)},\ \mu\circ\rho=\id_{\map(X,\mathcal{P}(Y))}$$
が成り立つことを示せばよい（cf. bij-inv）．
- $R \in \rel(X,Y)$とする．このとき，
$$ (x,y) \in \rho(\mu_{R}) \iff y \in \mu_{R}(x) \iff (x,y) \in R$$
より，
$$ (\rho\circ\mu)(R) = R = \id_{\rel(X,Y)}(R)$$
が成り立つ． - $f \in \map(X,\mathcal{P}(Y))$とする．このとき，
$$ y \in \mu_{\rho(f)}(x) \iff (x,y) \in \rho(f) \iff y \in f(x)$$
より，
$$ \forall\,x \in X,\ \mu_{\rho(f)}(x)=f(x) \quad\leadsto\quad (\mu\circ\rho)(f) = f = \id_{\map(X,\mathcal{P}(Y))}(f)$$
が成り立つ．
任意の写像$f=(F,X,Y)$に対して，
$$
y \in \mu_{F}(x) \iff (x,y) \in F \iff f(x)=y$$
より，
$$
\mu_{F}(x) = \{f(x)\}$$
が成り立つ．
- $S \in \rel(Y,Y')$とする．このとき，関係
$$ \{(B,y') \in \mathcal{P}(Y) \times Y' \mid \exists\,y \in B,\ (y,y') \in S\}$$
に対応する写像を$S_{*} \colon \mathcal{P}(Y)\to\mathcal{P}(Y')$で表わす：
$$ y' \in S_{*}(B) \iff \exists\,y \in B,\ (y,y') \in S.$$ - 写像$f=(F,X,Y)$に対して，$f_{*} \coloneqq F_{*} \colon \mathcal{P}(X) \to \mathcal{P}(Y)$とおく：
$$ y \in f_{*}(A) \iff \exists\,x \in A,\ (x,y) \in F \iff \exists\,x \in A,\ f(x)=y.$$
adjで構成した双射$\mu$は次の意味で“自然”である：
- 任意の関係$S \in \rel(Y,Y')$に対して，図式
$$ \xymatrix{ {\rel(X,Y)} \ar[rr]^{R \mapsto \mu_{R}} \ar[dd]_{R \mapsto RS} && {\map(X,\mathcal{P}(Y))} \ar[dd]^{f \mapsto S_{*}\circ f} \\ \\ {\rel(X,Y')} \ar[rr]_{R' \mapsto \mu_{R'}} && {\map(X,\mathcal{P}(Y'))} }$$
は可換である：
\begin{align} y' \in \mu_{RS}(x) &\iff (x,y') \in RS \\ &\iff \exists\,y \in Y,\ (x,y) \in R,\ (y,y') \in S \\ &\iff \exists\,y \in Y,\ y \in \mu_{R}(x),\ (y,y') \in S \\ &\iff y' \in (S_{*} \circ \mu_{R})(x). \end{align} - 任意の写像$g=(G,X',X)$に対して，図式
$$ \xymatrix{ {\rel(X,Y)} \ar[rr]^{R \mapsto \mu_{R}} \ar[dd]_{R \mapsto GR} && {\map(X,\mathcal{P}(Y))} \ar[dd]^{f \mapsto f \circ g} \\ \\ {\rel(X',Y)} \ar[rr]_{R' \mapsto \mu_{R'}} && {\map(X',\mathcal{P}(Y))} }$$
は可換である：
\begin{align} y \in \mu_{GR}(x') &\iff (x',y) \in GR \\ &\iff \exists\,x \in X,\ (x',x) \in G,\ (x,y) \in R \\ &\iff \exists\,x \in X,\ g(x')=x,\ y \in \mu_{R}(x) \\ &\iff y \in (\mu_{R} \circ g)(x'). \end{align}
選択公理
を次のように述べることができる：写像$g \colon X \to \mathcal{P}(Y)$が
$$
\forall\,x \in X,\ g(x) \neq \varnothing$$
を満たすならば，組$c \coloneqq (\rho(g),X,Y)$は写像である：
$$
\forall\,x \in X,\ (x,c(x)) \in \rho(g) \quad\leadsto\quad c(x) \in g(x).$$
実際，
- 集合$g_{*}(X)$の選択函数を$f \colon g_{*}(X) \to \bigcup g_{*}(X) \eqqcolon B$とするとき，写像
$$ c \coloneqq (\id_{Y}|_{B}) \circ f \circ g|^{g_{*}(X)} \colon X \to Y$$
のグラフを$C$とおくと，
$$ (x,y) \in C \iff y \in g(x) \iff (x,y) \in \rho(g)$$
が成り立つので，$(\rho(g),X,Y)=c$は写像である． - 任意の集合$X$に対して，$Y \coloneqq \bigcup_{x \in X} x$とおくと，写像$g \coloneqq \id_{\mathcal{P}(Y)}|_{X\smallsetminus\{\varnothing\}} \colon X \smallsetminus \{\varnothing\} \to \mathcal{P}(Y)$は
$$ \forall\,x \in X \smallsetminus \{\varnothing\},\ g(x)=x \neq \varnothing$$
を満たすので，写像$(\rho(g),X \smallsetminus \{\varnothing\},Y)$が$X$の選択函数を与える．
指示函数を考えることで双射$\mathcal{P}(X) \to \map(X,\{0,1\})$が得られ，これによって$\mathcal{P}(X)$と$\map(X,\{0,1\})$とを同一視すると，写像
$$
\mu \colon \map(X \times Y,\{0,1\}) \to \map(X,\map(Y,\{0,1\}))$$
は
$$
\mu(f)(x) \colon y \mapsto f(x,y)$$
で与えられる（cf.
Currying
）．
同値関係による商集合
関係$E \in \rel(X,X)$が
$$
\Delta_{X} \cup EE \subset E=E^{\top}$$
を満たすとき，$E$を$X$上の同値関係という．
- 等号関係は同値関係である．
- 任意の写像$f=(F,X,Y)$に対して，関係$\Ker_{f} \coloneqq FF^{\top}$は$X$上の同値関係である：
- $$ \Delta_{X} \subset FF^{\top} = \Ker_{f};$$
- $$ (\Ker_{f})^{\top} = (FF^{\top})^{\top} = (F^{\top})^{\top}F^{\top} = FF^{\top} = \Ker_{f};$$
- $$ \Ker_{f}\Ker_{f} = (FF^{\top})(FF^{\top}) = ((FF^{\top})F)F^{\top} = (F(F^{\top}F))F^{\top} \subset (F\Delta_{Y})F^{\top} = FF^{\top} = \Ker_{f}.$$
$X$上の同値関係$E \in \rel(X,X)$に対応する写像$\mu_{E} \colon X \to \mathcal{P}(X)$について，次が成り立つ：
- $x \in \mu_{E}(x);$
- $\mu_{E}(x)=\mu_{E}(x') \iff \mu_{E}(x) \cap \mu_{E}(x') \neq \varnothing.$
各$x \in X$に対して，$\mu_{E}(x) \in \mathcal{P}(X)$を$x$の同値類という．したがって，$X$はいくつかの同値類の非交和として表わせる．
- $(x,x) \in \Delta_{X} \subset E$より$x \in \mu_{E}(x)$を得る．
-
- $\mu_{E}(x)=\mu_{E}(x')$とすると，$x \in \mu_{E}(x) \cap \mu_{E}(x') \neq \varnothing$となる．
- $\mu_{E}(x) \cap \mu_{E}(x') \neq \varnothing$とし，$x_{0} \in \mu_{E}(x) \cap \mu_{E}(x')$を取ると，
$$ (x,x_{0}),\ (x',x_{0}) \in E=E^{\top}$$
より
\begin{align} y \in \mu_{E}(x) &\quad\leadsto\quad (x',x_{0}),\ (x_{0},x),\ (x,y) \in E \quad\leadsto\quad (x',y) \in (EE)E \subset EE \subset E \quad\leadsto\quad y \in \mu_{E}(x');\\ y \in \mu_{E}(x') &\quad\leadsto\quad (x,x_{0}),\ (x_{0},x'),\ (x',y) \in E \quad\leadsto\quad (x,y) \in (EE)E \subset EE \subset E \quad\leadsto\quad y \in \mu_{E}(x); \end{align}
となるので，$\mu_{E}(x)=\mu_{E}(x')$が成り立つ．
関係$E \in \rel(X,X)$が同値関係であるためには$E=\Ker_{\mu_{E}}$が成り立つことが必要かつ十分である：
- 必要性：$E$が同値関係であるとき，equiv-classより，
$$ (x,x') \in E \iff x' \in \mu_{E}(x) \iff \mu_{E}(x)=\mu_{E}(x') \iff (x,x') \in \Ker_{\mu_{E}}$$
が成り立つ． - 十分性：equiv-exで見た．
$X$を集合とし$E \in \rel(X,X)$を同値関係とする．このとき，集合
$$
X/E \coloneqq (\mu_{E})_{*}(X) = \{A \in \mathcal{P}(X) \mid \exists\,x \in X,\ \mu_{E}(x)=A\}$$
を$X$の$E$による商集合といい，$\mu_{E}$の$X/E$への余制限$q_{E} \coloneqq \mu_{E}|^{X/E}$を商写像という：
$$
q_{E} \colon X \to X/E.$$
$E \in \rel(X,X)$を同値関係とする．このとき次は同値である（cf. equiv-ker，equiv-class）：
- $(x,x') \in E;$
- $q_{E}(x)=q_{E}(x');$
- $q_{E}(x) \cap q_{E}(x') \neq \varnothing.$
商写像$q_{\Delta_{Y}} \colon Y \to Y/\Delta_{Y}$は双射である（cf. adj-ex）：
$$
(q_{\Delta_{Y}})^{-1}(\{y\}) = y.$$
準同型定理
$f \colon X \to Y$とする．関係$R \in \rel(X,X), S \in \rel(Y,Y)$に対して
$$
(x,x') \in R \implies (f(x),f(x')) \in S$$
が成り立つとき，$f$は$(R,S)$と両立するという．とくに$f$が$(R,\Delta_{Y})$と両立するとき，単に$f$は$R$と両立するという．
$f=(F,X,Y)$を写像とし，$R \in \rel(X,X)$とする．このとき，$f$が$R$と両立するためには，$R \subset \Ker_{f}$が成り立つことが必要かつ十分である．また，$\Delta_{X}\subset R$なるとき，
$$
R \subset \Ker_{f} \iff RF=F$$
が成り立つ．
前半は
$$
f(x)=f(x') \iff (x,x') \in \Ker_{f}$$
よりしたがう．
- $R \subset \Ker_{f}$のとき，
$$ RF \subset \Ker_{f}F = (FF^{\top})F = F(F^{\top}F) \subset F\Delta_{Y} = F = \Delta_{X}F \subset RF$$
より$RF=F$を得る． - $RF=F$のとき，
$$ (x,x') \in R \implies (x,f(x')) \in RF=F \implies f(x)=f(x')$$
より$R \subset \Ker_{f}$を得る．
$f=(F,X,Y)$を写像とし，$E \in \rel(X,X)$を同値関係とする．このとき，$f$が$E$と両立するならば，写像$\bar{f} \colon X/E \to Y$であって$\bar{f}\circ q_{E}=f$なるものがただ一つ存在する：
$$
\xymatrix{
{X} \ar[rr]^{f} \ar[dd]_{q_{E}} && {Y.} \\ \\
{X/E} \ar@{.>}[uurr]_{\bar{f}}
}$$
一意性
写像$q_{E}$の全射性より
$$
g \circ q_{E} = f \implies g \circ q_{E} = \bar{f} \circ q_{E} \implies g=\bar{f}$$
が成り立つ（cf. epi）．
存在
仮定より$EF=F=F\Delta_{Y}$であるから（cf. ref-rel），
$$
f_{*} \circ \mu_{E} = \mu_{EF} = \mu_{F\Delta_{Y}} = \mu_{\Delta_{Y}} \circ f$$
が成り立つ（cf. naturality）：
$$
\xymatrix{
{X} \ar[rr]^{f} \ar[dd]_{\mu_{E}} && {Y} \ar[dd]^{\mu_{\Delta_{Y}}} \\ \\
{\mathcal{P}(X)} \ar[rr]_{f_{*}} && {\mathcal{P}(Y).}
}$$
このとき
$$
f_{*}(q_{E}(x)) = (f_{*} \circ \mu_{E})(x) = (\mu_{\Delta_{Y}} \circ f)(x) = \{f(x)\} \in Y/\Delta_{Y}$$
となるので，写像
$$
\bar{f} \coloneqq (q_{\Delta_{Y}})^{-1} \circ f_{*}|_{X/E}^{Y/\Delta_{Y}} \colon X/E \to Y$$
が定まる：
$$
\xymatrix{
{X} \ar[rr]^{f} \ar[dd]_{q_{E}} && {Y} \ar[dd]^{q_{\Delta_{Y}}} \\ \\
{X/E} \ar[rr]_{f_{*}|_{X/E}^{Y/\Delta_{Y}}} \ar@{.>}[uurr]_{\bar{f}} && {Y/\Delta_{Y}.}
}$$
さらに，任意の$x \in X$に対して
$$
(\bar{f}\circ q_{E})(x) = (q_{\Delta_{Y}})^{-1}(f_{*}(q_{E}(x))) = (q_{\Delta_{Y}})^{-1}(\{f(x)\}) = f(x)$$
が成り立つ．
存在性のよくある証明は以下の通り：関係$\bar{F} \in \rel(X/E,Y)$を
$$
\bar{F} \coloneqq \{(A,y) \in (X/E) \times Y \mid \forall\,x \in A,\ f(x)=y\}$$
で定める．
- $A \in X/E$とする．$a \in X$であって$q_{E}(a)=A$なるものを取ると，任意の$x \in A$に対して
$$ x \in q_{E}(x) \cap q_{E}(a) \neq \varnothing \quad\leadsto\quad (x,a) \in E \subset \Ker_{f}$$
より$f(x)=f(a)$が成り立つので，$(A,f(a)) \in \bar{F}$を得る． - $(A,y),(A,y') \in \bar{F}$とする．このとき，$a \in X$であって$q_{E}(a)=A$なるものを取ると，
$$ a \in q_{E}(a)=A \quad\leadsto\quad y = f(a) = y'$$
を得る．
よって写像$\bar{f} \coloneqq (\bar{F},X/E,Y)$が定まる．さらに，任意の$x \in X$に対して
$$
x \in q_{E}(x) \quad\leadsto\quad (\bar{f} \circ q_{E})(x) = \bar{f}(q_{E}(x)) = f(x)$$
が成り立つ．
- $\bar{f}$が全射であるためには，$f$が全射であることが必要かつ十分である．
- $\bar{f}$が単射であるためには，$E \supset \Ker_{f}$が成り立つことが必要かつ十分である．
- compo-surjよりしたがう．
- $q_{E}=\mu_{E}|^{X/E}$の全射性より$(M_{E})^{\top}M_{E} = \Delta_{X/E}$であるから，
$$ M_{E}(\bar{F}\bar{F}^{\top})(M_{E})^{\top} = FF^{\top} = \Ker_{f},\ E = \Ker_{q_{E}} = M_{E}(M_{E})^{\top}$$
と併せて
$$ \bar{F}\bar{F}^{\top} = \Delta_{X/E} \iff E = \Ker_{f}$$
を得る．
写像$f \colon X \to Y$が全射ならば，写像
$$
\bar{f} \colon X/\Ker_{f} \to Y$$
は双射である．
写像$f \colon X \to Y$が同値関係$E \in \rel(X,X),E' \in \rel(Y,Y)$と両立するならば，写像$\bar{f}_{(E,E')} \colon X/E \to Y/E'$であって$\bar{f}_{(E,E')} \circ q_{E} = q_{E'} \circ f$なるものがただ一つ存在する：
$$
\xymatrix{
{X} \ar[rr]^{f} \ar[dd]_{q_{E}} && {Y} \ar[dd]^{q_{E'}} \\ \\
{X/E} \ar@{.>}[rr]_{\bar{f}_{(E,E')}} && {Y/E'.}
}$$
仮定より
$$
(x,x') \in E \implies (f(x),f(x')) \in E'=\Ker_{q_{E'}} \implies q_{E'}(f(x))=q_{E'}(f(x'))$$
が成り立つ．よって$q_{E'}\circ f$は$E$と両立するので，
$$
\bar{f}_{(E,E')} \coloneqq \overline{q_{E'}\circ f} \colon X/E \to Y/E'$$
とおけばよい．
$X$を集合とし，$E,E' \in \rel(X,X)$を同値関係とする．このとき，$E \subset E'$が成り立つならば，恒等写像$\id_{X}$は$(E,E')$と両立するので，全射$q \colon X/E \to X/E'$であって$q \circ q_{E} = q_{E'}$なるものがただ一つ存在する：
$$
\xymatrix{
{X} \ar[rr]^{\id_{X}} \ar[dd]_{q_{E}} && {X} \ar[dd]^{q_{E'}} \\ \\
{X/E} \ar@{.>}[rr]_{q} && {X/E'.}
}$$
そこで，$E'/E \coloneqq \Ker_{q} \in \rel(X/E,X/E)$とおくと，これは同値関係であるから，写像
$$
\bar{q} \colon (X/E)/(E'/E) \to X/E'$$
は双射である（cf. inj-surj-quoti）．
写像の貼り合わせ
$X$を集合とする．写像$\gamma \colon I \to \mathcal{P}(X)\smallsetminus\{\varnothing\}$が
$$
X = \bigcup_{i \in I} \gamma(i)$$
を満たすとき，$\gamma$を$X$の被覆という．
$X,Y$を集合とし，$\gamma \colon I \to \mathcal{P}(X)\smallsetminus\{\varnothing\}$を$X$の被覆とする．さらに，写像
$$
f_{\bullet} \in \map\left(I,\bigcup_{i \in I}\map(\gamma(i),Y)\right),\ f_{\bullet} \colon i \mapsto f_{i} \in \map(\gamma(i),Y)$$
が
$$
\forall\,i,j \in I,\ f_{i}|_{\gamma(i) \cap \gamma(j)} = f_{j}|_{\gamma(i) \cap \gamma(j)}$$
を満たしているとする．このとき，写像$f \colon X \to Y$であって
$$
\forall\,i \in I,\ f|_{\gamma(i)}=f_{i}$$
なるものがただ一つ存在する．
一意性
$\gamma$が被覆であることからしたがう（cf. eq）．
存在
- 集合$\coprod\gamma$を
$$ \coprod \gamma \coloneqq \bigcup_{i \in I} \{i\} \times \gamma(i)$$
で定める． - 写像$\Gamma \colon \coprod \gamma \to X$を$\Gamma \colon (i,x) \mapsto x$で定めると，これは全射であるから写像$\bar{\Gamma} \colon (\coprod\gamma)/\Ker_{\Gamma} \to X$は双射である（cf. isom）．
- 写像$\Gamma_{f_{\bullet}} \colon \coprod \gamma \to Y$を$\Gamma_{f_{\bullet}} \colon (i,x) \mapsto f_{i}(x)$で定めると，これは$\Ker_{\Gamma}$と両立する：
$$ ((i,x),(j,x')) \in \Ker_{\Gamma} \implies x=x' \in \gamma(i) \cap \gamma(j) \implies \Gamma_{f_{\bullet}}((i,x)) = f_{i}(x)=f_{j}(x') = \Gamma_{f_{\bullet}}((j,x')).$$ - そこで，$f \coloneqq \overline{\Gamma_{f_{\bullet}}} \circ \bar{\Gamma}^{-1} \colon X \to Y$とおくと，任意の$i \in I$に対して
$$ \forall\,x \in \gamma(i),\ f|_{\gamma(i)}(x) = \overline{\Gamma_{f_{\bullet}}}(q_{\Ker_{\Gamma}}((i,x))) = \Gamma_{f_{\bullet}}((i,x)) = f_{i}(x) \quad\leadsto\quad f|_{\gamma(i)}=f_{i}$$
が成り立つ：
$$ \xymatrix{ {\gamma(i)} \ar[rr]^{\id_{X}|_{\gamma(i)}} \ar@/^10ex/[rrrrrr]^{f_{i}} && {X} \ar@/^5ex/[rrrr]^{f} && {\coprod\gamma} \ar[dd]_{q_{\Ker_{\Gamma}}} \ar[ll]_{\Gamma} \ar[rr]^{\Gamma_{f_{\bullet}}}&& {Y.} \\ \\ &&&& {(\coprod\gamma)/\Ker_{\Gamma}} \ar[uull]^{\bar{\Gamma}\,:\,\text{bij.}} \ar[uurr]_{\overline{\Gamma_{f_{\bullet}}}} }$$
