10. 관계의 폐포, 동치관계(Closure of Relation & Equivalence Relation)

 

10. 1. 관계의 폐포(Closure of Relation)

 

- 폐포(Closure): 원래의 관계에 순서쌍을 새로 추가하여 특정 성질을 만족하도록 만든 Relation.

 

- 반사폐포(Reflexive Closure): Set A에 대한 Relation R을 포함하면서 Reflexive Relation을 만족하는 Relation S.

 

  S = R U {(a, a) ∈ A}.

 

- 대칭폐포(Symmetric Closure): Set A에 대한 Relation R을 포함하면서 Symmetric Relation을 만족하는 Relation S.

 

  S = R U R^-1.

 

- 추이폐포(Transitive Closure): Set A에 대한 Relation R을 포함하면서 Transitive Relation을 만족하는 Relation S.

 

---

 

10. 2 동치관계(Equivalence Relation)

- 동치관계(Equivalence Relation): Reflexive Relation, Symmetric Relation, Transitive Relation 이 모두 성립하는 Relation.

 

- 동치류(Equivalence Class, [a]): Set A에 대한 Relation R이 Equivalence Relation일 때, Domain의 원소가 Codomain의 원소들과 순서쌍을 이루는 것들끼리 모아 표현한 집합.

 

  ex) R = {(1,1), (1, 3), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2), (4, 4)}.

 

      [1] = [3] = {1, 3}, [2] = [4] = {2, 4}.

 

- 동치류 집합(위를 기준으로 {{1, 3}, {2, 4}})은 분할(Partition)의 특징을 가지고 있다.

 

- 부분순서관계(Partial Order Relation): Reflexive Relation, Asymmetric Relation, Transitive Relation 이 모두 성립하는 Relation.

 

- Set A에 대한 Relation R이 Partial Order Relation을 만족할 때, (a, b) ∈ R 이면 a ≼ b로 표기하고 a와 b는 비교가능(Comparable)하다고 말한다.

 

 a ≼ b는 a가 b보다 앞에 우선한다는 것을 의미한다.

 

- 완전순서관계(Total Order Relation): Set A에 대한 Relation R이 Partial Order Relation이고, Set A의 모든 원소들을 Relation R에서 비교할 수 있을 때의 Relation을 말한다. 이때 Set A를 Total Order Set이라 말한다.

 

- 하세도표(Hasse Diagram): Partial Order Relation을 만족하는 집합의 원소들을 Graph를 그려서 표현하는 방법.

 

  1) Directed Graph에서 Loop와 화살표는 생략한다.

 

  2) a ≼ b이면 a를 b보다 아래쪽에 그린다.

 

  3) a ≼ c ≼ b 이고, c ≠ a , c ≠ b 인 c가 Set A에 존재하면 a에서 b로 가는 선은 생략해도 된다.

 

Hasse Diagram

 

 

- 극대원소(Maximal Element): Partial Order Relation A의 원소 a에 대해 a ≼ b인 원소 b가 A에 존재하지 않을 때 원소 a.

 

- 극소원소(Minimal Element): Partial Order Relation A의 원소 a에 대해 b ≼ a인 원소 b가 A에 존재하지 않을 때 원소 a.

 

- 극대원소들 간의 우선순위는 같다. 또한 극소원소들 간의 우선순위는 같다.

 

- 최대원소(Greatest Element): Maximal Element가 하나만 있을 때 그 원소.

 

- 최소원소(Least Element): Minimal Element가 하나만 있을 때 그 원소.

 

 

---