[이산수학]동치관계와 동치류란?_예제포함

이산수학 동치관계, 동치류 예제로 이해하기

 

■ 동치관계

관계에서 동치관계라는 것은 집합의 원소들이 '같다'라는 것을 의미합니다. 즉 어떤 관계가 동치관계라고 하면, 그 관계에 포함된 순서쌍 원소 (a, b)에서 a와 b가 '같다'고 할 수 있습니다. 10진수의 7과 2인수 111이 같은 수임을 의미하는 것과 같습니다. 

 

동치관계가 성립되려면 반사관계, 대칭관계, 추이관계가 모두 성립해야 합니다. 

 

예제

정수 집합 Z에 대한 관계 R = {(a,b) ∈ Z × Z|a=b} 일 때, 관계 R이 동치관계인지 판별하라. 

 

풀이

예제풀이

- (a,b) ∈ R일 때, a = b이다.  ∴관계 R은 반사관계다.

- (a,b) ∈ R일 때, a = b므로 b = a도 성립하여 (b, a) ∈ R이다.  ∴관계 R은 대칭관계다.

- (a,b) ∈ R일 때, a = b고, (b, c) ∈ R일 때 b = c므로 a = c로 (a, c) ∈ R이다. 

∴ 관계 R은 추이관계다. 

∴ 관계 R은 반사, 대칭, 추이관계가 성립하므로 동치관계다.

 

■ 동치류

집합 A에 대한 관계 R이 동치관계일 때, 집합 A의 각 원소 a와 순서쌍을 이루는 원소들의 집합

[a] ={x|(a,x) ∈ R}

 

예제

위 예제에서 정수 집합 Z에 대한 관계 R = {(a,b) ∈ Z × Z|a=b}가 동치관계임을 증명하였다. a = 5, 9, 14에 대한 동치류를 구하여라. 

 

풀이

예제풀이

[5] = {5}, [9] = {9}, [14] = {14}, 

 

 

 

 

 

-----------------------------------

이산수학 총정리

목록 보러가기 

-----------------------------------