동치 관계

수학에서 **동치 관계**(同値關係, equivalence relation)는 논리적 동치와 유사한 성질들을 만족시키는 이항 관계이다.
# 정의

## 동치 관계
집합 X 위의 **동치 관계**는 다음 세 조건을 만족시키는, X 위의 이항 관계 {\sim}\subseteq X^2이다. * (반사 관계) 임의의 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]_\sim는 x와 동치인 원소들을 모은 집합이다. :[x]_\sim=\\{y\in X\colon x\sim y\\} 집합 X 위에 동치 관계 \sim이 주어졌을 때, X의 \sim에 대한 **몫집합**(-集合, quotient set) X/{\sim}은 모든 동치류들을 모은 집합이다. :X/{\sim}=\\{[x]_\sim\colon x\in X\\}
## 모임의 경우
선택 공리를 추가한 체르멜로-프렝켈 집합론(ZFC)에서, 모임은 하나의 자유 변수를 가지는 논리식으로 여길 수 있다. 어떤 집합이 이 논리식을 만족시킬 때, 집합은 이 논리식에 대응하는 모임의 원소가 된다. 자유 변수에 논리식을 대입하는 것은 합법적이지 않으므로, 고유 모임은 모임의 원소가 될 수 없다. 모임 위에서도 동치 관계·동치류·몫집합의 개념을 정의할 수 있다. 동치 관계의 정의는 집합 위에서의 정의를 옮겨 오면 충분하다. 다만, 모임 X 위의 동치 관계는 곱모임 X^2의 부분 모임으로서, 더 이상 집합이 아닐 수 있다. 모임의 원소의 동치류를 이 원소와 동치인 원소들의 모임으로 정의할 경우, 동치류들을 개별적으로 다루는 데에는 문제가 없으나, 동치류들이 고유 모임일 수 있으므로 동치류들의 모임을 합법적으로 정의할 수 없다. 즉, X/{\sim}을 정의하려면 동치류가 집합이 되도록 동치류의 정의에 수정을 가하여야 한다. 모임 X 위에 동치 관계 {\sim}\subseteq X^2가 주어졌다고 하자. 원소 x\in X에 대하여, 다음과 같이 정의한다.settheory0000jech_f7i465 :[x]'_\sim=\\{y\in X\colon x\sim y\land(\forall z\in X\colon x\sim z\implies\operatorname{rank}y\le\operatorname{rank}z)\\} 즉, [x]'_\sim는 x와 동치인 원소 가운데, (폰 노이만 전체에서의) 계수가 가장 낮은 것들의 모임이다. (이러한 최소 계수의 원소가 존재하는 것은 순서수의 모임이 정렬 전순서 모임이기 때문이다.) 이러한 최소의 계수를 \alpha라고 할 때, [x]'_\sim는 집합 V_{\alpha+1}의 부분 모임이므로, 집합이다. 따라서, 모임 :(X/{\sim})'=\\{[x]'\colon x\in X\\} 을 정의할 수 있다.65
# 성질
집합 X 위에 동치 관계 \sim이 주어졌을 때, 다음과 같은 표준적인 전사 함수가 존재한다. :X\to X/{\sim} :x\mapsto[x] 즉, 이 함수는 모든 원소를 이 원소가 속하는 동치류로 대응시킨다.
## 집합의 분할과의 관계
집합 X가 주어졌을 때, X 위의 동치 관계들과 X의 분할들 사이에 표준적인 일대일 대응이 존재하며, 이는 다음과 같다. 집합 X 위에 동치 관계 \sim이 주어졌을 때, 몫집합 X/{\sim}은 집합의 분할이다. 즉, X의 임의의 원소는 정확히 하나의 동치류에 속한다. 반대로, 집합 X의 분할 \mathcal P가 주어졌다고 하자 (즉, \mathcal P는 X의 부분 집합들의 집합이며, X의 임의의 원소는 정확히 하나의 \mathcal P의 원소에 속한다). X 위에 다음과 같은 이항 관계 \sim_{\mathcal P}를 정의하자. :x\sim_{\mathcal P}y\iff\exists A\in P\colon x,y\in A\qquad(x,y\in X) 그렇다면 \sim_{\mathcal P}는 X 위의 동치 관계이다. {\sim}\mapsto X/{\sim}과 \mathcal P\mapsto{\sim}_{\mathcal P}는 서로 역함수이다. 즉, :{\sim}_{X/{\sim={\sim} :X/{\sim}_{\mathcal P}=\mathcal P 이다. 따라서, 동치 관계와 집합의 분할의 개념은 동치이다.
## 순서론적 성질
집합 X가 주어졌다고 하자. 임의의 이항 관계 R\subseteq X^2에 대하여, R를 포함하는 최소의 동치 관계 \sim_R가 존재한다. 구체적으로, 다음 두 조건이 서로 동치이다. * x\sim_Ry * 다음 조건을 만족시키는 열 x_0,x_1,\dots,x_n\in X가 존재한다. ** x_0=x ** x_n=y ** i=1,\dots,n에 대하여, (x_{i-1},x_i)\in R이거나 (x_i,x_{i-1})\in R 집합 X 위의 동치 관계들의 (포함 관계에 의한) 부분 순서 집합 \operatorname{Eq}(X)는 완비 격자이다. \operatorname{Eq}(X)의 최소 원소는 (X로 국한된) 등호 =이며, 최대 원소는 전체 관계 X^2\subseteq X^2이다. 동치 관계들의 집합 \\{\sim_i\\}_{i\in I}의 만남 \bigwedge_{i\in I}{\sim}_i는 교집합 :(x,y)\in\bigwedge_{i\in I}{\sim}_i\iff\forall i\in I\colon x\sim_iy 이다. \\{\sim_i\\}_{i\in I}의 이음 \bigvee_{i\in I}\sim_i은 합집합 \bigcup_{i\in I}{\sim}_i을 포함하는 최소의 동치 관계 :(x,y)\in\bigvee_{i\in I}\sim_i\iff\exists n\in\mathbb N\exists x_0,\dots,x_n\in X\exists i_1,\dots,i_n\in I\colon x=x_0\sim_{i_1}x_1\sim_{i_2}\cdots\sim_{i_n}x_n=y 이다. 동치 관계 격자 \operatorname{Eq}(X)는 항상 대수적 격자(algebraic lattice)이자 반모듈러 격자(semimodular lattice)이다. 유한 집합 X의 경우, \operatorname{Eq}(X)는 단순 격자(simple lattice, 합동 관계가 자명한 격자)이다.
# 예
임의의 집합 X 위에서, 등호 =는 동치 관계를 이룬다. 평면 (또는 입체) 도형들의 집합 위에서, 닮음 관계는 동치 관계이다. 임의의 함수 f\colon X\to Y에 대하여, 같은 함숫값을 갖는 관계 :x\sim_fy\iff f(x)=f(y) 는 정의역 X 위의 동치 관계이다. 이를테면, X가 어떤 사람들의 집합이며, f가 사람의 생일을 찾는 함수라면, \sim_f는 같은 생일의 사람들을 한데 묶는 동치 관계로 생각할 수 있다.
# 반례

## 반사 관계가 아닌 대칭 추이적 관계
임의의 집합 X 위에서, 공관계 :\varnothing\subseteq X^2 는 항상 대칭 관계이자 추이적 관계이다. 그러나, 만약 X\ne\varnothing이라면 이는 반사 관계가 아니다. 반사 관계가 아닌 대칭 추이적 관계는 이러한 형태밖에 없다.
## 대칭 관계가 아닌 반사 추이적 관계
정수의 집합 \mathbb Z 위의 표준적인 순서 :x\le y\iff\exists z\in\mathbb Z_{\ge0}\colon y=x+z 를 생각하자. 이는 전순서이며, 특히 반사 관계이자 추이적 관계이지만, 대칭 관계가 아니다. 예를 들어, 0\le1이지만, 1\not\le0이다.
## 추이적 관계가 아닌 반사 대칭 관계
정수 집합 \mathbb Z 위의 이항 관계 :(x,y)\in R\iff y=x+1\lor y=x-1 는 반사 관계이자 대칭 관계이지만, 추이적 관계가 아니다.