우리는 이제 이항관계의 역, 그리고 이들의 합성을 정의한다.
이항관계의 역
정의 1 \(R\)이 이항관계라 하자. 그럼 \((x,y)\in R\)를 만족하는 모든 \((y,x)\)들로 이루어진 이항관계를 \(R\)의 역inverse이라 부르고 이를 \(R^{-1}\)로 표기한다. 또, 집합 \(R^{-1}(X)\)를 \(X\)의 preimage역상라 부른다. 만일 \(R^{-1}=R\)라면 \(R\)이 symmetric대칭적하다고 한다.
명시적으로 \(R^{-1}\)은 다음의 식
\[(x,y)\in R\iff (y,x)\in R^{-1}\]이 성립하도록 하는 집합이다.
집합 \(R^{-1}(X)\)는 이항관계 \(R\)에 의한 \(X\)의 preimage로 보거나, 혹은 \(R\)의 역관계 \(R^{-1}\)에 의한 \(X\)의 image로 볼 수 있다. 그러나 \(R^{-1}\)의 정의에 의하여 이들 중 어떠한 관점을 택하더라도 동일한 집합을 얻으므로 혼동의 여지가 없다.
명제 2 \(R^{-1}\)의 역은 \(R\)이다. 또, \(\pr_1R^{-1}=\pr_2R\)이고 \(\pr_2R^{-1}=\pr_1R\)이다.
증명
첫 번째 주장은 다음의 식
\[(x,y)\in R\iff (y,x)\in R^{-1}\iff (x,y)\in (R^{-1})^{-1}\]에 의해 자명하다.
둘째 주장을 보자. 만일 \(x\in\pr_1R^{-1}\)라면, 어떠한 \(y\)가 존재하여 \((x,y)\in R^{-1}\)이다. 이제 \((y,x)\in R\)이므로 \(x\in\pr_2R\)가 성립한다. 이 논증을 뒤집으면 \(\pr_2R\subset\pr_1R^{-1}\)임을 증명할 수 있다.
아직 보이지 않은 \(\pr_2R^{-1}=\pr_1R\)의 경우, 방금 주장의 \(R\) 자리에 대신 \(R^{-1}\)을 넣으면 된다.
주어진 집합 \(A,B\)에 대하여, \(A\times B\)는 \(A\)를 source로, \(B\)를 target으로 갖는 가장 큰 이항관계였다. 따라서 두 개의 식
\[\pr_1(A\times B)^{-1}=\pr_2(A\times B)=B,\qquad \pr_2(A\times B)^{-1}=\pr_1(A\times B)=A\]에서, \((A\times B)^{-1}\subseteq B\times A\)이다. 반대로, 만일 \((y,x)\in B\times A\)라면 \(x\in A\), \(y\in B\)이므로 \((x,y)\in A\times B\)이고, 따라서 \((y,x)\in (A\times B)^{-1}\)이므로 \((A\times B)^{-1}=B\times A\)가 성립한다.
이항관계의 합성
정의 3 \(R_1\)과 \(R_2\)이 이항관계라 하자. 이 두 이항관계의 합성composition \(R_2\circ R_1\)는 \((x,y)\in R_1\)이고 \((y,z)\in R_2\)이도록 하는 \(y\)가 존재하는 순서쌍들 \((x,z)\)의 집합이다.
이렇게 정의한 이항관계의 합성이 위에서 정의한 역과 어떠한 관계가 있는지 궁금한 것이 당연하다.
명제 4 \(R_1\), \(R_2\)가 이항관계라 하자. 그럼 \(R_2\circ R_1\)의 역은 \(R_2^{-1}\circ R_1^{-1}\)이다.
증명
\((z,x)\in (R_2\circ R_1)^{-1}\)인 것은 \((x,z)\in R_2\circ R_1\)인 것과 동치이다. 그리고 이는 다시
또한, 이항관계의 합성은 결합법칙을 만족한다.
명제 5 이항관계의 합성은 결합법칙을 만족한다. 즉, 세 이항관계 \(R_1,R_2,R_3\)에 대하여
\[(R_3\circ R_2)\circ R_1=R_3\circ(R_2\circ R_1)\]이 성립한다.
증명
임의의 \((x,w)\)가 \((R_3\circ R_2)\circ R_1\)의 원소인 것과 \(R_3\circ(R_2\circ R_1)\)의 원소임이 동치임을 보이면 충분하다.
우선 \((x,w)\in (R_3\circ R_2)\circ R_1\)은
따라서 이 공통의 결과인 \((R_3\circ R_2)\circ R_1=R_3\circ(R_2\circ R_1)\)을 괄호 없이 \(R_3\circ R_2\circ R_1\)로 표현해도 아무런 문제가 없다.
이제 남은 명제들은 위에서 정의한 이항관계의 역, 그리고 이항관계의 합성에 대하여 집합의 image가 어떻게 변하는지를 다룬다.
명제 6 \(R_1\), \(R_2\)가 이항관계이고 \(A\)가 집합이라 하자. 그럼
\[(R_2\circ R_1)(A)=R_2(R_1(A))\]가 성립한다.
증명
앞선 명제와 같이 진행한다.
어떠한 \(z\)에 대하여 \(z\in (R_2\circ R_1)(A)\)인 것은
명제 7 이항관계 \((R,A,B)\)에 대하여 \(X\subseteq A\), \(Y\subseteq B\)라 하자. 그럼
- \[R^{-1}(R(X))\supset X\cap\pr_1R\]
- \[R(R^{-1}(Y))\supset Y\cap\pr_2R\]
가 각각 성립한다.
증명
본격적으로 증명을 시작하기 전에, 위의 두 식은
이제 \(x\in X\cap\pr_1R\)라 하자. 그럼 \(x\in\pr_1R\)에서, 어떠한 \(y\)가 존재하여 \((x,y)\in R\)이고, \(x\in X\)이므로 이 \(y\)는 \(y\in R(X)\)를 만족한다. 이제 \((y,x)\in R^{-1}\)이므로, \(x\in R^{-1}(R(X))\)이다.
명제 8 \(R_1\), \(R_2\)가 이항관계라 하자. 그럼 다음의 두 식이 성립한다.
\[\pr_1(R_2\circ R_1)=R_1^{-1}(\pr_1R_2),\quad \pr_2(R_2\circ R_1)=R_2(\pr_2R_1).\]증명
다음 implication들의 chain
\[\begin{aligned} x\in\pr_1(R_2\circ R_1)&\iff \exists z\big((x,z)\in R_2\circ R_1\big)\\ &\iff\exists y,z\big(((x,y)\in R_1)\wedge((y,z)\in R_2)\big)\\ &\iff\exists y\big(((x,y)\in R_1)\wedge(y\in\pr_1R_2)\big)\\ &\iff x\in R_1^{-1}(\pr_1 R_2). \end{aligned}\]에 의해 자명하다. 두 번째 식도 마찬가지로 보일 수 있다.
마지막으로, 특별한 이항관계를 소개한다.
정의 9 집합 \(A\)에 대하여, \(\Delta_A\)는 이항관계
\[\Delta_A=\{(x,x)\mid x\in A\}\]를 뜻한다. 이를 \(A\times A\)의 diagonal대각집합이라 부른다.
정의에 의해 \(\pr_1\Delta_A=\pr_2\Delta_A=A\)이므로, 이를 이항관계
\[\left(\Delta_A,A,A\right)\]로 생각할 수 있다. 다음 글에서 이 관계가 함수가 된다는 것을 보일 수 있으며, 이를 집합 \(A\) 위에 정의된 항등함수라 부른다. \(A\)를 source로 갖는 이항관계 \(R_1\) 혹은, \(A\)를 target으로 갖는 이항관계 \(R_2\)에 대하여 두 식
\[R_1\circ\Delta_A=R_1,\qquad \Delta_A\circ R_2=R_2\]이 항상 성립하므로 \((\Delta_A,A,A)\)를 항등함수라고 부르는 것이 어색하지 않다.
참고문헌
[Bou] N. Bourbaki, Theory of Sets. Elements of mathematics. Springer Berlin-Heidelberg, 2013.
댓글남기기