[집합론] 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 저, 김창일, 이상덕, 정갑현 공역, 동영출판사