WIIS

関係

同値類

目次

関連知識

次のページ:

商集合

Mailで保存
Xで共有

同値類

集合\(A\)上の同値関係\(\sim \)が与えられているものとします。つまり、\(\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*}が成り立つということです。要素\(x\in A\)を任意に選んだ上で、同値関係\(\sim \)のもとで\(x\)と同値であるような\(A\)のすべての要素からなる集合を、\begin{equation*}\left[ x\right] =\left\{ y\in A\ |\ x\sim y\right\}
\end{equation*}で表記し、これを\(x\)を代表元(representative)とする同値類(equivalence class)と呼びます。定義より明らかに、任意の\(x\in A\)について、\begin{equation*}\left[ x\right] \subset A
\end{equation*}が成り立ちます。

同値関係\(\sim \)は対称律を満たすため、\(x,y\in A\)を任意に選んだとき、\begin{equation*}x\sim y\Leftrightarrow y\sim x
\end{equation*}という関係が成り立ちます。したがって、要素\(x\in A\)を代表元とする同値類を、\begin{equation*}\left[ x\right] =\left\{ y\in A\ |\ y\sim x\right\}
\end{equation*}と表現することもできます。

例(集団への所属関係)
ある学校の生徒からなる集合\(A\)が与えられたとき、それぞれの順序対\(\left( x,y\right) \in A\times A\)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x\text{は}y\text{と同じ学年}
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は同値関係です。学生\(x\in A\)を任意に選んだとき、この学生\(x\)を代表元とする同値類は、\begin{eqnarray*}\left[ x\right] &=&\left\{ y\in A\ |\ R\left( x,y\right) \right\} \quad
\because \text{同値類の定義} \\
&=&\left\{ y\in A\ |\ x\text{は}y\text{と同じ学年}\right\} \quad \because R\text{の定義}
\end{eqnarray*}となります。つまり、\(\left[ x\right] \)は学生\(x\)と同じ学年に属するすべての学生からなる集合です。例えば、学生\(x\)が1年生であれば、\(\left[ x\right] \)はすべての1年生からなる集合です。他についても同様です。
例(実数の相等関係)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x=y
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は同値関係です。実数\(x\in \mathbb{R} \)を任意に選んだとき、\(x\)を代表元とする同値類は、\begin{eqnarray*}\left[ x\right] &=&\left\{ y\in \mathbb{R} \ |\ R\left( x,y\right) \right\} \quad \because \text{同値類の定義} \\
&=&\left\{ y\in \mathbb{R} \ |\ x=y\right\} \quad \because R\text{の定義}
\end{eqnarray*}となります。つまり、\(\left[ x\right] \)は\(x\)と等しいすべての実数からなる集合です。例えば、\begin{equation*}\left[ 0\right] =\left\{ 0,\frac{0}{1},\frac{0}{2},\cdots \right\}
\end{equation*}となります。他についても同様です。

例(偶奇の一致判定)
すべての整数からなる集合\(\mathbb{Z} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{Z} \times \mathbb{Z} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x\text{と}y\text{の偶奇が一致する}
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は同値関係です。整数\(x\in \mathbb{Z} \)を任意に選んだとき、\(x\)を代表元とする同値類は、\begin{eqnarray*}\left[ x\right] &=&\left\{ y\in \mathbb{Z} \ |\ R\left( x,y\right) \right\} \quad \because \text{同値類の定義} \\
&=&\left\{ y\in \mathbb{Z} \ |\ x\text{と}y\text{の偶奇が一致する}\right\} \quad \because R\text{の定義}
\end{eqnarray*}となります。つまり、\(\left[ x\right] \)は\(x\)と偶奇が一致するすべての整数からなる集合です。例えば、\(2\)は偶数であるため、\(\left[ 2\right] \)は偶数の整数をすべて集めてできる集合であり、\begin{equation*}\left[ 2\right] =\left\{ \cdots ,-4,-2,0,2,4,\cdots \right\}
\end{equation*}です。他についても同様です。

例(相似関係)
平面上のすべての三角形からなる集合\(A\)が与えられたとき、それぞれの\(\left( x,y\right) \in A\times A\)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x\text{と}y\text{は相似}
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は同値関係です。三角形\(x\in A\)を任意に選んだとき、\(x\)を代表元とする同値類は、\begin{eqnarray*}\left[ x\right] &=&\left\{ y\in \mathbb{Z} \ |\ R\left( x,y\right) \right\} \quad \because \text{同値類の定義} \\
&=&\left\{ y\in \mathbb{Z} \ |\ x\text{と}y\text{は相似}\right\} \quad \because
R\text{の定義}
\end{eqnarray*}となります。つまり、\(\left[ x\right] \)は\(x\)と相似なすべての三角形からなる集合です。
例(整数の合同関係)
すべての整数からなる集合\(\mathbb{Z} \)が与えられたとき、それぞれの\(\left( x,y\right) \in \mathbb{Z} \times \mathbb{Z} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x\equiv y\ \left( \mathrm{mod}\ 2\right)
\end{equation*}を満たすものとして\(R\)を定義します。ただし、\(x\equiv y\ \left( \mathrm{mod}\ n\right) \)は\(x-y\)が\(n\)の整数倍であること(\(x\)が\(n\)を法として\(y\)と合同である)ことを表します。\(R\)は同値関係です。整数\(x\in \mathbb{Z} \)を任意に選んだとき、\(x\)を代表元とする同値類は、\begin{eqnarray*}\left[ x\right] &=&\left\{ y\in \mathbb{Z} \ |\ R\left( x,y\right) \right\} \quad \because \text{同値類の定義} \\
&=&\left\{ y\in \mathbb{Z} \ |\ x\equiv y\ \left( \mathrm{mod}\ 2\right) \right\} \quad \because R\text{の定義} \\
&=&\left\{ y\in \mathbb{Z} \ |\ \exists k\in \mathbb{Z} :x-y=2k\right\} \quad \because \equiv \text{の定義} \\
&=&\left\{ x-2k\in \mathbb{Z} \ |\ k\in \mathbb{Z} \right\}
\end{eqnarray*}となります。具体例を挙げると、整数\(1\in \mathbb{Z} \)を代表元とする同値類は、\begin{eqnarray*}\left[ 1\right] &=&\left\{ 1-2k\ |\ k\in \mathbb{Z} \right\} \\
&=&\left\{ \pm 1,\pm 3,\pm 5,\cdots \right\}
\end{eqnarray*}であり、整数\(2\in \mathbb{Z} \)を代表元とする同値類は、\begin{eqnarray*}\left[ 2\right] &=&\left\{ 2-2k\ |\ k\in \mathbb{Z} \right\} \\
&=&\left\{ 0,\pm 2,\pm 4,\cdots \right\}
\end{eqnarray*}です。他についても同様です。

例(有理数の相等関係)
分母が自然数で分子が整数であるようなすべての商からなる集合\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*}R\left( \frac{z_{1}}{n_{1}},\frac{z_{1}}{n_{2}}\right) \Leftrightarrow
z_{1}n_{2}=z_{2}n_{1}
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は同値関係です。商\(\frac{z}{n}\in \mathbb{Q} \)を任意に選んだとき、\(\frac{z}{n}\)を代表元とする同値類は、\begin{eqnarray*}\left[ \frac{z}{n}\right] &=&\left\{ \frac{z^{\prime }}{n^{\prime }}\in \mathbb{Q} \ |\ R\left( \frac{z}{n},\frac{z^{\prime }}{n^{\prime }}\right) \right\}
\quad \because \text{同値類の定義} \\
&=&\left\{ \frac{z^{\prime }}{n^{\prime }}\in \mathbb{Q} \ |\ zn^{\prime }=z^{\prime }n\right\} \quad \because R\text{の定義}
\end{eqnarray*}となりますが、これを有理数(rational number)と呼びます。例えば、商\(\frac{1}{2}\in \mathbb{Q} \)を代表元とする同値類は、\begin{eqnarray*}\left[ \frac{1}{2}\right] &=&\left\{ \frac{z}{n}\in \mathbb{Q} \ |\ 2z=n\right\} \\
&=&\left\{ \frac{n}{2n}\in \mathbb{Q} \ |\ n\in \mathbb{N} \right\} \\
&=&\left\{ \frac{1}{2},\frac{2}{4},\frac{3}{6},\frac{4}{8},\cdots \right\}
\end{eqnarray*}となります。つまり、有理数\(\left[ \frac{1}{2}\right] \)とは約分したときに\(\frac{1}{2}\)になる商からなる集合です。また、商\(-\frac{4}{5}\in A\)を代表元とする同値類は、\begin{eqnarray*}\left[ -\frac{4}{5}\right] &=&\left\{ \frac{z}{n}\in \mathbb{Q} \ |\ -4n=5z\right\} \\
&=&\left\{ -\frac{4n}{5n}\in \mathbb{Q} \ |\ n\in \mathbb{N} \right\} \\
&=&\left\{ -\frac{4}{5},-\frac{8}{10},-\frac{12}{15},-\frac{16}{20},\cdots
\right\}
\end{eqnarray*}となります。つまり、有理数\(\left[ -\frac{4}{5}\right] \)とは約分したときに\(-\frac{4}{5}\)になる商からなる集合です。有理数\(\left[ \frac{z}{n}\right] \)とは約分したときに\(\frac{z}{n}\)になる商からなる集合であり、\(\left[ \frac{z}{n}\right] \)に属するすべての商を区別せず、それらをすべて\(\frac{z}{n}\)と同一視するということです。
例(有向線分の相等関係)
平面上の点\(A\)を始点とし、点\(B\)を終点とする有向線分を\(\overrightarrow{AB}\)で表します。平面上のすべての有向線分からなる集合\(X\)が与えられたとき、それぞれの順序対\(\left( \overrightarrow{AB},\overrightarrow{CD}\right) \in X\times X\)に対して、\begin{equation*}R\left( \overrightarrow{AB},\overrightarrow{CD}\right) \Leftrightarrow
\overrightarrow{AB}\text{を平行移動すると}\overrightarrow{CD}\text{に重なる}
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は同値関係です。有向線分\(\overrightarrow{AB}\in X\)を任意に選ぶと、これを代表元とする同値類は、\begin{equation*}\left[ \overrightarrow{AB}\right] =\left\{ \overrightarrow{CD}\in X\ |\
\overrightarrow{AB}\text{を平行移動すると}\overrightarrow{CD}\text{に重なる}\right\}
\end{equation*}となりますが、これをベクトル(vector)と呼びます。有向線分は位置・向き・大きさという3つの情報からなる概念ですが、そこから位置情報を除いた概念がベクトルです。平行移動すると重なるような有向線分どうしを区別せず1つのベクトルとみなすということです。ベクトルは向きと大きさという2つの情報から構成される概念です。

例(同値類)
集合\(A=\left\{ 1,2,3,4\right\} \)上の二項関係\(R\)が、\begin{equation*}R=\left\{ \left( 1,1\right) ,\left( 2,2\right) ,\left( 3,3\right) ,\left(
4,4\right) \right\}
\end{equation*}で与えられているものとします。\(R\)は\(A\)上の同値関係です。\(1\in A\)を代表元とする同値類は、\begin{eqnarray*}\left[ 1\right] &=&\left\{ x\in A\ |\ \left( x,1\right) \in R\right\} \quad
\because \text{同値類の定義} \\
&=&\left\{ 1\right\}
\end{eqnarray*}となります。同様に、\begin{eqnarray*}
\left[ 2\right] &=&\left\{ 2\right\} \\
\left[ 3\right] &=&\left\{ 3\right\} \\
\left[ 4\right] &=&\left\{ 4\right\}
\end{eqnarray*}などが成り立ちます。

 

同値類の代表元は交換可能

集合\(A\)上の同値関係\(\sim \)が与えられたとき、適当な要素\(x\in A\)を選べば、\(x\)を代表元とする同値類\(\left[ x\right] \)を生成できます。さらに、\(\left[ x\right] \)の要素を任意に選んだ上で、その新たな要素を代表元とする同値類を構成すると、それは\(\left[ x\right] \)と一致することが保証されます。つまり、同値類は代表元を交換しても集合として区別されません。

命題(同値類の代表元は交換可能)
集合\(A\)上の同値関係\(\sim \)が与えられたとき、\begin{equation*}\forall x\in A,\ \forall y\in \left[ x\right] :\left[ y\right] =\left[ x\right] \end{equation*}が成り立つ。

証明

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

例(偶奇の一致判定)
すべての整数からなる集合\(\mathbb{Z} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{Z} \times \mathbb{Z} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x\text{と}y\text{の偶奇が一致する}
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は同値関係です。先に示したように、整数\(2\in \mathbb{Z} \)を代表元とする同値類\(\left[ 2\right] \)は偶数の整数をすべて集めてできる集合\begin{equation*}\left[ 2\right] =\left\{ \cdots ,-4,-2,0,2,4,\cdots \right\}
\end{equation*}であるため、先の命題より、\begin{equation*}
\cdots =\left[ -4\right] =\left[ -2\right] =\left[ 0\right] =\left[ 2\right] =\left[ 4\right] =\cdots
\end{equation*}が成り立ちます。実際、例えば、\begin{eqnarray*}
\left[ -2\right] &=&\left\{ y\in \mathbb{Z} \ |\ R\left( x,y\right) \right\} \quad \because \text{同値類の定義} \\
&=&\left\{ y\in \mathbb{Z} \ |\ -2\text{と}y\text{の偶奇が一致する}\right\} \quad \because R\text{の定義} \\
&=&\left\{ y\in \mathbb{Z} \ |\ y\text{は偶数}\right\} \quad \because -2\text{は偶数} \\
&=&\left\{ \cdots ,-4,-2,0,2,4,\cdots \right\}
\end{eqnarray*}となり、これは\(\left[ 2\right] \)と一致します。他についても同様です。
例(有理数の相等関係)
分母が自然数で分子が整数であるようなすべての商からなる集合\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*}R\left( \frac{z_{1}}{n_{1}},\frac{z_{1}}{n_{2}}\right) \Leftrightarrow
z_{1}n_{2}=z_{2}n_{1}
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は同値関係です。先に示したように、商\(\frac{1}{2}\in \mathbb{Q} \)を代表元とする同値類は、\begin{equation*}\left[ \frac{1}{2}\right] =\left\{ \frac{1}{2},\frac{2}{4},\frac{3}{6},\frac{4}{8},\cdots \right\}
\end{equation*}であるため、先の命題より、\begin{equation*}
\left[ \frac{1}{2}\right] =\left[ \frac{2}{4}\right] =\left[ \frac{3}{6}\right] =\left[ \frac{4}{8}\right] =\cdots
\end{equation*}が成り立ちます。実際、例えば、\begin{eqnarray*}
\left[ \frac{2}{4}\right] &=&\left\{ \frac{z}{n}\in \mathbb{Q} \ |\ 4z=2n\right\} \\
&=&\left\{ \frac{n}{2n}\in \mathbb{Q} \ |\ n\in \mathbb{N} \right\} \\
&=&\left\{ \frac{1}{2},\frac{2}{4},\frac{3}{6},\frac{4}{8},\cdots \right\}
\end{eqnarray*}となり、これは\(\left[ \frac{1}{2}\right] \)と一致します。他についても同様です。

 

演習問題

問題(同値類)
集合\(A=\left\{ -1,1,2,3,4\right\} \)上の二項関係\(R\)が、\begin{eqnarray*}R &=&\{\left( -1,-1\right) ,\left( 1,1\right) ,\left( 2,2\right) ,\left(
3,3\right) ,\left( 4,4\right) ,\left( -1,1\right) ,\left( 1,-1\right) , \\
&&\left( -1,3\right) ,\left( 3,-1\right) ,\left( 1,3\right) ,\left(
3,1\right) ,\left( 2,4\right) ,\left( 4,2\right) \}
\end{eqnarray*}と定義されているものとします。\(R\)が\(A\)上の同値関係であることを示すとともに、\(A\)のそれぞれの要素を代表元とする同値類を明らかにしてください。
証明

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

関連知識

次のページ:

商集合

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

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