Search
Duplicate

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

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

1

개념

수식은 연산과 관계로 표현 됨.
a+b=ca + b = c 에서 ‘++’는 연산 ‘==’ 은 관계
관계와 함수는 순서쌍의 집합
관계 RR, 집합 A,BA, B에 대하여 관계식은 아래와 같이 쓴다.
R:ABR: 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에 대하여 순서쌍을 거꾸로 쓴 집합. 역함수와 같다. R1R^{-1}
RR에 대하여 R1:={(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:ABR : 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} \}
동치관계
아래 조건을 모두 만족하는 관계를 동치관계라 부른다.
ϵ:XX\epsilon : X \to X
xX,xϵx\forall x \in X, x \epsilon x (반사율)
xϵyyϵxx \epsilon y \Rightarrow y \epsilon x (대칭율)
xϵyyϵzxϵzx \epsilon y \wedge y \epsilon z \Rightarrow x \epsilon z (추이율)
닮음도 동치관계
동치류, 상집합(Quotient Set)
ϵ:XX,xϵX\epsilon : X \to X, x \epsilon X 일 때
x/ϵ={aaϵx}x / \epsilon = \{ a | a \epsilon x \} 인 것을 동치류라고 한다.
X/ϵ={x/ϵxX}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살
ϵ:XX,aϵb:=\epsilon : X \to X, a \epsilon b := aabb는 동갑이다.
동치류는 다음과 같다.
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(R1)=Im(R)Dom(R^{-1}) = Im(R)
역관계의 정의역은 원래 관계의 치역과 같다.
Im(R1)=Dom(R)Im(R^{-1}) = Dom(R)
역관계의 치역은 원래 관계의 정의역과 같다.
x/ϵ,x/ϵXx / \epsilon \neq \emptyset, x / \epsilon \subseteq X
(반사율) 자기 자신이 동치이기 때문에, 동치인 집합이 공집합일 수는 없다.
xϵyx/ϵy/ϵx \epsilon y \Leftrightarrow x / \epsilon \cap y / \epsilon \neq \emptyset
x,yx, y가 동치관계일 때 xx의 동치류와 yy의 동치류의 교집합은 공집합이 아니다.
xϵyx/ϵ=y/ϵx \epsilon y \Leftrightarrow x / \epsilon = y / \epsilon
x,yx, y가 동치관계일 때 xx의 동치류와 yy의 동치류는 같다.