集合 X 上の同値関係 R は X 上の二項関係であるため、直積集合 X×X の部分集合としても解釈可能です。このような視点のもとで、同値関係 R が満たす性質である同値律(推移律・対称律・推移律)を、直積の部分集合が満たすべき性質として記述しなおします。

反射律 恒等関係 対称律 逆関係 推移律 合成関係

2019年10月11日:公開

直積の部分集合としての同値関係

集合\(X\)上の二項関係\(R\)を直積集合\(X\times X\)の部分集合と同一視するとき、それぞれの順序対\(\left( x,y\right) \in X\times X\)に対して、\begin{equation*}
(x,y)\in R\ \Leftrightarrow \ xRy
\end{equation*}という関係が成り立ちます。つまり、順序対\(\left( x,y\right) \)が同値関係\(R\)の要素であることと、\(R\)のもとで\(x\)が\(y\)と同値であることは必要十分です。

以上の表記を踏まえると、同値律を、\begin{eqnarray*}
&&\left( a\right) \ \forall x\in X:(x,x)\in R \\
&&\left( b\right) \ \forall x,y\in X:\left[ (x,y)\in R\ \Rightarrow \ (y,x)\in R\right] \\
&&\left( c\right) \ \forall x,y,z\in X:\left\{ \left[ (x,y)\in R\ \wedge \ (y,z)\in R)\right] \ \Rightarrow \ (x,z)\in R\right\}
\end{eqnarray*}と言い換えることができます。つまり、以上の性質を満たす\(X\times X\)の部分集合\(R\)として\(X\)上の同値関係を定義することも可能です。

 

恒等関係を用いた反射律の特徴づけ

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

さて、集合\(X\)上の二項関係\(R\)が反射律を満たすならば、任意の\(\left( x,y\right) \in X\times X\)に対して、\begin{align*}
(x,y)\in \Delta _{X}& \Leftrightarrow \ x=y\quad \because \Delta _{X}\text{の定義} \\
& \Rightarrow \ (x,y)\in R\quad \because R\text{の反射律}
\end{align*}となるため\(\Delta _{X}\subset R\)が成り立ちます。逆に、集合\(X\)上の二項関係\(R\)が\(\Delta _{X}\subset R\)を満たすものとしましょう。\(x\in X\)を任意に選ぶと、\(\Delta _{X}\)の定義より\(\left( x,x\right) \in \Delta _{x}\)が成り立ちますが、これと\(\Delta _{X}\subset R\)より\(\left( x,x\right) \in R\)が成り立ちます。したがって\(R\)は反射律を満たします。

以上の議論を踏まえると、集合\(X\)上の二項関係\(R\)が反射律を満たすことは、\(R\)が\(X\)上の恒等関係\(\Delta _{X}\)を部分集合として含むこととして言い換え可能です。

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

 

逆関係を用いた対称律の特徴づけ

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

さて、集合\(X\)上の二項関係\(R\)が対称律を満たすならば、任意の\(\left( x,y\right) \in X\times X\)に対して、\begin{align*}
\left( x,y\right) \in R& \Rightarrow \left( y,x\right) \in R\quad \because R\text{の対称律} \\
& \Leftrightarrow \left( x,y\right) \in R^{-1}\quad \because R^{-1}\text{の定義}
\end{align*}となるため\(R\subset R^{-1}\)が成り立ちます。同時に、\begin{align*}
\left( x,y\right) \in R^{-1}& \Leftrightarrow \left( y,x\right) \in R\quad \because R^{-1}\text{の定義} \\
& \Rightarrow \left( x,y\right) \in R\quad \because R\text{の対称律}
\end{align*}となるため\(R^{-1}\subset R\)が成り立つため\(R=R^{-1}\)となります。逆に、集合\(X\)上の二項関係\(R\)とその逆関係\(R^{-1}\)の間に\(R=R^{-1}\)が成り立つものとします。このとき、任意の\(\left( x,y\right) \in X\times X\)について、\begin{eqnarray*}
\left( x,y\right) \in R &\Leftrightarrow &\left( y,x\right) \in R^{-1}\quad \because R^{-1}\text{の定義} \\
&\Leftrightarrow &\left( y,x\right) \in R\quad \because R=R^{-1}
\end{eqnarray*}となるため\(R\)は対称律を満たします。

以上の議論を踏まえると、集合\(X\)上の二項関係\(R\)が対称律を満たすことは、\(R\)とその逆関係\(R^{-1}\)が一致することとして言い換え可能です。

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

 

合成関係を用いた推移律の特徴づけ

集合\(X\)上の二項関係\(R\)を直積集合\(X\times X\)の部分集合とみなすとき、\(R\)が推移律を満たすことは、\begin{equation*}
\forall x,y,z\in X:\left\{ \left[ (x,y)\in R\ \wedge \ (y,z)\in R)\right] \ \Rightarrow \ (x,z)\in R\right\}
\end{equation*}が成り立つことを意味しますが、このことは合成関係を用いて表現することもできます。ただし、集合\(X\)上の二項関係\(R,S\)の合成関係\(S\circ R\)とは、それぞれの順序対\(\left( x,y\right) \in X\times X\)に対して、\begin{equation*}
xS\circ Ry\ \overset{def}{\Leftrightarrow }\ \left[ \exists z\in X:(xRz\ \wedge \ zSy)\right] \end{equation*}を満たすものとして定義される\(X\)上の二項関係\(S\circ R\)です。つまり、順序対\(\left( x,y\right) \)について\(xRz\)と\(zSy\)をともに満たす\(z\)が存在するとき、そしてその場合にのみ\(S\circ R\)のもとで\(x\)と\(y\)は関係を持ちます。

さて、集合\(X\)上の二項関係\(R\)が推移律を満たすならば、任意の\(\left( x,y\right) \in X\times X\)に対して、\begin{align*}
\left( x,y\right) \in R\circ R& \Leftrightarrow \left[ \exists z\in X:(xRz\ \wedge \ zRy)\right] \quad \because R\circ R\text{の定義} \\
& \Rightarrow xRy\quad \because R\text{の推移律} \\
& \Leftrightarrow \left( x,y\right) \in R
\end{align*}となるため\(R\circ R\subset R\)が成り立ちます。逆に、集合\(X\)上の二項関係\(R\)と合成関係\(R\circ R\)の間に\(R\circ R\subset R\)が成り立つものとします。\(xRy\)かつ\(yRz\)を満たす\(x,y,z\in X\)を任意に選ぶと、\begin{eqnarray*}
\exists y\in X:(xRy\ \wedge \ yRz) &\Leftrightarrow &\ xR\circ Ry\quad \because R\circ R\text{の定義} \\
&\Leftrightarrow &\ \left( x,y\right) \in R\circ R \\
&\Rightarrow &\ \left( x,y\right) \in R\quad \because R\circ R\subset R \\
&\Leftrightarrow &\ xRy
\end{eqnarray*}となるため\(R\)は推移律を満たします。

以上の議論を踏まえると、集合\(X\)上の二項関係\(R\)が推移律を満たすことは、合成関係\(R\circ R\)が\(R\)の部分集合であることとして言い換え可能です。

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

次回は同値類と呼ばれる概念について学びます。
次へ進む 演習問題(プレミアム会員限定)

ワイズをさらに活用するための会員サービス

ユーザー名とメールアドレスを入力して一般会員に無料登録すれば、質問やコメントを投稿できるようになります。さらに、有料(500円/月)のプレミアム会員へアップグレードすることにより、プレミアムコンテンツ(命題の証明や演習問題、解答など)にアクセスできます。
会員サービス

ディスカッションに参加しますか?

質問やコメントを投稿するにはログインが必要です。
ログイン

アカウント
ログイン