二項關係, Binary relation
1 개요
두 대상이 이루는 관계를 말한다. 예를 들어 '1+1은 2와 같다', '5는 3보다 크다' 등이 이항 관계라고 할 수 있다.
2 정의
출발 집합 [math]X[/math]와 도착 집합 [math]Y[/math]사이의 이항 관계 [math]R[/math]는 곱집합 [math]X\times Y=\left\{\left(x, y\right)|x\in X, y\in Y\right\}[/math]의 부분집합 [math]G[/math]에 대해 순서모음 [math]\left(X, Y, G\right)[/math]로 정의된다. 여기서 집합 [math]G[/math]를 이항 관계 [math]R[/math]의 그래프라 부른다. 또, 집합 [math]X, Y[/math] 각각의 어떤 원소 [math]x, y[/math]가 [math]\left(x, y\right)\in G[/math]를 만족하는 것을 [math]xRy[/math]로 나타낸다.
이항 관계 [math]R[/math]의 정의역(domain), 치역(range), 역(field)은 다음과 같이 정의된다.
- 정의역: ([math]G[/math]의 원소들의 왼쪽 성분의 집합)=[math]\left\{x\in X| \exists y\in Y : xRy\right\}=\text{dom} \,R[/math]
- 치역: ([math]G[/math]의 원소들의 오른쪽 성분의 집합)=[math]\left\{y\in Y| \exists x\in X : xRy\right\}=\text{ran} \,R[/math]
- 역: (정의역과 치역의 합집합)=[math]\text{dom} \,R \cup \text{ran} \,R=\text{fld} \, R[/math]
이항 관계 [math]R[/math]의 역관계 [math]R^{-1}[/math]는 [math]G[/math]의 모든 원소들을 좌우 순서를 바꾼 집합 [math]G'=\left\{\left(y, x\right)| \left(x, y\right)\in G\right\}[/math]에 대하여 순서모음 [math]\left(Y, X, G'\right)[/math]을 말한다.
[math]X[/math]와 [math]Y[/math] 사이의 이항 관계 [math]R[/math]이 있고, [math]Y[/math]와 [math]Z[/math] 사이의 이항 관계 [math]S[/math]가 있다고 할 때 합성 이항 관계 [math]S\circ R[/math]는 [math]H=\left\{\left(x, z\right)|\exists y \in Y : xRy \,\ \text{and} \,\ ySz\right\}[/math]에 대하여 순서모음 [math]\left(X, Z, H\right)[/math]로 정의된다.
[math]X=Y[/math]인 경우, 즉 출발 집합과 도착 집합이 모두 [math]X[/math]로 같은 이항 관계를 [math]X[/math] 위의 이항 관계라 한다.
3 예시
- 함수는 대표적인 이항 관계의 예이다. 함수 [math]f:X\rightarrow Y[/math]는 정의역이 [math]X[/math]이고 정의역의 임의의 원소 [math]x[/math]에 대하여 [math]xRy[/math]가 성립하는 [math]y\in Y[/math]가 유일하게 존재하는 [math]X, Y[/math]사이의 이항 관계 [math]R[/math]와 같다.
- [math]X[/math] 위의 순서 관계는 다음의 두 가지 성질을 가지는 [math]X[/math] 위의 이항 관계 [math]R[/math]를 말한다.
(반사성) 임의의 [math]x\in X[/math]에 대해 [math]xRx[/math]
(추이성) 임의의 [math]x,y,z \in X[/math]에 대해 [math]xRy \,\ \text{and} \,\ yRz \Longrightarrow xRz[/math]