推移律を満たす二項関係
集合\(A\)上の二項関係\(R\)が以下の条件\begin{equation*}\forall x,y,z\in A:\left[ \left( R\left( x,y\right) \wedge R\left(
y,z\right) \right) \Rightarrow R\left( x,z\right) \right]
\end{equation*}すなわち、\begin{equation*}
\forall x,y,z\in A:\left[ \left( \left( x,y\right) \in R\wedge \left(
y,z\right) \in R\right) \Rightarrow \left( x,z\right) \in R\right]
\end{equation*}を満たす場合には、つまり、\(A\)の要素\(x,y,z\)を任意に選んだとき、\(R\)のもとで\(x\)が\(y\)と関係を持つとともに\(y\)が\(z\)と関係を持つ場合に、\(x\)と\(z\)が関係を持つことが保証されるならば\(R\)は推移律（transitive law）を満たすと言います。
以下は推移律を満たす二項関係の例です。
\end{equation*}を満たすものとして\(R\)を定義します。学生\(x,y,z\in A\)を任意に選んだとき、\(x\)と\(y\)が同じ学年であるとともに\(y\)と\(z\)が同じ学年である場合には\(x\)と\(z\)は同じ学年です。したがって\(R\)は推移律を満たします。
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x,y,z\in \mathbb{R} \)を任意に選んだとき、\begin{equation*}\left( x=y\wedge y=z\right) \Rightarrow x=z
\end{equation*}が成り立つため\(R\)は推移律を満たします。
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x,y,z\in \mathbb{R} \)を任意に選んだとき、\begin{equation*}\left( x\leq y\wedge y\leq z\right) \Rightarrow x\leq z
\end{equation*}が成り立つため\(R\)は推移律を満たします。
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x,y,z\in \mathbb{R} \)を任意に選んだとき、\begin{equation*}\left( x<y\wedge y<z\right) \Rightarrow x<z
\end{equation*}が成り立つため\(R\)は推移律を満たします。
\end{equation*}を満たすものとして\(R\)を定義します。集合\(A,B,C\in \mathfrak{A}\)を任意に選んだとき、\begin{equation*}\left( A\subset B\wedge B\subset C\right) \Rightarrow A\subset C
\end{equation*}が成り立つため\(R\)は推移律を満たします。
\end{equation*}を満たすものとして\(R\)を定義します。三角形\(x,y,z\in A\)を任意に選んだとき、\(x\)と\(y\)が相似であるとともに\(y\)と\(z\)が相似である場合には\(x\)と\(z\)は相似です。したがって\(R\)は推移律を満たします。
&\Leftrightarrow &x=y\wedge y=z\quad \because \text{恒等関係の定義} \\
&\Rightarrow &x=z \\
&\Leftrightarrow &\left( x,z\right) \in \Delta _{A}\quad \because \text{恒等関係の定義}
\end{eqnarray*}が成り立つからです。
\end{equation*}です。\(x,y,z\in A\)を任意に選んだとき、\begin{equation*}\left[ \left( x,y\right) \in A\times A\wedge \left( y,z\right) \in A\times A\right] \Rightarrow \left( x,z\right) \in A\times A
\end{equation*}が成り立つため\(R\)は推移律を満たします。
\end{equation*}です。\(x,y,z\in A\)を任意に選んだとき、\(\left( x,y\right) \in \phi \)と\(\left( y,z\right) \in \phi \)はともに偽であるため、\begin{equation*}\left[ \left( x,y\right) \in \phi \wedge \left( y,z\right) \in \phi \right] \Rightarrow \left( x,z\right) \in \phi
\end{equation*}は真です。したがって\(R\)は推移律を満たします。
2,3\right) ,\left( 3,3\right) \right\}
\end{equation*}で与えられているものとします。\(i,j,k\in A\)を任意に選んだとき、\begin{equation*}\left[ \left( i,j\right) \in R\wedge \left( j,k\right) \in R\right] \Rightarrow \left( i,k\right) \in R
\end{equation*}が成り立つため\(R\)は推移律を満たします。
推移律を満たさない二項関係
逆に、集合\(A\)上の二項関係\(R\)が推移律を満たさないこととは、\begin{equation*}\exists x,y,z\in A:\left[ R\left( x,y\right) \wedge R\left( y,z\right)
\wedge \lnot R\left( x,z\right) \right]
\end{equation*}すなわち、\begin{equation*}
\exists x,y,z\in A:\left[ \left( x,y\right) \in R\wedge \left( y,z\right)
\in R\wedge \left( x,z\right) \not\in R\right]
\end{equation*}が成り立つことを意味します。つまり、\(A\)の要素\(x,y,z\)の中に、\(R\)のもとで\(x\)が\(y\)と関係を持つとともに\(y\)が\(z\)と関係を持つ一方で\(x\)と\(z\)が関係を持たないようなものが存在するということです。
以下は推移律を満たさない二項関係の例です。
\end{equation*}を満たすものとして\(R\)を定義します。ヒト\(x,y,z\in A\)を任意に選んだとき、\(x\)は\(y\)の子供であるとともに\(y\)が\(z\)の子供であるとき\(x\)は\(z\)の子供ではありません。したがって\(R\)は推移律を満たしません。
\end{equation*}を満たすものとして\(R\)を定義します。\(1,2\in \mathbb{R} \)に注目したとき、\begin{equation*}1\not=2\wedge 2\not=1\wedge 1=1
\end{equation*}が成り立つため\(R\)は推移性を満たしません。
3,3\right) ,\left( 3,1\right) \right\}
\end{equation*}で与えられているものとします。このとき、\(1,2,3\in A\)について、\begin{equation*}\left( 1,2\right) \in R\wedge \left( 2,3\right) \in R\wedge \left(
1,3\right) \not\in R
\end{equation*}が成り立つため、\(R\)は推移律を満たしません。
推移律と合成関係の関係
集合\(A\)上の二項関係\(R,S\)の合成関係\(S\circ R\)とは、それぞれの\(x,y\in A\)に対して、\begin{equation*}\left( S\circ R\right) \left( x,y\right) \Leftrightarrow \exists z\in A:
\left[ R\left( x,z\right) \wedge S\left( z,y\right) \right]
\end{equation*}すなわち、\begin{equation*}
\left( x,y\right) \in S\circ R\Leftrightarrow \exists z\in A:\left[ \left(
x,z\right) \in R\wedge \left( z,y\right) \in S\right]
\end{equation*}を満たすものとして定義される\(A\)上の二項関係です。つまり、集合\(A\)の2つの要素\(x,y\)が任意に与えられたとき、\(R\)のもとで\(x\)と\(z\)が関係を持つとともに\(S\)のもとで\(z\)と\(y\)が関係を持つような\(A\)の要素\(z\)が存在するとき、そしてその場合にのみ\(S\circ R\)のもとで\(x\)と\(y\)が関係を持ちます。集合\(A\)上の二項関係\(R\)が推移律を満たすことは合成関係を用いて以下のように表現できます。
\end{equation*}が成り立つことは、\(R\)が推移律を満たすための必要十分条件である。ただし\(R\circ R\)は\(R\)と\(R\)の合成関係である。
つまり、集合\(A\)上の二項関係\(R\)が推移律を満たすことと、それが合成関係\(R\circ R\)を部分集合として持つことは必要十分であるということです。
推移律と関係の演算
推移律を満たす二項関係どうしの共通関係もまた推移律を満たすことが保証されます。
推移律を満たす二項関係の補関係は推移律を満たすとは限りません。以下の例より明らかです。
\end{equation*}で与えられているものとします。\(i,j,k\in A\)を任意に選んだとき、\(\left(i,j\right) \in R\)かつ\(\left( j,k\right) \in R\)は成り立たないため、\begin{equation*}\left[ \left( i,j\right) \in R\wedge \left( j,k\right) \in R\right] \Rightarrow \left( i,k\right) \in R
\end{equation*}は真であり、したがって\(R\)は推移性を満たします。\(R\)の補関係は、\begin{equation*}R^{c}=\left\{ \left( 1,1\right) ,\left( 1,3\right) ,\left( 2,1\right)
,\left( 2,2\right) ,\left( 2,3\right) ,\left( 3,1\right) ,\left( 3,2\right)
,\left( 3,3\right) \right\}
\end{equation*}ですが、\(1,2,3\in A\)について、\begin{equation*}\left( 1,3\right) \in R^{c}\wedge \left( 3,2\right) \in R^{c}\wedge \left(
1,2\right) \not\in R^{c}
\end{equation*}が成り立つため\(R\)は推移律を満たしません。
推移律を満たす二項関係どうしの和関係は推移律を満たすとは限りません。以下の例より明らかです。
S &=&\left\{ \left( 2,3\right) \right\}
\end{eqnarray*}で与えられているものとします。\(R\)と\(S\)はともに推移律を満たします。\(R\)と\(S\)の和関係は、\begin{equation*}R\cup S=\left\{ \left( 1,2\right) ,\left( 2,3\right) \right\}
\end{equation*}ですが、\(1,2,3\in A\)について、\begin{equation*}\left( 1,2\right) \in R\cup S\wedge \left( 2,3\right) \in R\cup S\wedge
\left( 1,3\right) \not\in R\cup S
\end{equation*}が成り立つため\(R\cup S\)は推移律を満たしません。
演習問題
\end{equation*}を満たすものとして\(R\)を定義します。ただし、\(x\equiv y\ \left( \mathrm{mod}\ 2\right) \)は\(x-y\)が\(2\)の整数倍であること（\(x\)が\(2\)を法として\(y\)と合同である）ことを表します。\(R\)は推移律を満たすでしょうか。議論してください。
z_{1}n_{2}=z_{2}n_{1}
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は推移律を満たすでしょうか。議論してください。
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は推移律を満たすでしょうか。議論してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】