[이산수학] (3) Partition

Partition을 알아보자. 

A가 집합일 때, partition P는 A의 disjoint subset이다. 

1) s in P, nonempty of S in A

2) for s, s* in P, s != s* and s disjoint s*

3) union of every s in P = A

 

예시2. 조건3이 충족되지 않은 경우

 

 

prop1. 만약 P1이 A1에 대해 partition이고, P2가 A2에 대한 partition이라면, 

{s1 X s2 | s1 in P1 and s2 in P2}는 A1 X A2에 대한 partition이다. 

 

R이 A에 대해 equiv relation이다. P = {[a] | a in A}를 모든 equiv class를 담는 집합이라 가정하자. 그럼 P는 A에 대한 partition이다. 

 

pf) a in [a], therefore (1) satisfied

[a], [b] in P, [a] disjoint [b] (2) satisfied

union of every equiv class of A = A (3) satisfied

 

mod(3)이면 equiv class가 3개 생성된다. 3으로 나눠떨어지는것, 나머지 1, 나머지2

(1) [0], [1], [2]는 각 0,1,2를 갖는다.

(2) 서로 disjoint하다

(3) union of [0], [1], [2] = A

 

1)

(1) for all x in A, (1,1) ... (4,4) in R

(2) inverse of R = R

(3) (1,1) (1,3) (3,1) (3,1) (1,1) (1,3) 등으로 증명된다.

2) equiv class는 정의상 [x] = {y | xRy} 이기 때문에 위와 같다.

3) 

1) a in [a] 

2) disjoint

3) union of all equiv class = A

 

 

위와 같이 equiv class는 partition과 밀접한 연관을 갖는다.

 

만약 R이 A에 대해 equiv relation이라면, P={[a] | a in A}는 A에 대한 partition을 형성한다.

 

P가 A에 대한 partiton이라면, A에 대한 equiv relation인 R이 존재한다. 즉, iff관계다.