이항 관계 문서 원본 보기

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

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

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

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

== 정의 ==
'''이항 관계'''는 다음 조건을 만족시키는 [[집합]] <math>R</math>이다.<ref name="Jech">{{서적 인용|성1=Jech|이름1=Thomas|제목=Set theory|url=https://archive.org/details/settheory0000jech_f7i4|언어=en|판=3|총서=Springer Monographs in Mathematics|출판사=Springer|위치=Berlin|날짜=2003|isbn=978-3-540-44085-7|issn=1439-7382|doi=10.1007/3-540-44761-X|mr=1940513|zbl=1007.03002|id={{iaid|settheory0000jech_f7i4}}}}</ref>{{rp|10}}<ref name="Kunen2011"/>{{rp|26, Definition I.6.1}}
* 모든 원소는 [[순서쌍]]이다. 즉, 임의의 <math>r\in R</math>에 대하여, <math>r=(x,y)</math>인 집합 <math>x</math>, <math>y</math>가 존재한다.
만약 <math>(x,y)\in R</math>라면, <math>x</math>와 <math>y</math> 사이에 관계 <math>R</math>가 성립한다고 해석한다. <math>xRy</math>는 <math>(x,y)\in R</math>를 뜻한다. <math>x\not Ry</math>는 <math>(x,y)\not\in R</math>를 뜻한다. <math>xRySz</math>는 <math>(x,y)\in R</math>이며 <math>(y,z)\in S</math>임을 뜻한다.

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

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

이항 관계의 합성은 [[결합 법칙]]을 만족시킨다.
:<math>(T\circ S)\circ R=T\circ(S\circ R)</math>
{{증명}}
:<math>\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}</math>
{{증명 끝}}

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

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

또한, 이항 관계 <math>R</math>의 거듭제곱
:<math>R^{\circ n}=\underbrace{R\circ\cdots\circ R}_n</math>
을 정의할 수 있다. 이에 대하여 다음 항등식들이 성립한다.
:<math>R^{\circ m} \circ R^{\circ n} =R^{\circ(m+n)}</math>
:<math>(R^{\circ m})^{\circ n} =R^{\circ mn}</math>
{{증명}}
:<math>\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}</math>
{{증명 끝}}

그 밖에도, 다음 항등식들이 성립한다.
:<math>\bigcup \mathcal{S} \circ R=\bigcup _{S\in \mathcal{S}}(S\circ R)</math>
:<math>S\circ \bigcup \mathcal{R} =\bigcup _{R\in \mathcal{R}}(S\circ R)</math>
{{증명}}
:<math>\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}
</math>
:<math>\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}
</math>
{{증명 끝}}

=== 역관계 ===
이항 관계 <math>R</math>의 '''역관계''' <math>R^{-1}</math>는 <math>R</math> 속 순서쌍의 두 성분을 뒤바꾼 이항 관계이다.
:<math>R^{-1}=\{(y,x)|(x,y)\in R\}</math>
역관계는 자명하게 [[대합 (수학)|대합]]을 이룬다.
:<math>(R^{-1})^{-1}=R</math>
{{증명}}
:<math>\begin{align}
(x,y) \in (R^{-1})^{-1}
&\Longleftrightarrow (y,x) \in R^{-1}\\
&\Longleftrightarrow (x,y) \in R
\end{align}
</math>
{{증명 끝}}
역관계와 합성은 다음과 같이 호환된다.
:<math>(S\circ R)^{-1}=R^{-1}\circ S^{-1}</math>
{{증명}}
:<math>\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}
</math> 
{{증명 끝}}
특히,
:<math>(R^{\circ n})^{-1}=(R^{-1})^{\circ n}</math>
이다.
{{증명}}
:<math>\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}
</math>
{{증명 끝}}

=== 정의역과 치역 ===
이항 관계 <math>R</math>가 주어졌을 때,
* [[집합]] 또는 [[모임 (집합론)|모임]] <math>A</math>의 '''상'''({{llang|en|image}})은 <math>A</math>의 원소와 관계를 이루는 원소들의 집합이다.
*:<math>R(A)=\{y|\exists x\in A\colon(x,y)\in R\}</math>
* [[집합]] 또는 [[모임 (집합론)|모임]] <math>B</math>의 '''원상'''({{llang|en|preimage}})은 역관계에 대한 상이다.
*:<math>R^{-1}(B)=\{x|\exists y\in B\colon (x,y)\in R\}</math>
* <math>R</math>의 '''정의역''' <math>\operatorname{dom}R</math>는 모든 집합의 [[고유 모임]]의 원상이다. (이는 범주 <math>\operatorname{Rel}</math>에서의 정의역과 다른 개념이다.)
*:<math>\operatorname{dom}R=R^{-1}(V)=\{x|\exists y\colon(x,y)\in R\}</math>
* <math>R</math>의 '''치역''' <math>\operatorname{ran}R</math>는 모든 집합의 [[고유 모임]]의 상이다.
*:<math>\operatorname{ran}R=R(V)=\{y|\exists x\colon(x,y)\in R\}</math>
만약 <math>(x,y)=\{\{x\},\{x,y\}\}\in R</math>라면, <math>\{x\},\{x,y\}\in\bigcup R</math>이므로, <math>x,y\in\bigcup\bigcup R</math>이다. 따라서, 이항 관계의 상·원상·정의역·치역은 항상 집합이다.<ref name="Kunen2011">{{서적 인용|성=Kunen|이름=Kenneth|저자링크=케네스 쿠넌|제목=Set theory|언어=en|총서=Studies in Logic (London)|권=34|출판사=College Publications|위치=London|날짜=2011|isbn=978-1-84890-050-9|mr=2905394|zbl=1262.03001|id={{iaid|settheory0000kune}}}}</ref>{{rp|27, Definition I.6.6, Justification}}

임의의 이항 관계 <math>R</math>에 대하여, 다음이 성립한다.
:<math>\operatorname{dom}R^{-1}=\operatorname{ran}R</math>
:<math>\operatorname{ran}R^{-1}=\operatorname{dom}R</math>
:<math>\operatorname{dom}R\cup\operatorname{ran}R=\bigcup\bigcup R</math>
:<math>\operatorname{dom}(S\circ R)\subseteq\operatorname{dom}R</math>
:<math>\operatorname{ran}(S\circ R)\subseteq\operatorname{ran}S</math>
{{증명}}
:<math>\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}
</math>
:<math>\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}
</math>
:<math>\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}
</math>
{{증명 끝}}

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

== 참고 문헌 ==
{{각주}}

== 외부 링크 ==
* {{수학노트|제목=이항관계}}
* {{eom|제목=Binary relation}}
* {{매스월드|id=Relation|제목=Relation}}
* {{nlab|id=Rel|제목=Rel}}
* {{플래닛매스|urlname=Relation|제목=Relation}}
* {{proofwiki|id=Definition:Relation|제목=Definition: relation}}

{{전거 통제}}
[[분류:관계 (수학)]]