Equivalence relations (1)

Equivalence Relation은 우리말로 하면 '동치관계'이다.

수학적인 구조를 만드는 기본적인 방법중에 하나는 집합 S에서부터 시작하여 S안의 특정 엘리먼트들을 같은 범주로 두는 새로운 집합을 생성하는것이다. 편가르기? 예를 들면, 정수 집합을 짝수와 홀수 두 개의 집합으로 나눌 수 있을 것이다. 또는 평면상에서 합동인 삼각형(Congruent Triangle)들을 지리적으로 동일한 오브젝트로 볼 수도 있다.

어떤 집합 S가 있을 때, Partition P of S란 S를 겹치지 않는 부분집합으로 나누는 것을 의미한다.

S = union of disjoint, nonempty subsets

예를 들면, 아래 집합은 집합 {1, 2, 3, 4, 5}의 Partition이다.

{1, 3}, {2, 5}, {4}

그리고 Equivalence Relation on S란 S에서 특정 엘리먼트들끼리의 관계를 의미한다. 이를 a ~ b 이렇게 쓰고 Equivalence of a and b라고 부른다.

Equivalence Relation은 아래와 같은 조건이 붙는다.

1. transitive: If a ~ b and b ~ c, then a ~ c
2. symmetric: If a ~ b, then b ~ a
3. reflexive: a ~ a for all a ∈ S

예를 들면, 합동인 삼각형(Congruent Triangle)들은 평면상의 삼각형들의 집합 S에서 Equivalence Relation이 될 수 있다.

좀 더 일반적으로 들어가보자. 집합 S에서 Relation을 갖는다는 의미는 S의 엘리먼트 두개를 짝지어 놓은 집합 S × S의 부분집합 R과 같다. 여기서 R은 a ~ b인 (a, b) 짝들로 구성된다. 그럼 부분집합의 관점에서 위에서 살펴본 Relation의 Axiom들을 아래와 같이 써볼 수 있다.

1. if (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R
2. if (a, b) ∈ R, then (b, a) ∈ R
3. (a, a) ∈ R for all a

Partition of S라는 말과 Equivalence Releation on S라는 말은 논리적으로는 서로 equivalent(동등)하여 실제로는 둘 중에 하나만 대표로 사용된다. 즉 주어진 Partition of S에서 a와 b가 Partion의 같은 부분집합에 놓여 있을 경우 이를 a ~ b라고 맺은 Equivalence Relation R을 정의할 수 있다. 위의 Axiom들을 모두 만족하기 때문이다. 반대로, 주어진 Equivalence Relation R에서도 Partition P를 다음과 같이 정의할 수 있다: 엘리먼트 a와 a ~ b인 모든 엘리먼트 b를 포함하는 부분집합. 이런 부분집합을 Equivalence Class of a 라고 하고, S가 Euqivalence Class로 Partition 되었다고도 한다.

Equivalent Relation이 집합 S에서 Partition을 만든다는 의미를 확인해보자. C_a를 a ∈ S인 Equivalence Class라고 하자. 즉, C_a는 a ~ b인 모든 b를 포함한다.

C_a = {b ∈ S | a ~ b}

위의 Axiom들 중 reflexive에 의해 a ∈ C_a 가 되기 때문에 모든 C_a 클래스들은 nonempty이다. 또한 a가 S의 어떤 엘리먼트도 될 수 있기 때문에 C_a 클래스들이 모이면 집합 S를 커버한다.

이어서 서로다른 Equivalence Class 들은 겹쳐서는 안된다는 속성을 확인해야 한다. 여기서 헷갈릴 수도 있는게, symmetric에 의해서 a ~ b가 b ~ a 도 되어, b ∈ C_a 가 될 수 있다. 그런데 b ∈ C_b 이기도 하기 때문에 서로 다른 Equivalence Class 들이 겹치는 문제가 발생한다. 하지만 사실은 두 클래스가 동일하다. 이어서 아래 내용을 살펴보자.

C_a와 C_b가 공통의 엘리먼트 d를 포함한다고 하자. 그러면, C_a = C_b 이다.

우선 a ~ b 이면 C_a = C_b 이라는 것을 확인해보자. x를 C_b의 임의의 엘리먼트라고 하면, b ~ x 이다. 그러면 a ~ b 이기 때문에 transitivity에 의하여, a ~ x 이며 x ∈ C_a 가 된다. 따라서 C_b ⊂ C_a 가 된다. a와 b의 순서를 바꾸어도 마찬가지이기 때문에 C_a ⊂ C_b 도 성립한다.

그리고 d가 C_a와 C_b의 공통의 엘리먼트라면, a ~ d 이면서 b ~ d 가 된다. 그러면 transitive에 의하여 a ~ b 가 되면서 위에서 밝힌 C_b ⊂ C_a와 C_a ⊂ C_b에 의해 C_a = C_d = C_b 가 성립된다(끝).

다시 말해서 각 Equivalence Class들간에 겹치는 엘리먼트가 있다면, 두 클래스가 완전히 동일하게 되므로 한 집합에서 겹치는 Equivalence Class가 생길 수 없게 되는 것이다.