동치관계

동치관계(equivalent relation)는 대칭률, 반사율, 추이율을 만족하는 관계이며, ~로 나타낸다.

정의

집합 S 위의 동치관계 ~는 다음과 같은 조건을 만족하는 관계이다:

반사율(Reflexivity): S의 원소 x에 대하여 x~x

대칭률(Symmetry): S의 원소 x, y에 대하여 x~y ⇔ y~x

추이율(Transitivity): S의 원소 x, y, z에 대하여 x~y, y~z ⇒ x~z

동치류

[math]\displaystyle{ x }[/math]의 동치류(equivalent class) [math]\displaystyle{ [x] }[/math]는 [math]\displaystyle{ x }[/math]와 동치관계에 있는 원소들의 집합이다. 이의 모음(collection) [math]\displaystyle{ S/\sim = \{ [x] | x \in S \} }[/math]을 몫집합(quotient set)이라고 한다. 어떤 원소를 동치류에 대응시키는 사상 [math]\displaystyle{ \pi : S \rightarrow S/\sim , x \mapsto [x] }[/math] 을 사영(projection)이라고 한다.

간단한 예시

추상적인 위 정의를 구체적인 예시를 통해 살펴보자. 예를 들어 '같은 반' 이라는 관계를 생각해보자. 즉, x라는 학생과 y라는 학생이 있어 x~y는 "x는 y와 같은 반에 속해있다." 를 의미한다고 하자. 그렇다면 이 관계는 동치관계인가?

반사율

임의의 학생 x는 당연히 자기 자신 x와 같은 반에 속해 있다. 그러므로 반사율이 성립한다.

대칭률

임의의 학생 x, y에 대해, x가 y와 같은 반에 속해 있다면, y가 x와 같은 반에 속해 있음은 자명하다. 그러므로 대칭률도 성립한다.

추이율

학생 x, y, z가 있어서 x가 y와 같은 반에 속해있고, y가 z와 같은 반에 속해있다면, x는 z와 같은 반에 속해있다. 따라서 추이율도 성립한다.

따라서 우리가 상정한 '같은 반' 관계는 동치관계라 부를 수 있다. 또한 이 예시에서 알 수 있듯이, 동치관계는 '반'과 같은 분할 (partition)과 밀접한 연관을 가지고 있다. 동치류는 바로 이 사실과 관련되는 개념이다.