이항 관계

수학에서 이항 관계(二項關係, 영어: 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$이다.^{:10:26, 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{aligned}(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{aligned}}$

이에 따라, 범주 $\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{aligned}&R^{\circ m}\circ R^{\circ 1}=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{aligned}}$

그 밖에도, 다음 항등식들이 성립한다.

$\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{aligned}(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{aligned}}$

${\begin{aligned}(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{aligned}}$

역관계

이항 관계 $R$의 역관계 $R^{-1}$는 $R$ 속 순서쌍의 두 성분을 뒤바꾼 이항 관계이다.

$R^{-1}=\{(y,x)|(x,y)\in R\}$

역관계는 자명하게 대합을 이룬다.

$(R^{-1})^{-1}=R$

증명:

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

역관계와 합성은 다음과 같이 호환된다.

$(S\circ R)^{-1}=R^{-1}\circ S^{-1}$

증명:

${\begin{aligned}(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{aligned}}$

특히,

$(R^{\circ n})^{-1}=(R^{-1})^{\circ n}$

이다.

증명:

${\begin{aligned}&(R^{\circ 1})^{-1}=R^{-1}=(R^{-1})^{\circ 1}\\&(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{aligned}}$

정의역과 치역

이항 관계 $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$이다. 따라서, 이항 관계의 상·원상·정의역·치역은 항상 집합이다.^{:27, 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{aligned}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{aligned}}$

${\begin{aligned}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{aligned}}$

${\begin{aligned}(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{aligned}}$

종류

• 함수는 이항 관계의 중요한 유형이다. 이항 관계 $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$

외부 링크

• 이철희. “이항관계”. 《수학노트》. 
• “Binary relation”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Relation”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “Rel”. 《nLab》 (영어). 
• “Relation”. 《PlanetMath》 (영어). 
• “Definition: relation”. 《ProofWiki》 (영어).