教材一覧
RELATION

商集合

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

同値であることと等しい同値類であることは必要十分

集合\(A\)上の同値関係\(\sim \)が与えられたとき、要素\(x,y\in A\)を代表元とする同値類について、\begin{equation*}\left[ x\right] =\left[ y\right] \end{equation*}が成り立つものとします。このとき、\begin{eqnarray*}
x &\in &\left\{ z\in A\ |\ z\sim x\right\} \quad \because \sim \text{の反射律より}z\sim z \\
&=&\left[ x\right] \quad \because \text{同値類の定義} \\
&=&\left[ y\right] \quad \because \left[ x\right] =\left[ y\right] \\
&=&\left\{ z\in A\ |\ z\sim y\right\} \quad \because \text{同値類の定義}
\end{eqnarray*}すなわち、\begin{equation*}
x\in \left\{ z\in A\ |\ z\sim y\right\}
\end{equation*}すなわち、\begin{equation*}
x\sim y
\end{equation*}が成り立ちます。つまり、2つの同値類\(\left[ x\right] ,\left[ y\right] \)が等しいとき、それらの代表元\(x,y\)が同値であることが保証されるということです。その逆も成立します。つまり、同値な2つの要素\(x,y\)が与えられたとき、それらを代表元とする同値類\(\left[ x\right] ,\left[ y\right] \)が等しいことが保証されます(演習問題にします)。したがって以下の命題を得ます。

命題(同値であることと等しい同値類であることは必要十分)
集合\(A\)上の同値関係\(\sim \)が与えられたとき、任意の\(x,y\in A\)に対して、\begin{equation*}\left[ x\right] =\left[ y\right] \Leftrightarrow x\sim y
\end{equation*}という関係が成り立つ。
証明

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

繰り返しになりますが、等しい同値類\(\left[ x\right] ,\left[ y\right] \)が与えられたとき、上の命題より、それらの代表元である\(x\)と\(y\)が同値であることが保証されます。逆に、\(x\)と\(y\)が同値であるとき、やはり上の命題より、それらを代表元とする同値類\(\left[ x\right] ,\left[ y\right] \)が等しいことが保証されます。つまり、「同値類として等しい」という事実と「同値である」という事実を必要に応じて言い換えながら議論を行うことができます。これは非常に便利な手法であり多用することになります。

例(学年)
ある学校の生徒からなる集合\(A\)が与えられたとき、それぞれの順序対\(\left( x,y\right) \in A\times A\)に対して、\begin{equation*}xRy\Leftrightarrow x\text{は}y\text{と同じ学年}
\end{equation*}を満たすものとして定義される\(R\)は\(A\)上の同値関係です。学生\(x\in X\)を任意に選んだとき、\(\left[ x\right] \)は\(x\)と同じ学年の学生からなる集合です。2人の学生\(x,y\in X\)を任意に選んだとき、上の命題より、\begin{equation*}\left[ x\right] =\left[ y\right] \Leftrightarrow x\text{は}y\text{と同じ学年}
\end{equation*}という関係が成り立ちます。つまり、\(x\)と同じ学生からなる集合と\(y\)と同じ学生からなる集合が等しいことと、\(x\)と\(y\)が同じ学年であることは必要十分です。
例(合同な整数)
すべての整数からなる集合\(\mathbb{Z} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{Z} \times \mathbb{Z} \)に対して、\begin{equation*}xRy\Leftrightarrow x\equiv y\ (\mathrm{mod}\ 2)
\end{equation*}を満たすものとして\(R\)を定義します。整数\(x\in \mathbb{Z} \)を任意に選んだとき、\begin{equation*}\left[ x\right] =\left\{ x,x\pm 2,x\pm 4,x\pm 6,\cdots \right\}
\end{equation*}となります。2つの整数\(x,y\in \mathbb{Z} \)を任意に選んだとき、上の命題より、\begin{equation*}\left[ x\right] =\left[ y\right] \Leftrightarrow x\equiv y\ (\mathrm{mod}\ 2)
\end{equation*}という関係が成り立ちます。

 

商集合は分割

集合\(A\)の部分集合族\(\mathfrak{A}\)について、\(\mathfrak{A}\)の要素がいずれも空集合ではなく、\(\mathfrak{A}\)の和集合が\(A\)と一致し、なおかつ\(\mathfrak{A}\)の任意の2つの要素が互いに素であるならば、すなわち、\begin{eqnarray*}&&\left( a\right) \ \forall X\in \mathfrak{A}:X\not=\phi \\
&&\left( b\right) \ \bigcup \mathfrak{A}=X \\
&&\left( c\right) \ \forall X,Y\in \mathfrak{A}:\left( X\not=Y\Rightarrow
X\cap Y=\phi \right)
\end{eqnarray*}がいずれも成り立つ場合には\(\mathfrak{A}\)を\(A\)の分割(partition)と呼びます。

例(集合の分割)
集合\(A\)が、\begin{equation*}A=\left\{ 1,2,3,4\right\}
\end{equation*}と与えられています。以下の集合族\begin{equation*}
\mathfrak{A}=\left\{ \left\{ 1,2\right\} ,\left\{ 3\right\} ,\left\{
4\right\} \right\}
\end{equation*}は\(A\)の分割です。なぜなら、\(\mathfrak{A}\)の任意の要素は\(A\)の部分集合であり、\(\mathfrak{A}\)の任意の要素は空集合ではなく、\(\mathfrak{A}\)の要素の和集合は\(A\)と一致し、なおかつ\(\mathfrak{A}\)の任意の2つの要素は互いに素だからです。また、以下の集合族\begin{eqnarray*}&&\left\{ \left\{ 1\right\} ,\left\{ 2,3\right\} ,\left\{ 4\right\} \right\}
\\
&&\left\{ \left\{ 1\right\} ,\left\{ 2\right\} ,\left\{ 3,4\right\} \right\}
\\
&&\left\{ \left\{ 1\right\} ,\left\{ 2\right\} ,\left\{ 3\right\} ,\left\{
4\right\} \right\} \\
&&\left\{ \left\{ 1,2,3,4\right\} \right\}
\end{eqnarray*}もまたいずれも\(A\)の分割です(確認してください)。

集合\(A\)上の同値関係\(\sim \)が与えられたとき、要素\(x\in X\)を任意に選べば、\(x\)を代表元とする同値類\(\left[ x\right] \)を生成できます。そこで、\(X\)のそれぞれの要素を代表元とする同値類からなる集合族を、\begin{equation*}A\backslash \sim =\left\{ \left[ x\right] \ |\ x\in A\right\}
\end{equation*}で表記し、これを\(A\)の\(\sim \)による商集合(quotient set)と呼びます。任意の\(x\in A\)について\(\left[ x\right]\subset A\)であるため、商集合\(A\backslash \sim \)は\(A\)の部分集合族です。

例(合同関係による整数集合の分割)
すべての整数からなる集合\(\mathbb{Z} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{Z} \times \mathbb{Z} \)に対して、\begin{equation*}xRy\Leftrightarrow x\equiv y\ (\mathrm{mod}\ 2)
\end{equation*}を満たすものとして\(R\)を定義します。このように定義された\(R\)は\(\mathbb{Z} \)上の同値関係です。この\(R\)のもとでは以下の2つの同値類\begin{eqnarray*}\left[ 0\right] &=&\{x\in \mathbb{Z} \ |\ x\equiv 0\ (\mathrm{mod}\ 2)\}=\{0,\pm 2,\pm 4,\cdots \} \\
\left[ 1\right] &=&\{x\in \mathbb{Z} \ |\ x\equiv 1\ (\mathrm{mod}\ 2)\}=\{\pm 1,\pm 3,\pm 5,\cdots \}
\end{eqnarray*}が存在するため、\(\mathbb{Z} \)の\(R\)による商集合は、\begin{equation*}\mathbb{Z} \backslash R=\left\{ \left[ 0\right] ,\left[ 1\right] \right\} \end{equation*}となります。\(\left[ 0\right] \)と\(\left[ 1\right] \)は\(\mathbb{Z} \)の非空な部分集合です。また、その和集合は、\begin{eqnarray*}\bigcup \mathbb{Z} \backslash R &=&\left[ 0\right] \cup \left[ 1\right] \\
&=&\mathbb{Z} \end{eqnarray*}を満たします。さらに\(\left[ 0\right] \)と\(\left[ 1\right] \)は互いに素です。したがって\(\mathbb{Z} \backslash R\)は\(\mathbb{Z} \)の分割です。つまり、それぞれの整数は\(\left[ 0\right] ,\left[ 1\right] \)のどちらか一方に必ず属するとともに、\(\left[ 0\right] ,\left[ 1\right] \)の両方に属することはありません。
例(学年分けによる生徒集合の分割)
ある小学校のすべての生徒からなる集合\(A\)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in A\times A\)に対して、\begin{equation*}xRy\Leftrightarrow x\text{は}y\text{と同じ学年}
\end{equation*}を満たすものとして\(R\)を定義します。このように定義された\(R\)は\(A\)上の同値関係です。この\(R\)のもとでは以下の6つの同値類\begin{eqnarray*}A_{1} &=&\{x\in A\ |\ x\text{は1年生}\} \\
A_{2} &=&\{x\in A\ |\ x\text{は2年生}\} \\
A_{3} &=&\{x\in A\ |\ x\text{は3年生}\} \\
A_{4} &=&\{x\in A\ |\ x\text{は4年生}\} \\
A_{5} &=&\{x\in A\ |\ x\text{は5年生}\} \\
A_{6} &=&\{x\in A\ |\ x\text{は6年生}\}
\end{eqnarray*}が存在するため、\(A\)の\(R\)による商集合は、\begin{equation*}A\backslash R=\{A_{1},A_{2},A_{3},A_{4},A_{5},A_{6}\}
\end{equation*}となります。\(A_{1},A_{2},A_{3},A_{4},A_{5},A_{6}\)はいずれも\(A\)の非空な部分集合です。また、その和集合は、\begin{eqnarray*}\bigcup A\backslash R &=&A_{1}\cup A_{2}\cup A_{3}\cup A_{4}\cup A_{5}\cup
A_{6} \\
&=&A
\end{eqnarray*}を満たします。また、\(A_{1},A_{2},A_{3},A_{4},A_{5},A_{6}\)の中の任意の2つは互いに素です。したがって\(A\backslash R\)は\(A\)の分割です。つまり、それぞれの学生は何らかの学年に属するとともに、異なる複数の学年に属することはありません。

以上の2つの例では、集合\(A\)上の同値関係\(\sim \)から定義した商集合\(A\backslash \sim \)が\(A\)の分割になっていますが、実は、このような性質はあらゆる商集合に関して成立します。以上の事実を踏まえた上で、集合\(A\)上の同値関係\(\sim \)から\(A\)の分割である商集合\(A\backslash \sim \)を生成することを、\(A\)の\(\sim \)による類別(classification)と呼びます。

命題(商集合は分割)
集合\(A\)上の同値関係\(\sim \)が与えられたとき、商集合\(A\backslash \sim \)は\(A\)の分割である。
証明

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

 

分割が生成する同値関係

集合\(A\)上の同値関係\(\sim \)が与えられれば商集合\(A\backslash \sim \)を生成できますが、これは\(A\)の分割であることが保証されます。逆に、\(A\)の分割が与えられれば、そこから以下のようにして\(A\)上の同値関係\(\sim \)を生成することができます。

集合\(A\)の分割\(\mathfrak{A}\)が与えられた状況を想定します。つまり、\begin{eqnarray*}&&\left( a\right) \ \forall X\in \mathfrak{A}:X\not=\phi \\
&&\left( b\right) \ \bigcup \mathfrak{A}=X \\
&&\left( c\right) \ \forall X,Y\in \mathfrak{A}:\left( X\not=Y\Rightarrow
X\cap Y=\phi \right)
\end{eqnarray*}を満たす\(A\)の部分集合族\(\mathfrak{A}\)について考えます。順序対\(\left( x,y\right) \in A\times A\)を任意に選んだとき、上の条件より、\(x\in X\)かつ\(y\in Y\)を満たす集合\(X,Y\in \mathfrak{A}\)が存在するため、\begin{equation*}xRy\Leftrightarrow X=Y
\end{equation*}を満たすものとして\(A\)上の二項関係\(R\)を定義できます。つまり、\(x\)が属する集合と\(y\)が属する集合が一致する場合、そしてその場合にのみ\(R\)のもとで\(x\)は\(y\)を関係を持つものとして定義するということです。このように定義される\(R\)は\(A\)上の同値関係になることが保証されます。このような\(R\)を分割\(A\)が生成する同値関係(equivalence relation induced by partition)と呼びます。

命題(分割が生成する同値関係)
集合\(A\)の分割\(\mathfrak{A}\)が与えられたとき、順序対\(\left( x,y\right) \in A\times A\)を任意に選んだとき、\(x\in X\)かつ\(y\in Y\)を満たす集合\(X,Y\in \mathfrak{A}\)が存在する。以上を踏まえた上で、\begin{equation*}xRy\Leftrightarrow X=Y
\end{equation*}として定義される\(R\)は\(A\)上の同値関係である。
証明

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

例(分割が生成する同値関係)
すべての整数からなる集合\(\mathbb{Z} \)はすべての偶数からなる集合\(E\)とすべての奇数からなる集合\(O\)とに分割可能です。順序対\(\left( x,y\right) \in \mathbb{Z} \times \mathbb{Z} \)を任意に選んだとき、\(x\in X\)かつ\(y\in Y\)を満たす集合\(X,Y\in \left\{ E,O\right\} \)が存在するため、\begin{equation*}xRy\Leftrightarrow X=Y
\end{equation*}を満たすものとして\(R\)を定義します。このとき、\begin{equation*}xRy\Leftrightarrow x\text{と}y\text{の偶奇が一致する}
\end{equation*}となります。以上の\(R\)が分割\(\left\{ E,O\right\} \)が生成する同値関係です。

集合\(A\)上の同値関係\(\sim \)が与えられれば\(A\)の分割である商集合\(A\backslash \sim \)を生成することができ、逆に、\(A\)の分割が与えられれば\(A\)上の同値関係を生成できることが明らかになりました。以上の事実は、\(A\)上の同値関係と\(A\)の分割が概念として実質的に等しいことを示唆します。

 

演習問題

問題(商集合)
すべての整数からなる集合\(\mathbb{Z} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{Z} \times \mathbb{Z} \)に対して、\begin{equation*}xRy\Leftrightarrow x\equiv y\ (\mathrm{mod}\ 4)
\end{equation*}を満たすものとして\(R\)を定義します。商集合\(\mathbb{Z} \backslash R\)を特定するとともに、それが\(\mathbb{Z} \)の分割であることを確認してください。
解答を見る

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

問題(分割が生成する同値関係)
集合\(A=\left\{ 1,2\right\} \)の分割をすべて列挙した上で、それぞれの分割から生成される同値関係を明らかにしてください。
解答を見る

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

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

関連知識

同値関係

同値関係

反射律、対称律、推移律を満たす二項関係を同値関係と呼びます。また、同値関係のもとで 2 つの要素が関係を持つとき、それらの要素は同値であると言います。同値関係を正確に定義した上で、同値関係の具体例を提示します。

ベクトル

同値類

集合 A 上の同値関係 R が与えられたとき、A の要素 x を任意に選べば、R のもとで x と同値であるような A のすべての要素からなる集合を構成できます。このような A の部分集合を x を代表元とする同値類と呼びます。

DISCUSSION

質問とコメント

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