PROOF 160
증명하라.
곱의 법칙과 합의 법칙
유한집합 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
유한집합 A 에 대하여 |A| = m 이라는 것은, A 에서 {1, 2, …, m} 으로 가는 전단사가 있다는 뜻이다.
증명.
(1)전단사는 서로 다른 원소를 서로 다른 값으로 보내며, 빠뜨리는 값이 없는 대응이다.약속
(2)그러므로 개수를 센다는 것은 전단사를 하나 짓는 일이다.(1)
(3)m = 0 일 때 {1, …, 0} 은 공집합이며, |A| = 0 은 A = ∅ 을 뜻한다.(1)
∎
정의 D2
A ∩ B = ∅ 일 때 두 집합은 배반이라 한다.
증명.
배반이면 어떤 원소도 두 집합에 동시에 속하지 않는다.약속
∎
정리 T1
|A| = m 이고 |B| = n 이면 |A × B| = mn 이다.
증명.
(1)m ≥ 1, n ≥ 1 이라 하고, 전단사 f : A → {1,…,m} 과 g : B → {1,…,n} 을 하나씩 고른다.가정, D1
(2)A × B 의 원소 (a, b) 에 h(a,b) = (f(a) − 1)n + g(b) 를 대응시킨다.(1)
(3)f(a) ≥ 1 이고 g(b) ≥ 1 이므로 h(a,b) ≥ 1(1), N
(4)f(a) ≤ m 이고 g(b) ≤ n 이므로 h(a,b) ≤ (m−1)n + n = mn(1), N
(5)그러므로 h 는 A × B 에서 {1, …, mn} 으로 가는 대응이다.(3), (4)
(6)h(a,b) = h(a′,b′) 이라 하자. 두 값은 모두 (i−1)n + j 꼴이고 j 는 1 이상 n 이하다.(1), (2)
(7)그 표현은 유일하므로 f(a) = f(a′) 이고 g(b) = g(b′)(6), A1
(8)f 와 g 는 전단사이므로 a = a′ 이고 b = b′ 이다. h 는 단사다.(7), (1), D1
(9)1 ≤ k ≤ mn 이라 하자. k = (i−1)n + j 이고 1 ≤ j ≤ n 인 i ≥ 1 과 j 가 유일하게 있다.A1
(10)j ≥ 1 이므로 (i−1)n < mn 이고, n > 0 이므로 i − 1 < m, 즉 i ≤ m 이다.(9), A2, N
(11)f 와 g 는 전사이므로 f(a) = i 인 a 와 g(b) = j 인 b 가 있고, 그 (a,b) 에 대하여 h(a,b) = k 다. h 는 전사다.(9), (10), (1), D1
(12)h 는 전단사이므로 |A × B| = mn(5), (8), (11), D1
(13)m = 0 이거나 n = 0 이면 A × B 는 공집합이고 mn = 0 이므로 등식은 그대로 성립한다.D1, N
∎
정리 T2
A 와 B 가 배반이고 |A| = m, |B| = n 이면 |A ∪ B| = m + n 이다.
증명.
(1)전단사 f : A → {1,…,m} 과 g : B → {1,…,n} 을 하나씩 고른다.가정, D1
(2)x ∈ A 이면 h(x) = f(x), x ∈ B 이면 h(x) = m + g(x) 로 정한다.(1)
(3)A 와 B 는 배반이므로 각 x 는 두 경우 가운데 하나에만 해당한다. h 는 하나의 값만 갖는다.가정, D2, (2)
(4)1 ≤ k ≤ m+n 이면 k ≤ m 이거나 k = m + j (1 ≤ j ≤ n) 이며, 두 경우가 동시에 성립하는 일은 없다.A3
(5)h 의 값은 m 이하이거나 m + j 꼴이므로 {1, …, m+n} 안에 있다.(2), (1), A3
(6)h(x) = h(y) 라 하자. (4) 에 의해 두 값은 같은 경우에 속하므로 x 와 y 는 함께 A 에 있거나 함께 B 에 있다.(4), (2)
(7)f 와 g 는 단사이므로 x = y 다. h 는 단사다.(6), (1), D1
(8)k ≤ m 이면 f(x) = k 인 x ∈ A 가 있고, k = m + j 이면 g(x) = j 인 x ∈ B 가 있다. h 는 전사다.(4), (1), D1
(9)h 는 전단사이므로 |A ∪ B| = m + n(3), (5), (7), (8), D1
∎
따름정리 C1
배반이 아닌 두 유한집합에 대하여 |A ∪ B| = |A| + |B| − |A ∩ B|
증명.
(1)A ∪ B = A ∪ (B∖A) 이고 두 집합은 배반이다.A4, D2
(2)|A ∪ B| = |A| + |B∖A|(1), T2
(3)B = (A∩B) ∪ (B∖A) 이고 두 집합은 배반이다.A5, D2
(4)|B| = |A∩B| + |B∖A|(3), T2
(5)|B∖A| = |B| − |A∩B|(4), A6
(6)|A ∪ B| = |A| + |B| − |A∩B|(2), (5)
(7)A ∩ B = ∅ 이면 |A∩B| = 0 이므로 (6) 은 T2 로 돌아간다.(6), D2, D1
(8)A ∩ B ≠ ∅ 이면 |A| + |B| 는 A ∩ B 의 원소를 두 번 센다. 그 초과분이 정확히 |A∩B| 다.(6), N
∎
비고
A3 은 이 증명에서 제거할 수 있는가.
곱의 법칙과 합의 법칙은 같은 방식으로 증명되었다. 제거하면 두 법칙이 함께 무너지는지 확인하라.