제 3 절 분할
정 의 4.44 공집합이 아닌 집합 X에서, 다음을 만족시키는 공집합이 아 닌 X의 부분집합들의 모임 T 를 X의분할(partition)이라 한다.
(1) A, B ∈ T 이고 A ̸= B이면 A ∩ B = ϕ (2) ∪
C∈T C = X
[[ 예 ]] 4.45 A ={1, 2, 3, 4, 5, 6, 7}라 하자.
{{1, 2}, {3, 4, 5}, {6, 7}}은 A의 분할이다.
{{1}, {2, 3, 4, 5}, {6, 7}}은 A의 분할이다.
{{1, 2, 3, 4, 5, 6, 7}}은 A의 분할이다.
{{1, 2}, {3}, {4, 5, 6, 7}, {3}}은 A의 분할이다. 그러나 {{1, 2}, {3}, {4, 5, 6, 7}, ϕ}은 A의 분할이 아니다.
{{1, 2}, {3, 4, 5}, {5, 6, 7}}은 A의 분할이 아니다.
{{1, 2}, {3, 4}, {6, 7}}은 A의 분할이 아니다.
[[ 예 ]] 4.46 자연수의 집합 N에서 E ={x | x는 짝수}
O ={x | x는 홀수}라 하면 T = {O, E}는 N의 분할이다.
(∵) (1) O ̸= E, Q ∩ E = ϕ (2)∪
T = O ∪ E = N
[[ 예 ]] 4.47 자연수의 집합 N에서 A ={x | 는 2의 배수}
B ={x | 는 3의 배수}
C = {x | 는 4의 배수}
T = {A, B, C}는 N의 분할이 아니다.
[[ 예 ]] 4.48 실수의 집합 R에서 T = {Q, Q′}는 R의 분할이다.
[[ 예 ]] 4.49 실수의 집합 R에서 T = {Q, Q′,N}는 R의 분할이 아니다. 왜냐 하면 N ∪ Q ∪ Q′ =R이지만 N ∩ Q ̸= ϕ이기 때문이다.
[[ 예 ]] 4.50 {(−∞, 0), {0}, (0, ∞)}는 R의 분할이다.
[[ 예 ]] 4.51 실수의 집합 R에서 Ai ={x | i ≤ x < i + 1}이라 하면 T = {Ai | i ∈ Z}는 R의 분할이다.
[[ 예 ]] 4.52 S ={x | x는 우리 학과 학생}
A ={x ∈ S | x는 혈액형이 A이다}
B ={x ∈ S | x는 혈액형이 B이다}
C = {x ∈ S | x는 혈액형이 AB이다}
O ={x ∈ S | x는 혈액형이 O이다}
라고 하면 T = {A, B, C, O}는 S의 분할이다.
정 의 4.53 공집합이 아닌 집합 X에서의 동치관계 E이 주어졌을 때 각 x∈ X 에 대하여 집합
[x] = x/E = {y ∈ X | yEx}
을 x의동치류(equivalence class)라 부른다. X에서의 모든 동치류의 집합
을 상집합(quotient set)이라 부르고, X/E와 같이 나타낸다. 즉,
X/E = {[x] | x ∈ X}
이 기호를 Xmod E라고 읽는다.
참 고 4.54 y ∈ [x] ⇐⇒ yEx.
[[ 예 ]] 4.55 관계 E를 집합 Z에서의 동치관계 ≡ (mod 3)이라 하면,
[0] ={y ∈ Z | y ≡ 0(mod 3)} = {. . . , −3, 0, 3, 6, . . . }
= [3] = [6] = . . .
[1] ={y ∈ Z | y ≡ 1(mod 3)} = {. . . , −2, 1, 4, 7, . . . }
= [4] = [7] = . . .
[2] ={y ∈ Z | y ≡ 2(mod 3)}{. . . , −1, 2, 5, 8, . . . }
= [5] = [8] = . . .
∴ Z/E = {[x] | x ∈ Z} = {[0], [1], [2]}.
[[ 예 ]] 4.56 관계 E를 집합 M = {1, 2, . . . , 31}에서의 동치관계 ≡
(mod 7)이라 하면,
[1] ={y ∈ M | y ≡ 1(mod 7)}
={1, 8, 15, 22, 29}
· · ·
[7] ={y ∈ M | y ≡ 7(mod 7)}
={7, 14, 21, 28}
등으로서 같은 요일에 속한 날짜가 되고,
M/E = {[x] | x ∈ M} = {[1], [2], [3], [4], [5], [6], [7]}.
[1] 1, 8, 15
2, 9, 16 23, 30
22, 29 [2]
[3] [4]
[5] [6]
[7]
M
그림 5 분할
[[ 예 ]] 4.57 f : X → Y 가 전사함수일 때 X 위에 정의된 동치관계 R = {(a, b) | f(a) = f(b)}에 대해 동치류들을 구하면
[b] ={a ∈ X | f(a) = f(b)} = f−1(f (b))이고
X/R ={f−1(f (b)) | b ∈ X} = {f−1(y) | y ∈ Y }이다.
[[ 예 ]] 4.58 키 순으로 번호가 부여된 학급의 학생를 4개조로 나누어서 농구 경기를 하려고 한다. 키가 비슷하게 섞이도록 조를 나누는 방법을 하나 들어 라.
풀이. 키가 번호순으로 부여되어 있으므로 번호를 mod 4인 동치관계를 사 용하여 동치류를 구하면 키가 골고루 섞여있는 조를 구성할 수 있다. 즉, 1조 ={1, 5, 9, . . . }
2조 ={2, 6, 10, . . . } 3조 ={3, 7, 11, . . . } 4조 ={4, 8, 12, . . . } 등으로 조를 나누면 된다.
정 리 4.59 E이 X 상에서의 동치관계일 때 다음과 같은 사실이 성립한다.
(1) [x]는 공집합이 아닌 X의 부분집합이다.
(2) [x]∩ [y] ̸= ϕ ⇐⇒ xEy.
(3) xEy ⇐⇒ [x] = [y].
증명. (1) x ∈ X, xEx (∵ E : 반사적).
그러므로 x ∈ [x]. 따라서 [x] ̸= ϕ이다.
(2)
[x]∩ [y] ̸= ϕ ⇐⇒ ∃z, z ∈ [x] ∧ z ∈ [y] (4.19)
⇐⇒ ∃z, zEx ∧ zEy (4.20)
⇐⇒ ∃z, xEz ∧ zEy (4.21)
⇐⇒ xEy (4.22)
(3) (⇐=)
[x] = [y] =⇒ [x] ∩ [y] ̸= ϕ (4.23)
=⇒ xEy (∵ (2)) (4.24)
(=⇒) xEy라 하자.
먼저 [x] ⊆ [y]을 보이자.
z ∈ [x] =⇒ zEx (4.25)
=⇒ zEy (∵ xEy) (4.26)
=⇒ z ∈ [y] (4.27)
∴ [x] ⊆ [y]
같은 방법으로 [y] ⊆ [x].
따라서 [x] = [y].
정 리 4.60 X ̸= ϕ이고 E가 X 위의 동치관계라고 하면 X/E는 X의 분 할이다.
증명. 분명히 집합 X/E = {[x] | x ∈ X}는 X의 공집합이 아닌 부분집합
