教材一覧
RELATION

同値関係

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

反射律

集合\(A\)上の二項関係\(R\)が以下の条件\begin{equation*}\forall x\in A:xRx
\end{equation*}を満たすとき、つまり、\(A\)の要素\(x\)を任意に選んだとき、\(R\)のもとで\(x\)が自身\(x\)と関係を持つことが保証される場合には、\(R\)は反射律(reflexive law)を満たすといいます。

例(反射律)
ある学校の生徒からなる集合\(A\)が与えられたとき、それぞれの順序対\(\left( x,y\right) \in A\times A\)に対して、\begin{equation*}xRy\Leftrightarrow x\text{は}y\text{と同じ学年}
\end{equation*}を満たすものとして\(R\)を定義します。学生\(x\in A\)を任意に選んだとき、\(x\)は\(x\)自身と同学年であるため\(xRx\)が成り立ちます。したがって\(R\)は反射律を満たします。
例(反射律)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}xRy\Leftrightarrow x=y
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x\in \mathbb{R} \)を任意に選んだとき、\(x=x\)すなわち\(xRx\)が成り立つため\(R\)は反射律を満たします。
例(反射律)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}xRy\Leftrightarrow x\leq y
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x\in \mathbb{R} \)を任意に選んだとき、\(x\leq x\)すなわち\(xRx\)が成り立つため\(R\)は反射律を満たします。
例(反射律)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}xRy\Leftrightarrow x<y
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x\in \mathbb{R} \)を任意に選んだとき、\(x<x\)すなわち\(xRx\)は成り立たないため\(R\)は反射律を満たしません。

集合\(A\)上の二項関係\(R\)を直積集合\(A\times A\)の部分集合とみなすとき、\(R\)が反射律を満たすことは、\begin{equation*}\forall x\in A:\left( x,x\right) \in R
\end{equation*}が成り立つこととして表現されますが、このことは恒等関係を用いて表現することもできます。ただし、集合\(A\)上の恒等関係とは、それぞれの\(\left( x,y\right) \in A\times A\)に対して、\begin{equation*}x\Delta _{A}y\Leftrightarrow x=y
\end{equation*}を満たすものとして定義される\(A\)上の二項関係\(\Delta _{A}\)です。つまり、\(x,y\in A\)が与えられたとき、\(x\)と\(y\)が一致する場合、そしてその場合にのみ\(\Delta _{A}\)のもとで\(x\)は\(y\)と関係を持ちます。

命題(反射律の特徴づけ)
集合\(A\)上の二項関係\(R\)について、\begin{equation*}\Delta _{A}\subset R
\end{equation*}が成り立つことは、\(R\)が反射律を満たすための必要十分条件である。ただし\(\Delta _{A}\)は\(A\)上の恒等関係である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

 

対称律

集合\(A\)上の二項関係\(R\)が以下の条件\begin{equation*}\forall x,y\in A:\left( xRy\Rightarrow yRx\right)
\end{equation*}を満たすとき、つまり、\(A\)の要素\(x,y\)を任意に選んだとき、\(R\)のもとで\(x\)が\(y\)と関係を持つ場合、逆に\(y\)が\(x\)と関係を持つことも保証される場合には、\(R\)は対称律(symmetric law)を満たすといいます。

例(対称律)
ある学校の生徒からなる集合\(A\)が与えられたとき、それぞれの順序対\(\left( x,y\right) \in A\times A\)に対して、\begin{equation*}xRy\Leftrightarrow x\text{は}y\text{と同じ学年}
\end{equation*}を満たすものとして\(R\)を定義します。学生\(x,y\in A\)を任意に選んだとき、\(x\)と\(y\)が同じ学年である場合には\(y\)は\(x\)と同じ学年であるため\(R\)は対称律を満たします。
例(対称律)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}xRy\Leftrightarrow x=y
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x,y\in \mathbb{R} \)を任意に選んだとき、\(x=y\)が成り立つ場合には\(y=x\)も成り立つため\(R\)は反射律を満たします。
例(対称律)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}xRy\Leftrightarrow x\leq y
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x,y\in \mathbb{R} \)を任意に選んだとき、\(x\leq y\)が成り立つ場合に\(y\leq x\)は成り立つとは限りません。実際、\(1\leq 2\)が成り立つ一方で\(2\leq 1\)は成り立ちません。したがって\(R\)は反射律を満たしません。
例(対称律)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}xRy\Leftrightarrow x<y
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x,y\in \mathbb{R} \)を任意に選んだとき、\(x<y\)が成り立つ場合に\(y<x\)は成り立つとは限りません。実際、\(1<2\)が成り立つ一方で\(2<1\)は成り立ちません。したがって\(R\)は反射律を満たしません。

集合\(A\)上の二項関係\(R\)を直積集合\(A\times A\)の部分集合とみなすとき、\(R\)が対称律を満たすことは、\begin{equation*}\forall x,y\in A:\left[ \left( x,y\right) \in R\Rightarrow \left( y,x\right)
\in R\right] \end{equation*}が成り立つこととして表現されますが、このことは逆関係を用いて表現することもできます。ただし、集合\(A\)上の二項関係\(R\)の逆関係とは、任意の\(x,y\in A\)に対して、\begin{equation*}\left( x,y\right) \in R^{-1}\Leftrightarrow \left( y,x\right) \in R
\end{equation*}を満たすものとして定義される\(A\)上の二項関係\(R^{-1}\)です。つまり、\(x,y\in A\)が与えられたとき、\(R\)のもとで\(y\)が\(x\)と関係するとき、そしてその場合にのみ\(R^{-1}\)のもとで\(x\)は\(y\)と関係を持ちます。

命題(対称律の特徴づけ)
集合\(A\)上の二項関係\(R\)について、\begin{equation*}R=R^{-1}
\end{equation*}が成り立つことは、\(R\)が対称律を満たすための必要十分条件である。ただし\(R^{-1}\)は\(R\)の逆関係である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

 

推移律

集合\(A\)上の二項関係\(R\)が以下の条件\begin{equation*}\forall x,y,z\in X:\left[ \left( xRy\wedge yRz\right) \Rightarrow xRz\right] \end{equation*}を満たすとき、つまり、\(A\)の要素\(x,y,z\)を任意に選んだとき、\(R\)のもとで\(x\)が\(y\)と関係を持ち、なおかつ\(y\)が\(z\)と関係を持つ場合、\(x\)と\(z\)が関係を持つことも保証される場合には、\(R\)は推移律(transitive law)を満たすといいます。

例(推移律)
ある学校の生徒からなる集合\(A\)が与えられたとき、それぞれの順序対\(\left( x,y\right) \in A\times A\)に対して、\begin{equation*}xRy\Leftrightarrow x\text{は}y\text{と同じ学年}
\end{equation*}を満たすものとして\(R\)を定義します。学生\(x,y,z\in A\)を任意に選んだとき、\(x\)と\(y\)が同じ学年であり、\(y\)が\(z\)と同じ学年であれば、\(x\)と\(z\)が同じ学年であることが保証されます。したがって\(R\)は推移律を満たします。
例(推移律)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}xRy\Leftrightarrow x=y
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x,y,z\in \mathbb{R} \)を任意に選んだとき、\(x=y\)と\(y=z\)が成り立つ場合には\(x=z\)が成り立つことが保証されます。したがって\(R\)は推移律を満たします。
例(推移律)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}xRy\Leftrightarrow x\leq y
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x,y,z\in \mathbb{R} \)を任意に選んだとき、\(x\leq y\)と\(y\leq z\)が成り立つ場合には\(x\leq z\)が成り立つことが保証されます。したがって\(R\)は推移律を満たします。
例(推移律)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}xRy\Leftrightarrow x<y
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x,y\in \mathbb{R} \)を任意に選んだとき、\(x<y\)と\(y<z\)が成り立つ場合には\(x<z\)が成り立つことが保証されます。したがって\(R\)は推移律を満たします。

集合\(A\)上の二項関係\(R\)を直積集合\(A\times A\)の部分集合とみなすとき、\(R\)が推移律を満たすことは、\begin{equation*}\forall x,y,z\in A:\left[ \left( x,y\right) \in R\wedge \left( y,z\right)
\in R\Rightarrow \left( x,z\right) \in R\right] \end{equation*}が成り立つこととして表現されますが、このことは合成関係を用いて表現することもできます。ただし、集合\(A\)上の二項関係\(R,S\)の合成関係とは、任意の\(x,y\in A\)に対して、\begin{equation*}\left( x,y\right) \in S\circ R\Leftrightarrow \exists z\in A:\left(
x,z\right) \in R\wedge \left( z,y\right) \in S
\end{equation*}を満たすものとして定義される\(A\)上の二項関係\(S\circ R\)です。つまり、\(x,y\in A\)が与えられたとき、\(R\)のもとで\(x\)と関係を持ち、なおかつ\(S\)のもとで\(y\)と関係を持つような\(A\)の要素が存在するとき、そしてその場合にのみ\(S\circ R\)のもとで\(x\)は\(y\)と関係を持ちます。

命題(推移律の特徴づけ)
集合\(A\)上の二項関係\(R\)について、\begin{equation*}R\circ R\subset R
\end{equation*}が成り立つことは、\(R\)が推移律を満たすための必要十分条件である。ただし\(R\circ R\)は\(R\)と\(R\)の合成関係である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

 

同値関係

集合\(A\)上の二項関係\(R\)が反射律と対称律および推移律を満たす場合、すなわち、\begin{eqnarray*}&&\left( E_{1}\right) \ \forall x\in A:xRx \\
&&\left( E_{2}\right) \ \forall x,y\in A:\left( xRy\Rightarrow yRx\right) \\
&&\left( E_{3}\right) \ \forall x,y,z\in X:\left[ \left( xRy\wedge
yRz\right) \Rightarrow xRz\right] \end{eqnarray*}を満たす場合、そのような\(R\)を同値関係(equivalence relation)と呼びます。同値関係を規定する以上の3つの条件を総称して同値律(equivalence law)と呼びます。また、要素\(x,y\in A\)を選んだとき、同値関係\(R\)のもとで\(x\)が\(y\)と関係を持つ場合、すなわち\(xRy\)が成り立つ場合には、\(x\)と\(y\)は同値(equivalent)であるといいます。

多くの場合、同値関係を記号\(\sim \)で表記します。つまり、集合\(A\)上の同値関係\(R\)が与えられたとき、任意の\(\left( x,y\right) \in A\times A\)について、\begin{equation*}x\sim y\Leftrightarrow xRy
\end{equation*}を満たすものとして\(\sim \)を定義するということです。この記号を用いて同値律を表現すると、\begin{eqnarray*}&&\left( E_{1}\right) \ \forall x\in A:x\sim x \\
&&\left( E_{2}\right) \ \forall x,y\in A:\left( x\sim y\Rightarrow y\sim
x\right) \\
&&\left( E_{3}\right) \ \forall x,y,z\in X:\left[ \left( x\sim y\wedge y\sim
z\right) \Rightarrow x\sim z\right] \end{eqnarray*}となります。

先の議論より、集合\(A\)上の二項関係\(R\)が同値関係であることを以下のように特徴づけることができます。

命題(同値関係の特徴づけ)
集合\(A\)上の二項関係\(R\)が、\begin{eqnarray*}&&\left( E_{1}\right) \ \Delta _{A}\subset R \\
&&\left( E_{2}\right) \ R=R^{-1} \\
&&\left( E_{3}\right) \ R\circ R\subset R
\end{eqnarray*}がすべて満たすことは、\(R\)が同値関係であるための必要十分条件である。
例(同値関係)
ある学校の生徒からなる集合\(A\)が与えられたとき、それぞれの順序対\(\left( x,y\right) \in A\times A\)に対して、\begin{equation*}xRy\Leftrightarrow x\text{は}y\text{と同じ学年}
\end{equation*}を満たすものとして\(R\)を定義します。先に示したように、この\(R\)は反射律、対称律および推移律を満たすため、これは\(A\)上の同値関係です。
例(推移律)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}xRy\Leftrightarrow x=y
\end{equation*}を満たすものとして\(R\)を定義します。先に示したように、この\(R\)は反射律、対称律および推移律を満たすため、これは\(\mathbb{R} \)上の同値関係です。
例(推移律)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}xRy\Leftrightarrow x\leq y
\end{equation*}を満たすものとして\(R\)を定義します。先に示したように、この\(R\)は反射律と推移律を満たす一方で対称律を満たさないため、これは\(\mathbb{R} \)上の同値関係ではありません。
例(推移律)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}xRy\Leftrightarrow x<y
\end{equation*}を満たすものとして\(R\)を定義します。先に示したように、この\(R\)は反射律と推移律を満たす一方で対称律を満たさないため、これは\(\mathbb{R} \)上の同値関係ではありません。

 

演習問題

問題(三角形の相似関係)
平面上のすべての三角形からなる集合\(A\)が与えられたとき、それぞれの順序対\(\left( x,y\right)\in A\times A\)に対して、\begin{equation*}xRy\Leftrightarrow x\text{は}y\text{と相似}
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は\(A\)上の同値関係ですか。議論してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(整数の合同関係)
すべての整数からなる集合\(\mathbb{Z} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{Z} \times \mathbb{Z} \)に対して、\begin{equation*}xRy\ \overset{def}{\Leftrightarrow }\ x\equiv y\ (\mathrm{mod}\ 2)
\end{equation*}を満たすものとして\(R\)を定義します。ただし、右側の\(x\equiv y\ (\mathrm{mod}\ 2)\)は、\(x\)が\(2\)を(mod)として\(y\)と合同であること、すなわち、\(x-y\)が\(2\)の整数倍であることを表す記号です。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(有理数の相等関係)
すべての有理数からなる集合は、\begin{equation*}\mathbb{Q} =\left\{ \frac{z}{n}\ |\ z\in \mathbb{Z} \wedge n\in \mathbb{N} \right\}
\end{equation*}と定義されます。このとき、それぞれの順序対\(\left( \frac{z_{1}}{n_{1}},\frac{z_{2}}{n_{2}}\right) \in \mathbb{Q} \times \mathbb{Q} \)に対して、\begin{equation*}\frac{z_{1}}{n_{1}}R\frac{z_{2}}{n_{2}}\Leftrightarrow z_{1}n_{2}=z_{2}n_{1}
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は\(\mathbb{Q} \)上の同値関係ですか。議論してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(有向線分の相等関係)
平面上の点\(A\)を始点とし、点\(B\)を終点とする有向線分を\(\overrightarrow{AB}\)で表します。平面上のすべての有向線分からなる集合\(X\)が与えられたとき、それぞれの順序対\(\left( \overrightarrow{AB},\overrightarrow{CD}\right) \in X\times X\)に対して、\begin{equation*}\overrightarrow{AB}\ R\ \overrightarrow{CD}\Leftrightarrow \overrightarrow{AB}\text{を平行移動すると}\overrightarrow{CD}\text{に重なる}
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は\(X\)上の同値関係ですか。議論してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

次回は同値類について解説します。

質問・コメント(プレミアム会員限定) 次へ進む
< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録