文献あり

二項関係の全域性・一意性

写像と集合演算について，悪い人さんの記事数学初心者が写像について学びを深める…… を読んで興味深いと思ったので，自分用のメモとして二項関係の言葉を用いて書き直してみます．

二項関係

二項関係の定義

二項関係

集合$X,Y$と直積集合$X\times Y$の部分集合$G$の3つ組$R=(X,Y,G)$を，$X$と$Y$の間の二項関係という．
$X$と$Y$の間の二項関係$R=(X,Y,G)$と$(x,y)\in X\times Y$に対して，$(x,y)\in G$であることを$x\mathrel{R}y$とも書く．

合同式

$2$以上の整数$m$に対して
$$ G_m:=\{(x,y)\in\mathbb{Z}\times\mathbb{Z}\mid\text{$x-y$ は $m$ で割り切れる}\}$$
とおくと，${\equiv_m}:=(\mathbb{Z},\mathbb{Z},G_m)$は$\mathbb{Z}$と$\mathbb{Z}$の間の二項関係となる．
（普通は$x\equiv_m y$であることを$x\equiv y\pmod{m}$と書く）

逆関係

$X$と$Y$の間の二項関係$R=(X,Y,G)$に対して，$Y$と$X$の間の二項関係$R^{-1}=(Y,X,G^{-1})$を
$$ G^{-1}:=\{(y,x)\in Y\times X\mid (x,y)\in G\}$$
で定め，$R$の逆関係という．

つまり$(x,y)\in X\times Y$について
$$ y\mathrel{R^{-1}}x \iff x\mathrel{R}y$$
が成り立つ．

集合$X,Y$および$X$と$Y$の間の二項関係$R$に対して，$(R^{-1})^{-1}=R$が成り立つ．

$R=(X,Y,G)$とすると
\begin{align*} (G^{-1})^{-1} &=\{(x,y)\in X\times Y\mid (y,x)\in G^{-1}\} \\ &=\{(x,y)\in X\times Y\mid (x,y)\in G\} \\ &=G. \end{align*}

二項関係の像・逆像

本記事でも以前書いた記事 $A$と$f^{-1}(f(A))$, $B$と$f(f^{-1}(B))$の包含関係と同様に，矢印記法を使う（逆関係／逆写像と逆像の混乱を防ぐため）．
また，集合$X$の冪集合（$X$の部分集合全体の集合）を$\powerset{X}$で表す．

二項関係の像・逆像

集合$X,Y$および$X$と$Y$の間の二項関係$R$に対して，2つの写像$\pushout{R}:\powerset{X}\to\powerset{Y}$と$\pullback{R}:\powerset{Y}\to\powerset{X}$を
\begin{align*} \pushout{R}(A)&:=\{y\in Y\mid\text{$a\mathrel{R}y$ を満たす $a\in A$ が存在する}\}&(A\in\powerset{X}), \\ \pullback{R}(B)&:=\{x\in X\mid\text{$x\mathrel{R}b$ を満たす $b\in B$ が存在する}\}&(B\in\powerset{Y})\phantom{,} \end{align*}
で定義する．

逆関係の像・逆像

集合$X,Y$および$X$と$Y$の間の二項関係$R$について，次のことが成り立つ．

$\pushout{(R^{-1})}=\pullback{R}$.
$\pullback{(R^{-1})}=\pushout{R}$.

任意の$A\in\powerset{X}$と$B\in\powerset{Y}$に対して，
\begin{align*} \pushout{(R^{-1})}(B) &=\{x\in X\mid {}^\exists b\in B,\ b\mathrel{R^{-1}}x\} \\ &=\{x\in X\mid {}^\exists b\in B,\ x\mathrel{R}b\} \\ &=\pullback{R}(B), \\ \pullback{(R^{-1})}(A) &=\{y\in Y\mid {}^\exists a\in A,\ y\mathrel{R^{-1}}a\} \\ &=\{y\in Y\mid {}^\exists a\in A,\ a\mathrel{R}y\} \\ &=\pushout{R}(A). \end{align*}

$X,Y$を集合，$R$を$X$と$Y$の間の二項関係とし，$A,A'\in\powerset{X}$, $B,B'\in\powerset{Y}$とする．

$A\subset A'$のとき，$\pushout{R}(A)\subset\pushout{R}(A')$である．
$\pushout{R}(A\cup A')=\pushout{R}(A)\cup\pushout{R}(A')$.
$\pushout{R}(A\cap A')\subset\pushout{R}(A)\cap\pushout{R}(A')$.
$B\subset B'$のとき，$\pullback{R}(B)\subset\pullback{R}(B')$である．
$\pullback{R}(B\cup B')=\pullback{R}(B)\cup\pullback{R}(B')$.
$\pullback{R}(B\cap B')\subset\pullback{R}(B)\cap\pullback{R}(B')$.

$y\in\pushout{R}(A)$のとき，$\pushout{R}$の定義から$a\mathrel{R}y$を満たす$a\in A$が存在するが，$A\subset A'$より$a\in A'$でもあるので$y\in\pushout{R}(A')$となる．
$A$と$A'$はどちらも$A\cup A'$に含まれるので，(1) より$\pushout{R}(A\cup A')\supset \pushout{R}(A)$かつ$\pushout{R}(A\cup A')\supset \pushout{R}(A')$，つまり$\pushout{R}(A\cup A')\supset\pushout{R}(A)\cup\pushout{R}(A')$が成り立つ．
逆の包含を示すため$y\in\pushout{R}(A\cup A')$とすると，$\pushout{R}$の定義から$a\mathrel{R}y$を満たす$a\in A\cup A'$が取れる．すると$a\in A$の場合は$y\in\pushout{R}(A)$となり，$a\in A'$の場合は$y\in\pushout{R}(A')$となるので，いずれにしても$y\in\pushout{R}(A)\cup\pushout{R}(A')$である．
$A$と$A'$はどちらも$A\cap A'$を含むので，(1) より$\pushout{R}(A\cap A')\subset \pushout{R}(A)$かつ$\pushout{R}(A\cap A')\subset \pushout{R}(A')$，つまり$\pushout{R}(A\cap A')\subset\pushout{R}(A)\cap\pushout{R}(A')$が成り立つ．

(4), (5), (6) は前命題と (1), (2), (3) から従う．

共通部分に関する (3), (6) では等号が成り立つとは限らないことに注意．
（後述の通り，(3), (6) で常に等号成立することは，$R$の左一意性，右一意性にそれぞれ同値である）

集合$X,Y$および$X$と$Y$の間の二項関係$R,S$に対して，次のことが成り立つことを示せ．

$\pushout{R}=\pushout{S}$ならば，$R=S$である．
$\pullback{R}=\pullback{S}$ならば，$R=S$である．

$x\in X$と$y\in Y$について，$x\mathrel{R}y$と$y\in\pushout{R}(\{x\})$と$x\in\pullback{R}(\{y\})$が互いに同値であることに注意．

$x\mathrel{R}y$のとき，$y\in\pushout{R}(\{x\})=\pushout{S}(\{x\})$より$x\mathrel{S}y$である．同様に$x\mathrel{S}y$であれば$x\mathrel{R}y$となるので，$R=S$である．
$x\mathrel{R}y$のとき，$x\in\pullback{R}(\{y\})=\pullback{S}(\{y\})$より$x\mathrel{S}y$である．同様に$x\mathrel{S}y$であれば$x\mathrel{R}y$となるので，$R=S$である．

二項関係の全域性・一意性

全域性・一意性

集合$X,Y$および$X$と$Y$の間の二項関係$R$に対して，

$R$が左全域的であるとは，任意の$x\in X$に対してある$y\in Y$が存在して$x\mathrel{R}y$が成り立つことをいう．
$R$が右全域的であるとは，任意の$y\in Y$に対してある$x\in X$が存在して$x\mathrel{R}y$が成り立つことをいう．
$R$が左一意的であるとは，各$y\in Y$に対して，$x\mathrel{R}y$を満たす$x\in X$が高々1つしかないことをいう．
$R$が右一意的であるとは，各$x\in X$に対して，$x\mathrel{R}y$を満たす$y\in Y$が高々1つしかないことをいう．

写像

$X$から$Y$への写像とは，$X$と$Y$の間の左全域的かつ右一意的な二項関係のことだった．
写像$f:X\to Y$と$x\in X$に対して，$x\mathrel{f}y$を満たす一意的な$y\in Y$のことを$f(x)$と書く．
また，右全域的な写像は全射のことであり，左一意的な写像は単射のことである．

逆関係を考えれば，全域性や一意性の左右は容易に取り換えられる．

集合$X,Y$および$X$と$Y$の間の二項関係$R$について，次のことが成り立つ．

$R$が左全域的であることと，$R^{-1}$が右全域的であることは同値である．
$R$が左一意的であることと，$R^{-1}$が右一意的であることは同値である．

\begin{align*} \text{$R$ が左全域的} &\iff {}^\forall x\in X,\ {}^\exists y\in Y,\ x\mathrel{R} y \\ &\iff {}^\forall x\in X,\ {}^\exists y\in Y,\ x\mathrel{R} y \\&\iff {}^\forall x\in X,\ {}^\exists y\in Y,\ y\mathrel{R^{-1}} x \\ &\iff \text{$R^{-1}$ が右全域的}, \\ \text{$R$ が左一意的} &\iff {}^\forall y\in Y,\ {}^\forall x,x'\in X,\ ({x\mathrel{R} y}\wedge{x'\mathrel{R} y}\Rightarrow x=x') \\ &\iff {}^\forall y\in Y,\ {}^\forall x,x'\in X,\ ({y\mathrel{R^{-1}} x}\wedge{y\mathrel{R^{-1}} x'}\Rightarrow x=x') \\ &\iff \text{$R^{-1}$ が右一意的}. \end{align*}

逆写像

写像$f:X\to Y$の逆関係$f^{-1}$が$Y$から$X$への写像であるための必要十分条件は，$f$が右全域的かつ左一意的（つまり全単射）なことである．
このとき，写像$f^{-1}:Y\to X$を$f$の逆写像というのだった．

$A$と$\pullback{R}(\pushout{R}(A))$，$B$と$\pushout{R}(\pullback{R}(B))$の包含関係

以前書いた記事 $A$と$f^{-1}(f(A))$, $B$と$f(f^{-1}(B))$の包含関係と同様に，$A$と$\pullback{R}(\pushout{R}(A))$，$B$と$\pushout{R}(\pullback{R}(B))$の包含関係について考える．

集合$X,Y$および$X$と$Y$の間の二項関係$R$について，次の2条件は互いに同値である．

$R$は左全域的である．
任意の$A\in\powerset{X}$に対して$A\subset\pullback{R}(\pushout{R}(A))$が成り立つ．

(1)$\Rightarrow$(2)：任意の$a\in A$に対して，$R$の左全域性から$a\mathrel{R}y$を満たす$y\in Y$が取れるが，このとき$y\in\pushout{R}(A)$より$a\in\pullback{R}(\pushout{R}(A))$となる．
(2)$\Rightarrow$(1)：任意の$x\in X$に対して，$\{x\}\subset\pullback{R}(\pushout{R}(\{x\}))$だから$x\mathrel{R}y$を満たす$y\in\pushout{R}(\{x\})$が取れる．

集合$X,Y$および$X$と$Y$の間の二項関係$R$について，次の2条件は互いに同値である．

$R$は右全域的である．
任意の$B\in\powerset{Y}$に対して$B\subset\pushout{R}(\pullback{R}(B))$が成り立つ．

逆関係$R^{-1}$に前命題を適用すればよい．

集合$X,Y$および$X$と$Y$の間の二項関係$R$について，次の3条件は互いに同値である．

$R$は左一意的である．
任意の$A\in\powerset{X}$に対して$A\supset\pullback{R}(\pushout{R}(A))$が成り立つ．
任意の$A,A'\in\powerset{X}$に対して$\pushout{R}(A\cap A')=\pushout{R}(A)\cap\pushout{R}(A')$が成り立つ．

(1)$\Rightarrow$(2)：任意の$x\in \pullback{R}(\pushout{R}(A))$に対して，$\pullback{R}$の定義から$x\mathrel{R}y$を満たす$y\in\pushout{R}(A)$が取れて，$\pushout{R}$の定義から$a\mathrel{R}y$を満たす$a\in A$が取れる．このとき$R$の左一意性より$x=a\in A$となるので，$A\supset\pullback{R}(\pushout{R}(A))$が成り立つ．
(2)$\Rightarrow$(3)：逆の包含は常に成り立つから，$\pushout{R}(A\cap A')\supset\pushout{R}(A)\cap\pushout{R}(A')$を示せばよい．$y\in\pushout{R}(A)\cap\pushout{R}(A')$を任意に取ると，$y\in\pushout{R}(A)$だから$a\mathrel{R}y$を満たす$a\in A$が存在し，$y\in\pushout{R}(A')$だから$a'\mathrel{R}y$を満たす$a\in A'$が存在する．すると
\begin{align*} a'\in\pullback{R}(\{y\}) &\subset\pullback{R}(\pushout{R}(\{a\}))\subset\{a\} \end{align*}
より$a=a'$となり，$y\in\pushout{R}(\{a\})\subset \pushout{R}(A\cap A')$が示された．
(3)$\Rightarrow$(1)：$x,x'\in X$と$y\in Y$が$x\mathrel{R}y$かつ$x'\mathrel{R}y$を満たすとする．このとき
$$ y\in \pushout{R}(\{x\})\cap\pushout{R}(\{x'\})=\pushout{R}(\{x\}\cap\{x'\})$$
であり，もし$x\ne x'$なら右辺$\pushout{R}(\emptyset)=\emptyset$が元$y$を持つことになり矛盾する．よって$x=x'$であり，$R$は左一意的である．

集合$X,Y$および$X$と$Y$の間の二項関係$R$について，次の3条件は互いに同値である．

$R$は右一意的である．
任意の$B\in\powerset{Y}$に対して$B\supset\pushout{R}(\pullback{R}(B))$が成り立つ．
任意の$B,B'\in\powerset{Y}$に対して$\pullback{R}(B\cap B')=\pullback{R}(B)\cap\pullback{R}(B')$が成り立つ．

逆関係$R^{-1}$に前命題を適用すればよい．

これで，$A$と$\pullback{R}(\pushout{R}(A))$，$B$と$\pushout{R}(\pullback{R}(B))$の包含関係と，$R$の全域性・一意性が綺麗に対応していることがわかった．
これらの結果を写像・全射・単射に適用すれば，次の命題を得る．

集合$X,Y$とその間の写像$f:X\to Y$について，次のことが成り立つ．

任意の$A\in\powerset{X}$に対して$A\subset\pullback{f}(\pushout{f}(A))$が成り立つ．
任意の$B\in\powerset{Y}$に対して$B\supset\pushout{f}(\pullback{f}(B))$が成り立つ．
任意の$B,B'\in\powerset{Y}$に対して$\pullback{f}(B\cap B')=\pullback{f}(B)\cap\pullback{f}(B')$が成り立つ．