2017년 1월 28일 (토) 16:22에 Maintenance script님의 편집

2017-01-28T16:22:14Z

새 문서

[include(틀:구별, rd1===)]

{{{+1 同値關係 / Equivalence relation}}}

[목차]

=== 개요 ===
[[논리학]]이나 [[수학]], 특히 [[집합론]]에서 쓰이는 도구 중 하나. 어떤 두 객체가 서로 "같다"는 개념을 추상화한다.

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

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

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

=== 정의 ===
어떤 이항관계 <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반이 있다고 할 때, '같은 반이다'라는 관계도 동치관계이다. (굳이 '같다'로 이 동치관계를 보고 싶다면, 학생의 여러 속성 중 소속 반만 떼어서 '같다'고 이해해도 되기는 하다....만, '같은 학생이다'는 말과는 억만광년 차이가 있다는 게 포인트.) 이 관계가 세 조건을 만족하는 지는 직접 확인해봐도 좋다.
--수학과 논리학에서 잠시 벗어나, 일상언어를 잠시 생각해보면, 대칭성을 만족시키는 관계는 상당히 드문 것이란 것을 알 수 있다. '누구'는 '누구'의 여동생이다. '누구'는 '누구'의 아버지이다. 등등 죄다 대칭성을 만족하지 않는다.--

==== 동치관계의 비교 ====
동치관계 간에 비교하는 개념도 있다. 두 동치관계 <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)'''고 한다.
예를 들어, '같은 반이다'라는 관계는 '같은 분단이다'라는 관계에 비해 엉성하다고 할 수 있다. 같은 분단이면 같은 반이기 때문이다. 반대로 '같은 분단이다'라는 관계는 '같은 반이다'에 비해 섬세한 동치관계이다.
=== 등호 ===
일반적으로 등호는 "같다"라는 개념을 나타내는 기호인데, 완전한 의미에서 "같다"는 개념은 앞서 설명했듯 무의미한 개념이기 때문에 역시 적당한 선에서 동치관계를 만들어 정의해야 한다.

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

> 어떤 객체 <math>x</math>, <math>y</math>에 대해 <math>x=y</math>는, 임의의 술어(predicate)[* 객체 하나를 받아 참, 거짓을 내놓는 함수. 사용하고 있는 형식논리 체계에 따라 그 정의가 약간씩 바뀔 수 있다.] <math>P</math>에 대해 <math>P\left(x\right)\leftrightarrow P\left(y\right)</math>가 성립함을 말한다.

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

[[집합론]]에서는 외연공리(Axiom of Extension)이라 하여, 이 등호를 단순화하는 방법을 다음과 같이 제시한다.[* 제법 거창하게 쓰긴 했지만 사실상 집합론을 처음 배울 때 접하는 집합의 같음 그 자체다.]
> 집합 <math>X</math>, <math>Y</math>에 대해, <math>X=Y</math>일 필요충분조건은, <math>w</math>가 무엇이든지 <math>w\in X\leftrightarrow w\in Y</math>인 것이다.

=== 동치류(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>를 쓸 때도 있다), 하여간 책 따라 저자 따라 상황 따라 제각각이라 이 동치류에 대한 기호는 조심해서 볼 필요가 있다.[* 일단 이 문서에서는 <math>\left[a\right]</math>와 같이 나타낸다.]([[대수학]]이나 [[위상수학]]에서 동치류가 중요한 도구 중 하나다 보니 이 기호 선정 문제가 더 불거진다.)

어떤 동치류 <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>(집합으로서) [* 이걸 증명하다 보면 왜 반사성, 대칭성, 추이성이 중요한 성질인지 자연스레 알 수 있다. 집합론에서만 쓰는 개념은 아니지만, 집합론에 응용했을 때 아주 편리한 개념인 것.]
여기서 <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>)이 더 자잘한 "자갈"을 지니고 있는 것.[* Munkres의 Topology에서 나온 비유이다. 원래는 위상공간을 비교할 때 엉성함(coarser)/섬세함(finer)을 설명하는 과정에서 나온 비유.]

==== 동치관계와 분할(partition) ====
어떤 집합 <math>X</math>의 부분집합의 모임 <math>\mathbf{P}</math>가 다음을 만족한다고 하자.[* 요약하자면, <math>\biguplus \mathbf{P}=X</math>라는 것으로, <math>\biguplus</math>는, disjoint union 즉 서로소인 집합들의 합집합이다.]

* <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>가 같은 반이라는 것"이다.
즉, 분할이 동치관계에 의해 유일하게 결정되고 역으로 동치관계가 분할에 의해 유일하게 결정되는 것은 어찌 보면 당연한 것이다.

==== 상집합으로의 사영(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>의 결과값이 대표원에 따라 좌지우지되는 상황이 빈번하기 때문이다.[* 함수는 한 값에 다른 값이 '''유일하게''' 대응되어야 한다는 성질을 가지는데, 지금 이 말은 정의하려는 함수가 그 성질을 가지고 있는지를 묻는 것과 같다. 그래서 함수로서 명확한지를 알아보는 문제라 하여 이 문제를 '''명확성(well-definedness)의 문제'''로 부른다.] 그렇기 때문에 대표원에 무관하다는 것을 별도로 보일 필요가 있고, 그 과정을 반영한 것이 위에 제시한 3단계의 논리 흐름이다.

=== 예시 ===
물론 등호(<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>로 닮음이다..
이상으로 도형의 모임에서 닮음 역시 동치관계임을 알 수 있다. 합동 개념 때문에 일반적으로 같은 도형까지는 취급받진 않지만, 변 간의 비나 각도 측정에서 유용하게 쓰인다.

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

* 함수 <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]]--
~~제일 유명한 식 [[오세느=트리니]]!~~

[[분류:논리학]][[분류:집합론]]

동치관계 - 편집 역사

2017년 1월 28일 (토) 16:22에 Maintenance script님의 편집