Search
Duplicate

데코수학/ 집합론/ 관계, 동치관계

(유튜브 동영상인데 현재는 삭제되어서 내용만 남김)

1

개념

•
수식은 연산과 관계로 표현 됨.
◦
a+b=ca + b = c 에서 ‘++’는 연산 ‘==’ 은 관계
•
관계와 함수는 순서쌍의 집합
•
관계 RR, 집합 A,BA, B에 대하여 관계식은 아래와 같이 쓴다.
◦
R:A→BR: A \to B
▪
A={a1,a2,a3},B={b1,b2,b3}A = \{ a_{1}, a_{2}, a_{3} \}, B = \{ b_{1}, b_{2}, b_{3} \}
◦
R:{(a1,b2),(a3,b1),(a3,b3)}R: \{ (a_{1}, b_{2}), (a_{3}, b_{1}), (a_{3}, b_{3}) \}
▪
두 집합 A,BA, B가 있고 어떤 AA에서 BB로 가는 어떤 관계 조건을 만족하는 순서쌍의 집합을 RR이라고 이해하면 된다.
▪
위 상황에서는 그 조건에 만족하는 순서쌍이 (a1,b2),(a3,b1),(a3,b3)(a_{1}, b_{2}), (a_{3}, b_{1}), (a_{3}, b_{3})이라는 것.
•
관계를 RR로 표시하고 아래와 같은 집합에서 철수와 영희가 배우자 관계일 때 다음과 같이 한다.
◦
집합 AA = { 철수, 영희, 진수 }
◦
R배우자R_{\text{배우자}} = { (철수, 영희), (영희, 철수) }
배우자
▪
위의 관계는 특히 대칭인 관계인데, (철수, 영희), (영희, 철수)가 존재하기 때문
▪
일반적인 관계 RR에서 aRb_{a}R_{b}와 bRa_{b}R_{a}가 성립하면 대칭인 관계라고 한다.
•
역관계
◦
어떤 관계 RR에 대하여 순서쌍을 거꾸로 쓴 집합. 역함수와 같다. R−1R^{-1}
◦
RR에 대하여 R−1:={(y,x)∣(x,y)∈R}R^{-1} := \{ (y, x) | (x, y) \in R \}
•
정의역 (Domain)
◦
Dom(R)={a∣(a,b)∈R}Dom(R) = \{ a | (a, b) \in R \}
•
치역 (Image)
◦
Im(R)={b∣(a,b)∈R}Im(R) = \{ b | (a, b) \in R \}
•
다음과 같은 상황에서 정의역과 치역은 다음과 같다.
◦
R:A→BR : A \to B
▪
A={a1,a2,a3},B={b1,b2,b3}A = \{ a_{1}, a_{2}, a_{3} \}, B = \{ b_{1}, b_{2}, b_{3} \}
▪
R={(a1,b2),(a3,b1),(a3,b3)}R = \{ (a_{1}, b_{2}), (a_{3}, b_{1}), (a_{3}, b_{3}) \}
▪
Domain(R)={a1,a3}Domain(R) = \{ a_{1}, a_{3} \}
▪
Im(R)={b1,b2,b3}Im(R) = \{ b_{1}, b_{2}, b_{3} \}
•
동치관계
◦
아래 조건을 모두 만족하는 관계를 동치관계라 부른다.
◦
ϵ:X→X\epsilon : X \to X
▪
∀x∈X,xϵx\forall x \in X, x \epsilon x (반사율)
▪
xϵy⇒yϵxx \epsilon y \Rightarrow y \epsilon x (대칭율)
▪
xϵy∧yϵz⇒xϵzx \epsilon y \wedge y \epsilon z \Rightarrow x \epsilon z (추이율)
◦
닮음도 동치관계
•
동치류, 상집합(Quotient Set)
◦
ϵ:X→X,xϵX\epsilon : X \to X, x \epsilon X 일 때
▪
x/ϵ={a∣aϵx}x / \epsilon = \{ a | a \epsilon x \} 인 것을 동치류라고 한다.
▪
X/ϵ={x/ϵ∣x∈X}X / \epsilon = \{ x / \epsilon | x \in X \} 인 것을 상집합이라고 한다. (동치류를 모아 놓은 집합)
◦
다음과 같은 조건이 있다고 할 때
▪
X={a,b,c,d,e,f}X = \{ a, b, c, d, e, f \}
•
a,b,fa, b, f는 11살
•
cc는 12살
•
d,ed, e 는 13살
▪
ϵ:X→X,aϵb:=\epsilon : X \to X, a \epsilon b := aa와 bb는 동갑이다.
◦
동치류는 다음과 같다.
▪
a/ϵ={a,b,f}a / \epsilon = \{ a, b, f \}
▪
b/ϵ={a,b,f}b / \epsilon = \{ a, b, f \}
▪
c/ϵ={c}c / \epsilon = \{ c \}
▪
d/ϵ={d,e}d / \epsilon = \{ d, e \}
▪
e/ϵ={d,e}e / \epsilon = \{ d, e \}
▪
f/ϵ={a,b,f}f / \epsilon = \{ a, b, f \}
◦
상집합은 다음과 같다.
▪
X/ϵ={{a,b,f},{c},{d,e}}X / \epsilon = \{ \{a, b, f\}, \{c\}, \{d, e\} \}

관계식

•
Dom(R−1)=Im(R)Dom(R^{-1}) = Im(R)
◦
역관계의 정의역은 원래 관계의 치역과 같다.
•
Im(R−1)=Dom(R)Im(R^{-1}) = Dom(R)
◦
역관계의 치역은 원래 관계의 정의역과 같다.
•
x/ϵ≠∅,x/ϵ⊆Xx / \epsilon \neq \emptyset, x / \epsilon \subseteq X
◦
(반사율) 자기 자신이 동치이기 때문에, 동치인 집합이 공집합일 수는 없다.
•
xϵy⇔x/ϵ∩y/ϵ≠∅x \epsilon y \Leftrightarrow x / \epsilon \cap y / \epsilon \neq \emptyset
◦
x,yx, y가 동치관계일 때 xx의 동치류와 yy의 동치류의 교집합은 공집합이 아니다.
•
xϵy⇔x/ϵ=y/ϵx \epsilon y \Leftrightarrow x / \epsilon = y / \epsilon
◦
x,yx, y가 동치관계일 때 xx의 동치류와 yy의 동치류는 같다.
Made with