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

집합 $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$위의 관계는 튜플 $\left ( X_1,X_2,...X_n,G \right )$ 로 정의된다.

 

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

 

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

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

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

 

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

 

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

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

 

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

 

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

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

반사성(Reflexivity) : $\forall x \in X : xGx$      대칭성(Symmetricity) : $\forall x_1,x_2 \in X : x_1Gx_2 \rightarrow x_2Gx_1$      비대칭성(Asymmetricity) : $\forall x_1,x_2 \in X : x_1Gx_2 \rightarrow \neg x_2Gx_1$      반대칭성(Antisymmetricity) : $\forall x_1,x_2 \in X :  x_1Gx_2 \wedge x_2Gx_1 \rightarrow x=y$      추이성(Transitivity) : $\forall x_1,x_2,x_3 \in X : x_1Gx_2 \wedge x_2Gx_3 \rightarrow x_1Gx_3$