二項関係 ⑫

Prop&Proof

1. $R$ が反射的であるならば、$\Delta_A\subseteq R$ が成り立つことを示す。
   $R$ が反射的であると仮定する。
   $\Delta_A\subseteq R$ を示すために、任意に
   $$ (x,y)\in\Delta_A $$
   を取る。
   対角関係の定義より、ある $a\in A$ が存在して、
   $$ (x,y)=(a,a) $$
   である。$R$ は反射的であるから、
   $$ (a,a)\in R $$
   である。したがって、
   $$ (x,y)\in R $$
   である。
   $(x,y)\in\Delta_A$ は任意であったから、
   $$ \Delta_A\subseteq R $$
   が成り立つ。
   $ $
2. $\Delta_A\subseteq R$ が成り立つならば、$R$ が反射的であることを示す。
   $$ \Delta_A\subseteq R $$
   が成り立つと仮定する。
   $R$ が反射的であることを示すには、
   $$ \forall a\in A\ ((a,a)\in R) $$
   を示せばよい。
   任意に $a\in A$ を取る。
   対角関係の定義より、
   $$ (a,a)\in\Delta_A $$
   である。仮定 $\Delta_A\subseteq R$ より、
   $$ (a,a)\in R $$
   である。
   $a\in A$ は任意であったから、
   $$ \forall a\in A\ ((a,a)\in R) $$
   が成り立つ。
   したがって、$R$ は反射的である。

-1. と 2. より、
$$ R\text{ が反射的である} \Longleftrightarrow \Delta_A\subseteq R $$
である。
$$ \Box$$

1. $R$ が対称的であるならば $R^{-1}=R$ であることを示す。
   $R$ が対称的であると仮定する。
   集合の外延性により、
   $$ R^{-1}\subseteq R \quad \text{かつ} \quad R\subseteq R^{-1} $$
   を示せばよい。
   i) まず、
   $$ R^{-1}\subseteq R $$
   　を示す。任意に $z\in R^{-1}$ をとる。
   　逆関係の定義より、ある $a,b\in A$ が存在して、
   $$ z=(b,a) \quad \text{かつ} \quad (a,b)\in R $$
   　が成り立つ。$R$ は対称的であるから、
   $$ (b,a)\in R $$
   　である。したがって、
   $$ z\in R $$
   　である。
   　$z\in R^{-1}$ は任意であったから、
   $$ R^{-1}\subseteq R $$
   　である。
   $ $
   ii) 次に、
   $$ R\subseteq R^{-1} $$
   　を示す。任意に $z\in R$ をとる。
   　$R\subseteq A\times A$ であるから、ある $a,b\in A$ が存在して、
   $$ z=(a,b) \quad \text{かつ} \quad (a,b)\in R $$
   　が成り立つ。
   　$R$ は対称的であるから、
   $$ (b,a)\in R $$
   　である。逆関係の定義より、
   $$ (a,b)\in R^{-1} $$
   　である。したがって、
   $$ z\in R^{-1} $$
   　である。
   　$z\in R$ は任意であったから、
   $$ R\subseteq R^{-1} $$
   　である。
   $ $
   i) と ii) より、
   $$ R^{-1}=R $$
   である。
   $ $
2. $R^{-1}=R$ ならば $R$ が対称的であることを示す。
   $$ R^{-1}=R $$
   と仮定する。
   $R$ が対称的であることを示すために、任意に $a,b\in A$ をとり、
   $$ (a,b)\in R $$
   と仮定する。
   逆関係の定義より、
   $$ (b,a)\in R^{-1} $$
   である。
   仮定 $R^{-1}=R$ より、
   $$ (b,a)\in R $$
   である。
   したがって、
   $$ (a,b)\in R\Rightarrow (b,a)\in R $$
   が成り立つ。
   $a,b\in A$ は任意であったから、
   $$ \forall a\in A\ \forall b\in A\ \bigl((a,b)\in R\Rightarrow (b,a)\in R\bigr) $$
   が成り立つ。
   よって、$R$ は対称的である。

-以上より、$R$ が対称的であることと $R^{-1}=R$ は同値である。
$$ \Box$$

1. $R$ が推移的であるならば $R\circ R\subseteq R$ であることを示す。
   $R$ が推移的であると仮定する。
   $$ R\circ R\subseteq R $$
   を示す。任意に $z\in R\circ R$ をとる。
   合成関係の定義より、ある $a,b,c\in A$ が存在して、
   $$ z=(a,c) \quad \text{かつ} \quad (a,b)\in R \quad \text{かつ} \quad (b,c)\in R $$
   が成り立つ。
   $R$ は推移的であるから、
   $$ (a,c)\in R $$
   である。
   したがって、
   $$ z\in R $$
   である。
   $z\in R\circ R$ は任意であったから、
   $$ R\circ R\subseteq R $$
   である。
   $ $
2. $R\circ R\subseteq R$ であるならば $R$ が推移的であることを示す。
   $$ R\circ R\subseteq R $$
   と仮定する。
   $R$ が推移的であることを示すために、任意に $a,b,c\in A$ をとり、
   $$ (a,b)\in R \quad \text{かつ} \quad (b,c)\in R $$
   と仮定する。
   このとき、合成関係の定義より、
   $$ (a,c)\in R\circ R $$
   である。
   仮定 $R\circ R\subseteq R$ より、
   $$ (a,c)\in R $$
   である。
   したがって、
   $$ \bigl((a,b)\in R\land (b,c)\in R\bigr)\Rightarrow (a,c)\in R $$
   が成り立つ。
   $a,b,c\in A$ は任意であったから、
   $$ \forall a\in A\ \forall b\in A\ \forall c\in A\ \bigl(((a,b)\in R\land (b,c)\in R)\Rightarrow (a,c)\in R\bigr) $$
   が成り立つ。
   したがって、$R$ は推移的である。

-以上より、$R$ が推移的であることと $R\circ R\subseteq R$ は同値である。
$$ \Box$$

1. $R$ が反対称的であるならば $R\cap R^{-1}\subseteq \Delta_A$ であることを示す。
   $R$ が反対称的であると仮定する。
   $$ R\cap R^{-1}\subseteq \Delta_A $$
   を示す。
   任意に $z\in R\cap R^{-1}$ をとる。
   共通部分の定義より、
   $$ z\in R \quad \text{かつ} \quad z\in R^{-1} $$
   である。
   $z\in R$ かつ $R\subseteq A\times A$ であるから、ある $a,b\in A$ が存在して、
   $$ z=(a,b) \quad \text{かつ} \quad (a,b)\in R $$
   が成り立つ。
   また、$z\in R^{-1}$ であるから、
   $$ (a,b)\in R^{-1} $$
   である。
   逆関係の定義より、
   $$ (b,a)\in R $$
   である。したがって、
   $$ (a,b)\in R \quad \text{かつ} \quad (b,a)\in R $$
   である。
   ここで、$R$ は反対称的であるから、
   $$ a=b $$
   である。ゆえに、
   $$ z=(a,b)=(a,a) $$
   である。
   したがって、恒等関係の定義より、
   $$ z\in \Delta_A $$
   である。
   $z\in R\cap R^{-1}$ は任意であったから、
   $$ R\cap R^{-1}\subseteq \Delta_A $$
   である。
   $ $
2. $R\cap R^{-1}\subseteq \Delta_A$ ならば $R$ が反対称的であることを示す。
   $$ R\cap R^{-1}\subseteq \Delta_A $$
   と仮定する。$R$ が反対称的であることを示す。
   $R$ が反対称的であることを示すために、任意に $a,b\in A$ をとり、
   $$ (a,b)\in R \quad \text{かつ} \quad (b,a)\in R $$
   と仮定する。
   逆関係の定義より、
   $$ (a,b)\in R^{-1} $$
   である。したがって、
   $$ (a,b)\in R\cap R^{-1} $$
   である。
   仮定 $R\cap R^{-1}\subseteq \Delta_A$ より、
   $$ (a,b)\in \Delta_A $$
   である。
   恒等関係の定義より、
   $$ a=b $$
   である。
   したがって、
   $$ (a,b)\in R \quad \text{かつ} \quad (b,a)\in R \Rightarrow a=b $$
   が成り立つ。
   $a,b\in A$ は任意であったから、$R$ は反対称的である。

-以上より、$R$ が反対称的であることと $R\cap R^{-1}\subseteq \Delta_A$ は同値である。
$$ \Box$$

1. $R$ が比較可能律を満たすならば、$A\times A\subseteq R\cup R^{-1}\cup\Delta_A$ が成り立つことを示す。
   $R$ が比較可能律を満たすと仮定する。
   $A\times A\subseteq R\cup R^{-1}\cup\Delta_A$ を示すために、任意に
   $$ (a,b)\in A\times A $$
   を取る。
   このとき、$a\in A$ かつ $b\in A$ である。
   ここで、$a=b$ であるか、$a\neq b$ であるかに分ける。
   i) $a=b$ の場合
   　対角関係の定義より、
   $$ (a,b)=(a,a)\in\Delta_A $$
   　である。
   　したがって、
   $$ (a,b)\in R\cup R^{-1}\cup\Delta_A $$
   　である。
   ii) $a\neq b$ の場合
   　$R$ は比較可能律を満たすから、
   $$ (a,b)\in R\lor(b,a)\in R $$
   　が成り立つ。
   　ここで、$(a,b)\in R$ ならば、
   $$ (a,b)\in R\cup R^{-1}\cup\Delta_A $$
   　である。
   　一方、$(b,a)\in R$ ならば、逆関係の定義より、
   $$ (a,b)\in R^{-1} $$
   　である。したがって、
   $$ (a,b)\in R\cup R^{-1}\cup\Delta_A $$
   　である。
   以上より、いずれの場合も、
   $$ (a,b)\in R\cup R^{-1}\cup\Delta_A $$
   が成り立つ。$(a,b)\in A\times A$ は任意であったから、
   $$ A\times A\subseteq R\cup R^{-1}\cup\Delta_A $$
   である。
   $ $
2. $A\times A\subseteq R\cup R^{-1}\cup\Delta_A$ が成り立つならば、$R$ が比較可能律を満たすことを示す。
   $$ A\times A\subseteq R\cup R^{-1}\cup\Delta_A $$
   が成り立つと仮定する。
   $R$ が比較可能律を満たすことを示すには、
   $$ \forall a\in A\ \forall b\in A\ \bigl(a\neq b\Rightarrow ((a,b)\in R\lor(b,a)\in R)\bigr) $$
   を示せばよい。
   任意に $a,b\in A$ を取り、
   $$ a\neq b $$
   と仮定する。このとき、
   $$ (a,b)\in A\times A $$
   である。
   仮定 $A\times A\subseteq R\cup R^{-1}\cup\Delta_A$ より、
   $$ (a,b)\in R\cup R^{-1}\cup\Delta_A $$
   である。
   一方、$a\neq b$ であるから、対角関係の定義より、
   $$ (a,b)\notin\Delta_A $$
   である。したがって、
   $$ (a,b)\in R\cup R^{-1} $$
   である。ゆえに、
   $$ (a,b)\in R\lor(a,b)\in R^{-1} $$
   が成り立つ。
   ここで、$(a,b)\in R^{-1}$ ならば、逆関係の定義より、
   $$ (b,a)\in R $$
   である。したがって、
   $$ (a,b)\in R\lor(b,a)\in R $$
   が成り立つ。
   $a,b\in A$ は任意であったから、
   $$ \forall a\in A\ \forall b\in A\ \bigl(a\neq b\Rightarrow ((a,b)\in R\lor(b,a)\in R)\bigr) $$
   が成り立つ。
   ゆえに、$R$ は比較可能律を満たす。

-1. と 2. より、
$$ R\text{ が比較可能律を満たす} \Longleftrightarrow A\times A\subseteq R\cup R^{-1}\cup\Delta_A $$
である。
$$ \Box$$

1. 反射性について示す。
   任意の $a\in A$ について、逆関係の定義より、
   $$ (a,a)\in R^{-1} \Longleftrightarrow (a,a)\in R $$
   である。
   したがって、
   $$ \forall a\in A\ ((a,a)\in R) \Longleftrightarrow \forall a\in A\ ((a,a)\in R^{-1}) $$
   が成り立つ。
   ゆえに、$R$ が反射的であることと、$R^{-1}$ が反射的であることは同値である。
   $ $
2. 対称性について示す。
   まず、$R$ が対称的であると仮定する。
   $R^{-1}$ が対称的であることを示すために、任意に $a,b\in A$ をとり、
   $$ (a,b)\in R^{-1} $$
   と仮定する。逆関係の定義より、
   $$ (b,a)\in R $$
   である。
   $R$ は対称的であるから、
   $$ (a,b)\in R $$
   である。
   再び逆関係の定義より、
   $$ (b,a)\in R^{-1} $$
   である。
   したがって、
   $$ (a,b)\in R^{-1}\Rightarrow (b,a)\in R^{-1} $$
   が成り立つ。
   $a,b\in A$ は任意であったから、$R^{-1}$ は対称的である。
   $ $
   逆に、$R^{-1}$ が対称的であると仮定する。
   $R$ が対称的であることを示すために、任意に $a,b\in A$ をとり、
   $$ (a,b)\in R $$
   と仮定する。逆関係の定義より、
   $$ (b,a)\in R^{-1} $$
   である。
   $R^{-1}$ は対称的であるから、
   $$ (a,b)\in R^{-1} $$
   である。
   再び逆関係の定義より、
   $$ (b,a)\in R $$
   である。
   したがって、
   $$ (a,b)\in R\Rightarrow (b,a)\in R $$
   が成り立つ。
   $a,b\in A$ は任意であったから、$R$ は対称的である。
   ゆえに、$R$ が対称的であることと、$R^{-1}$ が対称的であることは同値である。
   $ $
3. 反対称性について示す。
   まず、$R$ が反対称的であると仮定する。
   $R^{-1}$ が反対称的であることを示すために、任意に $a,b\in A$ をとり、
   $$ (a,b)\in R^{-1} \quad \text{かつ} \quad (b,a)\in R^{-1} $$
   と仮定する。
   逆関係の定義より、
   $$ (b,a)\in R \quad \text{かつ} \quad (a,b)\in R $$
   である。
   したがって、
   $$ (a,b)\in R \quad \text{かつ} \quad (b,a)\in R $$
   である。
   $R$ は反対称的であるから、
   $$ a=b $$
   である。
   $a,b\in A$ は任意であったから、$R^{-1}$ は反対称的である。
   $ $
   逆に、$R^{-1}$ が反対称的であると仮定する。
   $R$ が反対称的であることを示すために、任意に $a,b\in A$ をとり、
   $$ (a,b)\in R \quad \text{かつ} \quad (b,a)\in R $$
   と仮定する。
   逆関係の定義より、
   $$ (b,a)\in R^{-1} \quad \text{かつ} \quad (a,b)\in R^{-1} $$
   である。
   $R^{-1}$ は反対称的であるから、
   $$ b=a $$
   である。
   等号の対称性より、
   $$ a=b $$
   である。
   $a,b\in A$ は任意であったから、$R$ は反対称的である。
   ゆえに、$R$ が反対称的であることと、$R^{-1}$ が反対称的であることは同値である。
   $ $
4. 推移性について示す。
   まず、$R$ が推移的であると仮定する。
   $R^{-1}$ が推移的であることを示すために、任意に $a,b,c\in A$ をとり、
   $$ (a,b)\in R^{-1} \quad \text{かつ} \quad (b,c)\in R^{-1} $$
   と仮定する。
   逆関係の定義より、
   $$ (b,a)\in R \quad \text{かつ} \quad (c,b)\in R $$
   である。したがって、
   $$ (c,b)\in R \quad \text{かつ} \quad (b,a)\in R $$
   である。
   $R$ は推移的であるから、
   $$ (c,a)\in R $$
   である。
   逆関係の定義より、
   $$ (a,c)\in R^{-1} $$
   である。
   $a,b,c\in A$ は任意であったから、$R^{-1}$ は推移的である。
   $ $
   逆に、$R^{-1}$ が推移的であると仮定する。
   $R$ が推移的であることを示すために、任意に $a,b,c\in A$ をとり、
   $$ (a,b)\in R \quad \text{かつ} \quad (b,c)\in R $$
   と仮定する。
   逆関係の定義より、
   $$ (b,a)\in R^{-1} \quad \text{かつ} \quad (c,b)\in R^{-1} $$
   である。
   したがって、
   $$ (c,b)\in R^{-1} \quad \text{かつ} \quad (b,a)\in R^{-1} $$
   である。
   $R^{-1}$ は推移的であるから、
   $$ (c,a)\in R^{-1} $$
   である。
   逆関係の定義より、
   $$ (a,c)\in R $$
   である。
   $a,b,c\in A$ は任意であったから、$R$ は推移的である。
   ゆえに、$R$ が推移的であることと、$R^{-1}$ が推移的であることは同値である。
   $ $
5. 比較可能性について示す。
   まず、$R$ が比較可能であると仮定する。
   $R^{-1}$ が比較可能であることを示すために、任意に $a,b\in A$ をとり、
   $$ a\ne b $$
   と仮定する。
   $R$ は比較可能であるから、
   $$ (a,b)\in R\lor (b,a)\in R $$
   である。
   逆関係の定義より、
   $$ (a,b)\in R\Longleftrightarrow (b,a)\in R^{-1} $$
   かつ
   $$ (b,a)\in R\Longleftrightarrow (a,b)\in R^{-1} $$
   である。したがって、
   $$ (b,a)\in R^{-1}\lor (a,b)\in R^{-1} $$
   である。
   論理和の交換法則( 証明はコチラ )より、
   $$ (a,b)\in R^{-1}\lor (b,a)\in R^{-1} $$
   である。
   $a,b\in A$ は任意であったから、$R^{-1}$ は比較可能である。
   $ $
   逆に、$R^{-1}$ が比較可能であると仮定する。
   $R$ が比較可能であることを示すために、任意に $a,b\in A$ をとり、
   $$ a\ne b $$
   と仮定する。
   $R^{-1}$ は比較可能であるから、
   $$ (a,b)\in R^{-1}\lor (b,a)\in R^{-1} $$
   である。
   逆関係の定義より、
   $$ (a,b)\in R^{-1}\Longleftrightarrow (b,a)\in R $$
   かつ
   $$ (b,a)\in R^{-1}\Longleftrightarrow (a,b)\in R $$
   である。
   したがって、
   $$ (b,a)\in R\lor (a,b)\in R $$
   である。
   論理和の交換法則( 証明はコチラ )より、
   $$ (a,b)\in R\lor (b,a)\in R $$
   である。
   $a,b\in A$ は任意であったから、$R$ は比較可能である。
   ゆえに、$R$ が比較可能であることと、$R^{-1}$ が比較可能であることは同値である。

-以上より、
$$ \begin{array}{c} R\text{ は反射的}\Longleftrightarrow R^{-1}\text{ は反射的},\\[4pt] R\text{ は対称的}\Longleftrightarrow R^{-1}\text{ は対称的},\\[4pt] R\text{ は反対称的}\Longleftrightarrow R^{-1}\text{ は反対称的},\\[4pt] R\text{ は推移的}\Longleftrightarrow R^{-1}\text{ は推移的},\\[4pt] R\text{ は比較可能}\Longleftrightarrow R^{-1}\text{ は比較可能} \end{array} $$
が成り立つ。
$$ \Box$$