5.1 유한집합과 무한집합
Theorem 1 (1) X는 무한집합이고 X ⊆ Y 이면 Y 는 무한집합이다.
(2) 임의의 유한집합의 부분집합은 유한집합이다.
Proof. (1) X는 무한집합이고 X ⊆ Y 이라하자. 정의에 따라 단사함수 f : X → X 가 존재하고, f (X)는 X의 진부분집합이다. 이제 함수 g : Y → Y 를 다음과 같이 정의하자.
g(y) =f (y) y ∈ X y y ∈ Y − X
그러면 g : Y → Y 는 단사함수이고 f (X) ⊂ X이므로 g(Y )는 Y 의 진부분집 합이다.
(2) X ⊆ Y 이라하자. 만일 X가 무한집합이면 (1)에 의하여 Y 도 무한집 합이다. 따라서 Y 가 유한집합이면 X도 유한집합이다.
Theorem 2 (1) g : X → Y 가 일대일 대응이고 X가 무한집합이면 Y 도 무 한집합이다.
(2) g : X → Y 가 일대일 대응이고 X가 유한집합이면 Y 도 유한집합이 다.
Proof. (1) X를 무한집합이라하자. 정의에 의하여 단사함수 f : X → X 가 존재하고 f (X)는 X의 진부분집합이다. 가정에 의하여 g : X → Y 는 일 대일 대응이므로 g−1 : Y → X도 일대일 대응이다. 따라서
h = g ◦ f ◦ g−1 : Y → Y
는 단사함수이고
h(Y ) = (g ◦ f ◦ g−1)(Y ) = (g ◦ f )(g−1(Y )) = (g ◦ f )(X) = g(f (X)) f (X)는 X의 진부분집합이고 g : X → Y 는 일대일 대응이므로 h(Y )는 Y 의 진부분집합이다.
(2) X가 유한집합이면 일대일 대응 f : {1, 2, · · · , n} → X 이 존재한 다. (for some n ∈ N). g : X → Y 는 일대일 대응이므로 h = g ◦ f : {1, 2, · · · , n} → Y 도 일대일 대응이다. 따라서 Y 도 유한집합이다.
Theorem 3 X가 무한집합이고 x0는 X의 임의의 원소라 하면 X − {x0}는 무한집합이다.
Proof. X가 무한집합이므로 정의에 의하여 단사함수 f : X → X가 존 재하고 f (X) ⊂ X이다.
Case 1. x0 ∈ f (X)
x0 ∈ f (X)이므로 적당한 x1이 존재하여 f (x1) = x0를 만족한다. 함수 g : X − {x0} → X − {x0}를 다음과 같이 정의하자.
g(x) =f (x) x 6= x1 x2 x = x1 ∈ X − {x0}
여기서 x2 ∈ X − f (X)이다. 그러면 g : X − {x0} → X − {x0}는 단사함수이 고
g(X − {x0}) = f (X − {x0, x1}) ∪ {x2} 6= X − {x0} 따라서 X − {x0}는 무한집합이다.
Case 2. x0 ∈ X − f (X)
함수 g : X − {x0} → X − {x0}를 다음과 같이 정의하자. 각 x ∈ X − {x0}에 대하여 g(x) = f (x). 그러면 f : X → X가 단사함수이므로 g : X − {x0} → X − {x0}도 단사함수이다. 결국
g(X − {x0}) = f (X − {x0}) ⊂ X − {x0}
이므로 X − {x0}는 무한집합이다. 어느경우이던 X − {x0}는 무한집합이다.
Exercise
1. 집합 A가 무한집합이면 A × A도 무한집합임을 보여라.
Solution. A가 무한집합이므로 단사함수 f : A → A가 존재하고 f (A) ⊂ A이다. A × A에서의 함수를 다음과 같이 정의하자.
f × f : A × A → A × A by f × f (a, b) = (f (a), f (b))
그러면 f × f 는 단사함수이고 f × f (A × A) ⊂ A × A(why?)이다. 따라 서 A × A도 무한집합이다.
2. 집합 A와 B가 각각 무한집합이면 A ∪ B도 무한집합임을 보여라.
Solution. 집합 A와 B가 각각 무한집합이므로 단사함수 f : A → A와 g : B → B가 존재하고 f (A) ⊂ A, g(B) ⊂ B이다. 함수 f ∪g : A∪B → A ∪ B를 다음과 같이 정의하자.
f ∪ g(x) =f (x) x ∈ A g(x) x ∈ B
그러면 f ∪ g는 단사함수이고 f ∪ g(A ∪ B) ⊂ A ∪ B이므로 A ∪ B는 무 한집합이다.
3. 집합 A1, A2, · · · An이각각 유한집합이면 A1 ∪ A2∪ · · · ∪ An도 유한집 합임을보여라.
Solution. 풀이 각자가....
5.2 집합의 동치
Theorem 4 1. 임의의 가부번집합의 부분집합으로서 무한집합인 것은 가 부번집합이다.
2. 가산집합의 임의의 부분집합은 가산집합이다.
Proof. 1. 갑부번집합 X를 {x1, x2, x3, · · · }라 하고, Y ⊆ X라 하자. 또 한 Y 를 무한집합이라하자. Y 의 원소 중 그 첨자가 가장 작은 것을 n1이라하 자. 즉, xn1 ∈ Y . 다음에 Y − {xn1}의 원소 중 그 첨자가 가장 작은 것을 n2, 즉 xn2 ∈ Y − {xn1}. 이와같은 방법으로 xnk ∈ Y − {xn1, xn2, · · · , xnk−1를 선 택할 수 있다. 앞의 정리 3에서 각 집합 Y − {xn1, xn2, · · · , xnk−1는 무한집합 이므로 각집합은 공집합이 아니다. 이제 각 k ∈ N에 대하여 f : N → Y 를 f (k) = xnk로 정의하면 f 는 전단사함수이다. 따라서 N ∼ Y 이므로 Y 는 가 부번집합이다.
2. 가산집합의 정의에 의해 가산집합의 부분집합은 유한집합 또는 무한집 합이다. 무한집합이면 1에 의하여, 가부번이므로 임의의 부분집합은 가산집 합이다.
Theorem 5 1. A, B가 가부번집합이면, A ∪ B 도 가부번집합이다.
2. n개의 집합 A1, A2, · · · , An이 모두 가부번집합이면, 이들의 합집합 A1 ∪ A2∪ · · · ∪ An
도 가부번집합이다.
Proof. 다음 두경우로 나누어 증명한다.
Case 1. A ∩ B = ∅
A ∼ N, N ∼ No 이므로 A ∼ No. 여기서 No는 양의 홀수의 집합이다. 같 은방법으로 Ne를 짝수집합이라하면 B ∼ N, N ∼ Ne이므로 B ∼ Ne이다. 그 러면
A ∪ B ∼ Ne∪ No+ N 따라서, A ∪ B ∼ N. 즉, A ∪ B는 가부번집합이다.
Case 2. A ∩ B 6= ∅
C = B − A라 하자. 그러면 A ∪ C = A ∪ B, A ∩ C = ∅이다. 여기서 C ⊆ B는 유한집합 또는 가부번집합이다. 집합 C가 유한집합이면 A ∪ C는 가부번집합이다.(why?) 집합 C가 가부번집합이면 Case 1에 의하여 A∪C = A ∪ B는 가부번이다.
Theorem 6 집합 N × N은 가부번집합이다.
증명의 방법. N × N의 원소는 순서쌍 (n, m)으로 나타내진다. 이들 원소 를 나열하면
(1, 1) (1, 2) (1, 3) (1, 4) · · · (2, 1) (2, 2) (2, 3) (2, 4) · · · (3, 1) (3, 2) (3, 3) (3, 4) · · · (4, 1) (4, 2) (4, 3) (4, 4) · · · ... ... ... ... · · ·
원소의 순서를
(1, 1), (1, 2), (2, 1), (3, 1), (2, 2), · · · 와 같은 식으로 주면 N × N은 N과 동치임을 알 수 있다.
Exercise 다음을 증명하여라.
1. 유리수의 집합 Q는 가부번집합이다.
Solution. 각 유리수를 pq와 같이 나타내자. 여기서 p ∈ Z, q ∈ N이고 p와 q의 최대공약수는 1이다. 그러면
Q+= {p q | p
q > 0}, Q− = {−p q | p
q ∈ Q+} 로 놓으면
Q = Q+∪ Q−∪ {0}
여기서
Q+ ∼ N × N ∼ Q− 이므로 Q는 가부번집합이다.
2. 수직선에서 개구간 (0, 1)은 무한집합으로서 가부번집합이 아니다.
Solution. 먼저 각 수 x, 0 < x < 1을 0.x1x2x3· · · 와 같은 소수로 전개한 다. 여기서 각 n ∈ N에 대하여 xn ∈ {0, 1, 2, · · · , 9}, 즉
1
3 = 0.333 · · · ,
√2
2 = 0.707106 · · ·
이 경우 유한소수로 전개되는 수도 무한소수로 나타내기 위하여 유한소수 의 마지막 숫자에 1을 줄이고 숫자 9를 적도록한다. 즉 14는 0.25가 아니라 0.2499999 · · · 로 나타낸다. 이러한 약속하에 구간 (0, 1)의 두 수는 각각의 소 수전개가 같으면 같은 것으로 정의한다. 그러므로
x = 0, x1x2x3· · · = y = 0.y1y2y3· · · ⇐⇒ x1 = y1, x2 = y2· · · 또는
x 6= y ⇐⇒ xk6= yk for some k(소수점 아래 k째 자리)
이제 구간 (0, 1)이 가부번집합이라 가정하자. 그러면 일대일 대응 f : N ∼ (0, 1)이 존재함으로써 (0, 1)의 모든 원소를 다음과 같이 나타낼 수 있 다.
f (1) = 0.a11a12a13· · · f (2) = 0.a21a22a23· · · f (3) = 0.a31a32a33· · ·
...
f (k) = 0.ak1ak2ak3· · · ...
여기서 각 ajk ∈ {0, 1, 2, 3, · · · , 9}.
위에 나열된 f (k)들 중 그 어느 것과도 같지 않은 하나의 수 z ∈ (0, 1)을 다음과 같이 구성하여 (0, 1)과 N이 동치라는 것의 모순을 이끌어 낼 것이다.
각 k ∈ N에 대하여 akk6= 5이면 zk= 5로, akk= −5이면 zk = 1이라 놓는 다. 그러면 z = 0.z1z2z3· · · 는 (0, 1)의 원소이고, z1 6= a11이므로 6= f (1)이다.
z2 6= a22이므로 z2 6= f (2), · · · . 모든 k ∈ N에 대하여 zk 6= akk임로 z 6= f (k).
따라서 z는 f (n)의 그 어느것과도 같지않다. 즉 z /∈ f (N) = (0, 1). 그러므로 z /∈ (0, 1)이고 이는 가정에 모순.
