[집합론] 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 저, 이흥천 옮김, 경문사