[이산수학] 합성 관계 (composite relation)

반사, 대칭, 반대칭, 추이

관계 $R$이 집합 $A$에 있다고 하자.
반사 관계(reflexive relation): 집합 $A$에 있는 모든 원소 $x$에 대해 $_xR_x$일 때
대칭 관계(symmetric relation): 집합 $A$에 있는 모든 원소 $x, y$에 대해 $_xR_y$이고 $_yR_x$일 때
반대칭 관계(anti-symmetric relation): 집합 $A$에 있는 모든 원소 $x, y$에 대해 $_xR_y$이고 $_yR_x$일 때 $x = y$를 만족하는 경우
추이 관계(transitive relation): 집합 $A$에 있는 모든 원소 $x, y, z$에 대해 $_xR_y$이고 $_yR_z$이면 $_xR_z$일 때

 

추이 클로저

관계 $R$이 집합 $A$에 있다고 하자. 관계 $R$의 추이 클로저 $R^+$는 다음 3가지의 특징을 가진다.
(1) 만약 $(a, b) \in R$이면 $(a, b) \in R^+$이다.
(2) 만약 $(a, b) \in R^+$이고 $(b, c) \in R$이면 $(a, c) \in R^+$이다.
(3) 위의 (1), (2)의 경우를 제외하고는 어떤 것도 $R^+$에 속하지 않는다.