Equivalence Relation, Equivalence Class   동치 관계, 동치류

(2019-08-24)
1. 두 집합 상의 동치 관계(Equivalence Relation)

  ㅇ 비록 다르게 보이지만, 실제로는 같은 것들을 집합으로하는, 관계수학적으로, 동치관계는 `같다`는 개념의 일반화임
     - 例) 임의 실수 x,y 사이에, x ~ y (동치관계) 이면, 
        . 이같은 관계가 실수 전체 집합에서 성립함을 의미

  ㅇ 동치관계 표기 : A ~ B
     - `~` 표기는 A,B가 특정 동치 관계에 의해 동치 원소가 됨을 나타냄

  ㅇ 동치관계 성질 
     -  R ⊂ A x A 이고 다음 3가지 특수한 성질을 만족함
        . 반사적(reflexive)  :  A ~ A 이다
           ..  (a,a) ∈ R
        . 대칭적(symmetric)  :  A ~ B 이면, B ~ A 이다
           ..  (a,b) ∈ R 이면, (b,a) ∈ R  
        . 추이적(transitive) :  A ~ B 이고 B ~ C 이면, A ~ C 이다
           ..  (a,b) ∈ R, (b,c) ∈ R 이면, (a,c) ∈ R

     - 즉, 3가지 성질(반사율,대칭률,추이율)을 모두 만족시키는 집합으로써의 관계성을 가지면,
        . 이러한 경우를 동치관계라고 함


2. 동치류 (Equivalence Class)

  ㅇ 어떤 집합에 대해 정의된/성립된 연산이,
     - 반사적,대칭적,추이적인 세 조건을 만족한다면, (즉, 동치 관계)
     - 이 연산으로 이루어진 각 분할(Partition)들은 동치류를 이루게 됨

  ㅇ 표기 
     -  [a] = { x∈A | x R a } 
        .  [a]R : 주어진 a와 관계 R에 관해 a와 동치인 모든 집합

  ㅇ 例)
     - 합동 모듈로 4(Congruence Modulo 4)에서 0,1의 동치류
        . 0의 동치류 : a ≡ 0 (mod 4) 이 되는 모든 정수  
           .. [0] = {...,-8,-4,0,4,8,...}
        . 1의 동치류 : a ≡ 1 (mod 4) 이 되는 모든 정수  
           .. [1] = {...,-7,-3,1,5,9,...}

     - 합동 모듈로 4(Congruence Modulo 4)에 관한 모든 동치류
        . [0] = {...,-8,-4,0,4,8,...}
        . [1] = {...,-7,-3,1,5,9,...}
        . [2] = {...,-6,-2,2,6,10,...}
        . [3] = {...,-5,-1,3,7,11,...}


3. 동치관계/동치류 응용 例수학에서, 동치 관계는 수학적 대상을 분류할 때 유용하게 쓰임
     - 주어진 대상을 분류하여, 새로운 집합을 구성하여 줌

  ㅇ 컴퓨터 프로그래밍 언어에서, 동치 관계는,
     - 변수 명칭은 처음 몇개 문자들 만 맞으면 같음
     - 더이상 무모하고 제한없이 문자열 비교 작업을 계속하지 않아도 됨

  ㅇ 코드암호 이론에서,
     - 어떤 규칙이 정수 전체 집합 중 일부 정수들의 부분집합을 충족함으로써,
       이를 응용하여 코딩,암호화에 유용하게 쓰일 수 있음


[관계] 1. 관계 2. 순서쌍 3. 동치관계,동치류

 
        최근수정     요약목록     참고문헌