동치관계

수학에서 동치관계(同値關係, 영어: equivalence relation)는 논리적 동치와 비슷한 성질들을 만족시키는 이항관계이다.

정의

집합 $X$ 위의 동치관계 $\sim$는 반사관계이자 대칭관계이자 추이관계인 이항관계이다. 즉, 다음 조건들이 성립하여야 한다.

• (반사관계) 임의의 $x\in X$에 대하여, $x\sim x$
• (대칭관계) 임의의 $x,y\in X$에 대하여, 만약 $x\sim y$라면, $y\sim x$
• (추이관계) 임의의 $x,y,z\in X$에 대하여, 만약 $x\sim y$이고 $y\sim z$라면 $x\sim z$

동치류와 상집합

집합 $X$ 위에 동치관계 $\sim$이 주어졌을 때, 원소 $x\in X$의, 동치관계 $\sim$에 대한 동치류(同値類, 영어: equivalence class) $[x]$는 그 원소와 동치인 원소들의 집합이다 즉,

$[x]=\{y\in X\colon x\sim y\}$

집합 $X$의 $\sim$에 대한 상집합(-集合, 영어: quotient set) $X/{\sim }$은 $\sim$에 대한 동치류들의 집합이다. 즉,

$X/{\sim }=\{[x]\colon x\in X\}$

예

• 임의의 집합 위의 등호 관계
• 도형 집합 위의 닮음 관계
• 사람들의 집합 위의, 같은 생일을 갖는 관계

반례

• 공집합이 아닌 집합 $X\neq \varnothing$ 위의 공관계는 (유일한 유형의) 반사관계가 아닌 대칭관계이자 추이관계이다.
• 실수 집합 위의 순서 관계 $x\leq y$는 대칭관계가 아닌 반사관계이자 추이관계이다.
• 실수 집합 위의 이항관계 $|x-y|<1$은 추이관계가 아닌 반사관계이자 대칭관계이다.

성질

표준 사상

집합 위의 동치관계로부터, 표준사상을 구성할 수 있다. 즉, 집합 $X$ 위의 동치관계 $\sim$에 대하여, 함수

$f\colon X\to X/{\sim }$

$f\colon x\mapsto [x]$

를 표준사상이라고 한다.

반대로, 전사함수 $f\colon X\to Y$에 대하여, 이항관계

$x_{1}\sim _{f}x_{2}\iff f(x_{1})=f(x_{2})\qquad (x_{1},x_{2}\in X)$

는 동치관계이며, 그 상집합은

$X/{\sim }_{f}=\{f^{-1}(y)\colon y\in Y\}$

이다.

집합의 분할

집합 위의 동치관계와 그 집합의 분할 사이에는 자연적인 일대일 대응이 존재한다. 즉, 다음과 같다.

집합 $X$ 위의 동치관계 $\sim$에 대하여, 그 상집합 $X/{\sim }$은 $X$의 분할이다. 즉,

• 임의의 $x,y\in X$에 대하여, 만약 $x\sim y$이면, $[x]=[y]$이다.
• 임의의 $x,y\in X$에 대하여, 만약 $x\not \sim y$이면, $[x]\cap [y]=\varnothing$이다.

반대로, 집합 $X$의 분할 $P$에 대하여, 이항관계

$x\sim _{P}y\iff \exists A\in P\colon x,y\in A\qquad (x,y\in X)$

는 동치관계이다.

같이 보기

• 집합의 분할

외부 링크

• “Equivalence relation”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Equivalence relation”. 《Wolfram MathWorld》 (영어). Wolfram Research.