1. 집합 상의 동치 관계 (Equivalence Relation)
ㅇ 비록 다르게 보이지만, 실제로는 같은 것들을 집합으로하는, 관계
※ 수학적으로, 동치 관계는, `같다`는 개념의 일반화 임
- 例) 임의 실수 x,y 사이에, x ~ y (동치관계) 이면,
. 이같은 관계가, 실수 전체 집합에서도, 동일하게 성립함을 의미
2. 동치 관계의 표기, 조건, 성질
ㅇ 동치 관계의 표기 : 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가지 성질(반사율,대칭률,추이율)을 모두 만족시키는 집합으로써의 관계성을 가지면,
. 이러한 경우를 동치관계라고 함
ㅇ 동치 관계의 주요 성질 ☞ 분할(Partition) 참조
- 어떤 집합을 서로 공통 부분이 없으면서도 공집합이 아닌 클래스들로 완벽하게 분할 가능
3. 동치 류, 동치 클래스 (Equivalence Class)
ㅇ 어떤 집합에 대해 정의된/성립된 연산이,
- 반사적,대칭적,추이적인 세 조건을 만족한다면, (즉, 동치 관계)
- 이 연산으로 이루어진 각 분할들은 동치류를 이루게 됨
ㅇ 표기
- [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,...}
4. 동치관계, 동치류의 응용 例
ㅇ 수학에서, 동치 관계는 수학적 대상을 분류할 때 유용하게 쓰임
- 주어진 대상을 분류하여, 새로운 집합을 구성하여 줌
ㅇ 컴퓨터 프로그래밍 언어에서, 동치 관계는,
- 변수 명칭은 처음 몇개 문자들 만 맞으면 같음
- 더이상 무모하고 제한없이 문자열 비교 작업을 계속하지 않아도 됨
ㅇ 코드 및 암호 이론에서, 동치 관계는,
- 어떤 규칙이 정수 전체 집합 중 일부 정수들의 부분집합 만을 충족함으로써,
- 이를 응용하여 코딩,암호화에 유용하게 쓰일 수 있음