Math

Equivalence relations (1)

koodev 2017. 5. 31. 13:29

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을 만든다는 의미를 확인해보자. Ca를 a ∈ S인 Equivalence Class라고 하자. 즉, Ca는 a ~ b인 모든 b를 포함한다.

Ca = {b ∈ S | a ~ b}

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

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

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

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

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

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