동치 관계 문서 원본 보기

{{위키데이터 속성 추적}}
[[수학]]에서 '''동치 관계'''(同値關係, {{llang|en|equivalence relation}})는 [[동치|논리적 동치]]와 유사한 성질들을 만족시키는 [[이항 관계]]이다.

== 정의 ==
=== 동치 관계 ===
집합 <math>X</math> 위의 '''동치 관계'''는 다음 세 조건을 만족시키는, <math>X</math> 위의 [[이항 관계]] <math>{\sim}\subseteq X^2</math>이다.
* ([[반사 관계]]) 임의의 <math>x\in X</math>에 대하여, <math>x\sim x</math>
* ([[대칭 관계]]) 임의의 <math>x,y\in X</math>에 대하여, 만약 <math>x\sim y</math>라면, <math>y\sim x</math>
* ([[추이적 관계]]) 임의의 <math>x,y,z\in X</math>에 대하여, 만약 <math>x\sim y</math>이고 <math>y\sim z</math>라면 <math>x\sim z</math>

=== 동치류와 몫집합 ===
집합 <math>X</math> 위에 동치 관계 <math>\sim</math>이 주어졌을 때, 원소 <math>x\in X</math>의, <math>\sim</math>에 대한 '''동치류'''(同値類, {{llang|en|equivalence class}}) <math>[x]_\sim</math>는 <math>x</math>와 동치인 원소들을 모은 집합이다.
:<math>[x]_\sim=\{y\in X\colon x\sim y\}</math>

집합 <math>X</math> 위에 동치 관계 <math>\sim</math>이 주어졌을 때, <math>X</math>의 <math>\sim</math>에 대한 '''몫집합'''(-集合, {{llang|en|quotient set}}) <math>X/{\sim}</math>은 모든 동치류들을 모은 집합이다.
:<math>X/{\sim}=\{[x]_\sim\colon x\in X\}</math>

=== 모임의 경우 ===
[[선택 공리]]를 추가한 [[체르멜로-프렝켈 집합론]](ZFC)에서, [[모임 (집합론)|모임]]은 하나의 자유 변수를 가지는 논리식으로 여길 수 있다. 어떤 집합이 이 논리식을 만족시킬 때, 집합은 이 논리식에 대응하는 모임의 원소가 된다. 자유 변수에 논리식을 대입하는 것은 합법적이지 않으므로, [[고유 모임]]은 모임의 원소가 될 수 없다.

[[모임 (집합론)|모임]] 위에서도 동치 관계·동치류·몫집합의 개념을 정의할 수 있다. 동치 관계의 정의는 집합 위에서의 정의를 옮겨 오면 충분하다. 다만, 모임 <math>X</math> 위의 동치 관계는 곱모임 <math>X^2</math>의 부분 모임으로서, 더 이상 집합이 아닐 수 있다. 모임의 원소의 동치류를 이 원소와 동치인 원소들의 모임으로 정의할 경우, 동치류들을 개별적으로 다루는 데에는 문제가 없으나, 동치류들이 [[고유 모임]]일 수 있으므로 동치류들의 모임을 합법적으로 정의할 수 없다. 즉, <math>X/{\sim}</math>을 정의하려면 동치류가 집합이 되도록 동치류의 정의에 수정을 가하여야 한다.

모임 <math>X</math> 위에 동치 관계 <math>{\sim}\subseteq X^2</math>가 주어졌다고 하자. 원소 <math>x\in X</math>에 대하여, 다음과 같이 정의한다.<ref name="Jech">{{서적 인용|성1=Jech|이름1=Thomas|제목=Set theory|url=https://archive.org/details/settheory0000jech_f7i4|언어=en|판=3|총서=Springer Monographs in Mathematics|출판사=Springer|위치=Berlin|날짜=2003|isbn=978-3-540-44085-7|issn=1439-7382|doi=10.1007/3-540-44761-X|mr=1940513|zbl=1007.03002|id={{iaid|settheory0000jech_f7i4}}}}</ref>{{rp|65}}
:<math>[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)\}</math>
즉, <math>[x]'_\sim</math>는 <math>x</math>와 동치인 원소 가운데, ([[폰 노이만 전체]]에서의) [[누적 위계|계수]]가 가장 낮은 것들의 모임이다. (이러한 최소 계수의 원소가 존재하는 것은 [[순서수]]의 모임이 [[정렬 전순서 집합|정렬 전순서 모임]]이기 때문이다.) 이러한 최소의 계수를 <math>\alpha</math>라고 할 때, <math>[x]'_\sim</math>는 집합 <math>V_{\alpha+1}</math>의 부분 모임이므로, 집합이다. 따라서, 모임
:<math>(X/{\sim})'=\{[x]'\colon x\in X\}</math>
을 정의할 수 있다.<ref name="Jech"/>{{rp|65}}

== 성질 ==
집합 <math>X</math> 위에 동치 관계 <math>\sim</math>이 주어졌을 때, 다음과 같은 표준적인 [[전사 함수]]가 존재한다.
:<math>X\to X/{\sim}</math>
:<math>x\mapsto[x]</math>
즉, 이 함수는 모든 원소를 이 원소가 속하는 동치류로 대응시킨다.

=== 집합의 분할과의 관계 ===
집합 <math>X</math>가 주어졌을 때, <math>X</math> 위의 동치 관계들과 <math>X</math>의 [[집합의 분할|분할]]들 사이에 표준적인 [[일대일 대응]]이 존재하며, 이는 다음과 같다. 집합 <math>X</math> 위에 동치 관계 <math>\sim</math>이 주어졌을 때, 몫집합 <math>X/{\sim}</math>은 [[집합의 분할]]이다. 즉, <math>X</math>의 임의의 원소는 정확히 하나의 동치류에 속한다. 반대로, 집합 <math>X</math>의 [[집합의 분할|분할]] <math>\mathcal P</math>가 주어졌다고 하자 (즉, <math>\mathcal P</math>는 <math>X</math>의 부분 집합들의 집합이며, <math>X</math>의 임의의 원소는 정확히 하나의 <math>\mathcal P</math>의 원소에 속한다). <math>X</math> 위에 다음과 같은 [[이항 관계]] <math>\sim_{\mathcal P}</math>를 정의하자.
:<math>x\sim_{\mathcal P}y\iff\exists A\in P\colon x,y\in A\qquad(x,y\in X)</math>
그렇다면 <math>\sim_{\mathcal P}</math>는 <math>X</math> 위의 동치 관계이다. <math>{\sim}\mapsto X/{\sim}</math>과 <math>\mathcal P\mapsto{\sim}_{\mathcal P}</math>는 서로 역함수이다. 즉,
:<math>{\sim}_{X/{\sim}}={\sim}</math>
:<math>X/{\sim}_{\mathcal P}=\mathcal P</math>
이다. 따라서, 동치 관계와 [[집합의 분할]]의 개념은 [[동치]]이다.

=== 순서론적 성질 ===
집합 <math>X</math>가 주어졌다고 하자. 임의의 [[이항 관계]] <math>R\subseteq X^2</math>에 대하여, <math>R</math>를 포함하는 최소의 동치 관계 <math>\sim_R</math>가 존재한다. 구체적으로, 다음 두 조건이 서로 [[동치]]이다.
* <math>x\sim_Ry</math>
* 다음 조건을 만족시키는 열 <math>x_0,x_1,\dots,x_n\in X</math>가 존재한다.
** <math>x_0=x</math>
** <math>x_n=y</math>
** <math>i=1,\dots,n</math>에 대하여, <math>(x_{i-1},x_i)\in R</math>이거나 <math>(x_i,x_{i-1})\in R</math>

집합 <math>X</math> 위의 동치 관계들의 (포함 관계에 의한) [[부분 순서 집합]] <math>\operatorname{Eq}(X)</math>는 [[완비 격자]]이다. <math>\operatorname{Eq}(X)</math>의 [[최소 원소]]는 (<math>X</math>로 국한된) 등호 <math>=</math>이며, [[최대 원소]]는 전체 관계 <math>X^2\subseteq X^2</math>이다. 동치 관계들의 집합 <math>\{\sim_i\}_{i\in I}</math>의 만남 <math>\bigwedge_{i\in I}{\sim}_i</math>는 교집합
:<math>(x,y)\in\bigwedge_{i\in I}{\sim}_i\iff\forall i\in I\colon x\sim_iy</math>
이다. <math>\{\sim_i\}_{i\in I}</math>의 이음 <math>\bigvee_{i\in I}\sim_i</math>은 합집합 <math>\bigcup_{i\in I}{\sim}_i</math>을 포함하는 최소의 동치 관계
:<math>(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</math>
이다.

동치 관계 격자 <math>\operatorname{Eq}(X)</math>는 항상 [[대수적 격자]]({{llang|en|algebraic lattice}})이자 [[반모듈러 격자]]({{llang|en|semimodular lattice}})이다. [[유한 집합]] <math>X</math>의 경우, <math>\operatorname{Eq}(X)</math>는 [[단순 격자]]({{llang|en|simple lattice}}, [[합동 관계]]가 자명한 격자)이다.

== 예 ==
임의의 집합 <math>X</math> 위에서, [[등식|등호]] <math>=</math>는 동치 관계를 이룬다.

평면 (또는 입체) 도형들의 집합 위에서, [[닮음 (기하학)|닮음]] 관계는 동치 관계이다.

임의의 [[함수]] <math>f\colon X\to Y</math>에 대하여, 같은 함숫값을 갖는 관계
:<math>x\sim_fy\iff f(x)=f(y)</math>
는 정의역 <math>X</math> 위의 동치 관계이다. 이를테면, <math>X</math>가 어떤 사람들의 집합이며, <math>f</math>가 사람의 생일을 찾는 함수라면, <math>\sim_f</math>는 같은 생일의 사람들을 한데 묶는 동치 관계로 생각할 수 있다.

== 반례 ==
=== 반사 관계가 아닌 대칭 추이적 관계 ===
임의의 집합 <math>X</math> 위에서, 공관계
:<math>\varnothing\subseteq X^2</math>
는 항상 [[대칭 관계]]이자 [[추이적 관계]]이다. 그러나, 만약 <math>X\ne\varnothing</math>이라면 이는 [[반사 관계]]가 아니다. 반사 관계가 아닌 대칭 추이적 관계는 이러한 형태밖에 없다.

=== 대칭 관계가 아닌 반사 추이적 관계 ===
[[정수]]의 집합 <math>\mathbb Z</math> 위의 표준적인 순서
:<math>x\le y\iff\exists z\in\mathbb Z_{\ge0}\colon y=x+z</math>
를 생각하자. 이는 [[전순서]]이며, 특히 [[반사 관계]]이자 [[추이적 관계]]이지만, [[대칭 관계]]가 아니다. 예를 들어, <math>0\le1</math>이지만, <math>1\not\le0</math>이다.

=== 추이적 관계가 아닌 반사 대칭 관계 ===
[[정수]] 집합 <math>\mathbb Z</math> 위의 이항 관계
:<math>(x,y)\in R\iff y=x+1\lor y=x-1</math>
는 [[반사 관계]]이자 [[대칭 관계]]이지만, [[추이적 관계]]가 아니다.

== 같이 보기 ==
* [[집합의 분할]]

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{수학노트|제목=동치관계}}
* {{eom|title=Equivalence relation}}
* {{매스월드|id=EquivalenceRelation|title=Equivalence relation}}
* {{nlab|id=equivalence relation|제목=Equivalence relation}}
* {{플래닛매스|urlname=EquivalenceRelation|제목=Equivalence relation}}
* {{proofwiki|id=Definition:Equivalence Relation|제목=Definition: equivalence relation}}

{{전거 통제}}

[[분류:관계 (수학)]]