이항 관계

수학에서 **이항 관계**(二項關係, )는 “…는 …보다 크다” 또는 “…와 …는 같다”와 같이, 두 대상에 대하여 정의되는 성질을 집합론적으로 실현한 개념이다. 기술적으로, 이항 관계는 순서쌍들로 구성된 집합이다. 어떤 순서쌍이 이항 관계의 원소라면, 순서쌍의 두 성분 사이에 관계가 성립한다고 해석한다.

예를 들어, “…는 …의 약수”라는 조건은 두 정수 사이의 이항 관계 \mid를 정의한다. 이 이항 관계는 기술적으로 m이 n의 약수인 경우의 모든 순서쌍 (m,n)들의 집합이다. (5,20)은 이 이항 관계의 원소이며, (6,13)은 이항 관계의 원소가 아니다 (5는 20의 약수이며, 6은 13의 약수가 아니다). 보통 (5,20)\in{\mid}나 (6,13)\not\in{\mid} 대신
:5\mid 20
:6\nmid 13
와 같이 적는다.

이항 관계의 개념은 모임 위로 확장할 수 있다. 모임 위의 이항 관계는 모임이며, 고유 모임일 수 있다. 고유 모임은 모임의 원소가 될 수 없으므로, 주어진 두 모임 사이의 이항 관계들의 모임을 정의할 수 없다. 반면, 주어진 집합 위의 이항 관계들의 모임을 정의할 수 있으며, 이는 항상 집합이다.

이항 관계는 관계의 항수가 2인 경우이다. 이항 관계의 이론은 다른 항수의 관계보다 풍부하다. 일부 문헌에서는 이항 관계를 단순히 **관계**라고 부른다. 혹자는 이항 관계를 **대응**(對應, correspondence)이라고 일컫는다.

## 정의
**이항 관계**는 다음 조건을 만족시키는 집합 R이다.
* 모든 원소는 순서쌍이다. 즉, 임의의 r\in R에 대하여, r=(x,y)인 집합 x, y가 존재한다.
만약 (x,y)\in R라면, x와 y 사이에 관계 R가 성립한다고 해석한다. xRy는 (x,y)\in R를 뜻한다. x\not Ry는 (x,y)\not\in R를 뜻한다. xRySz는 (x,y)\in R이며 (y,z)\in S임을 뜻한다.

집합 X와 Y 위의 이항 관계는 이항 관계 R\subseteq X\times Y를 뜻한다. 집합 X 위의 이항 관계는 X와 X 위의 이항 관계 R\subseteq X\times X를 뜻한다. 모든 이항 관계 R는 어떤 집합 (예를 들어, X=\bigcup\bigcup R) 위의 이항 관계이다.

## 연산
### 합성
이항 관계 R와 S의 **합성** S\circ R는 다음과 같다.
:S\circ R=\{(x,z)|\exists y\colon(x,y)\in R\land(y,z)\in S\}

이항 관계의 합성은 결합 법칙을 만족시킨다.
:(T\circ S)\circ R=T\circ(S\circ R)

:\begin{align}
(x,y) \in T\circ (S\circ R)
&\Longleftrightarrow \exists z\colon(x,z) \in S\circ R\land (z,y) \in T\\
&\Longleftrightarrow \exists z\colon(\exists w\colon(x,w) \in R\land (w,z) \in S) \land (z,y) \in T\\
&\Longleftrightarrow \exists w\colon(x,w) \in R\land(\exists z\colon(w,z) \in S\land (z,y) \in T)\\
&\Longleftrightarrow \exists w\colon(x,w) \in R\land (w,z) \in T\circ S\\
&\Longleftrightarrow (x,y) \in (T\circ S) \circ R
\end{align}

이에 따라, 범주 \operatorname{Rel}을 다음과 같이 정의할 수 있다.
* 대상은 집합이다.
* 두 집합 사이의 사상 f\colon X\to Y은 이항 관계 f\subseteq X\times Y이다.
* 사상의 합성은 이항 관계의 합성이다.
* 집합 X의 항등 사상은 대각선 \operatorname{id}_X=\{(x,x)\colon x\in X\}\subseteq X\times X이다.

집합과 이항 관계의 범주 \operatorname{Rel}은 모든 작은 곱과 쌍대곱을 가지며, 둘 모두 분리합집합으로 주어진다. 또한, 동등자를 가지지 않지만, 모든 작은 약한 동등자()를 갖는다.

또한, 이항 관계 R의 거듭제곱
:R^{\circ n}=\underbrace{R\circ\cdots\circ R}_n
을 정의할 수 있다. 이에 대하여 다음 항등식들이 성립한다.
:R^{\circ m} \circ R^{\circ n} =R^{\circ(m+n)}
:(R^{\circ m})^{\circ n} =R^{\circ mn}

:\begin{align}
&R^{\circ m} \circ R^{\circ1} =R^{\circ m} \circ R=R^{\circ(m+1)}\\
&R^{\circ m} \circ R^{\circ(n+1)} =R^{\circ m} \circ (R^{\circ n} \circ R) =(R^{\circ m} \circ R^{\circ n}) \circ R=R^{\circ(m+n)} \circ R=R^{(m+n) +1} =R^{\circ m+(n+1)}\\
&(R^{\circ m})^{1} =R^{\circ m} =R^{\circ m1}\\
&(R^{\circ m})^{n+1} =R^{\circ m} \circ (R^{\circ m})^{\circ n} =R^{\circ m} \circ R^{\circ mn} =R^{\circ(m+mn)} =R^{\circ m(n+1)}
\end{align}

그 밖에도, 다음 항등식들이 성립한다.
:\bigcup \mathcal{S} \circ R=\bigcup _{S\in \mathcal{S}}(S\circ R)
:S\circ \bigcup \mathcal{R} =\bigcup _{R\in \mathcal{R}}(S\circ R)

:\begin{align}
(x,y) \in \bigcup \mathcal{S} \circ R
&\Longleftrightarrow \exists z((x,z) \in R\land (z,y) \in \bigcup \mathcal{S})\\
&\Longleftrightarrow \exists z\colon(x,z) \in R\land(\exists S\in \mathcal{S}\colon(z,y) \in S)\\
&\Longleftrightarrow \exists S\in \mathcal{S}\exists z\colon(x,z) \in R\land (z,y) \in S\\
&\Longleftrightarrow \exists S\in S\colon(x,y) \in S\circ R\\
&\Longleftrightarrow (x,y) \in \bigcup _{S\in \mathcal{S}}(S\circ R)\\
\end{align}

:\begin{align}
(x,y) \in S\circ \bigcup \mathcal{R}
&\Longleftrightarrow \exists z\colon(x,z) \in \bigcup \mathcal{R} \land (z,y) \in S\\
&\Longleftrightarrow \exists z\exists R\in \mathcal{R}\colon(x,z) \in R\land (z,y) \in S\\
&\Longleftrightarrow \exists R\in \mathcal{R} \exists z\colon(x,z) \in R\land (z,y) \in S\\
&\Longleftrightarrow \exists R\in \mathcal{R}\colon(x,y) \in S\circ R\\
&\Longleftrightarrow (x,y) \in \bigcup _{R\in \mathcal{R}}(S\circ R)
\end{align}


### 역관계
이항 관계 R의 **역관계** R^{-1}는 R 속 순서쌍의 두 성분을 뒤바꾼 이항 관계이다.
:R^{-1}=\{(y,x)|(x,y)\in R\}
역관계는 자명하게 대합을 이룬다.
:(R^{-1})^{-1}=R

:\begin{align}
(x,y) \in (R^{-1})^{-1}
&\Longleftrightarrow (y,x) \in R^{-1}\\
&\Longleftrightarrow (x,y) \in R
\end{align}


역관계와 합성은 다음과 같이 호환된다.
:(S\circ R)^{-1}=R^{-1}\circ S^{-1}

:\begin{align}
(x,y) \in (S\circ R)^{-1}
&\Longleftrightarrow (y,x) \in S\circ R\\
&\Longleftrightarrow \exists z\colon(y,z) \in R\land (z,x) \in S\\
&\Longleftrightarrow \exists z\colon(z,y) \in R^{-1} \land (x,z) \in S^{-1}\\
&\Longleftrightarrow \exists z\colon(x,z) \in S^{-1} \land (z,y) \in R^{-1}\\
&\Longleftrightarrow (x,y) \in R^{-1} \circ S^{-1}
\end{align}


특히,
:(R^{\circ n})^{-1}=(R^{-1})^{\circ n}
이다.

:\begin{align}
&(R^{\circ1})^{-1} =R^{-1} =(R^{-1})^{\circ1}\\
&(R^{\circ(n+1)})^{-1} =(R\circ R^{\circ n})^{-1} =(R^{\circ n})^{-1} \circ R^{-1} =(R^{-1})^{\circ n} \circ R^{-1} =(R^{-1})^{\circ(n+1)}
\end{align}


### 정의역과 치역
이항 관계 R가 주어졌을 때,
* 집합 또는 모임 A의 **상**()은 A의 원소와 관계를 이루는 원소들의 집합이다.
*:R(A)=\{y|\exists x\in A\colon(x,y)\in R\}
* 집합 또는 모임 B의 **원상**()은 역관계에 대한 상이다.
*:R^{-1}(B)=\{x|\exists y\in B\colon (x,y)\in R\}
* R의 **정의역** \operatorname{dom}R는 모든 집합의 고유 모임의 원상이다. (이는 범주 \operatorname{Rel}에서의 정의역과 다른 개념이다.)
*:\operatorname{dom}R=R^{-1}(V)=\{x|\exists y\colon(x,y)\in R\}
* R의 **치역** \operatorname{ran}R는 모든 집합의 고유 모임의 상이다.
*:\operatorname{ran}R=R(V)=\{y|\exists x\colon(x,y)\in R\}
만약 (x,y)=\{\{x\},\{x,y\}\}\in R라면, \{x\},\{x,y\}\in\bigcup R이므로, x,y\in\bigcup\bigcup R이다. 따라서, 이항 관계의 상·원상·정의역·치역은 항상 집합이다.

임의의 이항 관계 R에 대하여, 다음이 성립한다.
:\operatorname{dom}R^{-1}=\operatorname{ran}R
:\operatorname{ran}R^{-1}=\operatorname{dom}R
:\operatorname{dom}R\cup\operatorname{ran}R=\bigcup\bigcup R
:\operatorname{dom}(S\circ R)\subseteq\operatorname{dom}R
:\operatorname{ran}(S\circ R)\subseteq\operatorname{ran}S

:\begin{align}
x\in \operatorname{dom} R^{-1}
&\Longleftrightarrow \exists y\colon(x,y) \in R^{-1}\\
&\Longleftrightarrow \exists y\colon(y,x) \in R\\
&\Longleftrightarrow x\in \operatorname{ran} R\\
\end{align}

:\begin{align}
y\in \operatorname{ran} R^{-1}
&\Longleftrightarrow \exists x\colon(x,y) \in R^{-1}\\
&\Longleftrightarrow \exists x\colon(y,x) \in R\\
&\Longleftrightarrow y\in \operatorname{dom} R
\end{align}

:\begin{align}
(x,y) \in S\circ R
&\Longleftrightarrow \exists z\colon(x,z) \in R\land (z,y) \in S\\
&\Longrightarrow x\in \operatorname{dom} R\land y\in \operatorname{ran} S\\
&\Longleftrightarrow (x,y) \in \operatorname{dom} R\times \operatorname{ran} S
\end{align}


## 종류
* **[[함수]]**는 이항 관계의 중요한 유형이다. 이항 관계 F\subseteq X\times Y가 함수 F\colon X\to Y일 필요충분조건은 다음 두 조건을 만족시키는 것이다.
** \forall x\in X\exists y\in Y\colon xFy
** \forall x\in X\forall y,z\in Y\colon xFy\land xFz\implies y=z
* 이항 관계는 일반적으로 함수가 아니다. 예를 들어 약수 관계에서, 5로 나누어지는 정수는 유일하지 않다.
* **[[반사관계]]**는 다음 조건을 만족시키는 이항 관계 R\subseteq X^2이다.
*:\forall x\in X\colon xRx
* **[[대칭관계]]**는 다음 조건을 만족시키는 이항 관계 R\subseteq X^2이다.
*:\forall x,y\in X\colon xRy\implies yRx
* **[[반대칭관계]]**는 다음 조건을 만족시키는 이항 관계 R\subseteq X^2이다.
*:\forall x,y\in X\colon xRy\land yRx\implies x=y
* **[[추이관계]]**는 다음 조건을 만족시키는 이항 관계 R\subseteq X^2이다.
*:\forall x,y,z\in X\colon xRy\land yRz\implies xRz
* **[[완전관계]]**는 다음 조건을 만족시키는 이항 관계 R\subseteq X^2이다.
*:\forall x,y\in X\colon xRy\lor yRx

## 참고 문헌

## 외부 링크
* 
* 
* 
* 
* 
* 

분류:관계 (수학)