[집합론] 6. 관계와 함수(1. 데카르트곱, 관계)

[집합론] 6. 관계와 함수(1. 데카르트곱, 관계)

데카르트곱

임의의 두 대상 \(a,\,b\)에 대하여 순서쌍(ordered pair)이라고 하는 \((a,\,b)\)를 구성할 수 있다. 이때 순서쌍 \((a,\,b)\)는 집합 \(\{a,\,b\}\)와는 다르고 다음이 성립한다.$$(a,\,b)=(c,\,d)\,\Leftrightarrow\,a=c\wedge b=d$$임의의 두 집합 \(A,\,B\)에 대하여 \(x\in A\), \(y\in B\)의 순서쌍 \((x,\,y)\)의 집합을 \(A,\,B\)의 데카르트곱(카테시안 곱, Cartesian product)이라 하고 \(A\times B\)로 나타낸다. 즉 \(A\times B=\{(x,\,y)\,|\,x\in A\wedge y\in B\}\)

예를들어 집합 \(A=\{a,\,b,\,c\}\), \(B=\{1,\,2\}\)에 대하여 다음이 성립한다.$$\begin{align*}A\times B&=\{(a,\,1),\,(a,\,2),\,(b,\,1),\,(b,\,2),\,(c,\,1),\,(c,\,2)\}\\B\times A&=\{(1,\,a),\,(1,\,b),\,(1,\,c),\,(2,\,a),\,(2,\,b),\,(2,\,c)\}\end{align*}$$위의 예에서 \(A\times B\neq B\times A\)임을 알 수 있다.

위의 데카르트곱의 정의에서 \(A=B=\mathbb{R}\)인 경우 \(A\times B=\mathbb{R}\times\mathbb{R}=\{(x,\,y)\,|\,x\in\mathbb{R}\wedge y\in\mathbb{R}\}\)이고 이것은 실수의 모든 순서쌍의 집합으로서 좌표평면을 뜻한다.

임의의 집합 \(A\)에 대하여 \(A\times\phi=\phi\times A=\phi\)이다. 그 이유로 \(A\times\phi\)는 \(a\in A,\,b\in\phi\)인 순서쌍 \((a,\,b)\)의 집합과 같으나 \(\phi\)에는 원소가 없기 때문에 \(b\)는 \(\phi\)의 원소가 아니고 따라서 \(A\times\phi=\phi\)이다. 위와 같은 방법으로 \(\phi\times A=\phi\)가 됨을 확인할 수 있다.

임의의 집합 \(A,\,B,\,C\)에 대하여 다음이 성립한다.

(a) \(A\times(B\cap C)=(A\times B)\cap(A\times C)\) 

(b) \(A\times(B\cup C)=(A\times B)\cup(A\times C)\)

(c) \(A\times(B-C)=(A\times B)-(A\times C)\)

증명:

(a):$$\begin{align*}(a,\,x)\in A\times(B\cap C)&\Leftrightarrow a\in A\wedge x\in B\cap C\\&\Leftrightarrow a\in A\wedge(x\in B\wedge x\in C)\\&\Leftrightarrow a\in A\wedge a\in A\wedge(x\in B\wedge x\in C)\\&\Leftrightarrow(a\in A\wedge x\in B)\wedge(a\in A\wedge x\in C)\\&\Leftrightarrow(a,\,x)\in(A\times B)\wedge(a,\,x)\in(A\times C)\\&\Leftrightarrow(a,\,x)\in(A\times B)\cap(A\times C)\end{align*}$$이므로 \((a,\,x)\in A\times(B\cap C)\,\Leftrightarrow\,(a,\,x)\in(A\times B)\cap(A\times C)\)이고 \(A\times(B\cap C)=(A\times B)\cap(A\times C)\)이다.

(c):$$\begin{align*}(a,\,x)\in A\times(B-C)&\Leftrightarrow a\in A\wedge x\in(B-C)\\&\Leftrightarrow a\in A\wedge(x\in B\wedge x\notin C)\\&\Leftrightarrow a\in A\wedge a\in A\wedge x\in B\wedge x\notin C\\&\Leftrightarrow(a\in A\wedge x\in B)\wedge(a\in A\wedge x\notin C)\\&\Leftrightarrow(a,\,x)\in(A\times B)\wedge(a,\,x)\notin(A\times C)\\&\Leftrightarrow(a,\,x)\in[(A\times B)-(A\times C)]\end{align*}$$그러므로 \((a,\,x)\in A\times(B-C)\,\Leftrightarrow\,(a,\,x)\in(A\times B)-(A\times C)\)이고 \(A\times(B-C)=(A\times B)-(A\times C)\)이다.     

관계

집합 \(A\)에서 집합 \(B\)로의 관계(relation) \(\mathcal{R}\)은 데카르트곱 \(A\times B\)의 하나의 부분집합이다. 여기서 \((a,\,b)\in\mathcal{R}\)을 \(a\mathcal{R}b\)로 나타내고 "\(a\)는 \(\mathcal{R}\)에 따라 \(b\)와 관계된다"라고 한다. 특히 두 집합 \(A,\,B\)가 모두 \(X\)로 같으면 "\(X\)에서의 관계 \(\mathcal{R}\)"이라고 한다.

관계 \(\mathcal{R}\)의 역관계(inverse relation)을 \(\mathcal{R}^{-1}\)로 나타내고 \(B\)에서 \(A\)로의 관계로서 \(a\mathcal{R}b\,\Leftrightarrow\,b\mathcal{R}^{-1}a\)이고 \(\mathcal{R}^{-1}=\{(b,\,a)\,|\,(a,\,b)\in\mathcal{R}\}\)이다. 

예를들어 \(A=\{a,\,b\}\), \(B=\{x,\,y,\,z\}\)에 대하여 \(\mathcal{R}=\{(a,\,x),\,(b,\,y)\}\)라 놓으면 \(\mathcal{R}^{-1}=\{(x,\,a),\,(y,\,b)\}\)이다. 또한 \(\mathcal{R}=\{(x,\,y)\in\mathbb{N}\times\mathbb{N}\,|\,x\,\text{is a divisor of}\,y\}\)일 때 \(\mathcal{R}^{-1}=\{(y,\,x)\in\mathbb{N}\times\mathbb{N}\,|\,y\,\text{is a multiple of}\,y\}\)이다. 

집합 \(A\)에서 집합 \(B\)로의 관계 \(\mathcal{R}\)에서 적당한 \(b\in B\)에 대한 \(a\mathcal{R}b\)인 모든 \(a\in A\)들의 집합을 \(\mathcal{R}\)의 정의역(domain)이라 하고 \(\text{Dom}(\mathcal{R})\)로 나타낸다. 또한 적당한 \(a\in A\)에 대하여 \(a\mathcal{R}b\)인 모든 \(b\in B\)들의 집합을 \(\mathcal{R}\)의 상(image)이라 하고 \(\text{Im}(\mathcal{R})\)로 나타낸다.$$\begin{align*}&\text{Dom}(\mathcal{R})=\{a\in A\,|\,b\in B,\,(a,\,b)\in\mathcal{R}\}\\&\text{Im}(\mathcal{R})=\{b\in B\,|\,a\in A,\,(a,\,b)\in\mathcal{R}\}\end{align*}$$이때 \(\text{Dom}(\mathcal{R})=\text{Im}(\mathcal{R}^{-1})\), \(\text{Im}(\mathcal{R})=\text{Dom}(\mathcal{R}^{-1})\)이다. 

집합 \(X(\neq\phi)\)에서의 관계 \(\mathcal{R}\)이 다음의 조건을 만족할 때마다 그 왼편의 율이 성립된다고 한다. 

(a) 반사율(reflexive law): \(\forall x,\,x\mathcal{R}x\) (반사적)

(b) 대칭율(symmetric law): \(x\mathcal{R}y\,\Rightarrow\,y\mathcal{R}x\) (대칭적) 

(c) 추이율(transitive law): \(x\mathcal{R}y\wedge y\mathcal{R}z\,\Rightarrow\,x\mathcal{R}z\) (추이적)

(d) 동치관계(equivalence relation): \(\mathcal{R}\)에 대하여 반사율, 대칭율, 추이율 모두 성립한다.

예를들어 \(X=\{1,\,2,\,3,\,4\}\)에서의 관계$$\mathcal{R}=\{(1,\,1),\,(1,\,4),\,(2,\,2),\,(2,\,4),\,(4,\,1),\,(4,\,2),\,(4,\,4)\}$$에 대하여 \(3\in X\)이지만 \((3,\,3)\notin\mathcal{R}\)이므로 \(\mathcal{R}\)은 반사적이 아니고 \((1,\,4)\in\mathcal{R}\wedge(4,\,2)\in\mathcal{R}\)이지만 \((1,\,2)\notin\mathcal{R}\)이므로 추이적이 아니다. 그러나 대칭적이다. 

실제로 어느 집합 \(X(\neq\phi)\)에서 동치관계는 적어도 두 개 존재한다. 그 중 하나는 \(\Delta x=\{(x,\,x)\,|\,x\in X\}\)로 정의되는 항등관계(identity relation)(대각관계)이다. 여기서 \(X\)의 각 원소는 \(\Delta x\)에 따라 자기 자신에 관계지어졌음을 뜻한다.  

예를들어 \(m\)이 임의의 정해진 양의 정수일 때 집합 \(\mathbb{Z}\) 위에서의 법 \(m\)에 관한 합동관계 \(\equiv\)라는 것은 적당한 \(k\in\mathbb{Z}\)에 대하여$$x-y=km\,\Leftrightarrow\,x\equiv y\,(\text{mod}\,m)$$으로 정의된 것을 말한다. 이 합동은 동치관계이다.

참고자료:

집합론, You-Feng Lin, Shwu-Yeng T. Lin 저, 이흥천 옮김, 경문사