[ 이산 수학 ] 16. 관계(3)

Equivalence Relations

 

: 집합 A가 [ Reflexive + Symmetric + Transitive ] 하다면, Equivalence하다 고 한다.

 

출처 ) https://www.youtube.com/watch?v=pR89T9SPFX4&t=938s

 

 

 

---

예제 1)

 

(a,b) | a ≡ b( mod M)  , 즉 [ a를 m으로 나누었을 때 나머지= b를 m으로 나누었을 때 나머지 ] 이다.

* a-b 를 m으로 나누었을 때 0이면 됨

 

 

  ●  Reflexive : a ≡ a (mod m)  a - a = 0  은 m으로 나눴을 때 0이므로 ㅇㅋ

  ●  Symmetry : a - b 가 m으로 나누어질 때, a-b = km으로 표시할 수 있다.

                          b- a = (-k)m으로 될 것.

  ●  Transitive : (a-b) %m = km 이랑 (b-c) %m = lm 이면, a-c = (k+l)m이다.

 

---

 

예제 2) 

 

 ● Reflexive : a/a  의 값은 항상 1로 같다.         O

 

 ● Symmetric : 2/4 는 가능  4/2는 안 된다.  X

 

 ● Transitive    : a/b 와 b/c가 가능하면, c/a 가 가능해야함

                      --> a/b =>  (ak=b)     , b/c => (bq = c) 

                          c = a(kq)

 

---

동치류

: 동치 관계가 성립하는 것을 모아놓은 것

 

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

→  a와 동치관계가 성립하는 x들을 모아놓은 것이 a의 동치류라고 한다.

 

 

예제) 실수인 집합 A에서 다음 동치 관계가 존재한다.

R = { (x,y) | x-y 는 정수이다 }

위 동치 관계에서 0, 1/2의 동치류를 구해라

 

[ a ] = z ∈ A : z - a 는 정수이다.

[ 0 ] = z ∈ A : z - 0 는 정수이다   → { ... -1,0,1,... }

[ 1/2 ] = z ∈ A : z - 1/2 는 정수이다 → { ... -3/2 ,-1/2 ,1/2 ,3/2 ,... }  

 

 

---

 

집합의 분할

 

분할을 할 때는 이러한 특징이 사용된다.

 

S는 동치류(Ai)들의 합이라고 할 수 있고, 각 집합 Ai의 원소들 사이의 관계는 동치 관계이다.

역으로 말하면, 동치 관계는 집합 S를 분할한다. 

 

ex) 자연수 집합 S를 나머지 연산  3으로 나눴을 때 

    R : x = y (mod 3)

  나머지가 0인 집합 A0 : [0] = { 3,6,9,12 ... }        3|(0-y)
  나머지가 1인 집합 A1: [1] = { 1,4,7,10 ... }         3|(1-y)

  나머지가 1인 집합 A2 : [2] = { 2,5,8,11 ... }         3|(2-y)

 

 

이렇게 한 다음에 위 집합의 분할 특징을 보자.

●  공집합이 있는가? X

●  집합들 간에 공집합이 있는가 ? X

●  분할되어 있고, 합하면 S가 되는가? ㅇㅇ

 

 

---

Partial Orderings

 

집합 A에 대한 관계 R이 

● Reflexive

● Antisymmetric

● Transitive

가 성립하는 관계!

 

그냥 별 거 없음. Ordering 에는 아직 집중 안 해도 됨.

위 조건에만 맞추면 됨

 

 

X >= Y 는 Partial Ordering인가?

 

● Reflexive : a >= a is always true                          O

● Antisymmetric : a>= b , b>=a 이면 a=b이다.        O

● Transitivity       : a>=b and b>=c 이면 a>=c이다.  O

 

---

예제2)  '  | ' divisibility relation 이 partial ordering 인지 확인

 

● Reflexive : a | a is always true

● Antisymmetric : a | b , b | a 이면 a=b이다.        O

● Transitivity       : a | b and b | c 이면 a | c이다.  O

  --> b=a*k , c=b*p 이면 , c = a ( k+p ) 임 (대입 해봐라)

 

 

poset = Partial Ordering SET

 

 

 

 

---

 

Comparability 

 

 

  원소 a와 b가 모두 POSET에 있는 원소라면, 비교가 가능하다.

  즉 원소 a랑 b가 있는 집합이  [ Reflexive *  Antisymmetric * Transitivity ]라면 비교가 가능하다. 

  그렇지 않으면 비교할 수 없음음.

 

Wrtn 정리

1) 부분 집합(Partially ordered set, 줄여서 poset) (S, ≼ )의 원소 a와 b는 a ≼ b 또는 b ≼ a 중 하나가 성립될 경우,

이들은 비교 가능(comparable)하다

 

+ 만약 a와 b가 S의 원소이지만 a ≼ b 또는 b ≼ a 둘 다 성립되지 않는다면, a와 b는 비교 불가능(incomparable)하다

 

 

2) 만약 (S, ≼ )가 poset이고 S의 모든 원소가 비교 가능하다면, S를 전순서 집합(totally ordered set) 또는 선형순서 집합(linearly ordered set)이라고 합니다.

 

3) 잘 정렬된 집합(well-ordered set)이라는 것은, 이것이 poset이면서 ≼가 전순서이고 S의 모든 비어 있지 않은 부분 집합이 최소 원소를 가진다는 것을 의미합니다.

 

 

 

(참고)

https://m.blog.naver.com/qbxlvnf11/221360253754