反射律
集合\(A\)上の二項関係\(R\)が以下の条件\begin{equation*}\forall x\in A:xRx
\end{equation*}を満たすとき、つまり、\(A\)の要素\(x\)を任意に選んだとき、\(R\)のもとで\(x\)が自身\(x\)と関係を持つことが保証される場合には、\(R\)は反射律(reflexive law)を満たすといいます。
\end{equation*}を満たすものとして\(R\)を定義します。学生\(x\in A\)を任意に選んだとき、\(x\)は\(x\)自身と同学年であるため\(xRx\)が成り立ちます。したがって\(R\)は反射律を満たします。
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x\in \mathbb{R} \)を任意に選んだとき、\(x=x\)すなわち\(xRx\)が成り立つため\(R\)は反射律を満たします。
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x\in \mathbb{R} \)を任意に選んだとき、\(x\leq x\)すなわち\(xRx\)が成り立つため\(R\)は反射律を満たします。
\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\)と関係を持ちます。
\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)を満たすといいます。
\end{equation*}を満たすものとして\(R\)を定義します。学生\(x,y\in A\)を任意に選んだとき、\(x\)と\(y\)が同じ学年である場合には\(y\)は\(x\)と同じ学年であるため\(R\)は対称律を満たします。
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x,y\in \mathbb{R} \)を任意に選んだとき、\(x=y\)が成り立つ場合には\(y=x\)も成り立つため\(R\)は反射律を満たします。
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x,y\in \mathbb{R} \)を任意に選んだとき、\(x\leq y\)が成り立つ場合に\(y\leq x\)は成り立つとは限りません。実際、\(1\leq 2\)が成り立つ一方で\(2\leq 1\)は成り立ちません。したがって\(R\)は反射律を満たしません。
\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\)と関係を持ちます。
\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)を満たすといいます。
\end{equation*}を満たすものとして\(R\)を定義します。学生\(x,y,z\in A\)を任意に選んだとき、\(x\)と\(y\)が同じ学年であり、\(y\)が\(z\)と同じ学年であれば、\(x\)と\(z\)が同じ学年であることが保証されます。したがって\(R\)は推移律を満たします。
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x,y,z\in \mathbb{R} \)を任意に選んだとき、\(x=y\)と\(y=z\)が成り立つ場合には\(x=z\)が成り立つことが保証されます。したがって\(R\)は推移律を満たします。
\end{equation*}を満たすものとして\(R\)を定義します。実数\(x,y,z\in \mathbb{R} \)を任意に選んだとき、\(x\leq y\)と\(y\leq z\)が成り立つ場合には\(x\leq z\)が成り立つことが保証されます。したがって\(R\)は推移律を満たします。
\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\)と関係を持ちます。
\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\)が同値関係であることを以下のように特徴づけることができます。
&&\left( E_{2}\right) \ R=R^{-1} \\
&&\left( E_{3}\right) \ R\circ R\subset R
\end{eqnarray*}がすべて満たすことは、\(R\)が同値関係であるための必要十分条件である。
\end{equation*}を満たすものとして\(R\)を定義します。先に示したように、この\(R\)は反射律、対称律および推移律を満たすため、これは\(A\)上の同値関係です。
\end{equation*}を満たすものとして\(R\)を定義します。先に示したように、この\(R\)は反射律、対称律および推移律を満たすため、これは\(\mathbb{R} \)上の同値関係です。
\end{equation*}を満たすものとして\(R\)を定義します。先に示したように、この\(R\)は反射律と推移律を満たす一方で対称律を満たさないため、これは\(\mathbb{R} \)上の同値関係ではありません。
\end{equation*}を満たすものとして\(R\)を定義します。先に示したように、この\(R\)は反射律と推移律を満たす一方で対称律を満たさないため、これは\(\mathbb{R} \)上の同値関係ではありません。
演習問題
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は\(A\)上の同値関係ですか。議論してください。
\end{equation*}を満たすものとして\(R\)を定義します。ただし、右側の\(x\equiv y\ (\mathrm{mod}\ 2)\)は、\(x\)が\(2\)を法(mod)として\(y\)と合同であること、すなわち、\(x-y\)が\(2\)の整数倍であることを表す記号です。
\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} \)上の同値関係ですか。議論してください。
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は\(X\)上の同値関係ですか。議論してください。
次回は同値類について解説します。
質問・コメント(プレミアム会員限定) 次へ進む
プレミアム会員専用コンテンツです
【ログイン】【会員登録】