対応 ②

前回は「対応」を、まず集合 $A$ の各元 $a\in A$ に対して、集合 $B$ の部分集合をただ $1$ つ定める規則として定義し、
その後、$A$ から $B$ への対応を定めることと、二項関係 $R\subseteq A\times B$ を定めることが、
互いに一意に復元できるという意味で本質的に同じであることを示した。
$ $
そこで今回からは、対応を二項関係を用いた $3$ つ組 $(A,B,R)$ として再定義して議論を進める。

対応 $\Gamma=(A,B,R)$ のグラフ $G(\Gamma)$ は、$A\times B$ の部分集合である。
したがって、
$$ (a,b)\in G(\Gamma) $$
であることは、$a\in A$ と $b\in B$ が対応 $\Gamma$ によって結びついていることを意味する。
定義より、任意の $a\in A$ と $b\in B$ に対して、
$$ (a,b)\in G(\Gamma) \Longleftrightarrow (a,b)\in R $$
が成り立つ。

対応 $\Gamma=(A,B,R)$ に対して、任意の $a\in A$ と $b\in B$ について、
$$ b\in\Gamma(a) \Longleftrightarrow (a,b)\in R \Longleftrightarrow (a,b)\in G(\Gamma) $$
が成り立つ。
したがって、$G(\Gamma)$ は、各 $a\in A$ に対して $\Gamma(a)$ に属する $b\in B$ を、順序対 $(a,b)$ の形で集めた集合である。

対応 $\Gamma=(A,B,R)$ において、各 $a\in A$ における値 $\Gamma(a)$ は、$B$ の元ではなく、$B$ の部分集合である。
実際、
$$ \Gamma(a) = \{b\in B\mid (a,b)\in R\} $$
であるから、
$$ \Gamma(a)\subseteq B $$
が成り立つ。同値に、
$$ \Gamma(a)\in\mathcal{P}(B) $$
である。
したがって、対応は「$A$ の元 $a$ に $B$ の元を対応させるもの」とは限らず、
「$A$ の元 $a$ に $B$ の部分集合を対応させるもの」と見なすことができる。

対応 $\Gamma=(A,B,R)$ に対して、ある $a\in A$ で
$$ \Gamma(a)=\varnothing $$
となることを許す。
これは、二項関係 $R\subseteq A\times B$ において、ある $a\in A$ と関係する $b\in B$ が存在しない場合である。
実際、対応の値は
$$ \Gamma(a) := \{b\in B\mid (a,b)\in R\} $$
で定義されるから、
$$ \Gamma(a)=\varnothing $$
であることは、
$$ \forall b\in B\ ((a,b)\notin R) $$
が成り立つことと同値である。

対応 $\Gamma=(A,B,R)$ において、各 $a\in A$ に対する値
$$ \Gamma(a) = \{b\in B\mid (a,b)\in R\} $$
は、集合としてただ $1$ つ定まる。
ただし、これは異なる元が異なる値を持つことを意味しない。
したがって、$a,a'\in A$ かつ $a\ne a'$ であっても、
$$ \Gamma(a)=\Gamma(a') $$
となってよい。
つまり、対応の定義では、異なる始集合の元が異なる部分集合に対応することは要求されない。

$A=\{1,2,3\}$、$B=\{\alpha,\beta,\gamma\}$ とする。
また、
$$ R:=\{(1,\alpha),(1,\gamma),(2,\beta)\} $$
とおき、
$$ \Gamma:=(A,B,R) $$
と定める。
このとき、$\Gamma$ は $A$ から $B$ への対応であり、定義より
$$ G(\Gamma)=R $$
である。
したがって、
$$ G(\Gamma) = \{(1,\alpha),(1,\gamma),(2,\beta)\} $$
である。
また、対応の値は
$$ \Gamma(1)=\{\alpha,\gamma\}, \quad \Gamma(2)=\{\beta\}, \quad \Gamma(3)=\varnothing $$
である。
特に、$\Gamma(3)=\varnothing$ であるから、$3$ を第 $1$ 成分にもつ順序対は $G(\Gamma)$ に存在しない。

$A,B$ を集合とし、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
任意の $a\in A$ に対して、
$$ a\in\operatorname{dom}(\Gamma) \Longleftrightarrow \Gamma(a)\ne\varnothing $$
が成り立つ。
また、対応の値の定義より、
$$ a\in\operatorname{dom}(\Gamma) \Longleftrightarrow \exists b\in B\ ((a,b)\in R) $$
も成り立つ。

$A,B$ を集合とし、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
任意の $a\in A$ に対して、
$$ a\notin\operatorname{dom}(\Gamma) \Longleftrightarrow \Gamma(a)=\varnothing $$
が成り立つ。
また、対応の値の定義より、
$$ a\notin\operatorname{dom}(\Gamma) \Longleftrightarrow \forall b\in B\ ((a,b)\notin R) $$
も成り立つ( 証明はコチラ )。

対応 $\Gamma=(A,B,R)$ の始集合は $A$ である。
一方、実際に対応先を持つ元全体を区別したい場合は、
$$ \operatorname{dom}(\Gamma) := \{a\in A\mid \Gamma(a)\ne\varnothing\} $$
とおき、これを $\Gamma$ の(写像の『定義域』と区別して)『対応の定義域』という。
ただし、文脈より明らかな場合は、単に定義域と呼ぶ。
対応の値の定義より、
$$ \operatorname{dom}(\Gamma) = \{a\in A\mid \exists b\in B\ ((a,b)\in R)\} $$
である。
本定義では空値を許すため、一般には
$$ \operatorname{dom}(\Gamma)\ne A $$
となりうる。
特に、
$$ \operatorname{dom}(\Gamma)=A $$
が成り立つことは、$\Gamma$ が以下で定める全域的であることと同値である。

$A,B$ を集合とし、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
$\Gamma$ が全域的であることは、
$$ \forall a\in A\quad \Gamma(a)\ne\varnothing $$
が成り立つことと同値である。
さらに、対応の値の定義より、これは
$$ \forall a\in A\ \exists b\in B\ ((a,b)\in R) $$
が成り立つこととも同値である。
したがって、全域的対応とは、始集合 $A$ のすべての元が、少なくとも $1$ つの終集合 $B$ の元と対応している対応である。

$S$ の像 $\Gamma(S)$ は、$S$ の元と対応している $B$ の元をすべて集めた集合である。
すなわち、任意の $b\in B$ に対して、
$$ b\in\Gamma(S) \Longleftrightarrow \exists a\in S\ ((a,b)\in R) $$
が成り立つ。

$A,B$ を集合とし、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
任意の $a\in A$ に対して、
$$ \Gamma(\{a\})=\Gamma(a) $$
が成り立つ。
実際、単集合の定義より、
$$ x\in\{a\} \Longleftrightarrow x=a $$
である( 証明はコチラ )から、
集合の像の定義より、
$$ \begin{align} \Gamma(\{a\}) &= \{b\in B\mid \exists x\in\{a\}\ ((x,b)\in R)\}\\ &= \{b\in B\mid (a,b)\in R\}\\ &= \Gamma(a) \end{align} $$
である。

この段階では、記号
$$ \bigcup_{a\in S}\Gamma(a) $$
を
$$ \{b\in B\mid \exists a\in S\ (b\in\Gamma(a))\} $$
を表す略記として用いる。
対応の値の定義より、
$$ b\in\Gamma(a) \Longleftrightarrow (a,b)\in R $$
であるから、
$$ \{b\in B\mid \exists a\in S\ (b\in\Gamma(a))\} = \{b\in B\mid \exists a\in S\ ((a,b)\in R)\} $$
が成り立つ。したがって、
$$ \Gamma(S) = \bigcup_{a\in S}\Gamma(a) $$
と書いてよい。

対応 $\Gamma=(A,B,R)$ は、始集合 $A$、終集合 $B$、グラフ $R$ からなる $3$ つ組である。
したがって、対応の相等では、グラフだけでなく、始集合と終集合も一致することを要求する。
すなわち、対応 $\Gamma=(A,B,R)$ と $\Gamma'=(A',B',R')$ について、
$$ R=R' $$
だけでは、一般には
$$ \Gamma=\Gamma' $$
とはいえない。
対応として等しいためには、
$$ A=A', \quad B=B', \quad R=R' $$
がすべて必要である。

$A,B,A',B'$ を集合とする。
また、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とし、$\Gamma'=(A',B',R')$ を $A'$ から $B'$ への対応とする。
対応の相等の定義より、$\Gamma\ne\Gamma'$ であるとは、
$$ A\ne A' \ \lor\ B\ne B' \ \lor\ R\ne R' $$
が成り立つことである。
すなわち、始集合、終集合、グラフのうち少なくとも $1$ つが異なれば、対応として等しくない。

$A,B$ を集合とし、$\Gamma=(A,B,R)$ と $\Gamma'=(A,B,R')$ をともに $A$ から $B$ への対応とする。
このとき、
$$ \Gamma=\Gamma' \Longleftrightarrow R=R' $$
が成り立つ。
また、対応の値を用いれば、
$$ \Gamma=\Gamma' \Longleftrightarrow \forall a\in A\ \bigl(\Gamma(a)=\Gamma'(a)\bigr) $$
である。

$A,B$ を集合とし、$\Gamma=(A,B,R)$ と $\Gamma'=(A,B,R')$ をともに $A$ から $B$ への対応とする。
このとき、
$$ \Gamma\ne\Gamma' \Longleftrightarrow R\ne R' $$
である。
また、対応の値を用いれば、
$$ \Gamma\ne\Gamma' \Longleftrightarrow \exists a\in A\ \bigl(\Gamma(a)\ne\Gamma'(a)\bigr) $$
である。
実際、
$$ \begin{align} \Gamma\ne\Gamma' &\Longleftrightarrow \neg\forall a\in A\ \bigl(\Gamma(a)=\Gamma'(a)\bigr)\\ &\Longleftrightarrow \exists a\in A\ \neg\bigl(\Gamma(a)=\Gamma'(a)\bigr)\\ &\Longleftrightarrow \exists a\in A\ \bigl(\Gamma(a)\ne\Gamma'(a)\bigr) \end{align} $$
である( 証明はコチラ )。

左辺の $\Gamma(\{a\})$ は対応 $\Gamma$ による集合 $\{a\}$ の像を表し、
右辺の $\Gamma(a)$ は対応 $\Gamma$ の $a$ における値を表す。

特に、$S=A$ のとき、
$$ \Gamma(A)=\operatorname{ran}(\Gamma) $$
が成り立つ。