집합론, 그 다섯 번째 이야기 | 관계

집합 $X_1,X_2,...,X_n$ 가 존재할 때, 이들 위의 관계는 아래처럼 정의한다.

 

$X$를 $X={\displaystyle \prod _{i=1}^n{X}_i}$라 하자. 이 때 어떤 집합 $G$가 존재하여 $G\subset X$ 라면      $X_1,X_2,...,X_n$위의 관계는 튜플 $(X_1,X_2,...X_n,G)$ 로 정의된다.

 

위의처럼 정의될 때, $X_1,X_2,...,X_n$에서 각각 원소 $x_1,x_2,...,x_n$을 선택할 때, $(x_1,x_2,...,x_n)\in G$ 가 성립한다면, 이것을 "$x_1,x_2,...,x_n$이 관계 $G$를 갖는다." 라고 말하고, $G{x}_1{x}_2,...,x_n$ 이라고 쓴다.

 

이 중 특히, 이항관계(Binary Relation)에 대해 알아보자.

이는 위의 정의에서 $n=2$인 경우 즉, 집합 $X,Y$와 $G\subset X\times Y$ 인 $G$에 대해 튜플 $(X,Y,G)$ 를 말한다.

이 때, 이항관계에서는 $X,Y$의 원소 $x,y$에 대해 $(x,y)\in G$를 $Gxy$ 가 아닌, $xGy$와 같이 표기하기도 한다.

 

이항관계는 우리에게 친숙한 함수 또한 포함한다. 함수 $f:X\to Y$ 는 $X$의 원소 $x$에 대해 $xGy$가 성립하는 $y\in Y$가 유일하게 존재하는 이항관계 $G$처럼 생각할 수 있는 것이다.

 

또, 함수에서도 정의역, 치역이 존재하듯이, 일반적인 이항관계에 대해서도 정의역과 치역을 정의할 수 있다.

이항관계 $(X,Y,G)$에 대해, 정의역, 치역의 정의는 다음과 같다.      $\text{dom}G=\{x\in X:\mathrm{\exists }y\in Ys.t.xGy\}$ (정의역)      $\text{ran}G=\{y\in Y:\mathrm{\exists }x\in Xs.t.xGy\}$ (치역)      또한, 정의역과 치역의 합집합을 역이라고 한다.      $\text{dom}G\cup \text{ran}G=\text{fld}G$ (역)

 

위 정의에서의 $\text{dom}$, $\text{ran}$, $\text{fld}$ 는 각각 domain, range, field에서 따온 것이다.

 

만약 이항관계에서 $X=Y$인 경우, 이를 $X$ 위의 이항관계 또는 $Y$ 위의 이항관계라 부른다.

$X$ 위의 이항관계 $G$는 다음과 같은 유용한 성질을 가질 수도 있다. (무조건 가지는 것이 아님을 명심하자)

반사성(Reflexivity) : $\mathrm{\forall }x\in X:xGx$      대칭성(Symmetricity) : $\mathrm{\forall }{x}_1,x_2\in X:x_{1}G{x}_2\to x_{2}G{x}_1$      비대칭성(Asymmetricity) : $\mathrm{\forall }{x}_1,x_2\in X:x_{1}G{x}_2\to \mathrm{\neg }{x}_{2}G{x}_1$      반대칭성(Antisymmetricity) : $\mathrm{\forall }{x}_1,x_2\in X:x_{1}G{x}_2\wedge x_{2}G{x}_1\to x=y$      추이성(Transitivity) : $\mathrm{\forall }{x}_1,x_2,x_3\in X:x_{1}G{x}_2\wedge x_{2}G{x}_3\to x_{1}G{x}_3$