수학 에서 이항 관계 (二項關係, 영어 : binary relation )는 “…는 …보다 크다” 또는 “…와 …는 같다”와 같이, 두 대상에 대하여 정의되는 성질을 집합론 적으로 실현한 개념이다. 이항 관계는 순서쌍 들로 구성된 집합 이다. 어떤 순서쌍이 이항 관계의 원소라면, 순서쌍의 두 성분 사이에 관계가 성립한다고 해석한다.
예를 들어, “…는 …의 약수 ”라는 조건은 두 정수 사이의 이항 관계
∣
{\displaystyle \mid }
를 정의한다. 이 이항 관계는 구체적으로
m
{\displaystyle m}
이
n
{\displaystyle n}
의 약수인 경우의 모든 순서쌍
(
m
,
n
)
{\displaystyle (m,n)}
들의 집합이다.
(
5
,
20
)
{\displaystyle (5,20)}
은 이 이항 관계의 원소이며,
(
6
,
13
)
{\displaystyle (6,13)}
은 이항 관계의 원소가 아니다 (5는 20의 약수이며, 6은 13의 약수가 아니다). 보통
(
5
,
20
)
∈
∣
{\displaystyle (5,20)\in {\mid }}
나
(
6
,
13
)
∉
∣
{\displaystyle (6,13)\not \in {\mid }}
대신
5
∣
20
{\displaystyle 5\mid 20}
6
∤
13
{\displaystyle 6\nmid 13}
와 같이 적는다.
이항 관계의 개념은 모임 위로 확장할 수 있다. 모임 위의 이항 관계는 모임이며, 고유 모임 일 수 있다. 고유 모임은 모임의 원소가 될 수 없으므로, 주어진 두 모임 사이의 이항 관계들의 모임을 정의할 수 없다. 반면, 주어진 집합 위의 이항 관계들의 모임을 정의할 수 있으며, 이는 항상 집합이다.
이항 관계는 관계 의 항수가 2인 경우이다. 이항 관계의 이론은 다른 항수의 관계보다 풍부하다. 일부 문헌에서는 이항 관계를 단순히 관계 라고 부른다. 혹자는 이항 관계를 대응 (對應, correspondence)이라고 일컫는다.
이항 관계 는 다음 조건을 만족시키는 집합
R
{\displaystyle R}
이다.
모든 원소는 순서쌍 이다. 즉, 임의의
r
∈
R
{\displaystyle r\in R}
에 대하여,
r
=
(
x
,
y
)
{\displaystyle r=(x,y)}
인 집합
x
{\displaystyle x}
,
y
{\displaystyle y}
가 존재한다.
만약
(
x
,
y
)
∈
R
{\displaystyle (x,y)\in R}
라면,
x
{\displaystyle x}
와
y
{\displaystyle y}
사이에 관계
R
{\displaystyle R}
가 성립한다고 해석한다.
x
R
y
{\displaystyle xRy}
는
(
x
,
y
)
∈
R
{\displaystyle (x,y)\in R}
를 뜻한다.
x
R̸
y
{\displaystyle x\not Ry}
는
(
x
,
y
)
∉
R
{\displaystyle (x,y)\not \in R}
를 뜻한다.
x
R
y
S
z
{\displaystyle xRySz}
는
(
x
,
y
)
∈
R
{\displaystyle (x,y)\in R}
이며
(
y
,
z
)
∈
S
{\displaystyle (y,z)\in S}
임을 뜻한다.
집합
X
{\displaystyle X}
와
Y
{\displaystyle Y}
위의 이항 관계는 이항 관계
R
⊆
X
×
Y
{\displaystyle R\subseteq X\times Y}
를 뜻한다. 집합
X
{\displaystyle X}
위의 이항 관계는
X
{\displaystyle X}
와
X
{\displaystyle X}
위의 이항 관계
R
⊆
X
×
X
{\displaystyle R\subseteq X\times X}
를 뜻한다. 모든 이항 관계
R
{\displaystyle R}
는 어떤 집합 (예를 들어,
X
=
⋃
⋃
R
{\displaystyle X=\bigcup \bigcup R}
) 위의 이항 관계이다.
이항 관계
R
{\displaystyle R}
와
S
{\displaystyle S}
의 합성
S
∘
R
{\displaystyle S\circ R}
는 다음과 같다.
S
∘
R
=
{
(
x
,
z
)
|
∃
y
:
(
x
,
y
)
∈
R
∧
(
y
,
z
)
∈
S
}
{\displaystyle S\circ R=\{(x,z)|\exists y\colon (x,y)\in R\land (y,z)\in S\}}
이항 관계의 합성은 결합 법칙 을 만족시킨다.
(
T
∘
S
)
∘
R
=
T
∘
(
S
∘
R
)
{\displaystyle (T\circ S)\circ R=T\circ (S\circ R)}
이에 따라, 집합과 이항 관계의 범주
Rel
{\displaystyle \operatorname {Rel} }
를 다음과 같이 정의할 수 있다.
대상은 집합 이다.
두 집합 사이의 사상
f
:
X
→
Y
{\displaystyle f\colon X\to Y}
은 이항 관계
f
⊆
X
×
Y
{\displaystyle f\subseteq X\times Y}
이다.
사상의 합성은 이항 관계의 합성이다.
집합
X
{\displaystyle X}
의 항등 사상은 대각선
id
X
=
{
(
x
,
x
)
:
x
∈
X
}
⊆
X
×
X
{\displaystyle \operatorname {id} _{X}=\{(x,x)\colon x\in X\}\subseteq X\times X}
이다.
범주
Rel
{\displaystyle \operatorname {Rel} }
은 모든 작은 곱 과 쌍대곱 을 가지며, 둘 모두 분리합집합 으로 주어진다. 또한, 동등자 를 가지지 않지만, 모든 작은 약한 동등자 (영어 : weak equalizer )를 갖는다.
이항 관계
R
{\displaystyle R}
의 역관계
R
−
1
{\displaystyle R^{-1}}
는
R
{\displaystyle R}
속 순서쌍의 두 성분을 뒤바꾼 이항 관계이다.
R
−
1
=
{
(
y
,
x
)
|
(
x
,
y
)
∈
R
}
{\displaystyle R^{-1}=\{(y,x)|(x,y)\in R\}}
역관계는 자명하게 멱등 연산이다.
(
R
−
1
)
−
1
=
R
{\displaystyle (R^{-1})^{-1}=R}
역관계와 합성은 다음과 같이 호환된다.
(
S
∘
R
)
−
1
=
R
−
1
∘
S
−
1
{\displaystyle (S\circ R)^{-1}=R^{-1}\circ S^{-1}}
이항 관계
R
{\displaystyle R}
가 주어졌을 때,
집합 또는 모임
A
{\displaystyle A}
의 상 은
A
{\displaystyle A}
의 원소와 관계를 이루는 원소들의 집합이다.
R
(
A
)
=
{
y
|
∃
x
∈
A
:
(
x
,
y
)
∈
R
}
{\displaystyle R(A)=\{y|\exists x\in A\colon (x,y)\in R\}}
집합 또는 모임
B
{\displaystyle B}
의 원상 은 역관계에 대한 상이다.
R
−
1
(
B
)
=
{
x
|
∃
y
∈
B
:
(
x
,
y
)
∈
R
}
{\displaystyle R^{-1}(B)=\{x|\exists y\in B\colon (x,y)\in R\}}
R
{\displaystyle R}
의 정의역
dom
R
{\displaystyle \operatorname {dom} R}
는 모든 집합의 고유 모임 의 원상이다. (이는 범주
Rel
{\displaystyle \operatorname {Rel} }
에서의 정의역과 다른 개념이다.)
dom
R
=
R
−
1
(
V
)
=
{
x
|
∃
y
:
(
x
,
y
)
∈
R
}
{\displaystyle \operatorname {dom} R=R^{-1}(V)=\{x|\exists y\colon (x,y)\in R\}}
R
{\displaystyle R}
의 치역
ran
R
{\displaystyle \operatorname {ran} R}
는 모든 집합의 고유 모임 의 상이다.
ran
R
=
R
(
V
)
=
{
y
|
∃
x
:
(
x
,
y
)
∈
R
}
{\displaystyle \operatorname {ran} R=R(V)=\{y|\exists x\colon (x,y)\in R\}}
만약
(
x
,
y
)
=
{
{
x
}
,
{
x
,
y
}
}
∈
R
{\displaystyle (x,y)=\{\{x\},\{x,y\}\}\in R}
라면,
{
x
}
,
{
x
,
y
}
∈
⋃
R
{\displaystyle \{x\},\{x,y\}\in \bigcup R}
이므로,
x
,
y
∈
⋃
⋃
R
{\displaystyle x,y\in \bigcup \bigcup R}
이다. 따라서, 이항 관계의 상·원상·정의역·치역은 항상 집합이다.[ 1] :27, Definition I.6.6, Justification
임의의 이항 관계
R
{\displaystyle R}
에 대하여, 다음이 성립한다.
dom
R
−
1
=
ran
R
{\displaystyle \operatorname {dom} R^{-1}=\operatorname {ran} R}
ran
R
−
1
=
dom
R
{\displaystyle \operatorname {ran} R^{-1}=\operatorname {dom} R}
dom
R
∪
ran
R
=
⋃
⋃
R
{\displaystyle \operatorname {dom} R\cup \operatorname {ran} R=\bigcup \bigcup R}
함수 는 이항관계의 중요한 유형이다. 이항관계
F
⊆
X
×
Y
{\displaystyle F\subseteq X\times Y}
가 함수
F
:
X
→
Y
{\displaystyle F\colon X\to Y}
일 필요충분조건은 다음 두 조건을 만족시키는 것이다.
∀
x
∈
X
∃
y
∈
Y
:
x
F
y
{\displaystyle \forall x\in X\exists y\in Y\colon xFy}
∀
x
∈
X
∀
y
,
z
∈
Y
:
x
F
y
∧
x
F
z
⟹
y
=
z
{\displaystyle \forall x\in X\forall y,z\in Y\colon xFy\land xFz\implies y=z}
이항관계는 일반적으로 함수가 아니다. 예를 들어 약수 관계에서, 5로 나누어지는 정수는 유일하지 않다.
반사관계 는 다음 조건을 만족시키는 이항관계
R
⊆
X
2
{\displaystyle R\subseteq X^{2}}
이다.
∀
x
∈
X
:
x
R
x
{\displaystyle \forall x\in X\colon xRx}
대칭관계 는 다음 조건을 만족시키는 이항관계
R
⊆
X
2
{\displaystyle R\subseteq X^{2}}
이다.
∀
x
,
y
∈
X
:
x
R
y
⟹
y
R
x
{\displaystyle \forall x,y\in X\colon xRy\implies yRx}
반대칭관계 는 다음 조건을 만족시키는 이항관계
R
⊆
X
2
{\displaystyle R\subseteq X^{2}}
이다.
∀
x
,
y
∈
X
:
x
R
y
∧
y
R
x
⟹
x
=
y
{\displaystyle \forall x,y\in X\colon xRy\land yRx\implies x=y}
추이관계 는 다음 조건을 만족시키는 이항관계
R
⊆
X
2
{\displaystyle R\subseteq X^{2}}
이다.
∀
x
,
y
,
z
∈
X
:
x
R
y
∧
y
R
z
⟹
x
R
z
{\displaystyle \forall x,y,z\in X\colon xRy\land yRz\implies xRz}
완전관계 는 다음 조건을 만족시키는 이항관계
R
⊆
X
2
{\displaystyle R\subseteq X^{2}}
이다.
∀
x
,
y
∈
X
:
x
R
y
∨
y
R
x
{\displaystyle \forall x,y\in X\colon xRy\lor yRx}