対応 ①

本トピック【対応】では、まず集合 $A$ の各元 $a\in A$ に対して、集合 $B$ の部分集合をただ $1$ つ定める規則として『対応』を定義する。
その後、$A$ から $B$ への対応を定めることと、二項関係 $R\subseteq A\times B$ を定めることが、
互いに一意に復元できるという意味で本質的に同じであることを示す。
$ $
そこで次回以降は、対応を $3$ つ組 $(A,B,R)$ として再定義して議論を進める(事にした)。
そのため、対応において成り立つ性質の多くは、すでに示した二項関係に関する性質と重複することがある(;'∀')

文献によっては、$A$ から $B$ への対応を
$$ \Gamma:A\to B $$
のように書くことがある。
しかし、この記法は通常の意味での写像 $A\to B$ ではなく、各 $a\in A$ に対して $B$ の部分集合を対応させる規則を表す略記である。
本ノートでは、今後扱う通常の写像との混同を避けるため、対応は原則として
$$ \Gamma:A\to\mathcal{P}(B) $$
と書く。

対応の規則を明示するときには、
$$ A\ni x\mapsto \Gamma(x)\in\mathcal{P}(B) $$
のように書くことがある。
これは、$x$ が $A$ の元であり、その $x$ に対して $\Gamma(x)$ がただ $1$ つ定まり、さらに $\Gamma(x)$ が $\mathcal{P}(B)$ の元であることを表している。

対応 $\Gamma:A\to\mathcal{P}(B)$ において、各 $a\in A$ に対する値 $\Gamma(a)$ は $B$ の元ではなく、$B$ の部分集合である。
すなわち、
$$ \Gamma(a)\in\mathcal{P}(B) $$
であり、同値に
$$ \Gamma(a)\subseteq B $$
である。
したがって、対応は「要素 $a$ に要素 $b$ を対応させる規則」ではなく、
「要素 $a$ に集合を対応させる規則(対応)」である点に注意されたい。
集合を大文字の$A,B,C,\cdots$で表す事に慣れていると、$\Gamma(a)$ という表記は最初は戸惑うかもしれない。

対応 $\Gamma:A\to\mathcal{P}(B)$ では、各 $a\in A$ に対して $\Gamma(a)$ がただ $1$ つ定まる。
ただし、これは異なる元が異なる値を持つことを意味しない点に注意である。
したがって、$a,a'\in A$ かつ $a\ne a'$ であっても、
$$ \Gamma(a)=\Gamma(a') $$
となってよい。

空集合は任意の集合 $B$ の部分集合( 証明はこちら )であるから、
$$ \varnothing\subseteq B $$
が成り立ち、したがって
$$ \varnothing\in\mathcal{P}(B) $$
が成り立つ( 証明はコチラ )。ゆえに、ある $a\in A$ に対して
$$ \Gamma(a)=\varnothing $$
となることを許す。

$A=\{1,2,3\}$、$B=\{\alpha,\beta,\gamma\}$ とする。
規則 $\Gamma$ を
$$ \Gamma(1)=\{\alpha,\beta\}, \quad \Gamma(2)=\{\beta\}, \quad \Gamma(3)=\varnothing $$
によって定める。
このとき、各 $x\in A$ に対して $\Gamma(x)$ はただ $1$ つ定まっている。
また、
$$ \Gamma(1)\subseteq B, \quad \Gamma(2)\subseteq B, \quad \Gamma(3)\subseteq B $$
である。
したがって、任意の $x\in A$ に対して
$$ \Gamma(x)\in\mathcal P(B) $$
が成り立つ。
ゆえに、
$$ \Gamma:A\to\mathcal{P}(B) $$
は $A$ から $B$ への対応である。

対応 $\Gamma:A\to\mathcal P(B)$ は、任意の $a\in A$ に対して $\Gamma(a)$ を定める。
したがって、規則としての $\Gamma$ は始集合 $A$ のすべての元で定義されている。
一方で、本ノートでいう対応の定義域
$$ \operatorname{dom}(\Gamma) = \{a\in A\mid \Gamma(a)\ne\varnothing\} $$
は、$\Gamma$ が非空の値を持つ点全体である。
したがって、一般には
$$ \operatorname{dom}(\Gamma)\subseteq A $$
であり、
$$ \operatorname{dom}(\Gamma)\ne A $$
となることがある。

$A,B$ を集合とし、$\Gamma:A\to\mathcal P(B)$ を $A$ から $B$ への対応とする。
対応の定義域の定義より、$\Gamma$ が全域的であることは、
$$ \operatorname{dom}(\Gamma)=A $$
が成り立つことと同値である。
また、
$$ \operatorname{dom}(\Gamma) = \{a\in A\mid \Gamma(a)\ne\varnothing\} $$
であるから、これは
$$ \forall a\in A\ \bigl(\Gamma(a)\ne\varnothing\bigr) $$
が成り立つことと同値である。
したがって、全域的対応とは、始集合 $A$ のすべての元に対して、少なくとも $1$ つの終集合 $B$ の元が対応している対応である。

$S\subseteq A$ に対して、
$$ \Gamma(S) = \{b\in B\mid \exists a\in S\ (b\in\Gamma(a))\} $$
である。
この集合を簡潔に表すために、
$$ \Gamma(S) = \bigcup_{a\in S}\Gamma(a) $$
と書くことがある。
この記法は、$S$ の元 $a$ に対する集合 $\Gamma(a)$ をすべて合わせた集合を表している(※)。
※ 集合族は写像の後で扱うべき内容と判断しており、このような導入の仕方になる(;'∀')

対応の値域は、
$$ \operatorname{ran}(\Gamma) = \{b\in B\mid \exists a\in A\ (b\in\Gamma(a))\} $$
である。
この集合を簡潔に表すために、
$$ \operatorname{ran}(\Gamma) = \bigcup_{a\in A}\Gamma(a) $$
と書くことがある。
したがって、対応の値域とは、始集合 $A$ の元に対応する $B$ の元をすべて集めた集合である(※)。
※ 集合族は写像の後で扱うべき内容と判断しており、このような導入の仕方になる(;'∀')

上の定義における
$$ \forall a\in A\ \bigl(\Gamma(a)=\Gamma'(a)\bigr) $$
は、$A=A'$ が成り立っている状況で、同じ元 $a$ に対する値を比較しているという意味である。
実際、$\Gamma'$ は $A'$ 上の対応であるから、$A\ne A'$ の場合には、一般には $a\in A$ に対して $\Gamma'(a)$ が定義されているとは限らない。
したがって、対応の相等では、まず始集合と終集合が一致することを要求し、そのうえで各点における値が一致することを要求する。

$A,B$ を集合とし、
$$ \Gamma:A\to\mathcal P(B), \quad \Gamma':A\to\mathcal P(B) $$
をともに $A$ から $B$ への対応とする。
このとき、
$$ \Gamma=\Gamma' \Longleftrightarrow \forall a\in A\ \bigl(\Gamma(a)=\Gamma'(a)\bigr) $$
が成り立つ。

$A,B,A',B'$ を集合とし、
$$ \Gamma:A\to\mathcal P(B), \quad \Gamma':A'\to\mathcal P(B') $$
をそれぞれ対応とする。
対応の相等の定義より、$\Gamma=\Gamma'$ であるとは、
$$ A=A', \quad B=B', \quad \forall a\in A\ \bigl(\Gamma(a)=\Gamma'(a)\bigr) $$
がすべて成り立つことである。
したがって、$\Gamma\ne\Gamma'$ であるとは、次のいずれかが成り立つことである。
$$ A\ne A' \ \lor\ B\ne B' \ \lor\ \Bigl(A=A'\land B=B'\land \exists a\in A\ \bigl(\Gamma(a)\ne\Gamma'(a)\bigr)\Bigr) $$
ここで、最後の条件に $A=A'$ と $B=B'$ を入れているのは、$\Gamma(a)$ と $\Gamma'(a)$ を同じ $a$ に対して比較できるようにするためである。
実際、$\Gamma'$ は $A'$ 上の対応であるから、$A\ne A'$ の場合には、一般には $a\in A$ に対して $\Gamma'(a)$ が定義されているとは限らない。
ゆえに、始集合または終集合が異なる場合には、値を比較する以前に、対応として等しくない。

$A,B$ を集合とし、
$$ \Gamma:A\to\mathcal P(B), \quad \Gamma':A\to\mathcal P(B) $$
をともに $A$ から $B$ への対応とする。
このとき、
$$ \Gamma=\Gamma' \Longleftrightarrow \forall a\in A\ \bigl(\Gamma(a)=\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} $$
である( 証明はコチラ )。
したがって、同じ始集合 $A$ から同じ終集合 $B$ への対応同士を比較している場合には、
$$ \Gamma\ne\Gamma' \Longleftrightarrow \exists a\in A\ \bigl(\Gamma(a)\ne\Gamma'(a)\bigr) $$
と書いてよい。

$A,B$ を集合とし、$R\subseteq A\times B$ を二項関係とする。
各 $a\in A$ に対して、
$$ \Gamma_R(a) := \{b\in B\mid (a,b)\in R\} $$
と定める。
このとき、任意の $a\in A$ に対して、
$$ \Gamma_R(a)\subseteq B $$
であるから、
$$ \Gamma_R(a)\in\mathcal P(B) $$
である。
したがって、
$$ \Gamma_R:A\to\mathcal P(B) $$
は $A$ から $B$ への対応である。
さらに、任意の $a\in A$ と $b\in B$ に対して、
$$ b\in\Gamma_R(a) \Longleftrightarrow (a,b)\in R $$
が成り立つ。
したがって、二項関係 $R$ は、各 $a\in A$ に対して、それに対応する $b\in B$ 全体の集合 $\Gamma_R(a)$ を与える対応として見ることができる。

$A=\{1,2,3\}$、$B=\{a,b,c\}$ とする。
対応 $\Gamma:A\to\mathcal{P}(B)$ を
$$ \Gamma(1)=\{a,c\}, \quad \Gamma(2)=\{b\}, \quad \Gamma(3)=\varnothing $$
によって定める。
このとき、対応 $\Gamma$ のグラフ $G(\Gamma)$ は定義より、
$$ G(\Gamma) = \{(x,y)\in A\times B\mid y\in\Gamma(x)\} $$
であるから、
$$ G(\Gamma) = \{(1,a),(1,c),(2,b)\} $$
となる。
実際、
$$ a\in\Gamma(1), \quad c\in\Gamma(1), \quad b\in\Gamma(2) $$
であるので、
$$ (1,a)\in G(\Gamma), \quad (1,c)\in G(\Gamma), \quad (2,b)\in G(\Gamma) $$
が成り立つ。
一方で、
$$ \Gamma(3)=\varnothing $$
であるから、$3$ に対しては $G(\Gamma)$ に属する順序対は存在しない。
したがって、$G(\Gamma)$ とは、各 $a\in A$ に対して $\Gamma(a)$ に入っている $b\in B$ を順序対 $(a,b)$ の形で集めた集合である。

$A,B$ を集合とし、$\Gamma:A\to\mathcal P(B)$ を対応とする。
任意の $a\in A$ と $b\in B$ に対して、対応のグラフの定義より、
$$ (a,b)\in G(\Gamma) \Longleftrightarrow b\in\Gamma(a) $$
が成り立つ。
また、$G(\Gamma)\subseteq A\times B$ であるから、任意の対象 $x,y$ に対して、
$$ (x,y)\in G(\Gamma) \Longleftrightarrow \bigl(x\in A\land y\in B\land y\in\Gamma(x)\bigr) $$
が成り立つ。
ただし、右辺の $y\in\Gamma(x)$ は、$x\in A$ によって $\Gamma(x)$ が定義されている状況で読まれる。

ここでいう『グラフ』とは、座標平面上に描かれた図そのものではなく、対応を表す順序対の集合のことである。
実際、対応 $\Gamma:A\to\mathcal P(B)$ のグラフ
$$ G(\Gamma) = \{(a,b)\in A\times B\mid b\in\Gamma(a)\} $$
は、$A$ の元 $a$ と、それに対応する $B$ の元 $b$ との順序対をすべて集めた集合である。
$ $
この意味で、高校数学で見る座標平面上の関数 $y=f(x)$ のグラフは、対応のグラフの特別な場合として理解できる。
実際、$A,B\subseteq\mathbb R$ とし、関数
$$ y=f(x) $$
が与えられているとする。このとき、$f$ のグラフは
$$ G(f) = \{(x,y)\in A\times B\mid y=f(x)\} $$
で定義される順序対の集合である。
この順序対の集合を座標平面上の点として表したものが、いわゆる「関数のグラフ」と呼ばれる図である。
$ $
ただし、関数の場合には、各 $x\in A$ に対して対応する元 $f(x)\in B$ がただ $1$ つ定まる。
そのため、初等的な関数では、座標平面上のグラフは直線や曲線として表されることが多い。
$ $
一方、対応 $\Gamma:A\to\mathcal P(B)$ の場合には、各 $a\in A$ に対して定まる値は、$B$ の $1$ つの元ではなく、$B$ の部分集合 $\Gamma(a)$ である。
したがって、ある $a\in A$ に対して、対応する $b\in B$ が存在しないこともあれば、ただ $1$ つ存在することもあり、複数存在することもある。
$ $
そのため、$A,B\subseteq\mathbb R$ の場合でも、対応のグラフは直線や曲線に限られない。
たとえば、点の集合、曲線の集まり、縦方向の線分の集まり、あるいは平面上の領域のように表されることがある。
$ $
したがって、関数のグラフは、対応のグラフのうち、各 $x\in A$ に対して対応する $y\in B$ がただ $1$ つに限られる特別な場合である。
逆にいえば、対応のグラフは、関数のグラフの考え方を一般化したものと見ることができる。
$ $
ただし、$A$ や $B$ の元が必ずしも数であるとは限らない。
ゆえに、グラフはまず座標平面上の図ではなく、順序対の集合として理解するのが自然である。

ややこしいことに、数学では『グラフ』という語が別の文脈(分野)の中でも異なる意味で用いられる。
グラフ理論でいうグラフは、通常、『頂点の集合』と『辺の集合』からなる別種の数学的対象であり、
本稿で扱う順序対の集合そのものを指すわけではない。
$ $
したがって、本稿で「グラフ」というときは、
特に断らない限り、対応や関数に付随する順序対の集合を意味し、グラフ理論のグラフとは区別して考える。
$ $
グラフ理論のWikipediaリンク
$ $
グラフ理論は、ソーシャルネットワークや分子構造、交通網など、さまざまな複雑な構造を表現するための強力な枠組みである。近年では、グラフニューラルネットワークの発展により、機械学習の分野でも重要性が一段と高まっている(らしい)。

この命題は、対応をグラフに変換しても、各点 $a\in A$ における値 $\Gamma(a)$ を完全に復元できることを示している。
そのため、対応を調べることと、そのグラフを調べることは密接に関係している。

命題
$$ \Gamma_{G(\Gamma)}=\Gamma $$
と命題
$$ G(\Gamma_G)=G $$
は、互いに逆向きの復元を表している。

1. まず、
   $$ \Gamma_{G(\Gamma)}=\Gamma $$
   は、対応 $\Gamma$ からグラフ $G(\Gamma)$ を作り、そのグラフから対応を作り直すと、もとの対応 $\Gamma$ に戻ることを意味する。
   すなわち、
   $$ \Gamma \longmapsto G(\Gamma) \longmapsto \Gamma_{G(\Gamma)} $$
   という操作を行うと、
   $$ \Gamma_{G(\Gamma)}=\Gamma $$
   となる。
2. 一方、
   $$ G(\Gamma_G)=G $$
   は、部分集合 $G\subseteq A\times B$ から対応 $\Gamma_G$ を作り、その対応のグラフを取ると、もとの $G$ に戻ることを意味する。
   すなわち、
   $$ G \longmapsto \Gamma_G \longmapsto G(\Gamma_G) $$
   という操作を行うと、
   $$ G(\Gamma_G)=G $$
   となる。

-したがって、これら $2$ つの命題を合わせると、対応とグラフは互いに情報を失わずに行き来できることが分かる。
つまり、$A$ から $B$ への対応を定めることと、$A\times B$ の部分集合を定めることは、
互いに一意に復元できるという意味で本質的に同じである。
$ $
この意味で、対応は「各点に集合を対応させる規則」として見ることもできるし、
「$A\times B$ の部分集合」、すなわち二項関係として見ることもできる。

この命題では、単に $G=G(\Gamma)$ となる対応 $\Gamma$ が存在するだけでなく、そのような対応がただ $1$ つであることも主張している。
一意性とは、もし別の対応
$$ \Delta:A\to\mathcal P(B) $$
が
$$ G(\Delta)=G $$
を満たすならば、必ず
$$ \Delta=\Gamma_G $$
となる、という意味である。

命題
$$ G=G(\Gamma) $$
となる $A$ から $B$ への対応 $\Gamma:A\to\mathcal P(B)$ がただ $1$ つ存在する、という主張では、
集合 $A$ と $B$ をあらかじめ固定していることが重要である。
$ $
実際、グラフ $G\subseteq A\times B$ だけを見ると、$\Gamma(a)=\varnothing$ となる $a\in A$ は順序対の第 $1$ 成分として現れない。
また、どの $a\in A$ に対しても対応しない $b\in B$ は、順序対の第 $2$ 成分として現れない。
$ $
したがって、グラフ $G$ だけからは、一般には始集合 $A$ や終集合 $B$ を完全には復元できない。
本命題は、$A$ と $B$ を固定したうえで、$G\subseteq A\times B$ から対応
$$ \Gamma_G:A\to\mathcal P(B) $$
がただ $1$ つ定まることを述べている。

これまで、$A$ から $B$ への対応を、
各 $a\in A$ に対して $B$ の部分集合 $\Gamma(a)\in\mathcal P(B)$ をただ $1$ つ定める規則として扱ってきた。
一方で、以上の命題より、対応 $\Gamma:A\to\mathcal P(B)$ を定めることと、そのグラフ
$$ G(\Gamma) = \{(a,b)\in A\times B\mid b\in\Gamma(a)\} $$
を定めることは、互いに一意に復元できるという意味で本質的に同じである。

1. そこで、対応を
   $$ (A,B,R) $$
   という $3$ つ組として定義する事ができる。
   この流儀では、$A,B$ を集合とし、
   $$ R\subseteq A\times B $$
   を $A$ から $B$ への二項関係とするとき、$3$ つ組
   $$ \Gamma:=(A,B,R) $$
   を $A$ から $B$ への対応と定義する事ができる。
   $ $
2. このとき、$A$ を対応 $\Gamma$ の始集合、$B$ を対応 $\Gamma$ の終集合、$R$ を対応 $\Gamma$ のグラフという。
   また、この対応 $\Gamma=(A,B,R)$ の各 $a\in A$ における値を
   $$ \Gamma(a) := \{b\in B\mid (a,b)\in R\} $$
   で定義する。
   この定義により、対応 $\Gamma=(A,B,R)$ は、各 $a\in A$ に対して $B$ の部分集合 $\Gamma(a)$ を定める規則として読むことができる。
   したがって、$3$ つ組としての対応
   $$ \Gamma=(A,B,R) $$
   と、規則としての対応
   $$ \Gamma:A\to\mathcal P(B) $$
   は、グラフを介して互いに行き来できる。