동치 관계

수학에서 동치 관계(同値關係, 영어: 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 : x \sim y}

집합 $X$ 위에 동치 관계 $\sim$ 이 주어졌을 때, $X$ 의 $\sim$ 에 대한 몫집합(-集合, 영어: quotient set) $X / \sim$ 은 모든 동치류들을 모은 집합이다.

X / \sim = {[x]_{\sim} : x \in X}

모임의 경우

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

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

모임 $X$ 위에 동치 관계 $\sim \subseteq X^{2}$ 가 주어졌다고 하자. 원소 $x \in X$ 에 대하여, 다음과 같이 정의한다.^[1]^:65

[x]'_{\sim} = {y \in X : x \sim y \land (\forall z \in X : x \sim z ⟹ rank y \leq rank z)}

즉, $[x]'_{\sim}$ 는 $x$ 와 동치인 원소 가운데, (폰 노이만 전체에서의) 계수가 가장 낮은 것들의 모임이다. (이러한 최소 계수의 원소가 존재하는 것은 순서수의 모임이 정렬 전순서 모임이기 때문이다.) 이러한 최소의 계수를 $α$ 라고 할 때, $[x]'_{\sim}$ 는 집합 $V_{α + 1}$ 의 부분 모임이므로, 집합이다. 따라서, 모임

(X / \sim)^{'} = {[x]^{'} : x \in X}

을 정의할 수 있다.^[1]^:65

성질

집합 $X$ 위에 동치 관계 $\sim$ 이 주어졌을 때, 다음과 같은 표준적인 전사 함수가 존재한다.

X \to X / \sim

x \mapsto [x]

즉, 이 함수는 모든 원소를 이 원소가 속하는 동치류로 대응시킨다.

집합의 분할과의 관계

집합 $X$ 가 주어졌을 때, $X$ 위의 동치 관계들과 $X$ 의 분할들 사이에 표준적인 일대일 대응이 존재하며, 이는 다음과 같다. 집합 $X$ 위에 동치 관계 $\sim$ 이 주어졌을 때, 몫집합 $X / \sim$ 은 집합의 분할이다. 즉, $X$ 의 임의의 원소는 정확히 하나의 동치류에 속한다. 반대로, 집합 $X$ 의 분할 $𝒫$ 가 주어졌다고 하자 (즉, $𝒫$ 는 $X$ 의 부분 집합들의 집합이며, $X$ 의 임의의 원소는 정확히 하나의 $𝒫$ 의 원소에 속한다). $X$ 위에 다음과 같은 이항 관계 $\sim_{𝒫}$ 를 정의하자.

x \sim_{𝒫} y ⟺ \exists A \in P : x, y \in A (x, y \in X)

그렇다면 $\sim_{𝒫}$ 는 $X$ 위의 동치 관계이다. $\sim \mapsto X / \sim$ 과 $𝒫 \mapsto \sim_{𝒫}$ 는 서로 역함수이다. 즉,

\sim_{X / \sim} = \sim

X / \sim_{𝒫} = 𝒫

이다. 따라서, 동치 관계와 집합의 분할의 개념은 동치이다.

순서론적 성질

집합 $X$ 가 주어졌다고 하자. 임의의 이항 관계 $R \subseteq X^{2}$ 에 대하여, $R$ 를 포함하는 최소의 동치 관계 $\sim_{R}$ 가 존재한다. 구체적으로, 다음 두 조건이 서로 동치이다.

$x \sim_{R} y$
다음 조건을 만족시키는 열 x0,x1,…,xn∈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$ 위의 동치 관계들의 (포함 관계에 의한) 부분 순서 집합 $Eq (X)$ 는 완비 격자이다. $Eq (X)$ 의 최소 원소는 ( $X$ 로 국한된) 등호 $=$ 이며, 최대 원소는 전체 관계 $X^{2} \subseteq X^{2}$ 이다. 동치 관계들의 집합 ${\sim_{i}}_{i \in I}$ 의 만남 $\underset{i \in I}{⋀} \sim_{i}$ 는 교집합

(x, y) \in \underset{i \in I}{⋀} \sim_{i} ⟺ \forall i \in I : x \sim_{i} y

이다. ${\sim_{i}}_{i \in I}$ 의 이음 $\underset{i \in I}{⋁} \sim_{i}$ 은 합집합 $⋃_{i \in I} \sim_{i}$ 을 포함하는 최소의 동치 관계

(x, y) \in \underset{i \in I}{⋁} \sim_{i} ⟺ \exists n \in ℕ \exists x_{0}, \dots, x_{n} \in X \exists i_{1}, \dots, i_{n} \in I : x = x_{0} \sim_{i_{1}} x_{1} \sim_{i_{2}} \dots \sim_{i_{n}} x_{n} = y

이다.

동치 관계 격자 $Eq (X)$ 는 항상 대수적 격자(영어: algebraic lattice)이자 반모듈러 격자(영어: semimodular lattice)이다. 유한 집합 $X$ 의 경우, $Eq (X)$ 는 단순 격자(영어: simple lattice, 합동 관계가 자명한 격자)이다.

예

임의의 집합 $X$ 위에서, 등호 $=$ 는 동치 관계를 이룬다.

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

임의의 함수 $f : X \to Y$ 에 대하여, 같은 함숫값을 갖는 관계

x \sim_{f} y ⟺ f (x) = f (y)

는 정의역 $X$ 위의 동치 관계이다. 이를테면, $X$ 가 어떤 사람들의 집합이며, $f$ 가 사람의 생일을 찾는 함수라면, $\sim_{f}$ 는 같은 생일의 사람들을 한데 묶는 동치 관계로 생각할 수 있다.

반례

반사 관계가 아닌 대칭 추이적 관계

임의의 집합 $X$ 위에서, 공관계

\emptyset \subseteq X^{2}

는 항상 대칭 관계이자 추이적 관계이다. 그러나, 만약 $X \neq \emptyset$ 이라면 이는 반사 관계가 아니다. 반사 관계가 아닌 대칭 추이적 관계는 이러한 형태밖에 없다.

대칭 관계가 아닌 반사 추이적 관계

정수의 집합 $ℤ$ 위의 표준적인 순서

x \leq y ⟺ \exists z \in ℤ_{\geq 0} : y = x + z

를 생각하자. 이는 전순서이며, 특히 반사 관계이자 추이적 관계이지만, 대칭 관계가 아니다. 예를 들어, $0 \leq 1$ 이지만, $1 \leq̸ 0$ 이다.

추이적 관계가 아닌 반사 대칭 관계

정수 집합 $ℤ$ 위의 이항 관계

(x, y) \in R ⟺ y = x + 1 \lor y = x - 1

는 반사 관계이자 대칭 관계이지만, 추이적 관계가 아니다.

같이 보기

집합의 분할

각주

↑ ^가 ^나 Jech, Thomas (2003). 《Set theory》 3판 (영어). Springer Monographs in Mathematics. Berlin: Springer. doi:10.1007/3-540-44761-X. ISBN 978-3-540-44085-7. ISSN 1439-7382. MR 1940513. Zbl 1007.03002. IA settheory0000jech_f7i4.

외부 링크

이철희. “동치관계”. 《수학노트》.
“Equivalence relation” (영어). 《Encyclopedia of Mathematics》. Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
Weisstein, Eric Wolfgang. “Equivalence relation” (영어). 《Wolfram MathWorld》. Wolfram Research.
“Equivalence relation” (영어). 《nLab》.
“Equivalence relation” (영어). 《PlanetMath》.
“Definition: equivalence relation” (영어). 《ProofWiki》.

모듈:Authority_control 159번째 줄에서 Lua 오류: attempt to index field 'wikibase' (a nil value).

[Jech-1] 가 ^나 Jech, Thomas (2003). 《Set theory》 3판 (영어). Springer Monographs in Mathematics. Berlin: Springer. doi:10.1007/3-540-44761-X. ISBN 978-3-540-44085-7. ISSN 1439-7382. MR 1940513. Zbl 1007.03002. IA settheory0000jech_f7i4.

[1]