이제 우리는 동치관계에 대해 살펴본다.
동치관계의 정의
정의 1 이항관계 \((R,A,A)\)가 symmetric대칭적이라는 것은 \(x\mathrel{R}y\)가 성립하면 \(y\mathrel{R}x\)도 성립하는 것이다. 만일
\[(x\mathrel{R}y)\wedge(y\mathrel{R}z)\implies x\mathrel{R}z\]가 성립할 경우, 이를 transitive추이적라고 한다. 마지막으로 모든 \(x\)에 대하여 \(x\mathrel{R}x\)일 경우, \(R\)이 \(A\) 위에서 reflexive반사적라고 한다. Reflexive, symmetric, transitive한 관계 \(R\)을 동치관계equivalence relation라 부른다.
앞으로 \(R\)이 동치관계일 경우 \(x\sim_{\tiny R}y\)를 사용하기로 한다. 혼동의 여지가 없을 때에는 \(x\sim y\) 혹은 \(x\equiv y\)와 같이 적기도 한다.
예시 2 주어진 집합 \(A\) 위에서 관계
집합 \(A\) 위에 주어진 임의의 동치관계 \(R\)을 생각하자. \(R\)은 reflexive하므로 \(\Delta_A\subseteq R\)이며, 포함관계 \(R\subseteq A\times A\)가 성립하는 것은 자명하다. 따라서 위에서 든 두 가지의 예시 중 첫 번째는 \(A\) 위에서 정의할 수 있는 동치관계 중 가장 작은 것이고, 두 번째는 가장 큰 것이다.
이를 식으로 정리하면 다음과 같다.
명제 3 이항관계 \((R,A,A)\)가 동치관계인 것은 다음의 세 조건
\[\pr_1R=A,\qquad R=R^{-1},\qquad R\circ R=R\]과 동치이다.
증명
우선 \(R\)이 동치관계라 가정하자.
- 모든 \(x\in A\)에 대하여 \((x,x)\in R\)이므로 \(\pr_1R=A\)가 성립한다.
-
또, \(R\)은 symmetric이므로 \(x\sim_\tiny{R} y\iff y\sim_\tiny{R}x\)가 성립하고 따라서
\[(x,y)\in R\iff (y,x)\in R\iff (x,y)\in R^{-1}\tag{1}\]로부터 \(R=R^{-1}\)이 성립한다.
- 마지막으로 \(R\circ R=R\)임을 보여야 한다. 우선 임의의 \((x,y)\in R\)이 주어졌다 하자. \(R\)이 reflexive하므로 \((x,x)\in R\)이고, 따라서 \((x,x)\in R\), \((x,y)\in R\)로부터 \((x,y)\in R\circ R\)이 성립한다는 것을 안다. 거꾸로 임의의 \((x,y)\in R\circ R\)가 주어졌다 하자. 그럼 어떠한 \(z\in A\)가 존재하여 \((x,z)\in R\)이고 \((z,y)\in R\)이다. 이제 \(R\)의 transitivity에 의하여 \((x,y)\in R\)이 성립한다.
이제 주어진 세 조건을 만족하는 이항관계 \(R\)이 주어졌다 하자.
- \(R=R^{-1}\)이 성립하는 것으로부터, 식 (1)의 논리를 거꾸로 하여 \(R\)이 symmetric임을 안다.
- \(x\mathrel{R}y\)와 \(y\mathrel{R}z\)가 성립한다 가정하자. 그럼 \((x,z)\in R\circ R=R\)이므로 \(R\)이 transitive임을 안다.
- 마지막으로 \(\pr_1R=A\)인 것으로부터 적당한 \(y\in A\)가 존재하여 \((x,y)\in R\)임을 안다. 이제 \(R\)은 symmetric이므로 \(y\mathrel{R}x\) 또한 성립하고, transitivity로부터 \((x\mathrel{R}y)\wedge(y\mathrel{R}x)\implies x\mathrel{R}x\)가 성립한다. 즉 \(R\)은 reflexive하다.
이번 글에서는 동치관계의 핵심적인 성질을 살펴보고, 다음 글에서는 여러가지 상황에서 등장하는 동치관계를 살펴본다.
동치관계와 분할
정의 4 동치관계 \((R,A,A)\)를 생각하자. 임의의 \(x\in A\)에 대하여, \(x\)에서의 section \(R(x)\)를 \(R\)에서 \(x\)의 equivalence class동치류라 부른다. 이러한 equivalence class들의 모임을 \(R\)의 quotient set몫집합이라 부르고, \(A/R\)로 표기한다.
정의에 의하여 \(R(x)\)는 동치관계 \(R\)에 의해 \(x\)와 동등한 것으로 취급되는 원소들의 모임이다. 많은 경우 \(x\)를 포함하는 equivalence class를 \([x]_R\)로 적기도 한다. 혼동의 여지가 없을 경우, 이들의 집합 \(A/R\)을 \(A/\mathord{\sim}\)으로 표기하기도 한다.
예시 5 집합 \(A\) 위에서
우리는 앞선 예시 2에서 \(\Delta_A\)가 가장
보조정리 6 동치관계 \((R,A,A)\)에 대하여 \(p:A\rightarrow A/R\)을 \(x\mapsto [x]_R\)로 정의하자. 그럼 \(p\)는 함수이며, \(x\sim_{\tiny R} y\)와 \(p(x)=p(y)\)는 서로 동치이다.
증명
우선 위의 식으로 정의된 \(p\)가 실제로 함수가 된다는 것은 어렵지 않게 보일 수 있다. 여기에서는 동치관계만 보인다.
우선 \(x\sim_{\tiny R} y\)이라 가정하자. 그럼 \(y\in [x]_R=R(x)\)로부터 \(\{y\}\subseteq R(x)\)이고, 따라서 §이항관계들 사이의 연산, ⁋명제 6과 명제 3에 의하여
\[R(y)\subseteq R(R(x))=(R\circ R)(x)=R(x)\]가 성립한다. \(R\)은 동치관계이므로 \(x\)와 \(y\)의 역할을 바꿀 수 있고 따라서 \(R(x)=R(y)\)가 성립한다.
반대로 만일 \([x]_R=[y]_R\)이라면, \(x\in [x]_R=[y]_R\)로부터 \(y\sim_{\tiny R} x\)를 얻고 따라서 보조정리가 성립한다.
위의 함수 \(p\)를 canonical projection이라 부른다. 그럼 \(A\)의 부분집합 \([x]_R\subseteq A\)는 몫집합의 원소 \([x]_R\in A/R\)의 함수 \(p\)에 대한 preimage이므로 equivalence class들은 서로소임을 안다. 즉 동치관계 \((R,A,A)\)는 \(A\)의 분할을 유도한다.
다음 명제는 그 역 또한 성립한다는 것을 보여준다.
명제 7 \((A_i)_{i\in I}\)가 \(A\)의 분할이라 하자. 그럼
어떤 \(i\)가 존재하여 \(x,y\in A_i\)이다
는 \(x\), \(y\)에 대한 동치관계이다.
증명
위의 관계를 \(R\)이라 적자.
- \(R\)이 \(A\) 위에서 reflexive인 것은 자명하다.
- \(x\)와 \(y\)가 같은 집합에 포함되면 \(y\)와 \(x\)도 같은 집합에 포함되므로 \(x\mathrel{R}y\)이면 \(y\mathrel{R}x\)이다. 즉 \(R\)은 symmetric하다.
- 마지막으로 만일 \(x\mathrel{R}y\)이고 \(y\mathrel{R}z\)라면, \(x,y\in A_i\)이고 \(y,z\in A_j\)이다. 그런데 \(y\in A_i\cap A_j\)이고 \((A_i)_{i\in I}\)가 분할이므로 \(i=j\)이다. 따라서 \(x,z\in A_i\)이고 명제가 성립한다.
참고문헌
[Bou] N. Bourbaki, Theory of Sets. Elements of mathematics. Springer Berlin-Heidelberg, 2013.
댓글남기기