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