対応
Contents
対応とは
集合 $A$ から集合 $B$ への 対応 (英:correspondence) とは、$A$ の元 $a$ から、$B$ の部分集合 $\varGamma(a)$ を定める規則 $\varGamma$ のこと。このとき、$\varGamma(a)$ を $\varGamma$ による $a$ の像 (英:image)、$A$ を $\varGamma$ の始集合 (英:initial set)、$B$ を $\varGamma$ の終集合 (英:final set) と呼ぶ。$A$ から $B$ への $\varGamma$ は次式で表される。
\[ \varGamma : A\to B \]
対応は始集合の元に伴う、終集合の元の割り当てを広く指す概念であるため、以下全てを許容する。
- 始集合の元 $a\in A$ から、終集合の元 $b\in B$ への一対一の割り当て
- 始集合の元 $a\in A$ から、終集合の元 $b\in B$ への一対多の割り当て
- 始集合の元 $a\in A$ から、終集合の元 $b\in B$ への多対一の割り当て
- 始集合の元 $a\in A$ から、終集合の元 $b\in B$ への一対零の割り当て
対応の相等
集合 $A$ から集合 $B$ への対応 $\varGamma_1,\varGamma_2$ が与えられたとき、$\varGamma_1$ または $\varGamma_2$ によって定まる $A$ の元 $a$ において像 $\varGamma_1(a)$ と像 $\varGamma_2(b)$ が常に等しい限り、$\varGamma_1$ と $\varGamma_2$ は等しい。 \( \forall a~(\varGamma_1(a) = \varGamma_2(a)) \lrArr \varGamma_1=\varGamma_2 \)
対応とグラフ
集合 $A$ から集合 $B$ への対応 $\varGamma$ が与えられとき、$A$ の元 $a$ と像 $\varGamma(a)$ の元 $b$ の順序対からなる集合のことを $\varGamma$ のグラフ (英:graph) と呼び $G(\varGamma)$ で表す。また、$G(\varGamma)$ は $A$ と $B$ の直積集合の部分集合である。対応とグラフの関係から、グラフがあれば対応が一意に存在し、対応があればグラフが一意に存在する。空のグラフもなり得る。
\[ G(\varGamma) := \lbrace(a,b)\mid (a,b)\in A\times B, ~ b\in\varGamma(a)\rbrace \]
グラフの相等
グラフは対応により一意に定まることから、二つの対応が等しいとき、そのグラフもまた等しい。
\[ G(\varGamma_1) = G(\varGamma_2) \lrArr \varGamma_1 = \varGamma_2 \]
逆対応
逆対応 (英:inverse correspondence) とは、対応 $\varGamma$ のグラフ $G(\varGamma)$ の順序対の順序を入れ替えたもの。また、逆対応により定まる $\varGamma^{-1}(b)$ を逆像 (英:inverse image) という。
\[ G(\varGamma^{-1}) := \lbrace (b,a)\mid (a,b)\in G(\varGamma)\rbrace \]
対応の定義域と値域
対応 $\varGamma:A\to B$ の定義域 (英:domain of definition) とは、対応のグラフにおいて、グラフに伴う終集合の元 $b\in B$ が少なくとも一つ以上存在するときの始集合の元 $a\in A$ の集まりのこと。
\[ \operatorname{dom}(\varGamma) := \lbrace a\in A\mid\exists b\in B, ~(a,b)\in G(\varGamma)\rbrace \]
また反対に、グラフに伴う始集合の元 $a\in A$ が少なくとも一つ以上存在するときの終集合の元 $b\in B$ の集まりのことを、値域 (英:range of values) という。 \( \operatorname{ran}(\varGamma) := \lbrace b\in B\mid\exists a\in A, ~(a,b)\in G(\varGamma)\rbrace \)