[이산수학] 동치 관계(equivalence relation)와 분할

동치관계와 분할

동치 관계(equiavlence relation): 관계 $R$에서 반사 관계, 대칭 관계, 추이 관계가 모두 성립할 때

 

동치류, 동치 클래스(equivalence classes): 집합 $A$에 대한 동치 관계를 $R$이라고 할 때, $A$의 각 원소 $a$에 대하여 $[a]$를 $R$에 대한 $a$의 동치류라 함

$$ [x] = \{y \space | \space (x, y) \in R\} $$

 

분할(partition): 집합 $A$의 분할에 의해 유도된 관계 $R$은 다음 조건을 만족시킴. (1) $A_i ≠ \phi, 1 ≤ i ≤ n$ (2) $A = \underset{i = 1}{\overset{n}\bigcup}A^i$ (3) $A_i \cap A_j = \phi, i ≠ j$

 

mod 합동(congruence): $x$와 $y$를 $m$으로 각각 나누었을 때 나머지가 같은 경우를 말함. $x \equiv y (mod m)$으로 표기함.