관계와 분할
1. 관계
(1) 용어의 정의
1) 관계
곱집합 A X B의 부분 집합
\(R = (A, B, P(x,y))\)
여기서 P(x,y)는 명제함수이다.
ex) A={2,3}, B={4,6}
AXB = {{2,4},{2,6},{3,4},{3,6}} 일때
P(x,y) : x는 y의 약수이다라고하면
R = {{2,4},{2,6},{3,6}}
2) 관계 R의 해집합
\(= \left\{ (x,y) | x \in A, y \in B, P(x,y) = True \right\}\)
3) 정의역 (domain)
적당한 $y \in B$ 에 대하여, $ {x}R{y}$ 인 모든 $ x \in A $ 의 집합, Dom(R)
4) 상 (image)
적당한 $x \in A$ 에 대하여, $ {x}R{y}$ 인 모든 $ y \in B $ 의 집합. Im(R)
(2) 관계의 성질
집합 X에서의 관계 R에 대하여
X = {1,2,3}
1) 반사성
\(\forall x \in X, _{x}R_{x}\)
ex) $R_{1}$ = {(1,1),(2,2},(3,3)}
2) 대칭성
\(_{x}R_{y} \Rightarrow _{y}R_{x}\)
ex) $R_{2}$ = {(1,1),(1,2},(2,1)}
3) 반대칭성
\(_{x}R_{y} \wedge _{y}R_{x} \Rightarrow x = y\)
ex) $R_{3}$ = {(1,1)}
4) 추이성
\(_{x}R_{y} \wedge _{y}R_{z} \Rightarrow _{x}R_{z}\)
ex) $R_{4}$ = {(1,1),(1,2},(2,3),(1,3)}
(3) 여러가지 관계
1) 역관계 $R^{-1}$
\(_{x}R_{y}\) 이면 오직 그 때에만 \(_{y}R^{-1}_{x}\)
즉, \(R^{-1} = \left\{ (x,y) | (x,y) \in R \right\}\)
ex) R={(1,1),(1,2)}의 역관계는 {(1,1),(2,1)}
2) 합성관계
집합 X에서의 관계 G와 H에 대하여 합성관계 $ H \circ G $
= \(\left\{ (x,y) | \exists z, (x,z)\in G \wedge (z,y)\in H \right\}\)
ex) $ (1,2) \in G \wedge (2,3) \in H \Rightarrow H \circ G \ni (1,3) $
※ 역관계와 합성관계에 대한 정리
집합 X에서의 관계 F, G, H에 대하여 다음이 모두 성립한다.
$(F^{-1})^{-1} = F$
$(H\circ G) \circ F = H \circ (G \circ F) $
$(G\circ F)^{-1} = F^{-1} \circ G^{-1} $
3) 동치관계
반사적, 대칭적, 추이적인 관계
4) 순서 관계
반사적, 반대칭적, 추이적인 관계
2. 동치관계와 분할
(1) 용어의 정의
1) 분할
집합 X에 대하여 다음 세 조건을 만족하는 집합족이고 P로 표현
- 공집합을 원소로 하지 않는다
- X를 덮는다 즉, $\bigcup P = X$
- 서로소 집합족이다. 교집합이 없단 뜻이며 즉, $\forall A_{1}, A_{2} \in P, A_{1} \cap A_{2} = \varnothing \vee A_{1}= A_{2}$
2) 동치류
집합 X상의 하나의 동치관계를 E라고 할때,
\(E_{x} = \left\{ y \in X | _{x}E_{y} \right\}\)
ex) X = {1,2,3,4} E = {(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(2,4),(4,2)}
동치류 $E_{1}$ = {1,3} = E3
동치류 $E_{2}$ = {2,4} = E4
동치류 $E_{5}$ = {5}
3) 상집합
집합 X상에서의 모든 동치류의 집합. 즉, \(\left\{ E_{x} | x\in X \right\}\)
ex) 동치류에서 든 예시로 상집합 X/E를 만들어보자면
{{1,2},{2,4},{5}}
4) $R_{p}$ (= X/P), 분할 P에 의한 관계
\(\left\{ (x,y) | \exists A\in P, x,y \in A \right\}\)
ex) X = {1,2,3,4,5}
P = {{1,2},{3,4},{5}}
$A_{1}$ = {1,2}
$A_{2}$ = {3,4}
$A_{3}$ = {5}
$A_{1}$ ~ $A_{3}$를 순서쌍을 만들어 합치면
$ R_{p}$ = {(1,1), (1,2), (2,1), (2,2), (3,3), (3,4), (4,3), (4,4), (5,5)}
(2) 여러가지 정리
1) 공집합이 아닌 집합 X위의 동치관계 E에 대하여 다음이 모두 성립한다.
- $ E_{x} \neq \varnothing $
- $ E_{x} = E_{y} \Leftrightarrow {x}E{y} $
- $ E_{x} \cap E_{y} \neq \varnothing \Leftrightarrow {x}E{y} $
- X/E는 X의 분할이다.
2) 공집합이 아닌 집합 X의 분할 P에 대하여 다음이 모두 성립한다.
- $R_{p}$는 X상의 동치관계다.
- $X/R_{p}=P$