동치관계

혹시 ==을(를) 찾아오셨나요?

同値關係 / Equivalence relation

어떤 두 객체가 완전히 같다는 말은 잘 생각해 보면 정말 같은 두 객체 외에는 같다고 말할 수 없다는 것을 알 수 있다. 가령, 1과 1이라는 두 문자를 두고 보았을 때, 두 1은 실제로는 공간적으로 떨어져 있는 위치에 있기 때문에 서로 다른 1이라고 볼 수 있다. 합동인 도형을 '같다'라고 하지 않는 이유도 같은 이유에서다.

그러나 상식적으로 생각해 보면 이 둘은 같은 기호이므로 같은 1이라고 보아야 할 것이다. 하지만 엄밀함을 추구해야 할 논리학이나 수학 단계에서 이러한 "같음"을 상식적인 선이라는 말로 치부할 경우 엄밀성 등에서 문제가 생기므로, 이를 명확히 정의해야 할 필요가 생긴다.

그래서 어떤 이항 관계가 일정 조건을 만족할 때, 이를 동치관계라 불러, 객체 간에 "같다"라는 개념을 이 동치관계로 정의할 수 있도록 한다.

2 정의

어떤 이항관계 [math]\sim[/math]가 다음 세 조건을 만족한다고 하자.

임의의 객체 [math]a[/math], [math]b[/math], [math]c[/math]에 대해,
(반사성, Reflexive) [math]a\sim a[/math]

(대칭성, Symmetric) [math]a\sim b[/math] 면, [math]b\sim a[/math]다.

(추이성, Transitive) [math]a\sim b[/math]이고 [math]b\sim c[/math] 면 [math]a\sim c[/math]다.

그러면 이 이항관계 [math]\sim[/math]를 동치관계라 부른다. 실제로 어떤 이항관계가 동치관계임을 보일 때에는 이 세 가지를 일일이 보이면 된다. ~~참 쉽죠?~~ 다만, 대개는 저 3개를 일일이 보이는 작업은 엄청 귀찮거나 보일 필요도 없이 당연한 것 취급을 받는다. 대칭성이나 추이성의 증명이 생각보다 까다로울 때가 있긴 하지만, 그럴 경우 대개 정의가 어딘가 맛간 거라고 생각하는 편이 더 낫다. (...) ~~반사성이 까다로울 정도면 뭔가가 심각하게 잘못된 것일 수도 있다~~

단, 이 때 동치관계가 꼭 '같은 객체다'는 의미만 지니지는 않는다. 예를 들어 한 학교에 1반, 2반, 3반이 있다고 할 때, '같은 반이다'라는 관계도 동치관계이다. (굳이 '같다'로 이 동치관계를 보고 싶다면, 학생의 여러 속성 중 소속 반만 떼어서 '같다'고 이해해도 되기는 하다....만, '같은 학생이다'는 말과는 억만광년 차이가 있다는 게 포인트.) 이 관계가 세 조건을 만족하는 지는 직접 확인해봐도 좋다.
수학과 논리학에서 잠시 벗어나, 일상언어를 잠시 생각해보면, 대칭성을 만족시키는 관계는 상당히 드문 것이란 것을 알 수 있다. '누구'는 '누구'의 여동생이다. '누구'는 '누구'의 아버지이다. 등등 죄다 대칭성을 만족하지 않는다.

2.1 동치관계의 비교

동치관계 간에 비교하는 개념도 있다. 두 동치관계 [math]\sim[/math] 과 [math]\thickapprox[/math]가

[math]x\sim y[/math] 면 [math]x\thickapprox y[/math] 다

는 관계를 모든 객체 [math]x[/math], [math]y[/math]에 대해 만족하면, [math]\thickapprox[/math]는 [math]\sim[/math]보다 엉성하다(coarser) 혹은 [math]\sim[/math]는 [math]\thickapprox[/math]보다 섬세하다(finer)고 한다.
예를 들어, '같은 반이다'라는 관계는 '같은 분단이다'라는 관계에 비해 엉성하다고 할 수 있다. 같은 분단이면 같은 반이기 때문이다. 반대로 '같은 분단이다'라는 관계는 '같은 반이다'에 비해 섬세한 동치관계이다.

3 등호

일반적으로 등호는 "같다"라는 개념을 나타내는 기호인데, 완전한 의미에서 "같다"는 개념은 앞서 설명했듯 무의미한 개념이기 때문에 역시 적당한 선에서 동치관계를 만들어 정의해야 한다.

그렇다면 그 적당한 선이 어디냐는 물음이 되돌아오는데, 대개 논리학적으로는 다음과 같이 기술한다.

어떤 객체 [math]x[/math], [math]y[/math]에 대해 [math]x=y[/math]는, 임의의 술어(predicate)^[1] [math]P[/math]에 대해 [math]P\left(x\right)\leftrightarrow P\left(y\right)[/math]가 성립함을 말한다.

즉, 모든 논리식 안에서 두 객체를 서로 바꿔 쓸 수 있으면 이들은 논리적으로 같은 객체로 취급한다. 물론, 이런 식의 정의는 모든 술어에 대해 일일이 점검하는 것 외에는 딱히 이렇다 할 만한 방법이 없고, 형성원리 자체도 단순히 논리적으로 생각할 때 유의미한 것 중 제일 섬세한(finest) 동치관계로 정의한 것이다.

집합론에서는 외연공리(Axiom of Extension)이라 하여, 이 등호를 단순화하는 방법을 다음과 같이 제시한다.^[2]

집합 [math]X[/math], [math]Y[/math]에 대해, [math]X=Y[/math]일 필요충분조건은, [math]w[/math]가 무엇이든지 [math]w\in X\leftrightarrow w\in Y[/math]인 것이다.

4 동치류(equivalence class)

동치관계가 집합 내의 원소에 대해서 정의된 것이면, 집합을 잘 변형하여 그 동치관계를 사실상 등호와 같은 것으로 볼 수 있다.

어떤 집합 [math]X[/math] 내의 원소에 대한 동치관계 [math]\sim[/math]를 생각하자. (이 때 [math]\sim[/math]는 '[math]X[/math] 위의 동치관계'라 부른다) 이 때 [math]a\in X[/math]의 동치류(equivalence class)는 다음 집합을 말한다.

[math]\left\{b\in X:a\sim b\right\}[/math]

나타내는 기호도 가지가지라서, [math]a[/math]에다가 바([math]\overline{\phantom{\cdots}}[/math], 위에 선 긋기)를 써서, [math]\overline{a}[/math]라 할 때도 있고, 대괄호를 쳐서 [math]\left[a\right][/math]와 같이 나타낼 때도 있고(동치관계를 제대로 나타내야 할 때에는 아래첨자로 [math]\sim[/math]를 쓸 때도 있다), 하여간 책 따라 저자 따라 상황 따라 제각각이라 이 동치류에 대한 기호는 조심해서 볼 필요가 있다.^[3](대수학이나 위상수학에서 동치류가 중요한 도구 중 하나다 보니 이 기호 선정 문제가 더 불거진다.)

어떤 동치류 [math]A[/math]를 [math]\left[a\right][/math]와 같이 쓸 때, [math]a[/math]를 동치류 [math]A[/math]의 대표원(representative)라 부른다. 단, 한 동치류의 대표원은 하나가 아닌 여러개일 수 있다.

예컨대, 1반, 2반, 3반이 있고 철수가 1반이라고 하면, 철수의 동치류는 1반이다. 즉 철수는 1반의 대표원이고, 1반 = [철수].

동치류의 모임을 상집합(商集合, quotient set)이라 부르고, (동치관계 [math]\sim[/math]에 의한 것을) [math]X/\sim [/math]로 나타낸다. 즉,

[math]X/\sim := \left\{\left[a\right] : a\in X\right\}[/math]

와 같이 정의한다. 이 때 다음이 성립한다.

[math]a\sim b\leftrightarrow\left[a\right]=\left[b\right][/math](집합으로서) ^[4]

여기서 [math]X[/math] 위에서는 [math]\sim[/math]라는 동치관계가 그 상집합 [math]X/\sim [/math] 위에서는 등호라는 동치관계로 뒤바뀐 것을 알 수 있다.

상집합 개념으로 엉성함(coarser)/섬세함(finer) 용어 선정에 대한 이유도 어느 정도 설명할 수 있는데, 가령 ~가 ≈보다 섬세하다(finer)고 가정하면 [math]X/\sim [/math] 과 [math]X/\thickapprox[/math]를 구성하는 각 동치류는, [math]X/\sim [/math] 쪽이 [math]X/\thickapprox[/math]에 비해 덜 많은 원소를 지닌다. 곧 동치류를 일종의 "자갈"로 치면 섬세한 쪽([math]X/\sim [/math])이 더 자잘한 "자갈"을 지니고 있는 것.^[5]

4.1 동치관계와 분할(partition)

어떤 집합 [math]X[/math]의 부분집합의 모임 [math]\mathbf{P}[/math]가 다음을 만족한다고 하자.^[6]

[math]\mathbf{P}\neq \emptyset[/math]
임의의 [math]A,B\in P[/math]에 대해 [math]A\cap B= \emptyset[/math] 혹은 [math]A=B[/math] ~~모 아니면 도~~
모든 [math]x\in X[/math]에 대해, [math]A\in \mathbf{P}[/math]가 존재하여 [math]x \in A[/math]이다.

그러면 [math]\mathbf{P}[/math]를 [math]X[/math]의 분할(partition)이라 부른다. 이 때 다음이 알려져 있다.

임의의 분할 [math]P[/math]에 대해 어떤 [math]X[/math] 위의 동치관계 [math]\sim[/math]가 유일하게 존재해서 [math]\mathbf{P}=X/\sim[/math]이다.
임의의 [math]X[/math] 위의 동치관계 [math]\sim[/math]는 유일한 분할 [math]\sim[/math]에 대해 [math]X/\sim=\mathbf{P}[/math]이다.

즉, [math]X[/math] 위의 동치관계와 [math]X[/math]의 분할 간에는 일대일대응이 있고, 이에 근거해 분할과 동치관계는 거의 같은 것으로 취급한다.

쉽게 말하자면, 전교의 학생들(집합 [math]X[/math])을 1~3반으로 나누었을 때, 분할([math]\mathbf{P}[/math])이란 {1반, 2반, 3반}이란 집합이고, 이에 대응되는 동치관계 [math]a\sim b[/math]는 "학생 [math]a[/math], [math]b[/math]가 같은 반이라는 것"이다.
즉, 분할이 동치관계에 의해 유일하게 결정되고 역으로 동치관계가 분할에 의해 유일하게 결정되는 것은 어찌 보면 당연한 것이다.

4.2 상집합으로의 사영(projection)과 명확성(well-definedness)

집합 [math]X[/math] 위의 동치관계 [math]\sim[/math] 및 그 상집합 [math]X/\sim[/math]에 대해 다음 함수를 생각하자.

[math]q:X\rightarrow X/\sim[/math]
([math]q(a) = \left[a\right][/math])

이 때 이 함수 [math]q[/math]는 전사함수(surjection; onto function)이고, 상집합으로의 사영(projection)이라 불린다. 기하학의 사영과 비슷한 점이라면 '[math]q[/math]의 동치류의 원소로서 구분된다'는 성질을 무시했다는 것 정도?

이 사영함수는 [math]f:X/\sim\rightarrow Y[/math]꼴의 함수를 정의할 때 유용하게 쓰인다. 무슨 말인고 하니, 보통 이런 함수에 대해 쓸 때는

[math]f\left(\left[a\right]\right)=xyz...[/math]

와 같은 식으로 정의되기 마련인데, 정작 [math]xyz...[/math] 부분이 [math]\left[a\right][/math]가 아니라 [math]a[/math] 자체에 대한 식으로 주어져 있을 때가 잦다. 곧, 대개 저런 함수를 정의할 때는 [math]f:X/\sim\rightarrow Y[/math]를 정의한다기보다는, 사영과의 합성함수 [math]f\circ q:X\rightarrow X/\sim\rightarrow Y[/math]를 정의하는 것이 일반적이다. 때문에 많은 경우, [math]f:X/\sim\rightarrow Y[/math]꼴 함수를 정의할 때는

(가정1) [math]F:X\rightarrow Y[/math]꼴 함수를 정의하고
(가정2) [math]x\sim y[/math]면 [math]F\left(x\right)=F\left(y\right)[/math]를 보이고 나면
(결론) 유일한 함수 [math]f:X/\sim\rightarrow Y[/math]가 존재해서, [math]F=f\circ q[/math]으로 나타난다.

는 논리로 정의한다.

이와 같은 불편한/간접적인(...) 방법을 쓰는 이유는, [math]f[/math]가 받는 변수는 엄밀히 말하면 동치류이지만, 정작 수식을 써서 함수를 정의해야 할 때는 대표원을 써서 정의하는데도 불구하고, 대표원이 하나로 정해지는 게 아니라서 [math]f[/math]의 결과값이 대표원에 따라 좌지우지되는 상황이 빈번하기 때문이다.^[7] 그렇기 때문에 대표원에 무관하다는 것을 별도로 보일 필요가 있고, 그 과정을 반영한 것이 위에 제시한 3단계의 논리 흐름이다.

5 예시

물론 등호([math]=[/math])가 제일 알기 쉬운 예시이지만, 이 외에도 다양한 예가 있다.

논리적 동치([math]\leftrightarrow[/math])

어떤 두 명제 [math]P[/math], [math]Q[/math]에 대해, [math]P[/math]에 대해 [math]Q[/math]가 필요충분조건이면 명제 [math]P[/math], [math]Q[/math]는 논리적 동치라고 말하고 [math]P\leftrightarrow Q[/math]와 같이 쓴다. 특히,

한 명제는 자기 자신과 논리적 동치이다.
[math]P[/math]에게 [math]Q[/math]가 필요충분조건이면 [math]Q[/math]에게 [math]P[/math]도 '충분필요'조건이고, ('필요충분'조건이 각각 '충분필요'조건으로 바뀐다)
[math]P[/math]에게 [math]Q[/math]가, [math]Q[/math]에게 [math]R[/math]이 필요충분조건이면 [math]P[/math]에게 [math]R[/math]은 필요충분조건이다. ('필요조건'과 '충분조건'으로 나눠서 보일 수 있다.)

이 예는 집합론 외에, 순수히 논리학에서 동치관계 개념이 쓰이는 일례로 들 수 있다.

도형의 합동([math]\equiv[/math])

대표적인 동치관계의 예 중 하나이다.

한 도형은 자기 자신과 당연히 합동이다.
두 도형 [math]A[/math], [math]B[/math]가 합동일 때, [math]B[/math], [math]A[/math]도 합동이다.
도형 [math]A[/math], [math]B[/math]가 합동이고 [math]B[/math], [math]C[/math]가 합동이면 [math]A[/math], [math]C[/math]도 합동이다.

~~합동이라는 말을 등장변환(isometry)로 일일이 나타내지 않는 이상 뭐라 할 말이 없어~~ 이 때 합동인 도형을 일반적으로 같은 도형으로 취급한다.

도형의 닮음([math]\sim[/math])

희한하지만, 이것도 동치관계의 예 중 하나이다.

한 도형은 자기 자신과 닮음비 1로 닮음이다.
두 도형 [math]A[/math], [math]B[/math]가 닮음비 [math]x[/math]로 닮음이면, [math]B[/math], [math]A[/math]는 닮음비 [math]x^{-1}[/math]로 닮음이다.
도형 [math]A[/math], [math]B[/math]가 닮음비 [math]x[/math]로 닮음이고, [math]B[/math], [math]C[/math]가 닮음비 [math]y[/math]로 닮음이면, [math]A[/math], [math]C[/math]는 닮음비 [math]xy[/math]로 닮음이다..

이상으로 도형의 모임에서 닮음 역시 동치관계임을 알 수 있다. 합동 개념 때문에 일반적으로 같은 도형까지는 취급받진 않지만, 변 간의 비나 각도 측정에서 유용하게 쓰인다.

정수론의 법

정의는 해당 항목 참고. 정수 하나당 정수집합 위에 하나의 동치관계를 만들어 내기 때문에, 여러 개의 동치관계 간의 관계에 대한 정리가 이것저것 있다. 중국인의 나머지 정리가 그 중 하나.

함수 [math]f:X\rightarrow Y[/math]에 대해, [math]x\sim y\leftrightarrow f\left(x\right)=f\left(y\right)[/math].

함수만 주어지면 어떻게 하든 만들어지는 동치관계이기 때문에 (구조를 가진 집합 간의 함수를 자주 다루는) 대수학이나 위상수학에서 마구 양산되는 형태의 동치관계이다. 여러모로 쓰임새가 있긴 하지만, 그 중 하나로 상집합 X/∼와 f의 치역이 거의 같은 집합 취급을 받는다는 것을 들 수 있고, 다른 예로 위의 명확성(well-definedness) 문제와의 관계를 들 수 있다.

한편, 근사된다(≒)란 표현은 대충 보면 동치관계인 것 같으면서도 동치관계가 아닌 예로 들 수 있다. 반사성과 대칭성은 비교적 자연스럽지만,

4 ≒ 4.5 및 4.5 ≒ 5 이지만 4, 5는 근사되지 않는다

와 같은 예시를 고려하면 (물론 '근사된다'라는 표현 자체가 애매하므로 이 예시가 적절한지는 각자 판단하시길) 추이성에서 문제가 생기는 것을 알 수 있다.

~~1.3≒1, 1.3+1.3=2.6, 2.6≒3, 1+1=3~~

~~제일 유명한 식 오세느=트리니!~~

↑ 객체 하나를 받아 참, 거짓을 내놓는 함수. 사용하고 있는 형식논리 체계에 따라 그 정의가 약간씩 바뀔 수 있다.
↑ 제법 거창하게 쓰긴 했지만 사실상 집합론을 처음 배울 때 접하는 집합의 같음 그 자체다.
↑ 일단 이 문서에서는 [math]\left[a\right][/math]와 같이 나타낸다.
↑ 이걸 증명하다 보면 왜 반사성, 대칭성, 추이성이 중요한 성질인지 자연스레 알 수 있다. 집합론에서만 쓰는 개념은 아니지만, 집합론에 응용했을 때 아주 편리한 개념인 것.
↑ Munkres의 Topology에서 나온 비유이다. 원래는 위상공간을 비교할 때 엉성함(coarser)/섬세함(finer)을 설명하는 과정에서 나온 비유.
↑ 요약하자면, [math]\biguplus \mathbf{P}=X[/math]라는 것으로, [math]\biguplus[/math]는, disjoint union 즉 서로소인 집합들의 합집합이다.
↑ 함수는 한 값에 다른 값이 유일하게 대응되어야 한다는 성질을 가지는데, 지금 이 말은 정의하려는 함수가 그 성질을 가지고 있는지를 묻는 것과 같다. 그래서 함수로서 명확한지를 알아보는 문제라 하여 이 문제를 명확성(well-definedness)의 문제로 부른다.

[1] 객체 하나를 받아 참, 거짓을 내놓는 함수. 사용하고 있는 형식논리 체계에 따라 그 정의가 약간씩 바뀔 수 있다.

[2] 제법 거창하게 쓰긴 했지만 사실상 집합론을 처음 배울 때 접하는 집합의 같음 그 자체다.

[3] 일단 이 문서에서는 [math]\left[a\right][/math]와 같이 나타낸다.

[4] 이걸 증명하다 보면 왜 반사성, 대칭성, 추이성이 중요한 성질인지 자연스레 알 수 있다. 집합론에서만 쓰는 개념은 아니지만, 집합론에 응용했을 때 아주 편리한 개념인 것.

[5] Munkres의 Topology에서 나온 비유이다. 원래는 위상공간을 비교할 때 엉성함(coarser)/섬세함(finer)을 설명하는 과정에서 나온 비유.

[6] 요약하자면, [math]\biguplus \mathbf{P}=X[/math]라는 것으로, [math]\biguplus[/math]는, disjoint union 즉 서로소인 집합들의 합집합이다.

[7] 함수는 한 값에 다른 값이 유일하게 대응되어야 한다는 성질을 가지는데, 지금 이 말은 정의하려는 함수가 그 성질을 가지고 있는지를 묻는 것과 같다. 그래서 함수로서 명확한지를 알아보는 문제라 하여 이 문제를 명확성(well-definedness)의 문제로 부른다.

[1]

[2]

[3]

[4]

[5]

[6]

[7]