[집합론] 7. 관계와 함수(2. 동치관계, 분할)

[집합론] 7. 관계와 함수(2. 동치관계, 분할)

집합 $X(\neq\phi)$의 임의의 부분집합 $A,\,B,\,C$에 대하여 다음이 모두 성립할 때, 집합 $\mathcal{P}$를 $X$의 분할(partition)이라고 한다.

(a) $A,\,B\in\mathcal{P}\wedge A\neq B\,\Rightarrow\,A\cap B=\phi$ (b) $\displaystyle\bigcup_{C\in\mathcal{P}}{C}=X$

예를들어 $m$이 임의의 양의 정수일 때 각 정수 $j(0\leq j<m)$에 대하여 $$\mathbb{Z}_{j}=\{x\in\mathbb{Z}\,|\,\exists k\in\mathbb{Z},\,x-j=km\}$$ 라고 하면 첨수집합족 $\{\mathbb{Z}_{0},\,\mathbb{Z}_{1},\,\cdots,\,\mathbb{Z}_{m-1}\}$은 집합 $\mathbb{Z}$의 하나의 분할이다.

집합의 분할과 동치관계 사이에는 밀접한 관계가 있는데 이것을 이해하려면 다음의 정의가 필요하다.

집합 $X(\neq\phi)$ 위의 한 동치관계를 $\mathcal{E}$라고 할 때 각 $x\in X$에 대하여 $x/\mathcal{E}=\{y\in X\,|\,y\mathcal{E}x\}$로 정의된 집합을 $x$에 따른 동치류(equivalence class)라고 하고, 이러한 동치류들의 집합을 $X/\mathcal{E}$로 나타낸다. 즉 $X/\mathcal{E}=\{x/\mathcal{E}\,|\,x\in X\}$이라 하고 $X/\mathcal{E}$를 상집합(quotient set)이라고 한다.

집합 $X(\neq\phi)$ 위의 동치관계 $\mathcal{E}$에 대하여 다음이 성립한다.

(a) 각 동치류 $x/\mathcal{E}$는 $X$의 공집합이 아닌 부분집합이다. 

(b) $x\mathcal{E}y\,\Leftrightarrow\,x/\mathcal{E}\cap y/\mathcal{E}\neq\phi$

(c) $x/\mathcal{E}=y/\mathcal{E}\,\Leftrightarrow\,x\mathcal{E}y$

증명:

(a) 동치관계 $\mathcal{E}$는 반사적이므로 각 $x\in X$에 대하여 $x\mathcal{E}x$이고 따라서 $x\in x/\mathcal{E}$이므로 $x/\mathcal{E}\neq\phi$이다. 

(b) $\mathcal{E}$는 집합 $X$위의 동치관계이므로 $$\begin{align*}x/\mathcal{E}\cap y/\mathcal{E}\neq\phi&\Leftrightarrow\,\exists z(z\in x/\mathcal{E}\wedge z\in y/\mathcal{E})\\&\Leftrightarrow\,z\mathcal{E}x\wedge z\mathcal{E}y\\&\Leftrightarrow\,x\mathcal{E}z\wedge z\mathcal{E}y\\&\Leftrightarrow\,x\mathcal{E}y\end{align*}$$ 그러므로 $x/\mathcal{E}\cap y/\mathcal{E}\neq\phi\,\Leftrightarrow\,x\mathcal{E}y$이고 따라서 $x\mathcal{E}y\,\Leftrightarrow\,x/\mathcal{E}\cap y/\mathcal{E}\neq\phi$이다. 

(c) (a)와 (b)에 의해 $x/\mathcal{E}=y/\mathcal{E}\,\Rightarrow\,x\mathcal{E}y$이다. 그러면 $x\mathcal{E}y\,\Rightarrow\,x/\mathcal{E}=y/\mathcal{E}$임을 보이면 된다. 

$x\mathcal{E}y$라고 가정하면 $$\begin{align*}z\in x/\mathcal{E}\,&\Rightarrow\,z\mathcal{E}x\\z\mathcal{E}x\wedge x\mathcal{E}y\,&\Rightarrow\,z\mathcal{E}y\\&\Rightarrow z\in y/\mathcal{E}\end{align*}$$ 이므로 따라서 $z\in x/\mathcal{E}\,\Rightarrow\,z\in y/\mathcal{E}$이다. 그런데 $z$는 $X$의 임의의 원소이므로 $x/\mathcal{E}\subset y/\mathcal{E}$이고, 마찬가지로 $y/\mathcal{E}\subset x/\mathcal{E}$이다. 그러므로 $x/\mathcal{E}=y/\mathcal{E}$이다.  

*여기서부터 특별한 언급이 없는 한 $X\neq\phi$이다. 

 

집합 $X$위의 동치관계 $\mathcal{E}$에 대해 $X/\mathcal{E}$는 $X$의 분할이다.

증명: 상집합 $X/\mathcal{E}$는 $X$의 부분집합족이다. $x/\mathcal{E}\neq y/\mathcal{E}\,\Rightarrow\,x/\mathcal{E}\cap y/\mathcal{E}=\phi$을 보이기 위해 대우명제 $x/\mathcal{E}\cap y/\mathcal{E}\neq\phi\,\Rightarrow\,x/\mathcal{E}=y/\mathcal{E}$를 보이는데 이것은 앞의 정리의 (b)와 (c)로부터 성립한다.

마지막으로 $\displaystyle\bigcup_{x\in X}{x/\mathcal{E}}=X$가 성립함을 보이면 된다. 모든 $x\in X$에 대하여 $x\in x/\mathcal{E}$이므로 $\displaystyle X\subset\bigcup_{x\in X}{x/\mathcal{E}}$이고, $\displaystyle\bigcup_{x\in X}{x/\mathcal{E}}\subset X$인 것은 분명하므로 $\displaystyle\bigcup_{x\in X}{x/\mathcal{E}}=X$이다.

이 정리는 집합 위에 하나의 동치관계에 하나의 분할이 대응됨을 보인 것이다. 이 정리의 역 또한 성립하는데 다음의 과정을 따라 보일 것이다.  

집합 $X$의 분할 $\mathcal{P}$에 대해 $X$에서의 관계 $X/\mathcal{P}$를 다음과 같이 정의한다.

집합 $A\in\mathcal{P}$가 존재함으로써 $\forall x,\,y\in A\,\Leftrightarrow\,x(X/\mathcal{P})y$ 

*집합 $X$의 분할 $\mathcal{P}$에 따른 동치관계 $X/\mathcal{P}$에 대해 $\displaystyle X/\mathcal{P}=\bigcup_{A\in\mathcal{P}}{(A\times A)}$이다.

집합 $X$의 분할 $\mathcal{P}$에 따른 관계 $X/\mathcal{P}$는 $X$에서의 동치관계이고, 이때 $X/\mathcal{P}$에 따라 유도된 $X$의 동치류들은 바로 분할 $\mathcal{P}$를 이룬다. 즉 $X/(X/\mathcal{P})=\mathcal{P}$ 

증명: 집합 $X$의 각 원소 $x$는 적당한 $A\in\mathcal{P}$에 속하므로 $x(X/\mathcal{P})x$, 즉 $X/\mathcal{P}$는 반사적이다. 또한 $x(X/\mathcal{P})y$의 정의에 의해 대칭적이다. $X/\mathcal{P}$가 추이적임을 보이기 위해 임의의 $x,\,y,\,z\in X$에 대해 $x(X/\mathcal{P})y\wedge y(X/\mathcal{P})z$라고 가정하자. 그러면 적당한 $A,\,B\in\mathcal{P}$가 존재해서 $x,\,y\in A\wedge y,\,z\in B$이고 따라서 $y\in A\cap B$이고 $A\cap B\neq\phi$이다. 분할의 정의에 따라 $A=B$이므로 $x,\,z\in A$이고 따라서 $x(X/\mathcal{P})z$이다. 이상으로 $X/\mathcal{P}$는 $X$에서 동치관계이다. 

집합 $X$의 임의의 원소를 $x$라고 하면 집합 $A\in\mathcal{P}$가 유일하게 존재하여 $x\in A$이다. 그러면 $x/(X/\mathcal{P})=A$이고 동치관계 $X/\mathcal{P}$에 의한 동치류는 $\mathcal{P}$의 하나의 원소이다.

역으로 분할 $\mathcal{P}$의 임의의 원소인 집합을 $A$라고 하면 $A\neq\phi$이므로 집합 $X$의 원소로서 $A$에 속하는 원소 $x$가 존재한다. 그러므로 $x/(X/\mathcal{P})$이고 따라서 $X/(X/\mathcal{P})=\mathcal{P}$이다.

앞의 두 정리는 집합 $X$ 에서의 동치관계 $\mathcal{E}$는 분할 $X/\mathcal{E}$를 만들고, 이 분할은 동치관계를 만들며 이때 $X/(X/\mathcal{E})=\mathcal{E}$가 성립한다. 

예를들어 짝수, 홀수의 집합을 각각 $\mathbb{Z}_{0},\,\mathbb{Z}_{1}$이라 하면 $\mathcal{P}=\{\mathbb{Z}_{0},\,\mathbb{Z}_{1}\}$은 정수의 집합 $\mathbb{Z}$의 분할이다. 

이 경우 관계 $\mathbb{Z}/\mathcal{P}$의 정의에 따라 $a,\,b\in\mathbb{Z}_{0}$ 또는 $a,\,b\in\mathbb{Z}_{1}$이면 그리고 그때에만 $a(\mathbb{Z}/\mathcal{P})b$, 다시말해서 $a,\,b$가 모두 짝수이거나 홀수이면 그리고 그때에만 $a(\mathbb{Z}/\mathcal{P})b$이다. 

여기서 $\mathbb{Z}/\mathcal{P}$는 $\mathbb{Z}$에서의 동치관계이고 실제로 $a\equiv b\,(\text{mod}\,2)\,\Leftrightarrow\,a(\mathbb{Z}/\mathcal{P})b$이다. 

이 주장의 역을 알아보기 위해 $\mathbb{Z}$에서의 동치관계 $\mathcal{E}$를 $x\equiv y\,(\text{mod}\,2)\,\Leftrightarrow\,x\mathcal{E}y$라고 할 때 $$a/\mathcal{E}=\{x\in\mathbb{Z}\,|\,x\equiv a\,(\text{mod}\,2)\}=\begin{cases}\mathbb{Z}_{0}&\,(a:\,\text{even})\\ \mathbb{Z}_{1}&\,(a:\,\text{odd})\end{cases}$$ 이므로 $\mathbb{Z}/\mathcal{E}=\{\mathbb{Z}_{0},\,\mathbb{Z}_{1}\}$이다.

$X=\{a,\,b,\,c,\,d,\,e\}$, $\mathcal{P}=\{\{a,\,b\},\,\{c\},\,\{d,\,e\}\}$일 때 

$X/\mathcal{P}=\{(a,\,b),\,(b,\,a),\,(c,\,c),\,(d,\,e),\,(e,\,d),\,(a,\,a),\,(b,\,b),\,(d,\,d),\,(e,\,e)\}$ 이고 $a/\mathcal{E}=b/\mathcal{E}=\{a,\,b\}$, $c/\mathcal{E}=\{c\}$, $d/\mathcal{E}=e/\mathcal{E}=\{d,\,e\}$이다.

참고자료:

집합론, You-Feng Lin, Shwu-Yeng T. Lin 저, 이흥천 옮김, 경문사

집합론, Seymour Lipschitz 저, 김창일, 이상덕, 정갑현 공역, 동영출판사