分割と同値関係
分割と同値関係
集合\(A\)の分割\(\mathcal{P}\)に対し、2項関係\(\sim\)を\(x,y\in A\)のとき、
\[
x\sim y\Leftrightarrow\exists P\in\mathcal{P},x\in P\land y\in P
\]
と定めると、\(\sim\)は同値関係(反射律・対称律・推移律)を満たす。
逆に同値関係\(\sim\)による同値類の商集合\(A/\sim\)は\(A\)の分割となる。
-
反射律
\(\bigcup\mathcal{P}=A\)なので\(x\in A\)のとき、\(x\sim x\Leftrightarrow\exists P\in\mathcal{P},x\in P\Leftrightarrow x\in\bigcup\mathcal{P}\Leftrightarrow x\in A\Leftrightarrow\top\)となる。
対称律
\(x\sim y\Leftrightarrow\exists P\in\mathcal{P},x\in P\land y\in P=y\sim x\)となるので対称律を満たす。
推移律
\(x\sim y\land y\sim z\)のとき、\(P_{1},P_{2}\in\mathcal{P}\)とすると\(y\in P_{1}\cap P_{2}\Leftrightarrow y\in P_{1}\land P_{1}=P_{2}\)なので、
\begin{align*}
x\sim y\land y\sim z & \Leftrightarrow\left(\exists P_{1}\in\mathcal{P},x\in P_{1}\land y\in P_{1}\right)\land\left(\exists P_{2}\in\mathcal{P},y\in P_{2}\land z\in P_{2}\right)\\
& \Leftrightarrow\exists P_{1},P_{2}\in\mathcal{P},x\in P_{1}\land y\in P_{1}\land y\in P_{2}\land z\in P_{2}\\
& \Leftrightarrow\exists P_{1},P_{2}\in\mathcal{P},x\in P_{1}\land y\in P_{1}\cap P_{2}\land z\in P_{2}\\
& \Leftrightarrow\exists P_{1},P_{2}\in\mathcal{P},x\in P_{1}\land y\in P_{1}\land z\in P_{1}\land P_{1}=P_{2}\\
& \Leftrightarrow\exists P_{1}\in\mathcal{P},x\in P_{1}\land y\in P_{1}\land z\in P_{1}\\
& \Rightarrow\exists P_{1}\in\mathcal{P},x\in P_{1}\land z\in P_{1}\\
& \Leftrightarrow x\sim z
\end{align*}
となり、\(x\sim y\land y\sim z\Rightarrow x\sim z\)なので推移律を満たす。
-
これらより、反射律・対称律・推移律を満たすので同値関係となる。
-
空集合
\(x\in A\)の同値類を\(C\left(x\right)=\left\{ y\in A;x\sim y\right\} \)で表す。
任意の\(x\in A\)に対し、\(x\in C\left(x\right)\ne\emptyset\)なので、\(\emptyset\notin A/\sim\)となる。
和集合
明らかに\(\bigcup\left(A/\sim\right)\subseteq A\)となる。
また、任意の\(x\in A\)に対し、\(x\in C\left(x\right)\)なので、和集合は\(A=\bigcup_{x\in A}x\subseteq\bigcup_{x\in A}C\left(x\right)=\bigcup\left(A/\sim\right)\)となり\(A\subseteq\bigcup\left(A/\sim\right)\)となる。
これより、\(\subseteq\)と\(\supseteq\)が成り立つので、\(\bigcup\left(A/\sim\right)=A\)となる。
積集合
同値類の性質より、\(\forall a,b\in A,C\left(a\right)=C\left(b\right)\Leftrightarrow C\left(a\right)\cap C\left(b\right)\ne\emptyset\)なので、\(\forall C\left(a\right),C\left(b\right)\in A/\sim,C\left(a\right)\ne C\left(b\right)\Leftrightarrow C\left(a\right)\cap C\left(b\right)=\emptyset\)となる。
-
これらより同値関係\(\sim\)による同値類の商集合\(A/\sim\)は\(A\)の分割となる。
ページ情報
タイトル | 分割と同値関係 |
URL | https://www.nomuramath.com/l8opezqt/ |
SNSボタン |