Search
Duplicate

이상엽/ 집합론/ 관계와 분할

관계

용어 정리

•
관계
◦
곱집합 A×BA \times B의 부분집합
◦
R=(A,B,P(x,y))\mathcal{R} = (A, B, P(x, y))
◦
P(x, y)는 명제함수
◦
ex) A = {2, 3}, B = {4, 6} 이라 할 때,
▪
A×B={(2,4),(2,6),(3,4),(3,6)}A \times B = \{ (2, 4), (2, 6), (3, 4), (3, 6) \}이 되고
▪
명제함수 P(x, y)를 'x는 y의 약수이다' 라고 정의하면
▪
R={(2,4),(2,6),(3,6)}\mathcal{R} = \{ (2, 4), (2, 6), (3, 6) \}이 된다.
▪
이때 R\mathcal{R}의 한 원소인 (2, 4)는 (2,4)∈R(2, 4) \in \mathcal{R} 또는 2R4_{2} \mathcal{R}_{4}와 같이 표기가 가능하다.
•
관계 R\mathcal{R}의 해집합
◦
{(x,y)∣x∈A,y∈B,P(x,y)는 참}\{ (x, y) | x \in A, y \in B, P(x, y) \text{는 참} \}
•
정의역 (Domain)
◦
적당한 y∈By \in B에 대하여, xRy_{x} \mathcal{R}_{y}인 모든 x∈Ax \in A의 집합 Dom(R)Dom(\mathcal{R})
◦
xRy_{x} \mathcal{R}_{y}의 왼쪽에 오는 원소들(x). 위의 예시의 경우 Dom(R)={2,3}Dom(\mathcal{R}) = \{ 2, 3 \}
•
상 (Image)
◦
적당한 x∈Ax \in A 에 대하여, xRy_{x} \mathcal{R}_{y}인 모든 y∈By \in B의 집합 Im(R)Im(\mathcal{R})
◦
xRy_{x} \mathcal{R}_{y}의 오른쪽에 오는 원소들(y). 위의 예시의 경우 Im(R)={4,6}Im(\mathcal{R}) = \{ 4, 6 \}

관계의 성질

집합 X에서의 관계 R\mathcal{R}에 대하여
•
반사성: ∀x∈X,xRx\forall x \in X, _{x} \mathcal{R}_{x}
◦
ex) X = {1, 2, 3} 에서의 관계
▪
R1={(1,1),(2,2)}\mathcal{R}_{1} = \{ (1, 1), (2, 2) \} 는 반사적이지 않다. (3, 3)이 없기 때문
▪
R2={(1,1),(2,2),(3,3),(1,3)}\mathcal{R}_{2} = \{ (1, 1), (2, 2), (3, 3), (1, 3) \} 는 반사적이다. 자기 자신에 대해 반사적인 원소가 모두 있으면 추가적인 원소가 있는 것은 반사성에 영향이 없다.
▪
이때 반사성을 이루는 원소 (1, 1), (2, 2), (3, 3)을 특별히 Δx\Delta x 라고 표기하며 대각관계 또는 항등관계라고 부른다.
▪
집합이 반사적이라는 말은 대각관계(또는 항등관계)를 포함하고 있다는 말이 된다.
•
대칭성: xRx⇒yRx_{x} \mathcal{R}_{x} \Rightarrow _{y} \mathcal{R}_{x}
◦
ex) X = {1, 2, 3} 에서의 관계
▪
R3={(1,1),(1,2),(2,1)}\mathcal{R}_{3} = \{ (1, 1), (1, 2), (2, 1) \}는 대칭적이다. (1, 2)가 있을 때 (2, 1)이 있으면 대칭적이라고 인정한다.
•
반대칭성: xRy∧yRx⇒x=y_{x} \mathcal{R}_{y} \wedge _{y} \mathcal{R}_{x} \Rightarrow x = y
◦
ex) X = {1, 2, 3} 에서의 관계
▪
R3={(1,1),(1,2),(2,1)}\mathcal{R}_{3} = \{ (1, 1), (1, 2), (2, 1) \}는 반대칭적이지 않다. 대칭되는 쌍이 존재하기 때문. 만일 위 집합에서 (1, 2)나 (2, 1)이 빠지면 반대칭적이 된다.
▪
반면 반대칭성의 정의에 의해 (1, 1)은 반대칭적이다. 1R1∧1R1⇒1=1_{1} \mathcal{R}_{1} \wedge _{1} \mathcal{R}_{1} \Rightarrow 1 = 1이 성립하기 때문.
•
추이성: xRy∧yRz⇒xRz_{x} \mathcal{R}_{y} \wedge _{y} \mathcal{R}_{z} \Rightarrow _{x} \mathcal{R}_{z}
◦
ex) X = {1, 2, 3} 에서의 관계
▪
R4={(1,1),(1,2),(2,3)}\mathcal{R}_{4} = \{ (1, 1), (1, 2), (2, 3) \} 은 추이적이지 못하다. (1, 2), (2, 3)은 있지만 (1, 3)은 없기 때문. 위 집합에 (1, 3)을 추가하면 추이적이 된다. (3, 1)이 추가 되어야 하는 것이 아니므로 주의.
•
ex) X = {1, 2, 3} 에서의 관계
◦
R5={(1,1),(1,3),(2,2),(2,3),(3,1),(3,2)}\mathcal{R}_{5} = \{ (1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2) \}가 있을 때
◦
위 집합은 반사적이지 못하다. (3, 3)이 없기 때문.
◦
위 집합은 대칭적이다. (1, 3)에 대칭되는 (3, 1)이 존재하고 (2, 3)에 대칭되는 (3, 2)가 존재하기 때문.
◦
위 집합은 반대칭적이지 못하다. 대칭적이기 때문.
◦
위 집합은 추이적이지 못하다. (1, 3)과 (2, 3)이 존재하지만 (1, 2)가 없기 때문.

여러가지 관계

•
역관계 R−1\mathcal{R}^{-1}
◦
xRy_{x} \mathcal{R}_{y} 이면 오직 그 때에만 yRx−1_{y} \mathcal{R}_{x}^{-1} 즉, R−1={(y,x)∣(x,y)∈R}\mathcal{R}^{-1} = \{ (y, x) | (x, y) \in \mathcal{R} \}
◦
ex) R={(1,1),(1,2)}\mathcal{R} = \{ (1, 1), (1, 2) \} 의 역관계는 R−1={(1,1),(2,1)}\mathcal{R}^{-1} = \{ (1, 1), (2, 1) \}가 된다.
•
합성관계
◦
집합 X에서의 관계 G와 H에 대하여 합성관계 H∘G={(x,y)∣∃z(x,z)∈G∧(z,y)∈H}H \circ G = \{ (x, y) | \exists z (x, z) \in G \wedge (z, y) \in H \}
▪
합성 관계의 순서는 오른쪽에서 왼쪽으로 진행되기 때문에 위 합성관계에서 G를 먼저 쓰고 그 후에 H를 쓰면 된다.
◦
ex) (1,2)∈G∧(2,3)∈H⇒H∘G∋(1,3)(1, 2) \in G \wedge (2, 3) \in H \Rightarrow H \circ G \ni (1, 3)
•
역관계와 합성관계에 관한 정리
◦
집합 X에서의 관계 F, G, H에 대하여 다음이 모두 성립한다.
▪
(F−1)−1=F(F^{-1})^{-1} = F
▪
(H∘G)∘F=H∘(G∘F)(H \circ G) \circ F = H \circ (G \circ F)
▪
(G∘F)−1=F−1∘G−1(G \circ F)^{-1} = F^{-1} \circ G^{-1}
•
동치관계
◦
반사적, 대칭적, 추이적인 관계
◦
ex) "=" 는 반사적이고 대칭적이고 추이적이므로 동치 관계가 된다.
▪
반사적: a=ba = b
▪
대칭적: a=b⇒b=aa = b \Rightarrow b = a
▪
추이적: a=b∧b=c⇒a=ca = b \wedge b = c \Rightarrow a = c
◦
집합 XX에 대하여 가장 작은 동치관계는XX의 대각관계가 되고, 가장 큰 동치관계는 X2X^{2} 가 된다.
◦
동치관계는 E라고 표기하기도 한다.
•
순서관계
◦
반사적, 반대칭적, 추이적인 관계
◦
ex) R={(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)}\mathcal{R} = \{ (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3) \}은 순서 관계이다.

동치관계와 분할

용어 정리

•
분할: 집합 X에 대하여 다음 세 조건을 만족하는 집합족
◦
공집합을 원소로 하지 않는다.
◦
X를 덮는다.
◦
서로소 집합족이다.
◦
ex) X = {1, 2, 3, 4, 5} 에서의 분할 P를 다음과 같이 구성 P = { {1, 2}, {3, 4}, {5} }
•
동치류: 집합 X 상의 하나의 동치 관계를 E라 할 때
◦
Ex={y∈X∣xEy}E_{x} = \{ y \in X | _{x} E_{y} \}
◦
ex) X = {1, 2, 3, 4, 5} 일 때
▪
E = { (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 3), (3, 1), (2, 4), (4, 2) } 라 하면
▪
E1={1,3}E_{1} = \{ 1, 3 \}
•
1의 동치류라는 것은 왼쪽에 1이 나오는 순서쌍의 오른쪽 것을 의미한다.
▪
E2={2,4}E_{2} = \{ 2, 4 \}
▪
E3={1,3}=E1E_{3} = \{ 1, 3 \} = E_{1}
▪
E4={2,4}=E2E_{4} = \{ 2, 4 \} = E_{2}
▪
E5={5}E_{5} = \{ 5 \}
•
상집합: 집합 X에서의 모든 동치류의 집합
◦
X/E={Ex∣x∈X}X / E = \{ E_{x} | x \in X \}
◦
ex) 앞선 예와 같이 동치류들이 구성되었을 때
▪
상집합 X/EX / E 는 모든 동치류들을 합한 것이므로 다음과 같다. X/E={{1,3},{2,4}, 5 }X / E = \{ \{ 1, 3 \}, \{ 2, 4 \}, {\ 5\ } \}
▪
이 상집합은 집합의 분할과 동일하다. 이는 다시 말해 동치관계를 알면 그 동치관계를 이용해서 분할을 끌어낼 수 있다는 뜻이 된다.
▪
물론 그 역도 성립하므로 분할을 알면 동치 관계를 이끌어낼 수 있다.
•
Rp(=X/P)\mathcal{R}_{p} (= X / P) (분할 P에 의한 관계)
◦
{(x,y)∣∃A∈P,x,y∈A}\{ (x, y) | \exists A \in P, x, y \in A \}
◦
ex) X = {1, 2, 3, 4, 5}, P = { {1, 2}, {3, 4}, {5} } 일 때, P의 부분집합을 각각 A1,A2,A3A_{1}, A_{2}, A_{3} 이라 하면
▪
A1⇒(1,1),(1,2),(2,1),(2,2)A_{1} \Rightarrow (1, 1), (1, 2), (2, 1), (2, 2)
▪
A2⇒(3,3),(3,4),(4,3),(4,4)A_{2} \Rightarrow (3, 3), (3, 4), (4, 3), (4, 4)
▪
A3⇒(5,5)A_{3} \Rightarrow (5, 5)
▪
이 A1,A2,A3A_{1}, A_{2}, A_{3} 를 모두 모으면 Rp\mathcal{R}_{p} 이 된다.

여러가지 정리

•
공집합이 아닌 집합 X 위의 동치관계 E에 대하여 다음이 모두 성립한다.
◦
Ex≠∅E_{x} \neq \emptyset
◦
Ex=Ey⇔xEyE_{x} = E_{y} \Leftrightarrow _{x} E_{y}
◦
Ex∩Ey≠∅⇔xEyE_{x} \cap E_{y} \neq \emptyset \Leftrightarrow _{x} E_{y}
◦
X/EX / E 는 XX의 분할이다.
•
공집합이 아닌 집합 X의 분할 P에 대하여 다음이 모두 성립한다.
◦
RpR_{p} 는 XX상의 동치관계다.
◦
X/Rp=PX / R_{p} = P
Made with