관계(Relation), 분할(Partition)

정의1

관계(relation) :

임의의 집합 $S$의 관계 $\mathcal{R}$을 $S$의 데카르트곱의 부분집합 $\mathcal{R} \subseteq S \times S$로 정의한다.

$S$의 임의의 원소 $x,y \in S$가 관계 $\mathcal{R}$을 만족하기 위한 필요충분조건은 $(x,y) \in \mathcal{R}$인 것이다.

$(x,y) \in \mathcal{R}$을 $x \; \mathcal{R}\; y$ 또는 $\mathcal{R}(x,y)$로 표기할 수 있다.

$S$의 관계를 $S$의 이항관계(binary relation)라고도 한다.

동치관계(equivalence relation) :

다음이 모두 성립하는 집합 $S$의 관계 $\mathcal{R}$을 $S$의 동치관계로 정의한다.

반사성(reflexivity) : 모든 $x \in S$에 대해 $(x,x) \in \mathcal{R}$이다.

대칭성(symmetry) : 모든 $x,y \in S$에 대해 $(x,y) \in \mathcal{R}$이면 $(y,x) \in \mathcal{R}$이다.

추이성(transivity) : 모든 $x,y,z \in S$에 대해 $(x,y) \in \mathcal{R}$이고 $(y,z) \in \mathcal{R}$이면 $(x,z) \in \mathcal{R}$이다.

동치류(equivalence class) :

$\mathcal{R}$이 $S$의 동치관계일때 임의의 $a \in S$에 대해

$[a]_\mathcal{R} = \{ x \in S : (a, x)\in \mathcal{R}   \}$인 집합을 $\mathcal{R}$에 대한 $a$의 동치류라 한다.

임의의 집합 $E$에 대해 $E = [a]_\mathcal{R}$인 $a \in S$가 존재하면 $E$를 $\mathcal{R}$에 대한 동치류라고 정의한다.

$\mathcal{R}$에 대한 동치류인 집합 $E$는 아래 정리로 모든 $x \in E$에 대해 $E = [x]_\mathcal{R}$이다.

몫집합(quotient set) :

$\mathcal{R}$이 $S$의 동치관계일때 치환공리로

$\mathcal{R}$에 대한 동치류들의 집합 $S/\mathcal{R} = \{ X : \text{ 어떤 } x \in S \text{에 대해 } X = [x]_\mathcal{R} \} = \{[x]_\mathcal{R} : x \in S\}$을 

$\mathcal{R}$에 대한 $S$의 몫집합으로 정의한다.

 

 

 

정의5

임의의 집합 $S$의 부분집합들의 집합족 $\mathcal{P}$가 다음을 모두 만족하면 $\mathcal{P}$를 $S$의 분할(partition)로 정의한다.

1. 임의의 $A \in \mathcal{P}$에 대해 $A \subseteq S$이고 $A \ne \emptyset$이다

2. $A \ne B$인 임의의 $A,B \in \mathcal{P}$에 대해 $A \cap B = \emptyset$이다.

3. $\displaystyle \bigcup \mathcal{P} = \bigcup_{A \in \mathcal{P}} A$ $= S$

 

 

 

정리5

임의의 집합 $S$의 동치관계 $\mathcal{R}$에 대해 다음이 성립한다.

1. 임의의 $a,b \in S$에 대해 $(a,b) \in \mathcal{R}$이기 위한 필요충분조건은 $[a]_{\mathcal{R}} = [b]_\mathcal{R}$인 것이다.

2. 집합 $E $가 $\mathcal{R}$에 대한 동치류이면 모든 $x \in E$에 대해 $E = [x]_{\mathcal{R}}$이다.

3. 모든 원소가 $\mathcal{R}$에 대한 동치류인 $S$의 분할 $\mathcal{P}$가 유일하게 존재한다.

4. 3번의 분할 $\mathcal{P}$는 $\mathcal{R}$에 대한 $S$의 몫집합 $S/\mathcal{R}$에 대해 $\mathcal{P} = S/\mathcal{R}$이다.

증명

1.

$[a]_{\mathcal{R}} = [b]_\mathcal{R}$이면 $b \in [b]_\mathcal{R} = [a]_\mathcal{R}$이므로 $(a,b) \in \mathcal{R}$이다.

역으로 $(a,b) \in \mathcal{R}$일때

$x \in [a]_\mathcal{R}$이면 $(a,x) \in \mathcal{R}$이고 대칭성으로 $(x ,a) \in \mathcal{R}$이다.

또 $(x ,a) \in \mathcal{R}$이고 $(a,b) \in \mathcal{R}$이므로 추이성으로 $(x,b) \in \mathcal{R}$이고

다시 대칭성으로 $(b,x) \in \mathcal{R}$가 되어 $x \in [b]_\mathcal{R}$이므로 $[a]_\mathcal{R} \subseteq [b]_\mathcal{R}$이다.

$x \in [b]_\mathcal{R}$이면 $(b,x) \in \mathcal{R}$이고 $(a,b) \in \mathcal{R}$이므로 

추이성으로 $(a,x) \in \mathcal{R}$이 되어 $x \in [a]_\mathcal{R}$이고 $[b]_\mathcal{R} \subseteq [a]_\mathcal{R}$이다.

따라서 집합정리로 $[a]_{\mathcal{R}} = [b]_\mathcal{R}$이다.

2.

$E$는 어떤 $a \in S$에 대해 $E = [a]_\mathcal{R}$이므로 $x \in E$이면 $(a,x) \in \mathcal{R}$이고 1번으로 $E = [a]_\mathcal{R} = [x]_\mathcal{R}$이다.

3, 4

모든 원소가 $\mathcal{R}$에 대한 동치류인 $S$의 분할이 $\mathcal{P}_1, \mathcal{P}_2$라고 가정할때

$A \in \mathcal{P}_1$이면 분할의 정의로 $A\ne \emptyset$이므로 어떤 $x \in A$가 존재하여 2번으로 $A = [x]_\mathcal{R}$이고 $\displaystyle x\in S = \bigcup \mathcal{P}_2$이므로

합집합의 정의로 $x \in B$인 집합 $B\in \mathcal{P}_2$가 존재하고 $B$는 동치류임에 따라

2번으로 $B = [x]_\mathcal{R} = A$가 되어 $A =B \in \mathcal{P}_2$이므로 $\mathcal{P}_1 \subseteq \mathcal{P}_2$이다.

비슷하게 $\mathcal{P}_2 \subseteq \mathcal{P}_1$가 되어 집합정리로 $\mathcal{P}_1 = \mathcal{P}_2$이므로 모든 원소가 $\mathcal{R}$에 대한 동치류인 $S$의 분할은 유일하다.

치환공리로 $\mathcal{R}$에 대한 $S$의 몫집합 $S/\mathcal{R} = \{[x]_\mathcal{R} : x \in S\}$이 존재하여 $\mathcal{P} = S/\mathcal{R}$로 두면

아래 분할조건 1, 2, 3이 모두 성립하므로 집합족 $\mathcal{P} = S/\mathcal{R}$는 $S$의 분할이다.

분할조건 1

임의의 $A \in \mathcal{P}$는 $\mathcal{R}$에 대한 동치류이므로 $A \subseteq S$이고 $A \ne \emptyset$이다.

분할조건 2

임의의 $A,B \in \mathcal{P}$에 대해 $A \ne B$일때 $A \cap B \ne \emptyset$이라고 가정하면

$z \in A \cap B$가 존재하여 2번으로 $A = [z]_\mathcal{R} = B$임에 따라 모순이므로 $A \ne B$이면 $A \cap B = \emptyset$이다.

분할조건 3

임의의 $x\in \displaystyle \bigcup \mathcal{P}$는 합집합의 정의로 $x\in A$인 $A\in \mathcal{P}$가 존재하여 $x\in A\subseteq S$이므로 $\displaystyle \bigcup \mathcal{P}\subseteq S$이고

임의의 $x\in S$에 대해 $x\in [x]_\mathcal{R}\in S/\mathcal{R}=\mathcal{P}$이므로 합집합의 정의로 $x\in \displaystyle \bigcup \mathcal{P}$가 되어

$\displaystyle S\subseteq \bigcup \mathcal{P}$임에 따라 집합정리로 $\displaystyle \bigcup \mathcal{P}=S$이다.

 

 

 

정리6

임의의 유한집합 $S$의 분할 $\mathcal{P}$에 대해 다음이 성립한다.

1. $S = \emptyset$이기 위한 필요충분조건은 $\mathcal{P} = \emptyset$인 것이다.

2. $S$가 $n \in $ $\mathbb{Z}^+$개의 원소를 가지면 $\mathcal{P}$는 $1\le r \le n$인 $r \in \mathbb{Z}^+$개의 원소를 갖는 유한집합이다.

증명

1.

$S = \emptyset$일때 $\mathcal{P} \ne \emptyset$라고 가정하면 $A\in \mathcal{P}$가 존재하여

분할의 정의로 $A\subseteq S$이고 $A\ne \emptyset$이므로 $x\in A\subseteq S$가 존재함에 따라 $S\ne \emptyset$이 되어 모순이다.

따라서 $S = \emptyset$이면 $\mathcal{P} = \emptyset$이다.

역으로 $\mathcal{P} = \emptyset$이면 분할의 정의와 합집합의 정의로 $\displaystyle S =\bigcup \mathcal{P} = \bigcup \emptyset = \emptyset $이다.

2.

$S$는 $n\ge 1$인 $n$개의 원소를 가져 공집합이 아니므로

$x \in$ $\displaystyle S =\bigcup \mathcal{P} = \bigcup_{A \in \mathcal{P}} A $가 존재하여 $x \in A$인 $A \in \mathcal{P}$가 존재하므로 $\mathcal{P}\ne \emptyset$이다.

모든 $A \in \mathcal{P}$는 $A \ne \emptyset$이므로 $1$개이상의 원소를 갖고 $A \subseteq S$이므로 유한집합 정리로 $A$는 유한집합이다.

멱집합의 정의와 멱집합 정리와 유한집합 정리로 $\mathcal{P}$는 유한집합이고

$A \ne B$인 임의의 $A,B \in \mathcal{P}$에 대해 $A \cap B = \emptyset$이므로 $\mathcal{P}$가 $n$개보다 많은 원소를 갖는다고 가정하면

유한집합 정리로 $\displaystyle \bigcup \mathcal{P} = \bigcup_{A \in \mathcal{P}} A = S$가 $n$개보다 많은 원소를 갖게 되어 모순이다.

따라서 $\mathcal{P}$는 $1\le r \le n$인 $r \in \mathbb{Z}^+$개의 원소를 갖는 유한집합이다.

 

 

 

정리2

임의의 집합 $S$의 동치관계 $\mathcal{R}$에 대한 몫집합이 $S/\mathcal{R}$일때

임의의 $s \in S$의 $\mathcal{R}$에 대한 동치류 $[s]_\mathcal{R}$에 대해 $q(s) =[s]_\mathcal{R}$인 함수 $q:S\to S/\mathcal{R}$는 전사이다.

증명

몫집합의 정의로 모든 $E \in S/\mathcal{R}$에 대해 $E=[s]_\mathcal{R}$인 $s\in S$가 존재하여 $q(s) =[s]_\mathcal{R} = E$이므로 $q$는 전사이다.

 

 

 

정리1

임의의 가산집합 $S$의 동치관계 $\mathcal{R}$에 대한 몫집합 $S/\mathcal{R}$은 가산집합이다.

증명

$S = \emptyset$일때 위 정리와 위 정리로 $S/\mathcal{R} = \emptyset$이므로 $S/\mathcal{R}$은 유한집합이 되어 가산집합이다.

$S \ne \emptyset$일때 위 정리와 위 정리로 $S/\mathcal{R} \ne \emptyset$이고

위 정리로 모든 $s\in S$에 대해 $q(s) =[s]_\mathcal{R}$인 함수 $q:S\to S/\mathcal{R}$는 전사이므로

$S$가 가산임에 따라 가산집합 정리로 전사함수 $f : \mathbb{N} \to S$가 존재하고

함수 정리로 합성함수 $q \circ f : \mathbb{N} \to S/\mathcal{R}$는 전사가 되어 가산집합 정리로 $S/\mathcal{R}$은 가산이다.

 

 

 

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

정의의 링크 : 

https://openknowledgevl.tistory.com/58#def번호

번호는 해당 정의 옆에 붙어있는 작은 숫자입니다.

 

정리의 링크 : 

https://openknowledgevl.tistory.com/58#thm번호

번호는 해당 정리 옆에 붙어있는 작은 숫자입니다.

 

위 내용은 아래의 출처를 기반으로 정리한 내용입니다.

틀린 내용이 존재할 수 있습니다.

 

출처(저자 - 제목 - ISBN13)

Stephen H. Friedberg - Linear Algebra - 9780134860244

John B. Fraleigh - A First course in Abstract Algebra - 9788998308162