対応 ⑥
Def.
$A,B$ を集合とし、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
また、$S\subseteq A$ とする。
このとき、
$$
R|_S:=R\cap(S\times B)
$$
と定め、さらに
$$
\Gamma|_S:=(S,B,R|_S)
$$
と定める。
この $\Gamma|_S$ を、対応 $\Gamma$ の $S$ への制限という。
本稿では、対応を始集合 $A$、終集合 $B$、および二項関係 $R$ の $3$ つ組 $(A,B,R)$ で定義している。
一方、対応 $\Gamma=(A,B,R)$ に対応する集合値写像を、同じ記号で
$$
\Gamma:A\to\mathcal P(B)
$$
と表すならば、各 $x\in A$ に対して
$$
\Gamma(x)=\{b\in B\mid (x,b)\in R\}
$$
である。
このとき、$S\subseteq A$ に対する制限 $\Gamma|_S=(S,B,R|_S)$ は、対応規則の視点からは、各 $x\in S$ に対して
$$
\Gamma|_S(x)=\Gamma(x)
$$
を満たす対応
$$
\Gamma|_S:S\to\mathcal P(B)
$$
である。
つまり、対応の制限とは、始集合を $S$ に狭め、$S$ 上では元の対応と同じ値を与える対応である。
$A,A',B$ を集合とし、
$$
A\subseteq A'
$$
とする。
また、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とし、$\widetilde{\Gamma}=(A',B,\widetilde R)$ を $A'$ から $B$ への対応とする。
このとき、
$$
\widetilde R\cap(A\times B)=R
$$
が成り立つならば、$\widetilde{\Gamma}$ を $\Gamma$ の $A'$ への拡張という。
$A,A',B$ を集合とし、$A\subseteq A'$ とする。
また、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とし、$\widetilde{\Gamma}=(A',B,\widetilde R)$ を $A'$ から $B$ への対応とする。
$\widetilde{\Gamma}$ が $\Gamma$ の $A'$ への拡張であるとは、$\widetilde{\Gamma}$ をもとの始集合 $A$ に制限すると、$\Gamma$ に一致するということである。
すなわち、
$$
\widetilde{\Gamma}|_A=\Gamma
$$
である。
実際、対応の制限の定義より、
$$
\widetilde{\Gamma}|_A=(A,B,\widetilde R\cap(A\times B))
$$
である。
したがって、
$$
\widetilde{\Gamma}|_A=\Gamma
$$
であることは、
$$
\widetilde R\cap(A\times B)=R
$$
であることと同値である。
つまり、拡張とは、追加された始集合 $A'\setminus A$ 上では新しい値を許すが、もとの始集合 $A$ 上では元の対応 $\Gamma$ と一致するような対応である。
本稿では、対応を始集合 $A$、終集合 $B$、および二項関係 $R$ の $3$ つ組 $(A,B,R)$ で定義している。
一方、対応 $\Gamma=(A,B,R)$ に付随する集合値写像を、同じ記号で
$$
\Gamma:A\to\mathcal P(B)
$$
と表すならば、各 $x\in A$ に対して
$$
\Gamma(x)=\{b\in B\mid (x,b)\in R\}
$$
である。
同様に、対応 $\widetilde{\Gamma}=(A',B,\widetilde R)$ に付随する集合値写像を
$$
\widetilde{\Gamma}:A'\to\mathcal P(B)
$$
と表すならば、各 $x\in A'$ に対して
$$
\widetilde{\Gamma}(x)=\{b\in B\mid (x,b)\in\widetilde R\}
$$
である。
このとき、$A\subseteq A'$ であり、かつ任意の $x\in A$ に対して
$$
\widetilde{\Gamma}(x)=\Gamma(x)
$$
が成り立つならば、$\widetilde{\Gamma}$ は $\Gamma$ の $A'$ への拡張である。
この条件は、$3$ つ組による定義
$$
\widetilde R\cap(A\times B)=R
$$
と同値である。
Prop&Proof
$A,B$ を集合とし、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
また、$S\subseteq A$ とする。
このとき、
$$
R|_S:=R\cap(S\times B)
$$
と定めると、
$$
\Gamma|_S:=(S,B,R|_S)
$$
は $S$ から $B$ への対応として定まる。
$\Gamma=(A,B,R)$ は $A$ から $B$ への対応であるから、
$$
R\subseteq A\times B
$$
である。
また、$S\subseteq A$ であるから、
$$
S\times B\subseteq A\times B
$$
が成り立つ(
証明はコチラ
)。
いま、
$$
R|_S:=R\cap(S\times B)
$$
と定める。
このとき、共通部分の性質より、
$$
R|_S\subseteq S\times B
$$
である(
証明はコチラ
)。
したがって、$R|_S$ は $S$ から $B$ への二項関係である。
ゆえに、
$$
\Gamma|_S:=(S,B,R|_S)
$$
は $S$ から $B$ への対応として定まる。
$$ \Box$$
$A,B$ を集合とし、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
このとき、
$$
\Gamma|_A=\Gamma
$$
が成り立つ。
制限の定義より、
$$
\Gamma|_A=(A,B,R|_A)
$$
であり、ここで
$$
R|_A=R\cap(A\times B)
$$
である。
また、$\Gamma=(A,B,R)$ は $A$ から $B$ への対応であるから、
$$
R\subseteq A\times B
$$
である。
したがって、
$$
R\cap(A\times B)=R
$$
である(
証明はコチラ
)。
ゆえに、
$$
R|_A=R
$$
である。よって、
$$
\Gamma|_A=(A,B,R|_A)=(A,B,R)=\Gamma
$$
が成り立つ。
$$ \Box$$
$A,A',B$ を集合とし、$A\subseteq A'$ とする。また、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
このとき、
$$
\widetilde R_0:=R
$$
と定め、
$$
\widetilde{\Gamma}_0:=(A',B,\widetilde R_0)
$$
とおくと、$\widetilde{\Gamma}_0$ は $A'$ から $B$ への対応であり、かつ $\Gamma$ の $A'$ への拡張である。
- $\Gamma=(A,B,R)$ は $A$ から $B$ への対応であるから、
$$ R\subseteq A\times B $$
である。また、
$$ A\subseteq A' $$
であるから、
$$ A\times B\subseteq A'\times B $$
である( 証明はコチラ )。
したがって、
$$ \widetilde R_0=R\subseteq A'\times B $$
である。ゆえに、
$$ \widetilde{\Gamma}_0=(A',B,\widetilde R_0) $$
は $A'$ から $B$ への対応である。
$ $ - 次に、$\widetilde{\Gamma}_0$ が $\Gamma$ の $A'$ への拡張であることを示す。
拡張の定義より、
$$ \widetilde R_0\cap(A\times B)=R $$
を示せばよい。
いま、$\widetilde R_0=R$ であるから、
$$ \widetilde R_0\cap(A\times B)=R\cap(A\times B) $$
である。
また、$R\subseteq A\times B$ であるから、
$$ R\cap(A\times B)=R $$
である。
したがって、
$$ \widetilde R_0\cap(A\times B)=R $$
が成り立つ。
ゆえに、拡張の定義より、$\widetilde{\Gamma}_0$ は $\Gamma$ の $A'$ への拡張である。
-以上より、
$$
\widetilde{\Gamma}_0=(A',B,\widetilde R_0)=(A',B,R)
$$
は $A'$ から $B$ への対応であり、かつ $\Gamma$ の $A'$ への拡張である。
$$ \Box$$
$A,A',B$ を集合とし、$A\subseteq A'$ とする。
また、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とし、$\widetilde{\Gamma}_0=(A',B,R)$ を上で定めた自明な拡張とする。
任意の $x\in A'$ に対して、
$$
\widetilde{\Gamma}_0(x)
=
\{b\in B\mid (x,b)\in R\}
$$
である。
- $x\in A$ の場合。
対応の値の定義より、
$$ \widetilde{\Gamma}_0(x) = \{b\in B\mid (x,b)\in R\} = \Gamma(x) $$
である。
$ $ - $x\in A'\setminus A$ の場合。
このとき、$x\notin A$ である。
一方、$R\subseteq A\times B$ であるから、任意の $b\in B$ に対して、
$$ (x,b)\notin R $$
が成り立つ。
実際、もし $(x,b)\in R$ であれば、$R\subseteq A\times B$ より $(x,b)\in A\times B$ である。
したがって $x\in A$ となり、$x\notin A$ に矛盾する。
ゆえに、
$$ \{b\in B\mid (x,b)\in R\} = \varnothing $$
である。したがって、
$$ \widetilde{\Gamma}_0(x) = \varnothing $$
である。
-以上より、任意の $x\in A'$ に対して、
$$
\widetilde{\Gamma}_0(x)
=
\begin{cases}
\Gamma(x) & x\in A\\
\varnothing & x\in A'\setminus A
\end{cases}
$$
が成り立つ。
すなわち、自明な拡張 $\widetilde{\Gamma}_0$ は、もとの始集合 $A$ 上では $\Gamma$ と一致し、追加部分 $A'\setminus A$ 上では空集合を値として与える。
$A,A',B$ を集合とし、
$$
A\subseteq A'
$$
とする。また、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
- $\Gamma$ の $A'$ への拡張とは、
$$ \widetilde R\cap(A\times B)=R $$
を満たすような部分集合
$$ \widetilde R\subseteq A'\times B $$
を選び、
$$ \widetilde{\Gamma}=(A',B,\widetilde R) $$
と定めることである。
ここで、条件
$$ \widetilde R\cap(A\times B)=R $$
は、$\widetilde R$ のうち $A\times B$ 上の部分だけを指定している。
すなわち、もとの始集合 $A$ の元については、拡張後も $\Gamma$ と同じ対応関係を保たなければならない。
$ $ - 一方、追加された部分 $A'\setminus A$ の元については、拡張の条件だけでは値が指定されない。
実際、$\widetilde R$ のうち
$$ \widetilde R\cap((A'\setminus A)\times B) $$
の部分は、
$$ \widetilde R\cap(A\times B)=R $$
という条件には現れない。
したがって、$A'\setminus A$ の元に対して、どのような $B$ の部分集合を値として与えるかは、一般には自由に選べる。
特に、
$$ A'\setminus A\ne\varnothing \quad\text{かつ}\quad B\ne\varnothing $$
とする。
このとき、$a_0\in A'\setminus A$ と $b_0\in B$ を取ることができる。
$$ \widetilde R_0:=R $$
とおけば、
$$ \widetilde R_0\cap(A\times B)=R $$
であるから、
$$ \widetilde{\Gamma}_0:=(A',B,\widetilde R_0) $$
は $\Gamma$ の $A'$ への拡張である。
$ $ - 一方、
$$ \widetilde R_1:=R\cup\{(a_0,b_0)\} $$
とおく。
$R\subseteq A\times B$ かつ $A\subseteq A'$ であるから、
$$ R\subseteq A'\times B $$
である( 証明はコチラ )。
また、$a_0\in A'\setminus A$ かつ $b_0\in B$ であるから、
$$ (a_0,b_0)\in A'\times B $$
である。
したがって、
$$ \widetilde R_1\subseteq A'\times B $$
が成り立つ。
ゆえに、
$$ \widetilde{\Gamma}_1:=(A',B,\widetilde R_1) $$
は $A'$ から $B$ への対応として定まる。
さらに、$a_0\notin A$ であるから、
$$ (a_0,b_0)\notin A\times B $$
である。したがって、
$$ \begin{align} \widetilde R_1\cap(A\times B) &= (R\cup\{(a_0,b_0)\})\cap(A\times B)\\ &= (R\cap(A\times B))\cup(\{(a_0,b_0)\}\cap(A\times B))\\ &= R\cup\varnothing\\ &= R \end{align} $$
が成り立つ。
ここで、$2$つ目の等号では分配法則( 証明はコチラ )を$3$つ目の等号では空集合の和集合の性質( 証明はコチラ )を用いた。
ゆえに、$\widetilde{\Gamma}_1$ も $\Gamma$ の $A'$ への拡張である。
-したがって、$A'\setminus A\ne\varnothing$ かつ $B\ne\varnothing$ ならば、$\Gamma$ の $A'$ への拡張は一意ではない。
一方、$A'=A$ の場合、または $B=\varnothing$ の場合には、$\Gamma$ の $A'$ への拡張は一意である。
自明な拡張は、追加部分 $A'\setminus A$ 上で常に空集合を値として与える特別な拡張である。
$A,B$ を集合とし、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とする。
また、$S\subseteq A$ とし、$\Gamma|_S=(S,B,R|_S)$ を $\Gamma$ の $S$ への制限とする。
このとき、任意の $x\in S$ に対して、
$$
(\Gamma|_S)(x)=\Gamma(x)
$$
が成り立つ。
- 任意に $x\in S$ をとる。$S\subseteq A$ であるから、
$$ x\in A $$
である。
したがって、$\Gamma(x)$ は定義されている。
また、$x\in S$ であるから、$(\Gamma|_S)(x)$ も定義されている。
$ $ - 制限の定義より、
$$ \Gamma|_S=(S,B,R|_S) $$
であり、
$$ R|_S=R\cap(S\times B) $$
である。
ここで、任意の $b\in B$ に対して、$x\in S$ かつ $b\in B$ より、
$$ (x,b)\in S\times B $$
である。
したがって、任意の $b\in B$ に対して、
$$ \begin{align} (x,b)\in R|_S &\Longleftrightarrow (x,b)\in R\cap(S\times B)\\ &\Longleftrightarrow (x,b)\in R \land (x,b)\in S\times B\\ &\Longleftrightarrow (x,b)\in R \end{align} $$
が成り立つ。
対応の値の定義より、
$$ (\Gamma|_S)(x) = \{b\in B\mid (x,b)\in R|_S\} $$
であり、
$$ \Gamma(x) = \{b\in B\mid (x,b)\in R\} $$
である。
ゆえに、
$$ \begin{align} (\Gamma|_S)(x) &= \{b\in B\mid (x,b)\in R|_S\}\\ &= \{b\in B\mid (x,b)\in R\}\\ &= \Gamma(x) \end{align} $$
である。
-$x\in S$ は任意であったから、任意の $x\in S$ に対して、
$$
(\Gamma|_S)(x)=\Gamma(x)
$$
が成り立つ。
$$ \Box$$
$A,A',B$ を集合とし、$A\subseteq A'$ とする。
また、$\Gamma=(A,B,R)$ を $A$ から $B$ への対応とし、$\widetilde{\Gamma}=(A',B,\widetilde R)$ を $A'$ から $B$ への対応とする。
このとき、$\widetilde{\Gamma}$ が $\Gamma$ の $A'$ への拡張であることと、
$$
\forall x\in A\ (\widetilde{\Gamma}(x)=\Gamma(x))
$$
が成り立つことは同値である。
- $\widetilde{\Gamma}$ が $\Gamma$ の $A'$ への拡張であるならば、$\forall x\in A\ (\widetilde{\Gamma}(x)=\Gamma(x))$ が成り立つことを示す。
$\widetilde{\Gamma}$ が $\Gamma$ の $A'$ への拡張であると仮定する。
拡張の定義より、
$$ \widetilde R\cap(A\times B)=R $$
である。
任意に $x\in A$ をとる。$A\subseteq A'$ であるから、
$$ x\in A' $$
である。
したがって、$\Gamma(x)$ と $\widetilde{\Gamma}(x)$ はともに定義されている。
$\widetilde{\Gamma}(x)=\Gamma(x)$ を示すために、外延性により、任意の $b\in B$ に対して
$$ b\in\widetilde{\Gamma}(x) \Longleftrightarrow b\in\Gamma(x) $$
が成り立つことを示す。
任意に $b\in B$ をとる。
i) まず、
$$ b\in\widetilde{\Gamma}(x) $$
とする。
対応の値の定義より、
$$ (x,b)\in\widetilde R $$
である。
いま、$x\in A$ かつ $b\in B$ であるから、
$$ (x,b)\in A\times B $$
である。したがって、
$$ (x,b)\in\widetilde R\cap(A\times B) $$
である。
拡張の定義より、
$$ \widetilde R\cap(A\times B)=R $$
であるから、
$$ (x,b)\in R $$
である。
ゆえに、対応の値の定義より、
$$ b\in\Gamma(x) $$
である。
$ $
ii) 次に、
$$ b\in\Gamma(x) $$
とする。
対応の値の定義より、
$$ (x,b)\in R $$
である。
拡張の定義より、
$$ R=\widetilde R\cap(A\times B) $$
であるから、
$$ (x,b)\in\widetilde R\cap(A\times B) $$
である。したがって、
$$ (x,b)\in\widetilde R $$
である。
ゆえに、対応の値の定義より、
$$ b\in\widetilde{\Gamma}(x) $$
である。
以上より、任意の $b\in B$ に対して
$$ b\in\widetilde{\Gamma}(x) \Longleftrightarrow b\in\Gamma(x) $$
が成り立つ。
したがって、外延性により、
$$ \widetilde{\Gamma}(x)=\Gamma(x) $$
である。
$x\in A$ は任意であったから、
$$ \forall x\in A\ (\widetilde{\Gamma}(x)=\Gamma(x)) $$
が成り立つ。
$ $ - 逆に、$\forall x\in A\ (\widetilde{\Gamma}(x)=\Gamma(x))$ が成り立つならば、$\widetilde{\Gamma}$ が $\Gamma$ の $A'$ への拡張であることを示す。
そこで、
$$ \forall x\in A\ (\widetilde{\Gamma}(x)=\Gamma(x)) $$
が成り立つと仮定する。
拡張の定義より、
$$ \widetilde R\cap(A\times B)=R $$
を示せばよい。
i) まず、
$$ \widetilde R\cap(A\times B)\subseteq R $$
を示す。
任意に $(x,b)\in\widetilde R\cap(A\times B)$ をとる。
このとき、
$$ (x,b)\in\widetilde R \quad\text{かつ}\quad (x,b)\in A\times B $$
である。したがって、
$$ x\in A \quad\text{かつ}\quad b\in B $$
である。
また、$A\subseteq A'$ より、
$$ x\in A' $$
である。
$(x,b)\in\widetilde R$ であるから、対応の値の定義より、
$$ b\in\widetilde{\Gamma}(x) $$
である。
仮定より、$x\in A$ に対して
$$ \widetilde{\Gamma}(x)=\Gamma(x) $$
であるから、
$$ b\in\Gamma(x) $$
である。
ゆえに、対応の値の定義より、
$$ (x,b)\in R $$
である。したがって、
$$ \widetilde R\cap(A\times B)\subseteq R $$
が成り立つ。
$ $
ii) 次に、
$$ R\subseteq\widetilde R\cap(A\times B) $$
を示す。
任意に $(x,b)\in R$ をとる。
$\Gamma=(A,B,R)$ は $A$ から $B$ への対応であるから、
$$ R\subseteq A\times B $$
である。したがって、
$$ (x,b)\in A\times B $$
である。特に、
$$ x\in A \quad\text{かつ}\quad b\in B $$
である。
また、$A\subseteq A'$ より、
$$ x\in A' $$
である。
また、$(x,b)\in R$ であるから、対応の値の定義より、
$$ b\in\Gamma(x) $$
である。
仮定より、$x\in A$ に対して
$$ \widetilde{\Gamma}(x)=\Gamma(x) $$
であるから、
$$ b\in\widetilde{\Gamma}(x) $$
である。
ゆえに、対応の値の定義より、
$$ (x,b)\in\widetilde R $$
である。さらに、
$$ (x,b)\in A\times B $$
であるから、
$$ (x,b)\in\widetilde R\cap(A\times B) $$
である。したがって、
$$ R\subseteq\widetilde R\cap(A\times B) $$
が成り立つ。
以上より、
$$ \widetilde R\cap(A\times B)=R $$
である。
したがって、拡張の定義より、$\widetilde{\Gamma}$ は $\Gamma$ の $A'$ への拡張である。
-以上より、$\widetilde{\Gamma}$ が $\Gamma$ の $A'$ への拡張であることと、
$$
\forall x\in A\ (\widetilde{\Gamma}(x)=\Gamma(x))
$$
が成り立つことは同値である。
$$ \Box$$
この記事を高評価した人
この記事に送られたバッジ
投稿者
