(집합론) 동치관계와 집합의 분할

1. 관계

 관계는 곱집합 $A\times B$의 부분 집합입니다. 명제함수 $P(x,y)$에 대해 다음과 같은 형식으로 나타냅니다. $$ R=((x,y) | x\in X,~y\in Y,~P(x,y)) $$ 원소의 튜플이 이 부분 집합에 속하는지 여부를 통해 원소들 사이의 관계를 나타냅니다. 예를 들어 $X=\{6,8\},~Y=\{2,3\},~P(x,y):$ "$x$는 $y$의 배수이다." 일 때, $X\times Y = \{(6,2),(6,3),(8,2),(8,3)\}$이므로 $R=\{(6,2),(6,3),(8,2)\}$입니다.

 

 또한 이 예시처럼 관계가 즉 두 집합의 곱집합의 부분 집합이라면 그 관계를 이항관계라고 부릅니다. (비슷하게 세 집합의 곱집합의 부분 집합이라면 삼항관계라고 합니다.) 특히 두 집합이 $X$로 같은 경우, $R$을 $X$ 위의 이항관계라고 합니다. 이항관계에서는 $(x,y)\in R$을 $_{x}R_{y}$라고도 표현합니다. 위 예시에서의 $R$이 이항관계이며, $(6,2)$가 관계 $R$의 원소이므로 이를  $_{6}R_{2}$로 나타낼 수 있습니다. 읽을 땐 "$6$은 $2$와 관계한다" 또는 "$2$는 $6$과 관계된다" 정도로 읽으시면 됩니다. 

 

• 이항 관계의 정의역

적당한 $y\in Y$에 대해 $_{x}R_{y}$인 모든 $x\in X$의 집합 , $\text{Dom}(R)$ 

 

• 이항 관계의 상

적당한 $x\in X$에 대해 $_{x}R_{y}$인 모든 $y\in Y$의 집합 , $\text{Im}(R)$

 

위 예시의 경우, $\text{Dom}(R)=\{6,8\},~\text{Im}(R)=\{2,3\}$입니다. 

 

2. 이항관계의 성질과 동치관계

 집합 $X$ 위의 이항관계 $R$이 만족할 수 있는 성질들은 다음과 같습니다.

 

• 반사성 : $\forall x\in X,~_{x}R_{x}$
• 대칭성 : $_{x}R_{y} \Rightarrow _{y}R_{x} $
• 반대칭성 : $ _{x}R_{y} \wedge _{x}R_{y} \Rightarrow x=y $
• 추이성 : $_{x}R_{y} \wedge _{y}R_{z} \Rightarrow _{x}R_{z} $

여기서 반사성, 대칭성, 추이성을 만족하는 이항관계를 보고 동치관계라고 합니다. 예를 들어, 집합 $X=\{1,2,3\}$ 위의 이항관계$R_{1}=\{(1,1),(1,3),(2,2),(2,3),(3,1),(3,2),(3,3)\}$은 동치관계가 아닙니다. $_{2}R_{3}~\wedge~_{3}R_{1}$이지만 $_{2}R_{1}$이 아니므로 추이성이 성립하지 않습니다. (반사성, 대칭성은 성립합니다.)

 

 마찬가지로 $X$ 위의 이항관계인 $R_{2}=\{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}$는 동치관계입니다. 눈치가 빠르신 분들은 아시겠지만, $R_{2}=X^2$이죠? $X^2$는 항상 집합 $X$ 위의 동치관계가 되며, $X$ 위의 동치관계 중 가장 큰 동치관계입니다.

 

3. 분할과 동치류

 집합 $X$의 분할은 다음 3가지 조건을 만족하는 집합족 $P$를 말합니다.

 

• $P$는 공집합을 원소로 하지 않는다. $$\forall A\in P,~A\neq \varnothing$$
• $P$는 $X$를 덮는다. $$\bigcup P = X$$
• $P$는 서로소 집합족이다. $$\forall A_{1},A_{2}\in P,~A_{1} \cap A_{2}=\varnothing \vee A_{1}=A_{2}$$

예를 들어, 집합 $X=\{1,2,3\}$의 분할은 다음 5가지입니다. $\{\{1,2,3\}\},\{\{1\},\{2,3\}\},\{\{2\},\{1,3\}\},\{\{3\},\{1,2\}\},\{\{1\},\{2\},\{3\}\}$

보시면 아시겠지만, 어떤 거창한 개념은 아니고, 그냥 집합을 겹치지 않게 나누겠다는 의미입니다.

 

 집합 $X$ 위의 하나의 동치관계를 $E$라고 할 때, $E_{x}=\{y\in X\mid _{x}E_{y}\}$를 $x$의 동치류라고 합니다. ($E_{x}$가 아니라 $[x]$나 $\bar{x}$로 표기하기도 합니다.) 

 

 예를 들어, 집합 $X=\{1,2,3,4,5\}$ 위의 동치관계 $E=\{(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,1),(3,5),(5,3)\}$에서 $E_{1}=\{1,2\},~E_{2}=\{1,2\},~E_{3}=\{3,5\},~E_{4}=\{4\},~E_{5}=\{3,5\}$입니다.

 

 이 동치류들을 모은 집합을 상집합 $X/E$라고 부릅니다. 즉, $X/E=\{E_{x}\mid x\in X\}$입니다. 위의 예시에서 $X/E$는 $\{\{1,2\},\{3,5\},\{4\}\}$입니다. 보시는 바와 같이 이는 $X$의 분할입니다. 이 예시에서만 성립하는게 아니라, 상집합은 항상 분할이 됩니다. 증명은 나중에 나옵니다.

 

 상집합과 비슷하게 $X/P$로 쓰는 녀석이 있습니다. 다만 이때 $P$는 집합 $X$의 분할입니다. 정의는 다음과 같습니다. $\{(x,y)\mid \exists A\in P,~x,y\in A\}$.

 

 쓸데없이 이런 건 또 왜 만들었는지 예시를 통해 확인해 봅시다. 집합 $X=\{1,2,3,4,5\}$의 분할 $P=\{\{1,2\},\{3,5\},\{4\}\}$에 대해서, 정의에 의해 $X/P$는 $\{1,2\}$로 만들 수 있는 모든 순서쌍, $\{3,5\}$로 만들 수 있는 모든 순서쌍, $\{4\}$로 만들 수 있는 모든 순서쌍을 원소로 갖는 집합입니다. 즉, $X/P=\{(1,1),(1,2),(2,1),(2,2),(3,3),(3,5),(5,3),(5,5),(4,4)\}$입니다. 이는 위에서 봤던 $X$ 위의 동치관계 $E$와 정확히 일치합니다. 이 역시 우연이 아니고, 임의의 분할을 이용해 동치관계를 만들 수 있습니다. 증명은 나중에 나옵니다.

 

 정리하면, 동치관계를 통해 분할을 알 수 있고, 분할을 동해 동치관계를 알 수도 있습니다. 수식으로 표현하면 다음과 같습니다. $$X/E=P,~X/P=E$$

 

4. 동치관계와 집합의 분할

 $X\neq \varnothing$인 집합 $X$ 위의 동치관계 $E$에 대해 다음이 성립합니다.

 

• $E_{x}\neq \varnothing$

$$ (X\neq\varnothing~\Rightarrow~\exists x\in X) $$ $$ E : \textbf{동치관계}~\Rightarrow~E : \textbf{반사성}~\Rightarrow~_{x}E_{x}~~\therefore x\in E_{x} $$

 

• $E_{x}=E_{y}~\Leftrightarrow~_{x}E_{y}$

$$ \begin{align} & (\Rightarrow)~~E_{x}=E_{y}~\Rightarrow~x\in E_{x}=E_{y}~\Rightarrow~_{y}E_{x}~\Leftrightarrow~_{x}E_{y} \\ & (\Leftarrow)~~_{x}E_{y}(\equiv~ _{y}E_{x})~\Rightarrow~\begin{cases} z\in E_{x}~\Leftrightarrow~_{x}E_{z}~\Rightarrow~_{y}E_{z}~\Leftrightarrow~z\in E_{y}~\therefore E_{x}\subseteq E_{y} \\ z\in E_{y}~\Leftrightarrow~_{y}E_{z}~\Rightarrow~_{x}E_{z}~\Leftrightarrow~z\in E_{x}~\therefore E_{y}\subseteq E_{x} \\ \end{cases}~\Rightarrow~E_{x}=E_{y} \end{align} $$

 

• $E_{x}\cap E_{y}\neq \varnothing~\Leftrightarrow~_{x}E_{y}$

$$ \begin{align} & (\Rightarrow)~~E_{x}\cap E_{y}\neq \varnothing~\Leftrightarrow~\exists z,~z\in E_{x}\wedge z\in E_{y}~\Leftrightarrow~_{x}E_{z}\wedge _{y}E_{z}~\Rightarrow~_{x}E_{y} \\ & (\Leftarrow)~~ _{x}E_{y}~\Leftrightarrow~E_{x}=E_{y}~\Rightarrow~E_{x}\cap E_{y}\neq \varnothing \\ \end{align} $$

 

이제 오늘의 메인 명제들입니다. 중요한 만큼 증명을 접어두진 않겠습니다.

 

1. $X/E$는 $X$의 분할이다. ($X/E=P$)

 

증명) $X/E$가 분할의 3가지 조건을 만족하는 것을 보입니다. $$ \begin{align} & (1)~E_{x}\neq\varnothing~\Rightarrow~\varnothing\notin X/E~~(\because X/E\textbf{는 동치류들의 집합}) \\ & \\ & (2) \begin{cases}~\bigcup X/E \subseteq X~(\because E_{x}\textbf{의 원소는}X \textbf{의 원소}\wedge X/E\textbf{는} E_{x}\textbf{의 합집합}) \\~\forall x\in X,~\exists E_{x}\in X/E~s.t.~x\in E_{x}~\Rightarrow~X\subseteq \bigcup X/E \end{cases} \therefore~X=\bigcup X/E \\ & \\ & (3)~E_{x}\cap E_{y}\neq \varnothing~\Leftrightarrow~_{x}E_{y}~\Leftrightarrow~E_{x}=E_{y}~~~\therefore E_{x}\neq E_{y}~\Leftrightarrow~E_{x}\cup E_{y}=\varnothing \\ \end{align} $$

 

2. $X/P$는 $X$ 위의 동치관계이다. ($X/P=E$)

 

증명) 아까처럼 $X/P$가 동치관계의 3가지 성질을 만족하는 것을 보여줍니다. $$ \begin{align} & \textbf{(반사성)}~\forall x\in X,~\exists A\in P~~s.t.~x\in A~~~\therefore~(x,x)\in X/P \\ & ( \textbf{보충설명 : 정의에 따라} X/P \text{는} A\textbf{로 만들 수 있는 모든 순서쌍을 만듦.} \\ & \textbf{이때,} x\in A\textbf{이므로 "모든 순서쌍"에는 }(x,x)\textbf{도 포함}) \\ & \\ & \textbf{(대칭성)}~\forall (x,y)\in X/P,~\exists A\in P~~s.t.~x,y,\in A~~~\therefore (y,x)\in X/P \\ & (\textbf{위 보충설명과 같은 논리}) \\ & \\ & \textbf{(추이성)}~\forall  x,y,z\in X,~(x,y),(y,z)\in X/P~\Rightarrow~\exists A,B\in P~~s.t.~x,y\in A,~y,z\in B~A\cap B\neq\varnothing \\ & \Rightarrow~A=B~\Rightarrow~(x,z)\in X/P \\ & (\textbf{위 보충설명과 같은 논리})   \end{align} $$

 

이것들을 이용해서 다음의 따름정리를 얻을 수 있습니다.

 

• $X/(X/P)=P$

증명) $X/(X/P)=X/E=P$

 

• $X/(X/E)=E$

증명) $X/(X/E)=X/P=E$