[집합론] Partition과 Block

Partition

Partition의 정의

Partition$($분할$)$은 어떠한 집합 $X$를 겹치지 않고 나누는 부분집합들의 집합을 말한다.

ex) 집합 $A=\left\{1,2,3\right\}$에 대해 $A$의 partition으로 $ \left\{\left\{1,2\right\}, \left\{3\right\}\right\} $ 등이 있다.

 

 

어떤 집합 $\left\{B_{i}\right\}$가 집합 $A$의 partition이라면 다음 세 조건을 만족한다.

 

1. $\forall B_{i} \neq \emptyset$ , 즉 partiton의 모든 원소는 공집합이 아니어야 한다.

2. If $i \neq j$ then $B_{i} \cap B_{j} = \emptyset $ , 즉 partition의 모든 원소는 겹치지 않아야 한다.

3. $\cup_{i}B_{i} = A$ , 즉 partiton의 모든 원소의 합집합은 원래 집합이다. 

 

 

표현이 어려워 보이지만 잘 생각해보면 정말 어려운 내용은 아니다. 

단순히 어떤 집합을 여러개로 나누는 이미지를 떠올리면 쉽게 이해할 수 있다. 

 

 

Partition의 약간 다른 정의

집합 $P$가 집합 $X$의 partiton이 되기 위한 필요충분 조건은 다음과 같다.

$ (\emptyset \notin P) $ and $ (\cup_{A \in P}A = X) $ and $(\forall A, B \in P, (A \neq B) \rightarrow (A \cap B = \emptyset))$

 

사실 이 조건을 잘 읽어보면 위의 세 가지 조건을 축약한 것과 다를 바 없음을 알 수 있다.

 

 

Block

집합 $X$와 $X$의 partiton $P$를 생각해보자. Partion의 원소를 block이라 한다.

$X$의 원소 $a$에 대해 $a$를 포함하는 $P$의 한 block은 $[a]$와 같이 나타낼 수 있다. 

 

ex)집합 $X = \left\{1,2,3\right\}$, partition $ P = \left\{ \left\{ 1 \right\}, \left\{ 2,3 \right\}    \right\} $를 생각해보자.

$X$의 원소 1을 포함하는 block $[1] = \left\{   1  \right\}$

$X$의 원소 2를 포함하는 block $[2] = \left\{  2,3   \right\}$

$X$의 원소 3을 포함하는 block $[2] = \left\{  2,3   \right\}$

 

 

Block을 이용해 정의한 Relation

 

집합 $X$와 $X$의 partiton $P$에서 한 relation을 정의할 수 있다.

(Relation과 관련한 내용은 여기에서 확인할 수 있다 : https://hellworld.tistory.com/8)

 

$X$에서 relation $\sim_{P} \in X \times X$를 다음과 같이 정의하자. 

$a \sim_{P} b \Leftrightarrow a \in [b]$, 즉 $a \sim_{P} b$ 이면 원소 $a$가 block $[b]$에 포함된다는 것이다. 

 

 

ex) $X = \left\{1,2,3,4,5 \right\}$, $X$의 partiton $P = \left\{\left\{1 \right\}, \left\{2,3 \right\}, \left\{4,5 \right\} \right\}$에 대해

$1 \sim_{P} 1$, $2 \sim_{P} 2$, $2 \sim_{P} 3$, $ 4\sim_{P} 5$ 등이 성립한다. 

이 relation의 원소를 모두 나열해보면 다음과 같다. 

$\sim_{P} = \left\{  \left\{ 1,1\right\},  \left\{2,2 \right\}, \left\{2,3 \right\}, \left\{3,2 \right\}, \left\{3,3 \right\}, \left\{4,4 \right\}, \left\{4,5 \right\}, \left\{5,4 \right\}, \left\{5,5 \right\}     \right\}$

 

 

 

연습문제

집합 $X = \left\{ 1,2,3,4 \right\}$의 partiton을 모두 생각해보자.

그리고 그 중 하나를 선택해 $1 \sim_{P} 1$,$2 \sim_{P} 2$,$3 \sim_{P} 3$,$4 \sim_{P} 4$가 모두 성립하는지 확인해보자.