동치관계

동치관계는 반사적이고 대칭적이며 추이적인 집합 위의 이항관계이다.

동기

동치관계는 같음 관계를 조금 느슨하게 한 것이다. 집합의 두 원소가 같은지, 즉 a = b인지는 언제나 판단할 수 있다. 하지만 두 원소가 꼭 같지는 않더라도 비슷한지 알고 싶을 때가 있다. 다시 말해 어떤 중요한 성질이 같은지 알고 싶을 때이다. 예를 들어 두 책의 장르가 같으면 두 책이 비슷하다고 볼 수 있다. 동치관계로 말하면, 두 책의 장르가 같으면 두 책은 동치이다.

이런 동치관계에 무엇을 기대할까? 다른 예를 보자. 두 단어의 글자 수가 같으면 두 단어가 비슷하다(동치이다)고 하자.

같은 단어 두 개의 비슷함을 따지면 비슷하다는 결과가 나오기를 기대할 것이다. 즉 모든 단어는 자기 자신과 비슷해야(동치여야) 한다. 관계의 말로 하면, 동치관계는 반사적이어야 한다.

또 단어 ‘시냇물’이 단어 ‘호랑이’와 비슷하다면(동치라면), 당연히 ‘호랑이’도 ‘시냇물’과 동치이기를 기대한다. 다시 말해 순서는 상관없다. 관계의 말로 하면, 동치관계는 대칭적이어야 한다.

마지막으로 단어 ‘죽음’이 단어 ‘참새’와 비슷하고(동치이고) 단어 ‘참새’가 단어 ‘다리’와 동치라면, 단어 ‘죽음’과 ‘다리’도 동치이기를 기대한다. 즉 동치관계는 추이적이어야 한다.

동치관계에 그 밖의 것은 기대하지 않는다.

예

동치관계의 다른 예는 다음과 같다.

• 같은 도시에 산다. 준호는 당연히 준호와 같은 도시에 산다(반사성). 준호가 현우와 같은 도시에 살면 현우도 준호와 같은 도시에 산다(대칭성). 그리고 현우가 성민과 같은 도시에 살면 준호도 성민과 같은 도시에 산다(추이성).
• 작곡가가 같은 노래. 노래 ‘새벽 기차’는 당연히 노래 ‘새벽 기차’와 작곡가가 같다(반사성). 노래 ‘새벽 기차’와 ‘비 오는 골목’의 작곡가가 같으면 ‘비 오는 골목’과 ‘새벽 기차’도 작곡가가 같다(대칭성). 그리고 ‘비 오는 골목’과 ‘먼지의 진실’의 작곡가가 같으면 ‘새벽 기차’와 ‘먼지의 진실’도 작곡가가 같다(추이성).
• a − b가 짝수일 때 그리고 그때에만 (a, b) ∈ R이다. 여기서 a, b는 정수이다. 반사성: a − a = 0이고 0은 짝수이다. 대칭성: c = a − b라고 하자. 그러면 b − a = −(a − b) = −c이다. c가 짝수이면 −c도 짝수이다. 추이성: p = a − b, q = b − c라고 하자. p와 q가 모두 짝수라는 것은 알고 있다. 이제 a − c가 짝수임을 증명해야 한다. 이 식에서 c 대신 c = b − q를 대입하면 a − (b − q)이고, 이것은 a − b + q와 같다. 가정에서 a − b는 짝수이다. 짝수에 짝수 q를 더하면 다시 짝수가 된다.
• 같음 관계. 같음 관계는 동치관계이고, 임의의 집합 M에서 가장 작은 동치관계이기도 하다.

자명한 동치관계

공집합이 아닌 집합 M이 있다고 하자. 집합 M 위의 가장 작은 동치관계 R은 무엇일까? 곱집합 M × M의 가장 작은 부분집합은 공집합 ∅이다. 공집합은 동치관계의 조건을 만족할까?

대칭적인 것은 분명하다. 관계 R에는 원소가 하나도 없으므로 대칭성의 조건은 자동으로, 자명하게 만족한다. 추이성도 마찬가지이다. 문제는 반사성이다. 정의에 따르면 집합 M의 모든 원소 x에 대해 (x, x) ∈ R이어야 한다. 이것이 만족될까? 집합 M은 공집합이 아니므로 어떤 원소, 예를 들어 q를 가진다. 순서쌍 (q, q)는 관계 R에 있을까? 없다. 그러니 관계 R은 반사적이지 않다.

반사성을 만족하는 가장 작은 관계는 무엇일까? 같음 관계이다. 관계 R에는 적어도 M의 모든 원소에 대해 순서쌍 (x, x)가 있어야 한다. 이것이 바로 항등 관계이다. 이 관계는 대칭적일까? 쉽게 알 수 있듯이 그렇다. 추이적이라는 것도 쉽게 알 수 있다. 따라서 집합 M 위의 가장 작은 동치관계는 항등 관계이다. 항등 관계는 id_M으로 나타내고, 모든 x ∈ M에 대한 순서쌍 (x, x)로 이루어진다.

집합 M 위의 가장 큰 동치관계는 무엇일까? 가장 큰 부분집합은 집합 M × M 전체이다. 이것은 동치관계의 조건을 만족할까? 그렇다는 것은 자명하게 알 수 있을 것이다.

동치류

모든 동치관계는 집합 M을 서로소인 집합들로 나눈다. 이 집합들을 동치류라고 한다.

모든 단어의 집합 M과 ‘글자 수가 같은 단어’라는 동치관계 R이 있다고 하자. 즉 단어 a와 b의 글자 수가 같을 때 그리고 그때에만 (a, b) ∈ R이다. 이 동치관계는 단어의 집합을 더 작은 집합 몇 개로 나누는데, 각 집합에는 글자 수가 같은 단어들이 들어 있다. 각 동치류는 아래 첨자로 구별할 수 있는데, 이 첨자는 그 집합에 있는 단어의 글자 수도 나타낸다.

• M₁ = {물, 눈, 길, 꽃, …}
• M₂ = {바다, 구름, 나무, 하늘, …}
• M₃ = {호랑이, 시냇물, 고구마, 토요일, …}
• M₄ = {해바라기, 오토바이, 텔레비전, 도서관장, …}
• …

두 가지에 주목하자. 1) 각 집합은 서로소이다. 즉 공통인 원소가 하나도 없다. 2) 각 집합 안의 모든 원소는 서로 동치이다. 집합 M₃의 모든 단어는 서로 동치이다. 모든 단어의 글자 수가 3, 즉 같고, 이것이 동치의 조건이기 때문이다.

또 각 원소는 자기가 속한 동치류를 하나로 정한다. 이것을 보통 x ∈ M에 대해 M[x]로 쓴다. M[호랑이]라고 쓰면, 앞에서 M₃으로 나타낸 동치류를 하나로 정하는 것이다.

어떤 x ∈ M을 알 때 동치류는 어떻게 찾을까? M의 원소를 모두 살펴보고 그 가운데 원소 x와 동치인 것을 찾는다. 그 원소들이 모두 동치류 M[x]에 들어간다.

M[호랑이]라면 M의 단어를 모두 살펴보고 글자 수가 3인 단어를 M₃에 남긴다.

동치류의 정의와 성질

동치류는 다음과 같이 정의할 수 있다. 집합 M과 그 위에서 정의한 동치관계 R이 있다고 하자. 그러면 원소 x ∈ M을 포함하는 동치류는 다음과 같다.

$$M[x]=\{y\in M;(x,y)\in R\}$$

이 정의는 주어진 원소 x와 동치인 y를 모두 모은 것이라는 뜻이다. 동치관계는 반사적이므로 원소 x 자신도 이렇게 해서 들어간다. x는 자기 자신과 동치이기 때문이다.

동치관계에 의한 분할은 모든 동치류의 집합을 말한다. 그러니 모든 단어의 집합의 분할은 집합 {M₁, M₂, M₃, …}이다.

동치류의 기본 성질은 다음과 같다.

• (a, b) ∈ R일 필요충분조건은 M[a] = M[b]이다. 동치인 두 원소 a, b가 있으면 그 동치류는 같아야 한다.
• 거꾸로 (a, b) ∈ R이 성립하지 않으면 M[a] ≠ M[b]이고, 더 정확히는 M[a] ∩ M[b] = ∅이다. 동치가 아닌 두 원소가 있으면 그 동치류는 서로소이다.
• 모든 동치류의 합집합은 원래 집합 M이 되어야 한다. M₁ ∪ M₂ ∪ … ∪ M_n = M이다. (이 식은 동치류가 유한 개일 때만 쓸 수 있지만, 일반적으로 동치류는 무한히 많을 수도 있다.)

동치관계에 의한 분할의 예

첫 번째 예는 홀수와 짝수이다.

자연수의 집합 N에서 정의한 간단한 동치관계 R이 있다고 하자. a와 b가 모두 홀수이거나 a와 b가 모두 짝수일 때 그리고 그때에만 (a, b) ∈ R이다. 원소의 예는 (1, 7), (13, 9), (4, 6), (8, 136)이다. 이제 이 동치관계에 의한 동치류로의 분할을 구하자.

차례로 해 보자. 동치류 N[1]은 무엇일까? 1과 동치인 수를 모두 찾아야 한다. 동치의 조건에 따라 그런 수는 홀수 전체이므로 N[1] = {1, 3, 5, 7, 9, …}이다.

동치류 N[2]는 무엇일까? 2와 동치인 수를 모두 찾는다. 짝수 전체이다. 즉 N[2] = {2, 4, 6, 8, 10, …}이다.

이번에는 N[3]이다. 3과 동치인 수는 무엇일까? 홀수 전체이다. 그런데 이것은 두 문단 앞에서 구한 집합 N[1]이다. N[4]도 마찬가지로 다시 짝수의 집합이 된다.

이후로는 같은 집합이 계속 되풀이된다는 것을 알 수 있다. 다른 자연수 n을 아무것이나 잡아도 n ∈ N[1] 또는 n ∈ N[2]가 성립한다는 데서도 알 수 있다. 자연수에는 홀수와 짝수밖에 없으므로 이 두 집합이 동치관계에 의한 분할을 이룬다.

사람의 집합에서 ‘a와 b가 모두 남자이거나 a와 b가 모두 여자이다’라는 동치관계를 생각하는 것과 비슷하다. 그러면 분할로 여자의 집합과 남자의 집합을 얻는다.

두 번째 예는 절댓값이다.

정수의 집합 Z 위의 동치관계 R을 다음과 같이 정의하자. |a| = |b|일 때 그리고 그때에만 (a, b) ∈ R이다. (세로 막대는 절댓값이다.) 이번에도 차례로 해 보자.

• Z[0] = {0}. 0은 0하고만 관계에 있다.
• Z[1] = {−1, 1}. 1은 1, 그리고 -1과 관계에 있다. |1| = |−1|이기 때문이다.
• Z[2] = {−2, 2}. 2는 2, 그리고 -2와 관계에 있다.
• Z[3] = {−3, 3}.
• …

어떻게 이어질지는 분명할 것이다. 따라서 분할 전체는 다음 동치류들의 집합이다.

$$\{\{a,-a\};a\in {\mathbb{Z}}_0^{+}\}$$

(즉 a가 0 이상의 정수일 때 모든 쌍 a, −a이다.) 동치류가 무한히 많다는 것을 알 수 있다.