K

Grad. student in mathematics

이번 글에서 우리는 다양한 맥락에서 등장하는 동치관계들의 예시를 살펴본다.

함수에 의해 정의되는 동치관계

앞선 글에서 동치관계 $(R,A,A)$에서부터 canonical한 함수 $p:A\rightarrow A/R$이 잘 정의된다는 것을 보았는데, 그 역 또한 성립한다. 즉, 임의의 함수가 주어졌을 때, 이 함수를 사용하여 동치관계를 만들 수 있다.

명제 1 집합 $A$와 이를 정의역으로 갖는 함수 $f$가 주어졌다 하자. 그럼 $x$, $y$ 사이의 관계 $x$, $y\in A$이고 $f(x)=f(y)$는 $A$ 위에서의 동치관계다.

증명

주어진 관계가 $A$ 위에서 reflexive함은 자명하다. 한편, 만일 $f(x)=f(y)$라면 $f(y)=f(x)$이고, $f(x)=f(y)$, $f(y)=f(z)$이면 $f(x)=f(z)$이므로 이 관계는 symmetric, transitive하기도 하다.

정의 2 위의 명제에서 정의된 동치관계를 $f$에 의해 정의된 동치관계라 부른다.

동치관계 $(R,A,A)$와 이로부터 유도된 $p:A\rightarrow A/R$에 대하여, 동치관계 $R$은 정의 2를 $p$에 적용하여 얻은 동치관계와 정확하게 같다는 것을 확인할 수 있다.

단항관계와 compatible한 동치관계

정의 3 $(R,A,A)$가 동치관계라 하자. 그럼 단항관계 $P$가 $R$과 compatible하다는 것은 $P(x)\wedge (x\sim_{\tiny R}y)\implies P(y)$인 것이다.

예를 들어, 단항관계

$x$는 짝수이다

는 동치관계

$x-y$가 4의 배수이다

와 compatible하다. Equivalence class의 관점에서 위 정의를 다시 쓰면 다음과 같다.

명제 4 $R$이 집합 $A$ 위에서의 동치관계이고, $P$가 $R$과 compatible한 단항관계라 하자. 그럼 $t\in A/R$이고 어떤 $x\in t$가 존재하여 $P(x)$인 것과 $t\in A/R$이고 모든 $x\in t$에 대하여 $P(x)$인 것이 서로 동치이다.

증명

풀어 쓰자면,

$P$가 $R$과 compatible할 때, equivalence class의 단 하나의 원소만 $P$를 만족한다면, 그 원소와 같은 class에 들어있는 모든 원소에 대해서도 $P$가 성립한다.

그리고 이건 정확히 compatible한 단항관계의 정의다.

반대 방향은 자명하다. 만일 $t\in A/R$에 대하여 $a\in t$가 존재하여 $P(a)$라 하자. 그럼 모든 $x\in t$에 대하여 $a\sim_{\tiny R}x$이므로 $P(x)$이다.

동치관계의 포화

정의 5 $R$이 $A$ 위에서의 동치관계이고 $X$가 $A$의 부분집합이라 하자. $X$가 $R$에 대해 saturated포화되었다는 것은 단항관계 $x\in A$가 $R$과 compatible한 것이다.

saturated_set

주어진 몫집합 (위쪽) 에서의 saturated subset (왼쪽)과 saturated가 아닌 부분집합 (오른쪽)

위의 정의에 따르면, 어떤 집합 $X$가 $R$-saturated이기 위해서는 $x\in X$라면 $R(x)\subseteq X$가 반드시 성립해야 한다. 따라서 $R$-saturated인 부분집합 $X$는 어떠한 부분집합 $B\subseteq A$에 대하여 $\bigcup_{x\in B}R(x)$로 나타낼 수 있는 집합이다. 이로부터 다음의 두 결과를 쉽게 확인할 수 있다.

  1. 만일 $(A_i)_{i\in I}$가 $R$-saturated인 부분집합들의 family라면, $\bigcup_{i\in I} A_i$와 $\bigcap_{i\in I} A_i$도 마찬가지다.
  2. $X\subseteq A$가 $R$-saturated라면 $A\setminus X$도 그러하다..

이번에는 canonical projection $p:A\rightarrow A/R$와 $X\subseteq A$를 생각하자. §이항관계의 연산, ⁋명제 7에 의하여

\[p^{-1}(p(X))\supseteq X\]

를 얻는다. 일반적으로 반대방향 포함관계는 성립하지 않지만, 만일 $X$가 $R$-saturated라면 반대쪽 포함관계도 성립한다. 각각의 $x\in X$에 대하여, $p^{-1}(\left\{p(x)\right\})\subseteq X$이므로

\[p^{-1}(p(X))=\bigcup_{x\in X}p^{-1}(\left\{p(x)\right\})\subseteq X\]

가 성립하기 때문이다.

한편, $X$가 $R$-saturated가 아니더라도 집합 $p^{-1}(p(X))$는 $R$-saturated가 된다. 이를 보기 위해 $x\in p^{-1}(p(X))$를 임의로 택하고, $x\sim_{\tiny R} x’$를 만족하는 임의의 $x’$가 주어졌다 하자. 그럼

\[x\sim_{\tiny R} x'\iff p(x)=p(x')\]

이고, 주어진 가정으로부터 $p(x)\in p(X)$이므로 $x’\in p^{-1}(p(X))$를 얻는다. 한편, $X’$가 $X$를 포함하는 $R$-saturated subset이라면,

\[X'=p^{-1}(p(X'))\supseteq p^{-1}(p(X))\]

이므로 $p^{-1}(p(X))$는 $X$를 포함하는 $R$-saturated인 부분집합 중 가장 작은 것이다. 이를 $X$의 saturation이라 부른다.

Canonical decomposition

정의 6 동치관계 $(R,A,A)$와 $A$를 정의역으로 갖는 함수 $f$에 대하여, $f$가 $R$과 compatible하다는 것은 $x$에 대한 단항관계 $y=f(x)$가 $R$과 compatible하다는 것을 의미한다.

즉, $f$가 $R$과 compatible하려면 $f$는 각각의 equivalence class로 제한하였을 때 상수함수가 되어야 한다. 이제 §Retraction과 section, ⁋명제 4를 적용하면 다음을 얻는다.

명제 7 동치관계 $(R,A,A)$와 canonical $p:A\rightarrow A/R$을 생각하자. 그럼 $f:A\rightarrow B$가 $R$과 compatible한 것은 $f=h\circ p$이도록 하는 $h:A/R\rightarrow B$가 존재하는 것과 동치이다.

즉, 다음의 diagram이 commute한다.

induced_injection

이 때 $h$는 $p$의 section $s$에 의하여 $h=f\circ s$로 유일하게 결정된다.

특별히 $R$이 $f$에 의해 정의된 동치관계라 하자. (정의 2) 그럼 다음의 diagram을 생각할 수 있다.

canonical_decomposition

이 때 $\tilde{f}$는 $f$의 공역 $F$를 $f(A)$로 제한하여 얻어지는 함수이고, $j$는 canonical injection이다. 위 그림의 commutativity로부터 식

\[f=j\circ\tilde{f}=j\circ h\circ p\]

를 얻는다. 만일 어떠한 $t, t’\in A/R$에 대해 $h(t)=h(t’)$라면, $x\in t$, $x’\in t’$에 대하여 $f(x)=f(x’)$이므로 $x\sim_{\tiny R}x’$이고, 따라서 $t=t’$가 되어 $h$는 단사함수이다. 그런데 $h$의 공역은 $f$의 치역으로 제한된 상태이므로, $h$는 전사함수이기도 하다. 따라서 $h$는 전단사이며, 위의 식을 $f$의 canonical decomposition이라 부른다.

추가로 공역 $B$에 동치관계 $S$가 주어졌다고 하자. 그럼 우선 다음의 diagram을 얻는다.

induced_mapping_of_equivalence

만일 $q\circ f$이 $R$과 compatible하다면, $f$가 $(R,S)$-compatible하다고 한다. 명제 7에 의해 이는 다시 $h:A/R\rightarrow B/S$가 존재하여 $h\circ p=q\circ f$인 것과 동치이다.

동치관계의 preimage

함수 $f:A\rightarrow B$가 주어졌다 하고, 동치관계 $(S,B,B)$와 canonical $p:B\rightarrow B/S$를 생각하자.

inverse_image_of_equivalence

그럼 자연스레 함수 $p\circ f:A\rightarrow B/S$가 정의되며, 이 함수가 정의 2를 통해 만드는 동치관계를 $f$에 의한 $S$의 preimage라 부른다.

동치관계의 quotient

다음 정의는 이미 §동치관계, ⁋예시 5에서 언급했던 것이다.

정의 8 집합 $A$ 위에 정의된 두 동치관계 $R,S$에 대해, $S$가 $R$보다 finer세밀하다하다는 것은 $x\sim_{\tiny S}y\implies x\sim_{\tiny R}y$가 항상 성립하는 것이다.

집합 $A$ 위에 정의된 두 동치관계 $R,S$가 주어졌고, $S$가 $R$보다 finer하다고 하자.

third_iso_1

그럼 함수 $p_S$가 전사함수이고, $p_S(x)=p_S(y)\implies p_R(x)=p_R(y)$가 항상 성립한다. 따라서 $p_R=h\circ p_S$이도록 하는 유일한 $h:A/S \rightarrow A/R$이 존재한다. (§Retraction과 section, ⁋명제 4) 이 때, $h$가 $A/S$ 위에 정의하는 $R$의 $S$에 의한 quotient라 부르고, $R/S$로 적는다. Canonical decomposition을 거치면

third_iso_2

와 같으며, 특히 $k$는 전단사함수이다.

동치관계의 곱

마지막으로 두 동치관계 $(R,A,A)$, $(R’,A’,A’$이 주어졌다고 하고, 관계 $(S, A\times A’, A\times A’)$를

$u\sim_{\tiny S}v$인 것은 어떠한 $x$, $x’$, $y$, $y’$가 존재하여 $u=(x,x’)$, $v=(y,y’)$이고 $x\sim_{\tiny R}y$, $x’\sim_{\tiny R’}y’$인 것이다

로 정의하자. $u=(x,x’),v=(y,y’),w=(z,z’)$이 $A\times A’$의 원소들이라 하면,

  • $u\sim_{\tiny S}u$가 항상 성립하는 것은 자명하다. $x\sim_{\tiny R}x$이고 $x’\sim_{\tiny R’}x’$이기 때문이다.
  • $u\sim_{\tiny S}v$라면 $x\sim_{\tiny R}y$이고 $x'\sim_{\tiny R'}y'$이므로 $y\sim_{\tiny R}x$이고 $y'\sim_{\tiny R'}x'$이고, 따라서 $v\sim_{\tiny S}u$이다.
  • $u\sim_{\tiny S}v$이고 $v\sim_{\tiny S}$라 하자. 그럼 $x\sim_{\tiny R}y,x'\sim_{\tiny R'}y',y\sim_{\tiny R}z,y'\sim_{\tiny R'}z'$가 각각 성립한다. 이제 $x\sim_{\tiny R}y$와 $y\sim_{\tiny R}z$로부터 $x\sim_{\tiny R}z$이고, $x’\sim_{\tiny R’}y’$와 $y’\sim_{\tiny R’}z’$로부터 $x’\sim_{\tiny R’}z’$이다. 즉 $u\sim_{\tiny S}w$가 성립한다.

따라서 $S$는 동치관계가 된다. 이 동치관계를 $R$과 $R’$의 곱product이라 부르고 $R\times R’$로 적는다.

두 함수 $f:A\rightarrow B$, $f’:A’\rightarrow B’$가 주어졌다고 하고, $R$과 $R’$을 각각 $f$와 $f’$에 의해 유도되는 동치관계라 하자. 그럼 $f\times f’:A\times A’\rightarrow B\times B’$가 잘 정의되고, 이 함수를 통해 $A\times A’$ 위에 동치관계를 정의할 수 있다. 이 동치관계를 잠시 $S$라 하면, 임의의 $u=(x,x’),v=(y,y’)\in A\times A’$에 대해

\[\begin{aligned}u\sim_{\tiny S}v&\iff (f\times f')(u)=(f\times f')(v)\iff (f(x),f'(x')=(f(y),f'(y'))\\ &\iff (f(x)=f(y))\wedge(f'(x')=f'(y'))\iff (x\sim_{\tiny R}y)\wedge(x'\sim_{\tiny R'}y')\\&\iff u\sim_{\tiny R\times R'}v\end{aligned}\]

이므로 $S=R\times R’$이다. 이 때 $f\times f’$에 의한 $A\times A’$의 image는 $f(A)\times f’(A’)$와 같으므로, $f\times f’$의 canonical decomposition을 생각하면 $(A\times A’)/(R\times R’)$과 $f(A)\times f’(A’)$ 사이의 전단사함수가 존재한다.

canonical_bijection_between_product

한편 다음의 diagram을 생각하자.

canonical_bijection_between_product_2

여기서 $A/R\rightarrow f(A)$와 $A’/R’\rightarrow f’(A’)$는 각각 $f$와 $f’$의 canonical decomposition들로부터 얻어지는 전단사함수이다. 따라서 이들에 의해 유도되는 함수 $(A/R)\times (A/R’)\rightarrow f(A)\times f’(A’)$ 또한 전단사함수이다.

위에서 얻어진 두 개의 전단사함수와 그 역들을 적절히 합성해주면 $(A\times A’)/(R\times R’)$과 $(A/R)\times(A’/R’)$ 사이의 전단사함수를 얻을 수 있다. 이 전단사함수들 또한 canonical이라 부른다.

참고문헌

[Bou] N. Bourbaki, Theory of Sets. Elements of mathematics. Springer Berlin-Heidelberg, 2013.

댓글남기기