이항 관계

수학에서 **이항 관계**(二項關係, binary relation)는 “…는 …보다 크다” 또는 “…와 …는 같다”와 같이, 두 대상에 대하여 정의되는 성질을 집합론적으로 실현한 개념이다. 기술적으로, 이항 관계는 순서쌍들로 구성된 집합이다. 어떤 순서쌍이 이항 관계의 원소라면, 순서쌍의 두 성분 사이에 관계가 성립한다고 해석한다. 예를 들어, “…는 …의 약수”라는 조건은 두 정수 사이의 이항 관계 \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이다.settheory0000jech_f7i41026, Definition I.6.1 * 모든 원소는 순서쌍이다. 즉, 임의의 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}은 모든 작은 곱과 쌍대곱을 가지며, 둘 모두 분리합집합으로 주어진다. 또한, 동등자를 가지지 않지만, 모든 작은 약한 동등자(weak equalizer)를 갖는다. 또한, 이항 관계 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의 **상**(image)은 A의 원소와 관계를 이루는 원소들의 집합이다. *:R(A)=\\{y|\exists x\in A\colon(x,y)\in R\\} * 집합 또는 모임 B의 **원상**(preimage)은 역관계에 대한 상이다. *: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이다. 따라서, 이항 관계의 상·원상·정의역·치역은 항상 집합이다.settheory0000kune27, Definition I.6.6, Justification 임의의 이항 관계 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