[이산수학] 이항 관계 (binary relation)

이항 관계

이항 관계 (Binary Relation): 순서쌍들로 이루어지는 집합. 집합 $R$의 원소가 모두 순서쌍이라면, $R$을 이항 관계라고 함. $(x, y) \in R$을 $_xR_y$로 표기

이항 관계는 $n$항 관계(n-ary)의 $n = 2$인 경우를 말합니다(2-ary).

 

관계 $R$의 원소에서 첫 번째 집합을 정의역(domain)이라 하고, $Dom(R)$로 표시합니다.

$$ Dom(R) = \{a \space | \space (a, b) \in R \} \subseteq A $$

 

관계 $R$의 원소에서 두 번째 집합을 치역(range)이라 하고, $Ran(R)$로 표시합니다.

$$ Ran(R) = \{b \space | \space (a, b) \in R \} \subseteq B $$

 

이항 관계에서의 곱집합

$A$와 $B$가 집합이라고 가정하자. $A$에서 $B$인 관계 $R$은 $A \times B$의 모든 순서쌍의 집합을 A와 B의 곱집합(cartesian product)라 한다.

$$ A \times B = \{(x, y) \space | \space x \in A, y \in B\} $$

 

역관계

역관계 (inverse relation): 집합 $A$에서 $B$로의 관계 $R$에 대한 역관계 $R^{-1}$은 집합 $B$에서 $A$로의 관계를 나타냄

$$ R^{-1} = \{(b, a) \space | \space (a, b) \in R \} $$