二項関係 ⑧
Def.
$A,B$ を集合とする。
このとき、$A$ から $B$ への二項関係 $R$ が空関係であるとは、
$$
R=\varnothing
$$
が成り立つことをいう。
$R$ は $A$ から $B$ への二項関係であるから、
$$
R\subseteq A\times B
$$
である。
したがって、$R$ が空関係であることは、任意の $a\in A$ と任意の $b\in B$ に対して、
$$
(a,b)\notin R
$$
が成り立つことと同値である。
すなわち、空関係とは、$A$ のどの元も $B$ のどの元とも関係していない二項関係である。
$A$ から $B$ への二項関係とは、
$$
R\subseteq A\times B
$$
を満たす集合 $R$ のことである。
ここで空集合 $\varnothing$ は任意の集合の部分集合であるから、
$$
\varnothing\subseteq A\times B
$$
である(
証明はコチラ
)。したがって、
$$
R:=\varnothing
$$
と定めることで、$A$ から $B$ への二項関係を考えることができる。
この二項関係が、$A$ から $B$ への空関係である。
特に、$A=B$ の場合、$A$ 上の二項関係とは
$$
R\subseteq A\times A
$$
を満たす集合 $R$ のことである。
このとき、$A$ 上の空関係とは、
$$
R=\varnothing\subseteq A\times A
$$
である二項関係のことである。
すなわち、任意の $a,b\in A$ に対して、
$$
(a,b)\notin R
$$
が成り立つ関係である。
Prop&Proof
$A,B,C$ を集合とし、$R\subseteq A\times B,\ S\subseteq B\times C$ を二項関係とする。
このとき、
$$
R=\varnothing\lor S=\varnothing
\Rightarrow
S\circ R=\varnothing
$$
が成り立つ。
$R=\varnothing\lor S=\varnothing$ と仮定する。
場合分けにより示す。
- $R=\varnothing$ の場合
$S\circ R=\varnothing$ を示すため、任意の $z$ について
$$ z\notin S\circ R $$
を示す。
任意の $z$ をとる。背理法のため、
$$ z\in S\circ R $$
と仮定する。
合成関係の定義より、ある $a\in A,\ b\in B,\ c\in C$ が存在して、
$$ z=(a,c)\land (a,b)\in R\land (b,c)\in S $$
が成り立つ。特に、
$$ (a,b)\in R $$
である。しかし、$R=\varnothing$ であるから、空集合の定義より、
$$ (a,b)\notin R $$
である。これは矛盾である。
したがって、
$$ z\notin S\circ R $$
である。$z$ は任意であったから、$S\circ R$ に属する元は存在しない。ゆえに、
$$ S\circ R=\varnothing $$
である。
$ $ - $S=\varnothing$ の場合
$S\circ R=\varnothing$ を示すため、任意の $z$ について
$$ z\notin S\circ R $$
を示す。
任意の $z$ をとる。背理法のため、
$$ z\in S\circ R $$
と仮定する。
合成関係の定義より、ある $a\in A,\ b\in B,\ c\in C$ が存在して、
$$ z=(a,c)\land (a,b)\in R\land (b,c)\in S $$
が成り立つ。特に、
$$ (b,c)\in S $$
である。しかし、$S=\varnothing$ であるから、空集合の定義より、
$$ (b,c)\notin S $$
である。これは矛盾である。
したがって、
$$ z\notin S\circ R $$
である。
$z$ は任意であったから、$S\circ R$ に属する元は存在しない。ゆえに、
$$ S\circ R=\varnothing $$
である。
-以上より、$R=\varnothing\lor S=\varnothing$ のいずれの場合にも
$$
S\circ R=\varnothing
$$
が成り立つ。
したがって、
$$
R=\varnothing\lor S=\varnothing
\Rightarrow
S\circ R=\varnothing
$$
が成り立つ。
$$ \Box$$
合成関係 $S\circ R$ に元が属するためには、ある $a\in A$ と $b\in B$ と $c\in C$ が存在して
$$
(a,b)\in R\land (b,c)\in S
$$
が成り立つ必要がある。
しかし、$R=\varnothing$ であるならば、
$$
(a,b)\in R
$$
を満たす順序対は存在しない。
したがって、$S$ が空でなくても、
$$
S\circ R=\varnothing
$$
となる。
合成関係 $S\circ R$ に元が属するためには、ある $a\in A$ と $b\in B$ と $c\in C$ が存在して
$$
(a,b)\in R\land (b,c)\in S
$$
が成り立つ必要がある。
しかし、$S=\varnothing$ であるならば、
$$
(b,c)\in S
$$
を満たす順序対は存在しない。
したがって、$R$ が空でなくても、
$$
S\circ R=\varnothing
$$
となる。
一般には、
$$
S\circ R=\varnothing
\Rightarrow
R=\varnothing\lor S=\varnothing
$$
は成り立たない。
反例を与える。
$$
A:=\{1\},\qquad B:=\{2,3\},\qquad C:=\{4\}
$$
とし、
$$
R:=\{(1,2)\}\subseteq A\times B
$$
$$
S:=\{(3,4)\}\subseteq B\times C
$$
と定める。
このとき、
$$
R\neq\varnothing,\qquad S\neq\varnothing
$$
である。
しかし、$R$ の第 $2$ 成分として現れる元は $2$ であり、$S$ の第 $1$ 成分として現れる元は $3$ である。
したがって、同じ中間元 $b\in B$ によって
$$
(a,b)\in R\land (b,c)\in S
$$
を満たすことはできない。
実際、$b=2$ のときは $(2,4)\notin S$ であり、$b=3$ のときは $(1,3)\notin R$ である。
よって、
$$
S\circ R=\varnothing
$$
である。
したがって、
$$
S\circ R=\varnothing
$$
であっても、
$$
R=\varnothing\lor S=\varnothing
$$
とは限らない。
$A,B,C$ を集合とし、$R\subseteq A\times B,\ S\subseteq B\times C$ を二項関係とする。
このとき、
$$
A=\varnothing \lor B=\varnothing \lor C=\varnothing
\Rightarrow
S\circ R=\varnothing
$$
が成り立つ。
$A=\varnothing \lor B=\varnothing \lor C=\varnothing$ と仮定する。
このとき、場合分けにより示す。
- $A=\varnothing$ の場合
$S\circ R=\varnothing$ を示すため、任意の $z$ について
$$ z\notin S\circ R $$
を示す。
任意の $z$ をとる。背理法のため、
$$ z\in S\circ R $$
と仮定する。
合成関係の定義より、ある $a\in A,\ c\in C$ が存在して
$$ z=(a,c) $$
である。特に、
$$ a\in A $$
である。しかし、$A=\varnothing$ であるから、
$$ a\in\varnothing $$
となる。これは空集合の定義に矛盾する。
したがって、
$$ z\notin S\circ R $$
である。$z$ は任意であったから、
$$ S\circ R=\varnothing $$
である。
$ $ - $B=\varnothing$ の場合
$S\circ R=\varnothing$ を示すため、任意の $z$ について
$$ z\notin S\circ R $$
を示す。
任意の $z$ をとる。背理法のため、
$$ z\in S\circ R $$
と仮定する。
合成関係の定義より、ある $a\in A,\ b\in B,\ c\in C$ が存在して
$$ z=(a,c)\land (a,b)\in R\land (b,c)\in S $$
が成り立つ。特に、
$$ b\in B $$
である。しかし、$B=\varnothing$ であるから、
$$ b\in\varnothing $$
となる。これは空集合の定義に矛盾する。
したがって、
$$ z\notin S\circ R $$
である。$z$ は任意であったから、
$$ S\circ R=\varnothing $$
である。
$ $ - $C=\varnothing$ の場合
$S\circ R=\varnothing$ を示すため、任意の $z$ について
$$ z\notin S\circ R $$
を示す。
任意の $z$ をとる。背理法のため、
$$ z\in S\circ R $$
と仮定する。
合成関係の定義より、ある $a\in A,\ c\in C$ が存在して
$$ z=(a,c) $$
である。特に、
$$ c\in C $$
である。しかし、$C=\varnothing$ であるから、
$$ c\in\varnothing $$
となる。これは空集合の定義に矛盾する。
したがって、
$$ z\notin S\circ R $$
である。$z$ は任意であったから、
$$ S\circ R=\varnothing $$
である。
-以上より、$A=\varnothing \lor B=\varnothing \lor C=\varnothing$ のいずれの場合にも、
$$
S\circ R=\varnothing
$$
が成り立つ。したがって、
$$
A=\varnothing \lor B=\varnothing \lor C=\varnothing
\Rightarrow
S\circ R=\varnothing
$$
が成り立つ。
$$ \Box$$
合成関係 $S\circ R$ の元は、ある $a\in A,\ b\in B,\ c\in C$ によって
$$
z=(a,c)\land (a,b)\in R\land (b,c)\in S
$$
と書ける必要がある。
しかし、$A=\varnothing$ であるならば、そもそも $a\in A$ を満たす $a$ が存在しない。
したがって、$S\circ R$ に属する順序対は存在しない。
合成関係 $S\circ R$ の元は、ある中間元 $b\in B$ を用いて
$$
(a,b)\in R
$$
かつ
$$
(b,c)\in S
$$
を同時に満たすことによって作られる。
しかし、$B=\varnothing$ であるならば、そのような中間元 $b\in B$ は存在しない。
したがって、$S\circ R$ に属する順序対は存在しない。
合成関係 $S\circ R$ の元は、ある $a\in A,\ b\in B,\ c\in C$ によって
$$
z=(a,c)\land (a,b)\in R\land (b,c)\in S
$$
と書ける必要がある。
しかし、$C=\varnothing$ であるならば、終点となる $c\in C$ が存在しない。
したがって、$S\circ R$ に属する順序対は存在しない。
$R\subseteq A\times B,\ S\subseteq B\times C$ であることに注意する。
- $A=\varnothing$ または $B=\varnothing$ のとき、
$$ A\times B=\varnothing $$
である( 証明はコチラ )。したがって、
$$ R\subseteq A\times B=\varnothing $$
より、
$$ R=\varnothing $$
である( 証明はコチラ )。
$ $ - また、$B=\varnothing$ または $C=\varnothing$ のとき、
$$ B\times C=\varnothing $$
である( 証明はコチラ )。したがって、
$$ S\subseteq B\times C=\varnothing $$
より、
$$ S=\varnothing $$
である( 証明はコチラ )。
-よって、
$$
A=\varnothing\lor B=\varnothing\lor C=\varnothing
\Rightarrow
R=\varnothing\lor S=\varnothing
$$
が成り立つ。ただし、逆向きは一般には成り立たない。
すなわち、$R=\varnothing$ または $S=\varnothing$ であっても、$A,B,C$ のいずれかが空であるとは限らない。
$A,B,C$ を集合とし、$R\subseteq A\times B,\ S\subseteq B\times C$ を二項関係とする。
このとき、
$$
S\circ R=\varnothing
\Longleftrightarrow
\forall a\in A\ \forall c\in C\ \forall b\in B\
\bigl((a,b)\notin R\lor (b,c)\notin S\bigr)
$$
が成り立つ。
- まず、
$$ S\circ R=\varnothing \Rightarrow \forall a\in A\ \forall c\in C\ \forall b\in B\ \bigl((a,b)\notin R\lor (b,c)\notin S\bigr) $$
を示す。
$S\circ R=\varnothing$ と仮定する。任意に $a\in A,\ c\in C,\ b\in B$ をとる。
示すべきことは、
$$ (a,b)\notin R\lor (b,c)\notin S $$
である。背理法により示すため、
$$ \neg\bigl((a,b)\notin R\lor (b,c)\notin S\bigr) $$
と仮定する。ド・モルガンの法則( 証明はコチラ )より、
$$ (a,b)\in R\land (b,c)\in S $$
が成り立つ。
したがって、合成関係の定義より、
$$ (a,c)\in S\circ R $$
である。しかし、$S\circ R=\varnothing$ であるから、
$$ (a,c)\notin S\circ R $$
である。これは矛盾である。
したがって、
$$ (a,b)\notin R\lor (b,c)\notin S $$
が成り立つ。
$a\in A,\ c\in C,\ b\in B$ は任意であったから、
$$ \forall a\in A\ \forall c\in C\ \forall b\in B\ \bigl((a,b)\notin R\lor (b,c)\notin S\bigr) $$
が成り立つ。
$ $ - 次に、
$$ \forall a\in A\ \forall c\in C\ \forall b\in B\ \bigl((a,b)\notin R\lor (b,c)\notin S\bigr) \Rightarrow S\circ R=\varnothing $$
を示す。
$$ \forall a\in A\ \forall c\in C\ \forall b\in B\ \bigl((a,b)\notin R\lor (b,c)\notin S\bigr) $$
を仮定する。
$S\circ R=\varnothing$ を示すため、任意の $z$ について
$$ z\notin S\circ R $$
を示す。任意の $z$ をとる。
背理法により示すため、
$$ z\in S\circ R $$
と仮定する。
合成関係の定義より、ある $a\in A,\ b\in B,\ c\in C$ が存在して、
$$ z=(a,c)\land (a,b)\in R\land (b,c)\in S $$
が成り立つ。
$ $
一方、仮定より、この $a\in A,\ c\in C,\ b\in B$ に対して
$$ (a,b)\notin R\lor (b,c)\notin S $$
が成り立つ。しかし、
$$ (a,b)\in R\land (b,c)\in S $$
であるから、これは矛盾である。
したがって、
$$ z\notin S\circ R $$
である。$z$ は任意であったから、$S\circ R$ に属する元は存在しない。
ゆえに、
$$ S\circ R=\varnothing $$
である。
-以上より、
$$
S\circ R=\varnothing
\Longleftrightarrow
\forall a\in A\ \forall c\in C\ \forall b\in B\
\bigl((a,b)\notin R\lor (b,c)\notin S\bigr)
$$
が成り立つ。
$$ \Box$$
$S\circ R=\varnothing$ であるとは、$A$ の元 $a$ から $C$ の元 $c$ へ、$B$ の中間元 $b$ を通って到達する方法が存在しないということである。
すなわち、任意の $a\in A,\ b\in B,\ c\in C$ に対して、
$$
(a,b)\in R
$$
と
$$
(b,c)\in S
$$
が同時には成り立たない。
したがって、任意の $a\in A,\ c\in C,\ b\in B$ に対して、
$$
(a,b)\notin R\lor (b,c)\notin S
$$
が成り立つのである。
この記事を高評価した人
この記事に送られたバッジ
投稿者
