동치관계
1. 개요
同値關係 / Equivalence relation
논리학이나 수학, 특히 집합론에서 쓰이는 도구 중 하나. 어떤 두 객체가 서로 "같다"는 개념을 추상화한다. 이항 관계의 일종.
위에서 "같다"는 개념이란 두 객체가 '''질적으로''' 같다는 개념을 포착하고자 하는 것이다. 예를 들어 화면 상에서 서로 다른 픽셀로 표시되는 '''1'''과 '''1'''이라는 두 문자는 공간적으로 떨어져 있으므로 '''수적으로'''는 다르지만 수 1을 나타낸다는 점에서는 질적으로 같다고 볼 수도 있다. 도형의 합동도 비슷한 예시다.
2. 정의
어떤 이항관계 $$\sim$$가 다음 세 조건을 만족한다고 하자.
그러면 이 이항관계 $$\sim$$를 '''동치관계'''라 부른다. 실제로 어떤 이항관계가 동치관계임을 보일 때에는 이 세 가지를 일일이 보이면 된다. 다만, 대개는 저 3개를 일일이 보이는 작업은 엄청 귀찮거나 보일 필요도 없이 당연한 것 취급을 받는다. 대칭성이나 추이성의 증명이 생각보다 까다로울 때가 있긴 하지만, 그럴 경우 대개 정의가 어딘가 맛간 거라고 생각하는 편이 더 낫다.임의의 객체 $$a$$, $$b$$, $$c$$에 대해,
* (반사성, Reflexive) $$a\sim a$$
* (대칭성, Symmetric) $$a\sim b$$ 면, $$b\sim a$$다.
* (추이성, Transitive) $$a\sim b$$이고 $$b\sim c$$ 면 $$a\sim c$$다.
단, 이 때 동치관계가 꼭 '같은 객체다'는 의미만 지니지는 않는다. 예를 들어 한 학교에 1반, 2반, 3반이 있다고 할 때, '같은 반이다'라는 관계도 동치관계이다. (굳이 '같다'로 이 동치관계를 보고 싶다면, 학생의 여러 속성 중 소속 반만 떼어서 '같다'고 이해해도 되기는 하다....만, '같은 학생이다'는 말과는 억만광년 차이가 있다는 게 포인트.) 이 관계가 세 조건을 만족하는 지는 직접 확인해봐도 좋다.
수학적으로는 가장 흔하게 드는 예시는 '특정 수로 나눠서 나머지가 같은 수들'끼리 묶는 것이다. 예를 들어 1부터 10까지 정수가 모여있을 때, 3으로 나누어서 나머지가 같은 수들을 찾아보자. 나머지가 0인 수는 3, 6, 9이고, 나머지가 1인 수는 1, 4, 7, 10이고, 나머지가 2인 수는 2, 5, 8이다. 이때, '나머지가 같다'는 건 위에 나온 반사성[1], 대칭성[2], 추이성[3]을 모두 만족하기에 동치 관계이고, 따라서 3~6 혹은 2~8은 모두 동치관계로 연결되었다고 할 수 있다.[4] 이때 3과 6이 동일한 수는 아니지만 엄연한 동치관계(3~6)이다. 위에서도 언급했듯이 '질적으로 같은 것'(여기서는 나머지가 같다는 특징)이지, 객체가 동일함을 가리키진 않는 것이다.[5]
2.1. 동치관계의 비교
동치관계 간에 비교하는 개념도 있다. 두 동치관계 $$\sim$$ 과 $$\thickapprox$$가
는 관계를 모든 객체 $$x$$, $$y$$에 대해 만족하면, $$\thickapprox$$는 $$\sim$$보다 '''엉성하다(coarser)''' 혹은 $$\sim$$는 $$\thickapprox$$보다 '''섬세하다(finer)'''고 한다.$$x\sim y$$ 면 $$x\thickapprox y$$ 다
예를 들어, '같은 반이다'라는 관계는 '같은 분단이다'라는 관계에 비해 엉성하다고 할 수 있다. 같은 분단이면 같은 반이기 때문이다. 반대로 '같은 분단이다'라는 관계는 '같은 반이다'에 비해 섬세한 동치관계다.
한국 등지에서는 $$\thickapprox$$보다 더 '섬세한' $$\fallingdotseq$$를 쓰는 경우도 있다.
2.2. 관련 문서
3. 등호 '='
일반적으로 등호는 "같다"라는 개념을 나타내는 기호인데, 완전한 의미에서 "같다"는 개념은 앞서 설명했듯 무의미한 개념이기 때문에 역시 적당한 선에서 동치관계를 만들어 정의해야 한다. 그렇다면 그 적당한 선이 어디냐는 물음이 되돌아오는데, 대개 논리학적으로는 다음과 같이 기술한다.
즉, 모든 논리식 안에서 두 객체를 서로 바꿔 쓸 수 있으면 이들은 논리적으로 같은 객체로 취급한다. 물론, 이런 식의 정의는 모든 술어에 대해 일일이 점검하는 것 외에는 딱히 이렇다 할 만한 방법이 없고, 형성원리 자체도 단순히 '''논리적으로 생각할 때 유의미한 것 중 제일 섬세한(finest) 동치관계'''로 정의한 것이다.[7] 위와 같은 고차 논리 식을 철학에서는 흔히 "라이프니츠의 법칙(Leibniz's Law)"라고 부른다.어떤 객체 $$x$$, $$y$$에 대해 $$x=y$$는, 임의의 술어(predicate)[6]
$$P$$에 대해 $$P\left(x\right)\leftrightarrow P\left(y\right)$$가 성립함을 말한다.
집합론에서는 외연공리(Axiom of Extension)이라 하여, 이 등호를 단순화하는 방법을 다음과 같이 제시한다.[8]
등호 기호 '='는 영국의 로버트 레코드라는 수학자가 1557년에 쓴 <지혜의 숫돌>에서 처음 사용했다. 이 책은 영어로 된 최초의 대수학 책으로 알려져 있다. 이 기호를 사용한 것에 대해 레코드는 "두 개의 평행선만큼 같은 것은 달리 없기 때문이다"라고 말했다. 그래서 옛날엔 더 넙적했다고.집합 $$X$$, $$Y$$에 대해, $$X=Y$$일 필요충분조건은, $$w$$가 무엇이든지 $$w\in X\leftrightarrow w\in Y$$인 것이다.
반대로 이 등호에 슬래시가 그어지면($$\neq$$) "다르다"라는 의미가 된다.
한국어에서 '='은 조사 '은/는'으로 읽히기 때문에 초등학교 저학년 대상으로 해당 기호를 '등호'라고 읽는 것임을 밝히는 경우가 많다.
4. 동치류(equivalence class)
동치관계가 집합 내의 원소에 대해서 정의된 것이면, 집합을 잘 변형하여 그 동치관계를 '''사실상 등호와 같은''' 것으로 볼 수 있다.
어떤 집합 $$X$$ 내의 원소에 대한 동치관계 $$\sim$$를 생각하자. (이 때 $$\sim$$는 '$$X$$ 위의 동치관계'라 부른다) 이 때 $$a\in X$$의 '''동치류(equivalence class)'''는 다음 집합을 말한다.
나타내는 기호도 가지가지라서, $$a$$에다가 바($$\overline{\phantom{\cdots}}$$, 위에 선 긋기)를 써서, $$\overline{a}$$라 할 때도 있고, 대괄호를 쳐서 $$\left[a\right]$$와 같이 나타낼 때도 있고(동치관계를 제대로 나타내야 할 때에는 아래첨자로 $$\sim$$를 쓸 때도 있다), 하여간 책 따라 저자 따라 상황 따라 제각각이라 이 동치류에 대한 기호는 조심해서 볼 필요가 있다.[9](대수학이나 위상수학에서 동치류가 중요한 도구 중 하나다 보니 이 기호 선정 문제가 더 불거진다.)$$\left\{b\in X:a\sim b\right\}$$
어떤 동치류 $$A$$를 $$\left[a\right]$$와 같이 쓸 때, $$a$$를 동치류 $$A$$의 '''대표원(representative)'''라 부른다. 단, 한 동치류의 대표원은 하나가 아닌 여러개일 수 있다.
예컨대, 1반, 2반, 3반이 있고 철수가 1반이라고 하면, 철수의 동치류는 1반이다. 즉 철수는 1반의 대표원이고, 1반 = [철수].
동치류의 모임을 '''상집합(商集合, quotient set)'''이라 부르고, (동치관계 $$\sim$$에 의한 것을) $$X/\sim $$로 나타낸다. 즉,
와 같이 정의한다. 이 때 다음이 성립한다.$$X/\sim := \left\{\left[a\right] : a\in X\right\}$$
여기서 $$X$$ 위에서는 $$\sim$$라는 동치관계가 그 상집합 $$X/\sim $$ 위에서는 등호라는 동치관계로 뒤바뀐 것을 알 수 있다.$$a\sim b\leftrightarrow\left[a\right]=\left[b\right]$$(집합으로서) [10]
상집합 개념으로 엉성함(coarser)/섬세함(finer) 용어 선정에 대한 이유도 어느 정도 설명할 수 있는데, 가령 ~가 ≈보다 섬세하다(finer)고 가정하면 $$X/\sim $$ 과 $$X/\thickapprox$$를 구성하는 각 동치류는, $$X/\sim $$ 쪽이 $$X/\thickapprox$$에 비해 '''덜''' 많은 원소를 지닌다. 곧 동치류를 일종의 "자갈"로 치면 섬세한 쪽($$X/\sim $$)이 더 자잘한 "자갈"을 지니고 있는 것.[11]
4.1. 동치관계와 분할(partition)
어떤 집합 $$X$$의 부분집합의 모임 $$\mathbf{P}$$가 다음을 만족시킨다고 하자.[12]
- $$\mathbf{P}\neq \emptyset$$
- 임의의 $$A,B\in P$$에 대해 $$A\cap B= \emptyset$$ 혹은 $$A=B$$
- 모든 $$x\in X$$에 대해, $$A\in \mathbf{P}$$가 존재하여 $$x \in A$$이다.
- 임의의 분할 $$P$$에 대해 어떤 $$X$$ 위의 동치관계 $$\sim$$가 유일하게 존재해서 $$\mathbf{P}=X/\sim$$이다.
- 임의의 $$X$$ 위의 동치관계 $$\sim$$는 유일한 분할 $$\sim$$에 대해 $$X/\sim=\mathbf{P}$$이다.
쉽게 말하자면, 전교의 학생들(집합 $$X$$)을 1~3반으로 나누었을 때, 분할($$\mathbf{P}$$)이란 {1반, 2반, 3반}이란 집합이고, 이에 대응되는 동치관계 $$a\sim b$$는 "학생 $$a$$, $$b$$가 같은 반이라는 것"이다.
즉, 분할이 동치관계에 의해 유일하게 결정되고 역으로 동치관계가 분할에 의해 유일하게 결정되는 것은 어찌 보면 당연한 것이다.
위에서 나온 간단한 수학적인 예로 살펴보면, 1부터 10까지의 정수들(전체 집합 X)은 (3, 6, 9), (1, 4, 7, 10), (2, 5, 8), 이 세 집합으로 나눌 수 있다. 이 세 집합은 교집합이 없으며, 세 집합의 합집합은 전체 집합 X가 되므로 분할이라 할 수 있다. 이때, 이 숫자들을 무얼 기준으로 묶었느냐를 물을 수 있다. 집합 내의 특정 숫자들을 골라내 묶을 때 어떤 기준, 다르게 말하면 그 숫자들의 '공통점'이 있을 수 있다는 것이다. 위의 세 집합은 '3으로 나눠서 나머지가 같은 숫자들'이라는 특징을 쉽게 알 수 있다. 이 때 '3으로 나눠서 나머지가 같다'는 공통점의 부여는 다름아닌 '질적으로 같음'을 의미하는 '동치관계'이다. 이를 거꾸로 말하자면, 전체 집합에 속해있는 숫자들(원소들)에 '질적으로 같다고 할 수 있는 기준'(동치관계)을 부여해주면 그 기준에 따라 공통점이 있는 숫자들(원소들)끼리 묶을 수가 있고, 그러면 자연스럽게 전체 집합을 나눌 수 있는 것이다. 동치관계와 동치류를 이용한 분할의 정의는 이러한 표현을 보다 추상적이고 엄밀하게, 그리고 일반화한 것이다.
초등학교 수학에서는 가르기라는 이름으로 잠깐 등장한다.
4.2. 상집합으로의 사영(projection)과 명확성(well-definedness)
집합 $$X$$ 위의 동치관계 $$\sim$$ 및 그 상집합 $$X/\sim$$에 대해 다음 함수를 생각하자.
이 때 이 함수 $$q$$는 전사함수(surjection; onto function)이고, 상집합으로의 '''사영(projection)'''이라 불린다. 기하학의 사영과 비슷한 점이라면 '$$q$$의 동치류의 원소로서 구분된다'는 성질을 무시했다는 것 정도?$$q:X\rightarrow X/\sim$$
($$q(a) = \left[a\right]$$)
이 사영함수는 $$f:X/\sim\rightarrow Y$$꼴의 함수를 정의할 때 유용하게 쓰인다. 무슨 말인고 하니, 보통 이런 함수에 대해 쓸 때는
와 같은 식으로 정의되기 마련인데, 정작 $$xyz...$$ 부분이 $$\left[a\right]$$가 아니라 '''$$a$$ 자체'''에 대한 식으로 주어져 있을 때가 잦다. 곧, 대개 저런 함수를 정의할 때는 $$f:X/\sim\rightarrow Y$$를 정의한다기보다는, 사영과의 합성함수 $$f\circ q:X\rightarrow X/\sim\rightarrow Y$$를 정의하는 것이 일반적이다. 때문에 많은 경우, $$f:X/\sim\rightarrow Y$$꼴 함수를 정의할 때는$$f\left(\left[a\right]\right)=xyz...$$
- (가정1) $$F:X\rightarrow Y$$꼴 함수를 정의하고
- (가정2) $$x\sim y$$면 $$F\left(x\right)=F\left(y\right)$$를 보이고 나면
- (결론) 유일한 함수 $$f:X/\sim\rightarrow Y$$가 존재해서, $$F=f\circ q$$으로 나타난다.
이와 같은 불편한/간접적인 방법을 쓰는 이유는, $$f$$가 받는 변수는 '''엄밀히 말하면''' 동치류이지만, 정작 수식을 써서 함수를 정의해야 할 때는 '''대표원을 써서''' 정의하는데도 불구하고, '''대표원이 하나로 정해지는 게 아니라서''' $$f$$의 결과값이 대표원에 따라 좌지우지되는 상황이 빈번하기 때문이다.[13] 그렇기 때문에 대표원에 무관하다는 것을 별도로 보일 필요가 있고, 그 과정을 반영한 것이 위에 제시한 3단계의 논리 흐름이다.
5. 예시
물론 등호($$=$$)가 제일 알기 쉬운 예시지만, 이 외에도 다양한 예가 있다.
어떤 두 명제 $$P$$, $$Q$$에 대해, $$P$$에 대해 $$Q$$가 필요충분조건이면 명제 $$P$$, $$Q$$는 실질적 동치라고 말하고 $$P\leftrightarrow Q$$와 같이 쓴다. 특히,
- 한 명제는 자기 자신과 실질적 동치이다.
- $$P$$에게 $$Q$$가 필요충분조건이면 $$Q$$에게 $$P$$도 '충분필요'조건이고, ('필요충분'조건이 각각 '충분필요'조건으로 바뀐다)
- $$P$$에게 $$Q$$가, $$Q$$에게 $$R$$이 필요충분조건이면 $$P$$에게 $$R$$은 필요충분조건이다. ('필요조건'과 '충분조건'으로 나눠서 보일 수 있다.)
이 예는 집합론 외에, 순수히 논리학에서 동치관계 개념이 쓰이는 일례로 들 수 있다.
- 도형의 합동($$\equiv$$)
대표적인 동치관계의 예 중 하나이다.
- 한 도형은 자기 자신과 당연히 합동이다.
- 두 도형 $$A$$, $$B$$가 합동일 때, $$B$$, $$A$$도 합동이다.
- 도형 $$A$$, $$B$$가 합동이고 $$B$$, $$C$$가 합동이면 $$A$$, $$C$$도 합동이다.
이 때 합동인 도형을 일반적으로 같은 도형으로 취급한다.
- 도형의 닮음($$\sim$$)
희한하지만, 이것도 동치관계의 예 중 하나이다.
- 한 도형은 자기 자신과 닮음비 1로 닮음이다.
- 두 도형 $$A$$, $$B$$가 닮음비 $$x$$로 닮음이면, $$B$$, $$A$$는 닮음비 $$x^{-1}$$로 닮음이다.
- 도형 $$A$$, $$B$$가 닮음비 $$x$$로 닮음이고, $$B$$, $$C$$가 닮음비 $$y$$로 닮음이면, $$A$$, $$C$$는 닮음비 $$xy$$로 닮음이다..
이상으로 도형의 모임에서 닮음 역시 동치관계임을 알 수 있다. 합동 개념 때문에 일반적으로 같은 도형까지는 취급받진 않지만, 변 간의 비나 각도 측정에서 유용하게 쓰인다.
정의는 해당 항목 참고. 정수 하나당 정수집합 위에 하나의 동치관계를 만들어 내기 때문에, 여러 개의 동치관계 간의 관계에 대한 정리가 이것저것 있다. 중국인의 나머지 정리가 그 중 하나.
- 함수 $$f:X\rightarrow Y$$에 대해, $$x\sim y\leftrightarrow f\left(x\right)=f\left(y\right)$$.
함수만 주어지면 어떻게 하든 만들어지는 동치관계이기 때문에 (구조를 가진 집합 간의 함수를 자주 다루는) 대수학이나 위상수학에서 마구 양산되는 형태의 동치관계이다. 여러모로 쓰임새가 있긴 하지만, 그 중 하나로 상집합 X/∼와 f의 치역이 거의 같은 집합 취급을 받는다는 것을 들 수 있고, 다른 예로 위의 명확성(well-definedness) 문제와의 관계를 들 수 있다.
한편, 근사된다(≒)란 표현은 대충 보면 동치관계인 것 같으면서도 동치관계가 아닌 예로 들 수 있다. 반사성과 대칭성은 비교적 자연스럽지만,와 같은 예시를 고려하면 (물론 '근사된다'라는 표현 자체가 애매하므로 이 예시가 적절한지는 각자 판단하시길) 추이성에서 문제가 생기는 것을 알 수 있다.4 ≒ 4.5 및 4.5 ≒ 5 이지만 4, 5는 근사되지 않는다
6. 관련 문서
[1] 예: 4는 3으로 나누면 나머지가 1이고 4는 3으로 나누면 나머지가 1이다. 둘의 나머지는 같다. 따라서 4~4이다. 이게 다른 모든 숫자에도 적용된다.[2] 예: 4는 3으로 나누면 나머지가 1이고 7은 3으로 나누면 나머지가 1이다. 둘의 나머지는 같다. 따라서 4~7이다. 이때 4~7이면 7~4도 성립한다. 말의 순서를 바꾸어도 성립한다는 것이며 이게 다른 모든 숫자에 대해서도 성립한다.[3] 예: 4는 3으로 나누면 나머지가 1이다. 7도 3으로 나누면 나머지가 1이다. 둘의 나머지는 같으므로 4~7이다. 7을 3으로 나누면 나머지가 1이다. 10을 3으로 나누면 나머지가 1이다. 둘의 나머지가 같으므로 7~10이다. 이때 1과 10도 3으로 나눈 나머지가 같다. 따라서 4~7이고 7~10일 때 1~10도 성립한다. 이게 다른 모든 숫자에 대해서도 성립한다.[4] 더 자세하고 엄밀한 논의는 집합 기호와 논리 기호를 사용해 이 모든 과정을 집합의 관계로 표현해야 한다. 뱀발로, 말로 서술한 반사성, 대칭성, 추이성의 검증이 같은 말 반복에 말장난처럼 보일 수도 있으나, 이러한 당연해보이는 표현마저 엄밀하게 논리적으로 성립함을 따져나가는 게 핵심이다. 그리고 보다 추상적인 대상을 다루게 되면 반사성, 대칭성, 추이성을 따지는 게 더이상 당연한 말 반복으로 보이지 않게 된다. 나머지가 같은 걸로 묶는 게 굉장히 간단한 예라서 그 관계가 당연해보였을 뿐.[5] 물론 객체가 반드시 동일할 필요가 없을 뿐, 객체가 동일한 것도 동치관계의 일부이다. 수학적 표현을 쓰자면 임의의 집합 X위에서 정의된(엄밀히는 X×X에 속하는) R={(x, x)|x는 X의 원소}라는 관계는 자기자신에게만 성립하는 동치관계이다. 즉, X가 1부터 5까지의 정수라면, 해당 동치관계는 (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), 이 다섯 개를 원소로 가지며, 따라서 1~1, 2~2, 3~3, 4~4, 5~5 라는 동치관계가 성립한다. 여기서 이 동치관계가 서술하는 것은 '객체가 같다'는 것에 다름없다. 즉, '객체가 같다'는 건 동치관계의 일부이며, 수학적으로는 가장 작은 동치관계이다.[6] 객체 하나를 받아 참, 거짓을 내놓는 함수. 사용하고 있는 형식논리 체계에 따라 그 정의가 약간씩 바뀔 수 있다.[7] 섬세함이라는 용어를 배제하고 말하면, "a=b면 모든 동치관계 ~에 대해 a~b이다"가 성립하게끔 =(등호)를 정의했다고 이해할 수 있다.[8] 제법 거창하게 쓰긴 했지만 사실상 집합론을 처음 배울 때 접하는 집합의 같음 그 자체다.[9] 일단 이 문서에서는 $$\left[a\right]$$와 같이 나타낸다.[10] 이걸 증명하다 보면 왜 반사성, 대칭성, 추이성이 중요한 성질인지 자연스레 알 수 있다. 집합론에서만 쓰는 개념은 아니지만, 집합론에 응용했을 때 아주 편리한 개념인 것.[11] Munkres의 Topology에서 나온 비유이다. 원래는 위상공간을 비교할 때 엉성함(coarser)/섬세함(finer)을 설명하는 과정에서 나온 비유.[12] 요약하자면, $$\biguplus \mathbf{P}=X$$라는 것으로, $$\biguplus$$는, disjoint union 즉 서로소인 집합들의 합집합이다.[13] 함수는 한 값에 다른 값이 '''유일하게''' 대응되어야 한다는 성질을 가지는데, 지금 이 말은 정의하려는 함수가 그 성질을 가지고 있는지를 묻는 것과 같다. 그래서 함수로서 명확한지를 알아보는 문제라 하여 이 문제를 '''명확성(well-definedness)의 문제'''로 부른다.[14] "논리적 동치"와 같은 것으로 오해하기 쉽다. 양자 간의 차이는 동치 항목 참조.