여기서는 이항관계만을 다루므로 아래에서 이항관계 대신 짧게 "관계"(relation)라고 줄여 쓰기도 하겠다.
$R$이 집합 $V$에 대한 이항관계임을 수학에서 쓰는 표기로는 다음과 같이 나타낼 수 있다.
$(x,y)\in R$라는 집합 원소 표기 대신 $x\,R\,y$라로 중위(infix) 표기법을 자주 쓴다.
이항관계를 진리값(False 또는 True)을 돌려주는 함수 즉 $V\times V \to 2$ 또는 $V\times V \to \textsf{Bool}$ 타입의 함수로 생각할 수도 있다.
이항관계를 정의하는 집합에 들어 있는 원소에 대해서는 True를 돌려주고 들어있지 않은 함수에 대해서는 False를 돌려주는 함수를 생각해 보라.
이항관계의 합성은 함수의 합성과 비슷하다. 두 이항관계 $R_1$과 $R_2$의 합성은 함수 합성과 마찬가지 기호를 써서 $R_1 \circ R_2$와 같이 표현하며 그 정의는 다음과 같다.
$$ R_1 \circ R_2 = \{(x,z) \mid (x,y) \in R_1, (y,z) \in R_2\} $$
또는 중위 표기법을 써서 나타낸다면
$$ R_1 \circ R_2 = \{(x,z) \mid x\mathop{R_1}y,~ y\mathop{R_2}z\} $$
이렇게 기존의 두 이항관계를 합성해 만든 이항관계를 합성관계(compsite relation)라고 부르기도 한다.
예를 들어 $R_1 = \{(a,b),(c,d)\}$ 이고 $R_2 = \{(b,c),(d,b)\}$ 이면 $R_1 \circ R_2 = \{(a,c),(c,b)\}$가 된다.
합성관계 중에서도 특히 같은 관계끼리 합성한 $R \circ R$을 $R^2$와 같이 표기한다. 예컨대 $R=\{(a,b),(b,c)\}$이면 $R \circ R=\{(a,c)\}$가 된다.
일반적으로 같은 관계를 여러 번 반복해 합성한 관계들을 다음과 같이 표기한다. $$ \begin{array}{l} R^1 = R \\ R^2 = R \circ R \\ R^3 = R \circ R \circ R \\ R^4 = R \circ R \circ R \circ R \\ R^5 = R \circ R \circ R \circ R \circ R \\ \vdots \\ ~ \end{array} $$ 위를 수학적귀납법스럽게 혹은 점화식처럼 공식으로 정리하면 다음과 같다. $$ \begin{array}{l} R^1 = R \\ R^{n} = R \circ R^{n-1} \qquad (n>1) \end{array} $$
$R^0$라는 표기법을 쓰기도 한다. $R^0$는 실제로는 $R$에 관계없이 $V$만으로 정의되는 집합이다. $$ R^0 = \{ (x,x) \mid x\in V \} $$
$R^{-1}$이라는 표기법도 쓰는데 이는 $R$의 역관계이다. $$ R^{-1} = \{ (y,x) | (x,y)\in R \} $$
참고로 유한집합 $V$에 대해 정의된 이항관계는 방향그래프에 해당한다. 방향그래프에서 점으로 나타나는 vertex의 집합이 $V$에 해당하며 화살표로 나타나는 edge의 집합이 $R$에 해당한다. 즉 $xRy$ 는 $x$ 에서 $y$ 로 가는 화살표가 있다는 뜻. 이런 관계를 보고 방향그래프를 그림으로 그릴 수 있고 방향그래프 그림을 보고 집합으로 옮겨 쓸 수도 있다. 방향그래프와 연관지어 생각하면 $R^k$를 직관적으로 이해할 수 있다. $R^k$는 화살표를 따라 $k$ 걸음만큼 갈 수 있는 모든 시작점과 도착점의 관계인 것이다.
위 세 성질을 한꺼번에 만족하면 equlvalence (동치) 관계이다. 즉 $R$이 동치관계라는 뜻은, $R$이 반사관계이면서 전이관계이면서 대칭관계이기도 하다는 말이다.
어떤 관계로부터 관심있는 무슨무슨 성질을 만족하도록 최소한으로 확장된 관계를 $R$의 무슨무슨 closure라고 한다.
$R$의 무슨무슨 closure를 $R'$이라고 이름붙이자. 이 때 $R'$의 정의는 다음과 같다.
예컨대, $$V = \{a,b,c,d\}$$ $$R=\{(a,b),(b,c)\}$$ 이라고 하고 $R$ 의 여러가지 closure 들을 생각해 보자.
$R=\{(a,b),(b,c)\}$의 reflexive closure는 다음과 같다. $$\{(a,b),(b,c),(a,a),(b,b),(c,c),(d,d)\}$$ 여기에다 $(c,d)$를 하나 더 원소로 추가한 또다른 관계를 생각해 보자. $$\{(a,b),(b,c),(a,a),(b,b),(c,c),(d,d),(c,d)\}$$ 이 관계도 $R$을 포함하는 reflexive relation이기는 하나 $R$의 reflexive closure는 될 수 없다. 왜냐하면 $R$을 포함하면서도 refexive인 그보다 더 작은 집합이 따로 있기 때문이다.
일반적으로 reflexive closure를 계산하는 방법은 원래의 관계에 $R^0$를 추가한 합집합을 구하면 된다. 즉, $R$의 reflexive closure는 $R\cup R^0$이다.
$R=\{(a,b),(b,c)\}$의 symmetric closure는 다음과 같다. $$\{(a,b),(b,c),(b,a),(c,b)\}$$ 여기에다 $(a,a)$를 하나 더 원소로 추가한 또다른 관계를 생각해 보자. $$\{(a,b),(b,c),(b,a),(c,b),(a,a)\}$$ 이 관계도 $R$ 을 포함하는 symmetric relation이기는 하나 $R$의 symmetric closure는 될 수 없다. 왜냐하면 $R$ 을 포함하면서도 symmetric인 그보다 더 작은 집합이 따로 있기 때문이다.
일반적으로 symmetric closure를 계산하는 방법은 원래의 관계에 $R^{-1}$를 추가한 합집합을 구하면 된다. 즉, $R$의 reflexive closure는 $R\cup R^{-1}$이다.
$R=\{(a,b),(b,c)\}$의 transitive closure는 다음과 같다. $$\{(a,b),(b,c),(a,c)\}$$ 여기에다 $(a,a)$를 하나 더 원소로 추가한 또다른 관계를 생각해 보자. $$\{(a,b),(b,c),(a,c),(a,a)\}$$ 이 관계도 $R$ 을 포함하는 transtive relation이기는 하나 $R$의 transitive closure는 될 수 없다. 왜냐하면 $R$ 을 포함하면서도 transitive인 그보다 더 작은 집합이 따로 있기 때문이다.
일반적으로 transitive closure를 구하는 방법은 다음과 같이 정의되는 $R^+$를 계산하면 된다. $$R^+ = R^1\cup R^2\cup R^3 \cdots = \bigcup_{k \in \mathbb{Z}^{+}}R^k$$ $V$가 유한집합인 경우에는 계산할 수 있다. 계산방법에 대해서는 Haskell 프로그램으로 작성한 예시가 뒷부분에 나온다.
reflexive와 transitive 두 성질을 동시에 만족하는 closure이다. $R$ 의 reflexive transitive closure는 일단 transitive closure를 구한 뒤 그것의 reflexive closure를 구해주면 된다. 즉, $R^0 \cup R^+$를 구하면 되는데 이것을 $R^{*}$ 라고 표기하기도 한다. 즉, $$R^* = R^0 \cup R^1 \cup R^2 \cup R^3 \cdots = \bigcup_{k\in\mathbb{N}}R^k = R^0 \cup R^+$$
이것 말고도 다른 두 성질의 조합에 대한 closure를 생각할 수 있다. 예를 들면 reflexive symmetric closure라던가 symmetric transtive closure라던가.
reflexive symmetric transitive closure에 해당한다. $R^*$를 구한 다음 그것의 symmetric closure를 구하면 된다. 즉, $R$ 의 equivalence closure는 $R^* \cup (R^*)^{-1}$ 이다.
아래에서는 유한한 $V$ 에 대한 이항관계 $R$ 의 transitive closure 즉 $R^+$ 를 구하는 예시를 보여준다. 계산하는 방법은 아래 $R^+$의 부분집합 공식에서 n을 1부터 하나씩 늘려가보면서 더 이상 집합의 크기가 늘어나지 않고 변화가 없을 때까지 반복하면 된다. $$\bigcup_{k=1..n} R^n$$
v = ['a','b','c','d']
reflexive r = and [elem (x,x) r | x<-v]
symmetric r = and [elem (y,x) r | (x,y)<-r]
transitive r = and [elem (x,z) r | (x,y1)<-r, (y2,z)<-r, y1==y2]
equivalence r = and [reflexive r, transitive r, symmetric r]
r1 = [('a','b'),('b','c'),('c','d')]
r2 = [('a','b'),('b','c'),('c','d'),('d','b')]
[x | x <- v]
[(x,x) | x <- v]
-- (.@.)은 관계 합성 연산자를 정의한 것이다
r1 .@. r2 = [(x,z) | (x,y1)<-r1, (y2,z)<-r2, y1==y2]
-- r .^ k 는 $R^k$에 해당
r .^ 1 = r
r .^ n = r .@. (r .^ (n-1))
rel1 = r1 .^ 1
rel2 = r1 .^ 2
rel3 = r1 .^ 3
rel4 = r1 .^ 4
rel5 = r1 .^ 5
import Data.List
rel1
rel1 `union` rel2
rel1 `union` rel2 `union` rel3
rel1 `union` rel2 `union` rel3 `union` rel4
rel1 `union` rel2 `union` rel3 `union` rel4 `union` rel5
rr1 = r2 .^ 1
rr2 = r2 .^ 2
rr3 = r2 .^ 3
rr4 = r2 .^ 4
rr5 = r2 .^ 5
rr1
rr1 `union` rr2
rr1 `union` rr2 `union` rr3
rr1 `union` rr2 `union` rr3 `union` rr4
rr1 `union` rr2 `union` rr3 `union` rr4 `union` rr5