함수의 기초 (3) - 분할과 동치관계

수학에서 집합을 다룰 때, 어떤 원소들이 "같다"고 볼 수 있는지를 정의하는 일은 매우 중요합니다. 이때 자주 등장하는 개념이 동치 관계(equivalence relation) 와 분할(partition) 입니다. 이 두 개념은 서로 독립적으로 정의되지만, 실제로는 서로를 정확히 규정해 줄 정도로 밀접한 관계를 가집니다. 이 글에서는 두 개념의 정의와 예시를 살펴보고, 이들이 서로를 어떻게 결정하는지를 증명을 통해 알아보겠습니다.

 

이 시리즈는 "함수의 기초"이지만 분할과 동치관계, 동치류 등은 추상적인 개념이므로 직관적으로 이해하기 어려울 수 있습니다.
대학교 수준의 서술이 필요하지 않은 분들은 가볍게 보고 넘어가셔도 좋습니다.

---

분할 (Partition)

비어 있지 않은 집합 X에 대해, P가 X의 분할(Partition)이라 함은 다음 조건을 만족하는 X의 공집합이 아닌 서로소 부분집합들의 집합을 의미합니다.

1. 각 A∈P는 공집합이 아니다.
2. 서로 다른 두 집합 A,B∈P에 대해 A≠B ⇒ A∩B=∅
3. ∪_(A∈P) A = X : 기본적으로 집합족의 표기를 할 수 없으므로 앞으로 이런식으로 표기하겠습니다.

즉, X를 겹치지 않게 나누어 전체를 완전히 덮는 것이라 볼 수 있습니다.

---

예를 하나 살펴보면

정수 집합 ℤ를 짝수와 홀수로 나눈 집합 {Z₀, Z₁}은 분할입니다.

• Z₀ = {x∈ℤ | x≡0 (mod 2)}
• Z₁ = {x∈ℤ | x≡1 (mod 2)}

각 원소는 오직 하나의 집합에 속하고, 두 집합의 합집합은 전체 ℤ가 됩니다.

---

동치 관계 (Equivalence Relation)

동치 관계는 앞서서 살펴본 관계에서 간단하게 살펴보았으나 중요한 내용이므로 다시 한번 살펴보겠습니다.

 

집합 X 안의 관계 ⨁ ⊆ X×X가 다음 세 조건을 만족하면 ⨁를 X위의 동치 관계(equivalence relation)라고 합니다.

1. 반사적(reflexive) 특성: 모든 x∈X에 대해 x ⨁ x가 성립
2. 대칭적(symmetric) 특성: x ⨁ y ⇒ y ⨁ x
3. 추이적(transitive) 특성: x ⨁ y ∧ y ⨁ z ⇒ x ⨁ z

---

위에서 살펴본 예제인 정수 ℤ에 대해 x⨁y = x≡y (mod 2)는 동치 관계입니다.

---

동치류 (Equivalence class)

동치 관계 ⨁에 대해, x∈X가 주어졌을 때 x에 대한 동치류(Equivalence class)는 다음과 같이 정의됩니다:

x / ⨁ = {y∈X | y⨁x}

---

전체 동치류의 집합 X / ⨁ = {x / ⨁ | x∈X}는 X의 분할이 됩니다. 이는 아래의 정리로 증명할 수 있습니다.

정리 1

• ⨁가 X 위의 동치 관계이면 X / ⨁는 X의 분할입니다.

증명>

1. 각 x / ⨁는 동치 관계의 반사적 특성(x ⨁ x)을 만족하므로 공집합이 아니며 따라서 분할의 첫번째 조건을 만족합니다
2. 분할의 두번째 조건은 A≠B ⇒ A∩B=∅이므로 대우의 법칙에 의해 A∩B≠∅ ⇒ A=B를 증명해보도록 하겠습니다.
   1. 가정(A∩B≠∅)에 의해 어떤 z∈(x/⨁ ∩ y/⨁)가 존재하며 따라서 z ⨁ x ∧ z ⨁ y가 성립합니다.
   2. 이는 동치 관계의 대칭적 특성(x ⨁ y ⇒ y ⨁ x)에 의해 x ⨁ z ∧ z ⨁ y가 만족하고
   3. 역시 동치 관계의 추이적 특성(x ⨁ y ∧ y ⨁ z ⇒ x ⨁ z)에 따라 x ⨁ y가 성립합니다.
   4. 이는 동치류의 정의에 의해 x / ⨁ = {y∈X | y⨁x} 및  y / ⨁ = {x∈X | x⨁y}라고 둘 수 있으며
   5. 따라서 x / ⨁ = y / ⨁, 즉, A=B가 성립합니다.
3. 각 x∈X는 자기 동치류 x / ⨁에 속하므로 이들의 전체 합집합은 X가 되므로 분할의 세번째 조건을 만족합니다.

---

집합 X의 분할이 P일 때, 아래와 같이 관계 X / P를 정의할 수 있습니다:

x(X / P)y ⇔ ∃A∈P such that x,y∈A

여기서 such that이라는 말은 "..과 같은"의 의미로 ∃A∈P such that x,y∈A는

"x,y∈A인 A∈P가 적어도 하나 존재한다"라는 의미로 받아들일 수 있습니다.

 

정리 2

• 관계 X / P는 X 위의 동치 관계이며, 이에 따른 동치류 x / (X / P)는 정확히 x가 속한 집합인 A∈P입니다. 즉, X / (X / P) = P.

증명>

1. 정의에 따라 x∈A ⇒ x(X / P)x 이므로 동치 관계 첫번째 조건인 반사적 특성이 성립합니다.
2. 정의에 따라 x(X / P)y 및 y(X / P)x가 만족하므로 동치 관계 두번째 조건인 대칭적 특성이 성립합니다.
3. 정의에 따라 x,y∈A 및 y,z∈B 를 둘 수 있는데 여기서 y∈A∩B ≠ ∅ 이 만족합니다.
   1. 이는 분할 두번째 조건의 대우의 규칙에 의해 A=B가 성립하며
   2. x,z∈A 이고 이는 관계 X / P의 정의에 따라 x(X / P)z를 만족하므로
   3. 이에 따라 동치 관계 세번째 조건인 추이적 특성이 성립합니다.
4. X / (X / P) = P 의 증명은 아래와 같습니다.
   1. 임의의 x∈X에 대해 분할은 원소를 정확히 하나의 조각에만 포함시키므로 x는 정확히 하나의 A∈P에 속하게 됩니다.
   2. 이는 정의에 따라 x / (X / P) = {y∈X | x(X / P)y} = A 입니다.
   3. 반대로 A∈P인 경우 A≠∅ 이므로 어떤 x∈A가 존재하며 이는 앞서 봤듯이 x / (X / P) = A가 됩니다.

---

지금까지 살펴본 두 정리를 요약하면 다음과 같습니다:

• 임의의 동치 관계 E는 분할 P를 정의한다.
• 해당 분할로부터 다시 동치 관계 X / (X / E)를 정의하면 원래의 E를 다시 얻는다.
• 임의의 분할 P는 동치 관계 X / P를 정의한다.
• 이 동치 관계로부터 다시 분할 X / (X / P)를 정의하면 원래의 P를 다시 얻는다.

이처럼 동치 관계와 분할은 서로를 완전히 결정하며, 사실상 동일한 구조를 다른 방식으로 바라본 것이라 할 수 있습니다.