対応 ⑨
記事 『
対応①
』 の冒頭でも述べた通り、$A,B$ を固定すると、$A$ から $B$ への対応 $\Gamma=(A,B,R)$ を定めることと、二項関係 $R\subseteq A\times B$ を定めることは、互いに一意に復元できるという意味で本質的に同じである。
$ $
したがって、対応において成り立つ性質の多くは、すでに示した二項関係に関する性質と重複する部分も出てくる。しかし、本稿で扱う逆対応ならびに次回の合成対応については、改めて証明を示す方針で進める。
Def.
$A,B$ を集合とし、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
このとき、
$$
R^{-1}:=\{(b,a)\in B\times A\mid (a,b)\in R\}
$$
と定め、さらに
$$
\Gamma^{-1}:=(B,A,R^{-1})
$$
と定める。この $\Gamma^{-1}$ を、$\Gamma$ の逆対応という。
$A,B$ を集合とし、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
逆対応の定義より、
$$
R^{-1}:=\{(b,a)\in B\times A\mid (a,b)\in R\}
$$
である。したがって、
$$
R^{-1}\subseteq B\times A
$$
が成り立つ。ゆえに、
$$
(B,A,R^{-1})
$$
は $B$ から $A$ への対応である。
したがって、
$$
\Gamma^{-1}=(B,A,R^{-1})
$$
は $B$ から $A$ への対応として定まる。
したがって、一般の対応に対して成り立つ集合の像に関する公式は、$\Gamma^{-1}$ にもそのまま適用できる。
すなわち、一般の対応 $\Delta=(X,Y,Q)$ に関する公式において、
$$ \Delta=\Gamma^{-1},\quad X=B,\quad Y=A $$
とおけばよい。
特に、$T_1,T_2\subseteq B$ に対して、
$$
\begin{align}
1.\ \ &\Gamma^{-1}(T_1\cup T_2)
=
\Gamma^{-1}(T_1)\cup\Gamma^{-1}(T_2),\\
2.\ \ &\Gamma^{-1}(T_1\cap T_2)
\subseteq
\Gamma^{-1}(T_1)\cap\Gamma^{-1}(T_2),\\
3.\ \ &T_1\subseteq T_2
\Longrightarrow
\Gamma^{-1}(T_1)\subseteq\Gamma^{-1}(T_2),\\
4.\ \ &\Gamma^{-1}(T_1)\setminus\Gamma^{-1}(T_2)
\subseteq
\Gamma^{-1}(T_1\setminus T_2)
\end{align}
$$
が成り立つ。
これらは逆対応に固有の新しい性質というより、$\Gamma^{-1}$ が $B$ から $A$ への対応であることから、
一般の対応に関する集合の像の公式を適用したものである。
$A,B$ を集合とし、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
$\Gamma^{-1}=(B,A,R^{-1})$ を $\Gamma$ の逆対応とする。各 $b\in B$ に対して、$b$ における逆対応 $\Gamma^{-1}$ の値を
$$
(\Gamma^{-1})(b):=\{a\in A\mid (b,a)\in R^{-1}\}
$$
で定義する。
$A,B$ を集合とし、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
また、$\Gamma^{-1}=(B,A,R^{-1})$ を $\Gamma$ の逆対応とする。
$ $
- このとき、任意の $b\in B$ に対して、
$$ \Gamma^{-1}(b)=\{a\in A\mid (a,b)\in R\} $$
が成り立つ。
実際、逆対応の値の定義より、
$$ \begin{align} \Gamma^{-1}(b) &= \{a\in A\mid (b,a)\in R^{-1}\}\\ &= \{a\in A\mid (a,b)\in R\} \end{align} $$
である。
$ $ - さらに、対応の値の定義より、任意の $a\in A$ と $b\in B$ に対して、
$$ b\in\Gamma(a) \Longleftrightarrow (a,b)\in R $$
である。
したがって、任意の $b\in B$ に対して、
$$ \Gamma^{-1}(b) = \{a\in A\mid b\in\Gamma(a)\} $$
が成り立つ。
-この集合 $(\Gamma^{-1})(b)$ を、元の対応 $\Gamma$ に関する $b$ の逆像、または $b$ に対応するファイバーという。
$A,B$ を集合とし、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
また、$\Gamma^{-1}=(B,A,R^{-1})$ を $\Gamma$ の逆対応とする。
対応のグラフの定義より、
$$
G(\Gamma)=R,
\qquad
G(\Gamma^{-1})=R^{-1}
$$
である。
したがって、
$$
G(\Gamma^{-1})
=
\{(b,a)\in B\times A\mid (a,b)\in G(\Gamma)\}
$$
が成り立つ。
すなわち、逆対応のグラフは、もとの対応のグラフの順序対の成分を入れ替えたものである。
本稿では、対応を始集合 $A$ と終集合 $B$、そして二項関係 $R$ の$3$つ組 $(A,B,R)$ で定義している。
対応規則の視点からは以下のように定義が与えられる。
$ $
$\Gamma:A\to\mathcal{P}(B)$ を対応とする。このとき、各 $b\in B$ に対して
$$
\Gamma^{-1}(b):=\{a\in A\mid b\in \Gamma(a)\}
$$
と定める。ここで、右辺は $A$ の部分集合であるから
$$
\Gamma^{-1}(b)\in\mathcal{P}(A)
$$
が成り立つ。したがって、
$$
\Gamma^{-1}:B\to\mathcal{P}(A)
$$
は $B$ から $A$ への対応である。この対応 $\Gamma^{-1}$ を、$\Gamma$ の逆対応という。
Prop&Proof
$A,B$ を集合とし、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
また、$\Gamma^{-1}=(B,A,R^{-1})$ を $\Gamma$ の逆対応とする。このとき、
$$
\operatorname{dom}(\Gamma^{-1})=\operatorname{ran}(\Gamma)
$$
が成り立つ。
外延性により、任意の $b$ に対して、
$$
b\in\operatorname{dom}(\Gamma^{-1})
\Longleftrightarrow
b\in\operatorname{ran}(\Gamma)
$$
が成り立つことを示せば十分である。
任意に $b$ をとる。
- 逆対応の定義より、
$$ R^{-1} = \{(y,x)\in B\times A\mid (x,y)\in R\} $$
である。
したがって、任意の $a\in A$ と $b\in B$ に対して、
$$ (b,a)\in R^{-1} \Longleftrightarrow (a,b)\in R $$
が成り立つ。
まず、$\Gamma^{-1}=(B,A,R^{-1})$ は $B$ から $A$ への対応であるから、定義域の定義より、
$$ \operatorname{dom}(\Gamma^{-1}) = \{b\in B\mid \exists a\in A\ ((b,a)\in R^{-1})\} $$
である。ゆえに、
$$ b\in\operatorname{dom}(\Gamma^{-1}) \Longleftrightarrow b\in B\land\exists a\in A\ ((b,a)\in R^{-1}) $$
である。
上の逆対応の定義より、
$$ b\in B\land\exists a\in A\ ((b,a)\in R^{-1}) \Longleftrightarrow b\in B\land\exists a\in A\ ((a,b)\in R) $$
である。
$ $ - 一方、$\Gamma=(A,B,R)$ の値域の定義より、
$$ \operatorname{ran}(\Gamma) = \{b\in B\mid \exists a\in A\ ((a,b)\in R)\} $$
である。したがって、
$$ b\in\operatorname{ran}(\Gamma) \Longleftrightarrow b\in B\land\exists a\in A\ ((a,b)\in R) $$
である。
-以上より、
$$
b\in\operatorname{dom}(\Gamma^{-1})
\Longleftrightarrow
b\in\operatorname{ran}(\Gamma)
$$
が成り立つ。$b$ は任意であったから、外延性により、
$$
\operatorname{dom}(\Gamma^{-1})=\operatorname{ran}(\Gamma)
$$
を得る。
$$ \Box$$
$A,B$ を集合とし、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
また、$\Gamma^{-1}=(B,A,R^{-1})$ を $\Gamma$ の逆対応とする。このとき、
$$
\operatorname{ran}(\Gamma^{-1})=\operatorname{dom}(\Gamma)
$$
が成り立つ。
外延性により、任意の $a$ に対して、
$$
a\in\operatorname{ran}(\Gamma^{-1})
\Longleftrightarrow
a\in\operatorname{dom}(\Gamma)
$$
が成り立つことを示せば十分である。
任意に $a$ をとる。
- 逆対応の定義より、
$$ R^{-1} = \{(b,x)\in B\times A\mid (x,b)\in R\} $$
である。
したがって、任意の $a\in A$ と $b\in B$ に対して、
$$ (b,a)\in R^{-1} \Longleftrightarrow (a,b)\in R $$
が成り立つ。
まず、$\Gamma^{-1}=(B,A,R^{-1})$ は $B$ から $A$ への対応であるから、値域の定義より、
$$ \operatorname{ran}(\Gamma^{-1}) = \{a\in A\mid \exists b\in B\ ((b,a)\in R^{-1})\} $$
である。
ゆえに、
$$ a\in\operatorname{ran}(\Gamma^{-1}) \Longleftrightarrow a\in A\land\exists b\in B\ ((b,a)\in R^{-1}) $$
である。
上の逆対応の定義より、
$$ a\in A\land\exists b\in B\ ((b,a)\in R^{-1}) \Longleftrightarrow a\in A\land\exists b\in B\ ((a,b)\in R) $$
である。
$ $ - 一方、$\Gamma=(A,B,R)$ の定義域の定義より、
$$ \operatorname{dom}(\Gamma) = \{a\in A\mid \exists b\in B\ ((a,b)\in R)\} $$
である。したがって、
$$ a\in\operatorname{dom}(\Gamma) \Longleftrightarrow a\in A\land\exists b\in B\ ((a,b)\in R) $$
である。
-以上より、
$$
a\in\operatorname{ran}(\Gamma^{-1})
\Longleftrightarrow
a\in\operatorname{dom}(\Gamma)
$$
が成り立つ。
$a$ は任意であったから、外延性により、
$$
\operatorname{ran}(\Gamma^{-1})=\operatorname{dom}(\Gamma)
$$
を得る。
$$ \Box$$
$A,B$ を集合とし、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
また、$\Gamma^{-1}=(B,A,R^{-1})$ を $\Gamma$ の逆対応とする。このとき、
$$
(\Gamma^{-1})^{-1}=\Gamma
$$
が成り立つ。
- 逆対応の定義より、
$$ \Gamma^{-1}=(B,A,R^{-1}) $$
であり、
$$ R^{-1} = \{(b,a)\in B\times A\mid (a,b)\in R\} $$
である。
さらに、$\Gamma^{-1}$ の逆対応は、
$$ (\Gamma^{-1})^{-1}=(A,B,(R^{-1})^{-1}) $$
であり、
$$ (R^{-1})^{-1} = \{(a,b)\in A\times B\mid (b,a)\in R^{-1}\} $$
である。
したがって、$(\Gamma^{-1})^{-1}=\Gamma$ を示すには、
$$ (R^{-1})^{-1}=R $$
を示せばよい。
$ $ - 外延性により、任意の順序対 $(a,b)$ に対して、
$$ (a,b)\in(R^{-1})^{-1} \Longleftrightarrow (a,b)\in R $$
が成り立つことを示す。
任意の順序対 $(a,b)$ をとる。逆関係の定義より、
$$ \begin{align} (a,b)\in(R^{-1})^{-1} &\Longleftrightarrow (a,b)\in A\times B\land(b,a)\in R^{-1}\\ &\Longleftrightarrow a\in A\land b\in B\land(b,a)\in R^{-1} \end{align} $$
である。
また、$R^{-1}$ の定義より、
$$ (b,a)\in R^{-1} \Longleftrightarrow (b,a)\in B\times A\land(a,b)\in R $$
である。ここで、
$$ (b,a)\in B\times A \Longleftrightarrow b\in B\land a\in A $$
であるから、
$$ \begin{align} (a,b)\in(R^{-1})^{-1} &\Longleftrightarrow a\in A\land b\in B\land(a,b)\in R \end{align} $$
である。
$ $ - 一方、$\Gamma=(A,B,R)$ は $A$ から $B$ への対応であるから、
$$ R\subseteq A\times B $$
である。したがって、
$$ (a,b)\in R \Longrightarrow a\in A\land b\in B $$
が成り立つ。
ゆえに、
$$ a\in A\land b\in B\land(a,b)\in R \Longleftrightarrow (a,b)\in R $$
である。
-以上より、
$$
(a,b)\in(R^{-1})^{-1}
\Longleftrightarrow
(a,b)\in R
$$
が成り立つ。$(a,b)$ は任意であったから、外延性により、
$$
(R^{-1})^{-1}=R
$$
である。
したがって、
$$
(\Gamma^{-1})^{-1}
=
(A,B,(R^{-1})^{-1})
=
(A,B,R)
=
\Gamma
$$
である。
$$ \Box$$
既に示した命題より、任意の対応 $\Delta$ に対して、
$$
\operatorname{dom}(\Delta^{-1})=\operatorname{ran}(\Delta)
$$
が成り立つ。ここで、
$$
\Delta:=\Gamma^{-1}
$$
とおくと、
$$
\operatorname{dom}\bigl((\Gamma^{-1})^{-1}\bigr)
=
\operatorname{ran}(\Gamma^{-1})
$$
を得る。
一方、本命題より、
$$
(\Gamma^{-1})^{-1}=\Gamma
$$
であるから、
$$
\operatorname{dom}\bigl((\Gamma^{-1})^{-1}\bigr)
=
\operatorname{dom}(\Gamma)
$$
である。
したがって、
$$
\operatorname{ran}(\Gamma^{-1})
=
\operatorname{dom}(\Gamma)
$$
が成り立つ。
すなわち、逆対応の値域と元の対応の定義域が一致することは、逆対応の定義域と対応の値域に関する命題を $\Gamma^{-1}$ に適用し、
さらに $(\Gamma^{-1})^{-1}=\Gamma$ を用いることによっても導ける。
この記事を高評価した人
この記事に送られたバッジ
投稿者
