혹시 ==을(를) 찾아오셨나요?
同値關係 / Equivalence relation
목차
[숨기기]1 개요
논리학이나 수학, 특히 집합론에서 쓰이는 도구 중 하나. 어떤 두 객체가 서로 "같다"는 개념을 추상화한다.
어떤 두 객체가 완전히 같다는 말은 잘 생각해 보면 정말 같은 두 객체 외에는 같다고 말할 수 없다는 것을 알 수 있다. 가령, 1과 1이라는 두 문자를 두고 보았을 때, 두 1은 실제로는 공간적으로 떨어져 있는 위치에 있기 때문에 서로 다른 1이라고 볼 수 있다. 합동인 도형을 '같다'라고 하지 않는 이유도 같은 이유에서다.
그러나 상식적으로 생각해 보면 이 둘은 같은 기호이므로 같은 1이라고 보아야 할 것이다. 하지만 엄밀함을 추구해야 할 논리학이나 수학 단계에서 이러한 "같음"을 상식적인 선이라는 말로 치부할 경우 엄밀성 등에서 문제가 생기므로, 이를 명확히 정의해야 할 필요가 생긴다.
그래서 어떤 이항 관계가 일정 조건을 만족할 때, 이를 동치관계라 불러, 객체 간에 "같다"라는 개념을 이 동치관계로 정의할 수 있도록 한다.
2 정의
어떤 이항관계 ∼가 다음 세 조건을 만족한다고 하자.
임의의 객체 a, b, c에 대해,
- (반사성, Reflexive) a∼a
- (대칭성, Symmetric) a∼b 면, b∼a다.
- (추이성, Transitive) a∼b이고 b∼c 면 a∼c다.
그러면 이 이항관계 ∼를 동치관계라 부른다. 실제로 어떤 이항관계가 동치관계임을 보일 때에는 이 세 가지를 일일이 보이면 된다. 참 쉽죠? 다만, 대개는 저 3개를 일일이 보이는 작업은 엄청 귀찮거나 보일 필요도 없이 당연한 것 취급을 받는다. 대칭성이나 추이성의 증명이 생각보다 까다로울 때가 있긴 하지만, 그럴 경우 대개 정의가 어딘가 맛간 거라고 생각하는 편이 더 낫다. (...) 반사성이 까다로울 정도면 뭔가가 심각하게 잘못된 것일 수도 있다
단, 이 때 동치관계가 꼭 '같은 객체다'는 의미만 지니지는 않는다. 예를 들어 한 학교에 1반, 2반, 3반이 있다고 할 때, '같은 반이다'라는 관계도 동치관계이다. (굳이 '같다'로 이 동치관계를 보고 싶다면, 학생의 여러 속성 중 소속 반만 떼어서 '같다'고 이해해도 되기는 하다....만, '같은 학생이다'는 말과는 억만광년 차이가 있다는 게 포인트.) 이 관계가 세 조건을 만족하는 지는 직접 확인해봐도 좋다.
수학과 논리학에서 잠시 벗어나, 일상언어를 잠시 생각해보면, 대칭성을 만족시키는 관계는 상당히 드문 것이란 것을 알 수 있다. '누구'는 '누구'의 여동생이다. '누구'는 '누구'의 아버지이다. 등등 죄다 대칭성을 만족하지 않는다.
2.1 동치관계의 비교
동치관계 간에 비교하는 개념도 있다. 두 동치관계 ∼ 과 ≈가
x∼y 면 x≈y 다
는 관계를 모든 객체 x, y에 대해 만족하면, ≈는 ∼보다 엉성하다(coarser) 혹은 ∼는 ≈보다 섬세하다(finer)고 한다.
예를 들어, '같은 반이다'라는 관계는 '같은 분단이다'라는 관계에 비해 엉성하다고 할 수 있다. 같은 분단이면 같은 반이기 때문이다. 반대로 '같은 분단이다'라는 관계는 '같은 반이다'에 비해 섬세한 동치관계이다.
3 등호
일반적으로 등호는 "같다"라는 개념을 나타내는 기호인데, 완전한 의미에서 "같다"는 개념은 앞서 설명했듯 무의미한 개념이기 때문에 역시 적당한 선에서 동치관계를 만들어 정의해야 한다.
그렇다면 그 적당한 선이 어디냐는 물음이 되돌아오는데, 대개 논리학적으로는 다음과 같이 기술한다.
어떤 객체 x, y에 대해 x=y는, 임의의 술어(predicate)[1] P에 대해 P(x)↔P(y)가 성립함을 말한다.
즉, 모든 논리식 안에서 두 객체를 서로 바꿔 쓸 수 있으면 이들은 논리적으로 같은 객체로 취급한다. 물론, 이런 식의 정의는 모든 술어에 대해 일일이 점검하는 것 외에는 딱히 이렇다 할 만한 방법이 없고, 형성원리 자체도 단순히 논리적으로 생각할 때 유의미한 것 중 제일 섬세한(finest) 동치관계로 정의한 것이다.
집합론에서는 외연공리(Axiom of Extension)이라 하여, 이 등호를 단순화하는 방법을 다음과 같이 제시한다.[2]
집합 X, Y에 대해, X=Y일 필요충분조건은, w가 무엇이든지 w∈X↔w∈Y인 것이다.
4 동치류(equivalence class)
동치관계가 집합 내의 원소에 대해서 정의된 것이면, 집합을 잘 변형하여 그 동치관계를 사실상 등호와 같은 것으로 볼 수 있다.
어떤 집합 X 내의 원소에 대한 동치관계 ∼를 생각하자. (이 때 ∼는 'X 위의 동치관계'라 부른다) 이 때 a∈X의 동치류(equivalence class)는 다음 집합을 말한다.
{b∈X:a∼b}
나타내는 기호도 가지가지라서, a에다가 바(¯⋯, 위에 선 긋기)를 써서, ¯a라 할 때도 있고, 대괄호를 쳐서 [a]와 같이 나타낼 때도 있고(동치관계를 제대로 나타내야 할 때에는 아래첨자로 ∼를 쓸 때도 있다), 하여간 책 따라 저자 따라 상황 따라 제각각이라 이 동치류에 대한 기호는 조심해서 볼 필요가 있다.[3](대수학이나 위상수학에서 동치류가 중요한 도구 중 하나다 보니 이 기호 선정 문제가 더 불거진다.)
어떤 동치류 A를 [a]와 같이 쓸 때, a를 동치류 A의 대표원(representative)라 부른다. 단, 한 동치류의 대표원은 하나가 아닌 여러개일 수 있다.
예컨대, 1반, 2반, 3반이 있고 철수가 1반이라고 하면, 철수의 동치류는 1반이다. 즉 철수는 1반의 대표원이고, 1반 = [철수].
동치류의 모임을 상집합(商集合, quotient set)이라 부르고, (동치관계 ∼에 의한 것을) X/∼로 나타낸다. 즉,
X/∼:={[a]:a∈X}
와 같이 정의한다. 이 때 다음이 성립한다.
a∼b↔[a]=[b](집합으로서) [4]
여기서 X 위에서는 ∼라는 동치관계가 그 상집합 X/∼ 위에서는 등호라는 동치관계로 뒤바뀐 것을 알 수 있다.
상집합 개념으로 엉성함(coarser)/섬세함(finer) 용어 선정에 대한 이유도 어느 정도 설명할 수 있는데, 가령 ~가 ≈보다 섬세하다(finer)고 가정하면 X/∼ 과 X/≈를 구성하는 각 동치류는, X/∼ 쪽이 X/≈에 비해 덜 많은 원소를 지닌다. 곧 동치류를 일종의 "자갈"로 치면 섬세한 쪽(X/∼)이 더 자잘한 "자갈"을 지니고 있는 것.[5]
4.1 동치관계와 분할(partition)
어떤 집합 X의 부분집합의 모임 P가 다음을 만족한다고 하자.[6]
- P≠∅
- 임의의 A,B∈P에 대해 A∩B=∅ 혹은 A=B
모 아니면 도 - 모든 x∈X에 대해, A∈P가 존재하여 x∈A이다.
그러면 P를 X의 분할(partition)이라 부른다. 이 때 다음이 알려져 있다.
- 임의의 분할 P에 대해 어떤 X 위의 동치관계 ∼가 유일하게 존재해서 P=X/∼이다.
- 임의의 X 위의 동치관계 ∼는 유일한 분할 ∼에 대해 X/∼=P이다.
즉, X 위의 동치관계와 X의 분할 간에는 일대일대응이 있고, 이에 근거해 분할과 동치관계는 거의 같은 것으로 취급한다.
쉽게 말하자면, 전교의 학생들(집합 X)을 1~3반으로 나누었을 때, 분할(P)이란 {1반, 2반, 3반}이란 집합이고, 이에 대응되는 동치관계 a∼b는 "학생 a, b가 같은 반이라는 것"이다.
즉, 분할이 동치관계에 의해 유일하게 결정되고 역으로 동치관계가 분할에 의해 유일하게 결정되는 것은 어찌 보면 당연한 것이다.
4.2 상집합으로의 사영(projection)과 명확성(well-definedness)
집합 X 위의 동치관계 ∼ 및 그 상집합 X/∼에 대해 다음 함수를 생각하자.
q:X→X/∼(q(a)=[a])
이 때 이 함수 q는 전사함수(surjection; onto function)이고, 상집합으로의 사영(projection)이라 불린다. 기하학의 사영과 비슷한 점이라면 'q의 동치류의 원소로서 구분된다'는 성질을 무시했다는 것 정도?
이 사영함수는 f:X/∼→Y꼴의 함수를 정의할 때 유용하게 쓰인다. 무슨 말인고 하니, 보통 이런 함수에 대해 쓸 때는
f([a])=xyz...
와 같은 식으로 정의되기 마련인데, 정작 xyz... 부분이 [a]가 아니라 a 자체에 대한 식으로 주어져 있을 때가 잦다. 곧, 대개 저런 함수를 정의할 때는 f:X/∼→Y를 정의한다기보다는, 사영과의 합성함수 f∘q:X→X/∼→Y를 정의하는 것이 일반적이다. 때문에 많은 경우, f:X/∼→Y꼴 함수를 정의할 때는
- (가정1) F:X→Y꼴 함수를 정의하고
- (가정2) x∼y면 F(x)=F(y)를 보이고 나면
- (결론) 유일한 함수 f:X/∼→Y가 존재해서, F=f∘q으로 나타난다.
는 논리로 정의한다.
이와 같은 불편한/간접적인(...) 방법을 쓰는 이유는, f가 받는 변수는 엄밀히 말하면 동치류이지만, 정작 수식을 써서 함수를 정의해야 할 때는 대표원을 써서 정의하는데도 불구하고, 대표원이 하나로 정해지는 게 아니라서 f의 결과값이 대표원에 따라 좌지우지되는 상황이 빈번하기 때문이다.[7] 그렇기 때문에 대표원에 무관하다는 것을 별도로 보일 필요가 있고, 그 과정을 반영한 것이 위에 제시한 3단계의 논리 흐름이다.
5 예시
물론 등호(=)가 제일 알기 쉬운 예시이지만, 이 외에도 다양한 예가 있다.
- 논리적 동치(↔)
- 어떤 두 명제 P, Q에 대해, P에 대해 Q가 필요충분조건이면 명제 P, Q는 논리적 동치라고 말하고 P↔Q와 같이 쓴다. 특히,
- 한 명제는 자기 자신과 논리적 동치이다.
- P에게 Q가 필요충분조건이면 Q에게 P도 '충분필요'조건이고, ('필요충분'조건이 각각 '충분필요'조건으로 바뀐다)
- P에게 Q가, Q에게 R이 필요충분조건이면 P에게 R은 필요충분조건이다. ('필요조건'과 '충분조건'으로 나눠서 보일 수 있다.)
- 이 예는 집합론 외에, 순수히 논리학에서 동치관계 개념이 쓰이는 일례로 들 수 있다.
- 도형의 합동(≡)
- 대표적인 동치관계의 예 중 하나이다.
- 한 도형은 자기 자신과 당연히 합동이다.
- 두 도형 A, B가 합동일 때, B, A도 합동이다.
- 도형 A, B가 합동이고 B, C가 합동이면 A, C도 합동이다.
합동이라는 말을 등장변환(isometry)로 일일이 나타내지 않는 이상 뭐라 할 말이 없어이 때 합동인 도형을 일반적으로 같은 도형으로 취급한다.
- 도형의 닮음(∼)
- 희한하지만, 이것도 동치관계의 예 중 하나이다.
- 한 도형은 자기 자신과 닮음비 1로 닮음이다.
- 두 도형 A, B가 닮음비 x로 닮음이면, B, A는 닮음비 x−1로 닮음이다.
- 도형 A, B가 닮음비 x로 닮음이고, B, C가 닮음비 y로 닮음이면, A, C는 닮음비 xy로 닮음이다..
- 이상으로 도형의 모임에서 닮음 역시 동치관계임을 알 수 있다. 합동 개념 때문에 일반적으로 같은 도형까지는 취급받진 않지만, 변 간의 비나 각도 측정에서 유용하게 쓰인다.
- 정의는 해당 항목 참고. 정수 하나당 정수집합 위에 하나의 동치관계를 만들어 내기 때문에, 여러 개의 동치관계 간의 관계에 대한 정리가 이것저것 있다. 중국인의 나머지 정리가 그 중 하나.
- 함수 f:X→Y에 대해, x∼y↔f(x)=f(y).
- 함수만 주어지면 어떻게 하든 만들어지는 동치관계이기 때문에 (구조를 가진 집합 간의 함수를 자주 다루는) 대수학이나 위상수학에서 마구 양산되는 형태의 동치관계이다. 여러모로 쓰임새가 있긴 하지만, 그 중 하나로 상집합 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
- 이동 ↑ 객체 하나를 받아 참, 거짓을 내놓는 함수. 사용하고 있는 형식논리 체계에 따라 그 정의가 약간씩 바뀔 수 있다.
- 이동 ↑ 제법 거창하게 쓰긴 했지만 사실상 집합론을 처음 배울 때 접하는 집합의 같음 그 자체다.
- 이동 ↑ 일단 이 문서에서는 [a]와 같이 나타낸다.
- 이동 ↑ 이걸 증명하다 보면 왜 반사성, 대칭성, 추이성이 중요한 성질인지 자연스레 알 수 있다. 집합론에서만 쓰는 개념은 아니지만, 집합론에 응용했을 때 아주 편리한 개념인 것.
- 이동 ↑ Munkres의 Topology에서 나온 비유이다. 원래는 위상공간을 비교할 때 엉성함(coarser)/섬세함(finer)을 설명하는 과정에서 나온 비유.
- 이동 ↑ 요약하자면, ⨄P=X라는 것으로, ⨄는, disjoint union 즉 서로소인 집합들의 합집합이다.
- 이동 ↑ 함수는 한 값에 다른 값이 유일하게 대응되어야 한다는 성질을 가지는데, 지금 이 말은 정의하려는 함수가 그 성질을 가지고 있는지를 묻는 것과 같다. 그래서 함수로서 명확한지를 알아보는 문제라 하여 이 문제를 명확성(well-definedness)의 문제로 부른다.