大学数学基礎解説

文献あり

二項関係の全域性・一意性

二項関係

112

写像と集合演算について，悪い人さんの記事数学初心者が写像について学びを深める…… を読んで興味深いと思ったので，自分用のメモとして二項関係の言葉を用いて書き直してみます．

二項関係

二項関係の定義

二項関係

集合 $X, Y$ と直積集合 $X \times Y$ の部分集合 $G$ の3つ組 $R = (X, Y, G)$ を， $X$ と $Y$ の間の二項関係という．
$X$ と $Y$ の間の二項関係 $R = (X, Y, G)$ と $(x, y) \in X \times Y$ に対して， $(x, y) \in G$ であることを $x R y$ とも書く．

合同式

$2$ 以上の整数 $m$ に対して
$G_{m} := {(x, y) \in Z \times Z ∣ x - y は m で割り切れる}$
とおくと， $\equiv_{m} := (Z, Z, G_{m})$ は $Z$ と $Z$ の間の二項関係となる．
（普通は $x \equiv_{m} y$ であることを $x \equiv y (\mod m)$ と書く）

逆関係

$X$ と $Y$ の間の二項関係 $R = (X, Y, G)$ に対して， $Y$ と $X$ の間の二項関係 $R^{- 1} = (Y, X, G^{- 1})$ を
$G^{- 1} := {(y, x) \in Y \times X ∣ (x, y) \in G}$
で定め， $R$ の逆関係という．

つまり $(x, y) \in X \times Y$ について
$y R^{- 1} x ⟺ x R y$
が成り立つ．

集合 $X, Y$ および $X$ と $Y$ の間の二項関係 $R$ に対して， $(R^{- 1})^{- 1} = R$ が成り立つ．

$R = (X, Y, G)$ とすると
$\begin{aligned} (G^{- 1})^{- 1} & = {(x, y) \in X \times Y ∣ (y, x) \in G^{- 1}} \\ = {(x, y) \in X \times Y ∣ (x, y) \in G} \\ = G . \end{aligned}$

二項関係の像・逆像

本記事でも以前書いた記事 $A$ と $f^{- 1} (f (A))$ , $B$ と $f (f^{- 1} (B))$ の包含関係と同様に，矢印記法を使う（逆関係／逆写像と逆像の混乱を防ぐため）．
また，集合 $X$ の冪集合（ $X$ の部分集合全体の集合）を $2^{X}$ で表す．

二項関係の像・逆像

集合 $X, Y$ および $X$ と $Y$ の間の二項関係 $R$ に対して，2つの写像 $R^{\to} : 2^{X} \to 2^{Y}$ と $R^{\leftarrow} : 2^{Y} \to 2^{X}$ を
$\begin{aligned} R^{\to} (A) & := {y \in Y ∣ a R y を満たす a \in A が存在する} & (A \in 2^{X}), \\ R^{\leftarrow} (B) & := {x \in X ∣ x R b を満たす b \in B が存在する} & (B \in 2^{Y}) \end{aligned}$
で定義する．

逆関係の像・逆像

集合 $X, Y$ および $X$ と $Y$ の間の二項関係 $R$ について，次のことが成り立つ．

$(R^{- 1})^{\to} = R^{\leftarrow}$ .
$(R^{- 1})^{\leftarrow} = R^{\to}$ .

任意の $A \in 2^{X}$ と $B \in 2^{Y}$ に対して，
$\begin{aligned} (R^{- 1})^{\to} (B) & = {x \in X ∣^{\exists} b \in B, b R^{- 1} x} \\ = {x \in X ∣^{\exists} b \in B, x R b} \\ = R^{\leftarrow} (B), \\ (R^{- 1})^{\leftarrow} (A) & = {y \in Y ∣^{\exists} a \in A, y R^{- 1} a} \\ = {y \in Y ∣^{\exists} a \in A, a R y} \\ = R^{\to} (A) . \end{aligned}$

$X, Y$ を集合， $R$ を $X$ と $Y$ の間の二項関係とし， $A, A^{'} \in 2^{X}$ , $B, B^{'} \in 2^{Y}$ とする．

$A \subset A^{'}$ のとき， $R^{\to} (A) \subset R^{\to} (A^{'})$ である．
$R^{\to} (A \cup A^{'}) = R^{\to} (A) \cup R^{\to} (A^{'})$ .
$R^{\to} (A \cap A^{'}) \subset R^{\to} (A) \cap R^{\to} (A^{'})$ .
$B \subset B^{'}$ のとき， $R^{\leftarrow} (B) \subset R^{\leftarrow} (B^{'})$ である．
$R^{\leftarrow} (B \cup B^{'}) = R^{\leftarrow} (B) \cup R^{\leftarrow} (B^{'})$ .
$R^{\leftarrow} (B \cap B^{'}) \subset R^{\leftarrow} (B) \cap R^{\leftarrow} (B^{'})$ .

$y \in R^{\to} (A)$ のとき， $R^{\to}$ の定義から $a R y$ を満たす $a \in A$ が存在するが， $A \subset A^{'}$ より $a \in A^{'}$ でもあるので $y \in R^{\to} (A^{'})$ となる．
$A$ と $A^{'}$ はどちらも $A \cup A^{'}$ に含まれるので，(1) より $R^{\to} (A \cup A^{'}) \supset R^{\to} (A)$ かつ $R^{\to} (A \cup A^{'}) \supset R^{\to} (A^{'})$ ，つまり $R^{\to} (A \cup A^{'}) \supset R^{\to} (A) \cup R^{\to} (A^{'})$ が成り立つ．
逆の包含を示すため $y \in R^{\to} (A \cup A^{'})$ とすると， $R^{\to}$ の定義から $a R y$ を満たす $a \in A \cup A^{'}$ が取れる．すると $a \in A$ の場合は $y \in R^{\to} (A)$ となり， $a \in A^{'}$ の場合は $y \in R^{\to} (A^{'})$ となるので，いずれにしても $y \in R^{\to} (A) \cup R^{\to} (A^{'})$ である．
$A$ と $A^{'}$ はどちらも $A \cap A^{'}$ を含むので，(1) より $R^{\to} (A \cap A^{'}) \subset R^{\to} (A)$ かつ $R^{\to} (A \cap A^{'}) \subset R^{\to} (A^{'})$ ，つまり $R^{\to} (A \cap A^{'}) \subset R^{\to} (A) \cap R^{\to} (A^{'})$ が成り立つ．

(4), (5), (6) は前命題と (1), (2), (3) から従う．

共通部分に関する (3), (6) では等号が成り立つとは限らないことに注意．
（後述の通り，(3), (6) で常に等号成立することは， $R$ の左一意性，右一意性にそれぞれ同値である）

集合 $X, Y$ および $X$ と $Y$ の間の二項関係 $R, S$ に対して，次のことが成り立つことを示せ．

$R^{\to} = S^{\to}$ ならば， $R = S$ である．
$R^{\leftarrow} = S^{\leftarrow}$ ならば， $R = S$ である．

$x \in X$ と $y \in Y$ について， $x R y$ と $y \in R^{\to} ({x})$ と $x \in R^{\leftarrow} ({y})$ が互いに同値であることに注意．

$x R y$ のとき， $y \in R^{\to} ({x}) = S^{\to} ({x})$ より $x S y$ である．同様に $x S y$ であれば $x R y$ となるので， $R = S$ である．
$x R y$ のとき， $x \in R^{\leftarrow} ({y}) = S^{\leftarrow} ({y})$ より $x S y$ である．同様に $x S y$ であれば $x R y$ となるので， $R = S$ である．

二項関係の全域性・一意性

全域性・一意性

集合 $X, Y$ および $X$ と $Y$ の間の二項関係 $R$ に対して，

$R$ が左全域的であるとは，任意の $x \in X$ に対してある $y \in Y$ が存在して $x R y$ が成り立つことをいう．
$R$ が右全域的であるとは，任意の $y \in Y$ に対してある $x \in X$ が存在して $x R y$ が成り立つことをいう．
$R$ が左一意的であるとは，各 $y \in Y$ に対して， $x R y$ を満たす $x \in X$ が高々1つしかないことをいう．
$R$ が右一意的であるとは，各 $x \in X$ に対して， $x R y$ を満たす $y \in Y$ が高々1つしかないことをいう．

写像

$X$ から $Y$ への写像とは， $X$ と $Y$ の間の左全域的かつ右一意的な二項関係のことだった．
写像 $f : X \to Y$ と $x \in X$ に対して， $x f y$ を満たす一意的な $y \in Y$ のことを $f (x)$ と書く．
また，右全域的な写像は全射のことであり，左一意的な写像は単射のことである．

逆関係を考えれば，全域性や一意性の左右は容易に取り換えられる．

集合 $X, Y$ および $X$ と $Y$ の間の二項関係 $R$ について，次のことが成り立つ．

$R$ が左全域的であることと， $R^{- 1}$ が右全域的であることは同値である．
$R$ が左一意的であることと， $R^{- 1}$ が右一意的であることは同値である．

$\begin{aligned} R が左全域的 & ⟺^{\forall} x \in X,^{\exists} y \in Y, x R y \\ ⟺^{\forall} x \in X,^{\exists} y \in Y, x R y \\ ⟺^{\forall} x \in X,^{\exists} y \in Y, y R^{- 1} x \\ ⟺ R^{- 1} が右全域的, \\ R が左一意的 & ⟺^{\forall} y \in Y,^{\forall} x, x^{'} \in X, (x R y \land x^{'} R y \Rightarrow x = x^{'}) \\ ⟺^{\forall} y \in Y,^{\forall} x, x^{'} \in X, (y R^{- 1} x \land y R^{- 1} x^{'} \Rightarrow x = x^{'}) \\ ⟺ R^{- 1} が右一意的 . \end{aligned}$

逆写像

写像 $f : X \to Y$ の逆関係 $f^{- 1}$ が $Y$ から $X$ への写像であるための必要十分条件は， $f$ が右全域的かつ左一意的（つまり全単射）なことである．
このとき，写像 $f^{- 1} : Y \to X$ を $f$ の逆写像というのだった．

$A$ と $R^{\leftarrow} (R^{\to} (A))$ ， $B$ と $R^{\to} (R^{\leftarrow} (B))$ の包含関係

以前書いた記事 $A$ と $f^{- 1} (f (A))$ , $B$ と $f (f^{- 1} (B))$ の包含関係と同様に， $A$ と $R^{\leftarrow} (R^{\to} (A))$ ， $B$ と $R^{\to} (R^{\leftarrow} (B))$ の包含関係について考える．

集合 $X, Y$ および $X$ と $Y$ の間の二項関係 $R$ について，次の2条件は互いに同値である．

$R$ は左全域的である．
任意の $A \in 2^{X}$ に対して $A \subset R^{\leftarrow} (R^{\to} (A))$ が成り立つ．

(1) $\Rightarrow$ (2)：任意の $a \in A$ に対して， $R$ の左全域性から $a R y$ を満たす $y \in Y$ が取れるが，このとき $y \in R^{\to} (A)$ より $a \in R^{\leftarrow} (R^{\to} (A))$ となる．
(2) $\Rightarrow$ (1)：任意の $x \in X$ に対して， ${x} \subset R^{\leftarrow} (R^{\to} ({x}))$ だから $x R y$ を満たす $y \in R^{\to} ({x})$ が取れる．

集合 $X, Y$ および $X$ と $Y$ の間の二項関係 $R$ について，次の2条件は互いに同値である．

$R$ は右全域的である．
任意の $B \in 2^{Y}$ に対して $B \subset R^{\to} (R^{\leftarrow} (B))$ が成り立つ．

逆関係 $R^{- 1}$ に前命題を適用すればよい．

集合 $X, Y$ および $X$ と $Y$ の間の二項関係 $R$ について，次の3条件は互いに同値である．

$R$ は左一意的である．
任意の $A \in 2^{X}$ に対して $A \supset R^{\leftarrow} (R^{\to} (A))$ が成り立つ．
任意の $A, A^{'} \in 2^{X}$ に対して $R^{\to} (A \cap A^{'}) = R^{\to} (A) \cap R^{\to} (A^{'})$ が成り立つ．

(1) $\Rightarrow$ (2)：任意の $x \in R^{\leftarrow} (R^{\to} (A))$ に対して， $R^{\leftarrow}$ の定義から $x R y$ を満たす $y \in R^{\to} (A)$ が取れて， $R^{\to}$ の定義から $a R y$ を満たす $a \in A$ が取れる．このとき $R$ の左一意性より $x = a \in A$ となるので， $A \supset R^{\leftarrow} (R^{\to} (A))$ が成り立つ．
(2) $\Rightarrow$ (3)：逆の包含は常に成り立つから， $R^{\to} (A \cap A^{'}) \supset R^{\to} (A) \cap R^{\to} (A^{'})$ を示せばよい． $y \in R^{\to} (A) \cap R^{\to} (A^{'})$ を任意に取ると， $y \in R^{\to} (A)$ だから $a R y$ を満たす $a \in A$ が存在し， $y \in R^{\to} (A^{'})$ だから $a^{'} R y$ を満たす $a \in A^{'}$ が存在する．すると
$\begin{aligned} a^{'} \in R^{\leftarrow} ({y}) & \subset R^{\leftarrow} (R^{\to} ({a})) \subset {a} \end{aligned}$
より $a = a^{'}$ となり， $y \in R^{\to} ({a}) \subset R^{\to} (A \cap A^{'})$ が示された．
(3) $\Rightarrow$ (1)： $x, x^{'} \in X$ と $y \in Y$ が $x R y$ かつ $x^{'} R y$ を満たすとする．このとき
$y \in R^{\to} ({x}) \cap R^{\to} ({x^{'}}) = R^{\to} ({x} \cap {x^{'}})$
であり，もし $x \neq x^{'}$ なら右辺 $R^{\to} (\emptyset) = \emptyset$ が元 $y$ を持つことになり矛盾する．よって $x = x^{'}$ であり， $R$ は左一意的である．

集合 $X, Y$ および $X$ と $Y$ の間の二項関係 $R$ について，次の3条件は互いに同値である．

$R$ は右一意的である．
任意の $B \in 2^{Y}$ に対して $B \supset R^{\to} (R^{\leftarrow} (B))$ が成り立つ．
任意の $B, B^{'} \in 2^{Y}$ に対して $R^{\leftarrow} (B \cap B^{'}) = R^{\leftarrow} (B) \cap R^{\leftarrow} (B^{'})$ が成り立つ．

逆関係 $R^{- 1}$ に前命題を適用すればよい．

これで， $A$ と $R^{\leftarrow} (R^{\to} (A))$ ， $B$ と $R^{\to} (R^{\leftarrow} (B))$ の包含関係と， $R$ の全域性・一意性が綺麗に対応していることがわかった．
これらの結果を写像・全射・単射に適用すれば，次の命題を得る．

集合 $X, Y$ とその間の写像 $f : X \to Y$ について，次のことが成り立つ．

任意の $A \in 2^{X}$ に対して $A \subset f^{\leftarrow} (f^{\to} (A))$ が成り立つ．
任意の $B \in 2^{Y}$ に対して $B \supset f^{\to} (f^{\leftarrow} (B))$ が成り立つ．
任意の $B, B^{'} \in 2^{Y}$ に対して $f^{\leftarrow} (B \cap B^{'}) = f^{\leftarrow} (B) \cap f^{\leftarrow} (B^{'})$ が成り立つ．

$f$ が単射の場合，(1) で常に等号が成り立ち，さらに任意の $A, A^{'} \in 2^{X}$ に対して $f^{\to} (A \cap A^{'}) = f^{\to} (A) \cap f^{\to} (A^{'})$ が成り立つ．
$f$ が全射の場合，(2) で常に等号が成り立つ．