이것은 가정에 모순이 되므로 Y 는 유한집합이다. [[ 예 ]] 6.8 (1) f :N → No, f (x) = 2x− 1는 자연수의 집합과 홀수의 집합 No 사이의 전단사 함수이므로 홀수의 집합은 무한집합이다.
(2) f : N → A, f(x) = 3x가 자연수의 집합과 3의 배수의 집합 A 사이의 전단사 함수이므로 3의 배수의 집합은 무한집합이다.
정 리 6.9 집합 X가 무한이고 x0 ∈ X이면 X − {x0}도 무한집합이다.
증명. X가 무한집합이므로
f (X)̸= X인 단사함수 f : X → X가 존재한다.
i) x0 ∈ f(X)인 경우:
∃x1 ∈ X, f(x1) = x0
이제 함수 g : X − {x0} → X − {x0}를 다음과 같이 정의하자.
g(x) =
f (x), x̸= x1일 때 x2, x = x1일 때
여기서 x2는 임의의 X − f(X)의 임의의 원소이다.
그러면 g는 단사함수이다.
또한 g는 전사함수가 아니다.
(∵) g(X − {x0})
= g(X − {x0, x1}) ∪ g({x1})
= f (X− {x0, x1}) ∪ {x2}
= (f (X)− {f(x0), f (x1)}) ∪ {x2}
̸= X − {x0} (∵ f(x0) /∈ 좌변, f(x0)∈ 우변) 즉 g는 전사함수가 아니다.
전사가 아닌 단사함수가 존재하므로, X − {x0}는 무한집합이다.
ii) x0 ∈ f(X)인 경우:/
g : X− {x0} → X − {x0}를
g(x) = f (x)로 정의하자.
그러면 f가 단사이므로 g도 단사함수이다.
그런데
g(X − {x0}) = f(X − {x0}) (6.1)
= f (X)− f({x0}) (6.2)
̸= X − {x0} (∵ f(x0) /∈ 좌변, f(x0) ∈ 우변) (6.3)
따라서 g는 전사가 아니다.
전사가 아닌 단사함수가 존재하므로, X − {x0}는 무한집합이다.
위의 두 가지 경우 모두 X − {x0}는 무한집합이다.
따름정리 6.10 집합 X가 무한집합이고 x1, x2, . . . , xn ∈ X이면,
X − {x1, x2, . . . , xn}도 무한집합이다.
[[ 예 ]] 6.11 N이 무한집합이므로 {2, 3, 4, . . . },
{5, 6, 7, . . . },
{100, 101, 102, . . . } 등도 무한집합이다.
정 의 6.12 앞으로는 임의의 k ∈ N 에 대하여 1부터 k까지의 모든 자연
수의 집합을 Nk로 나타낸다.
즉 Nk ={1, 2, 3, 4, . . . , k} .
[[ 예 ]] 6.13 N1 ={1}
N4 ={1, 2, 3, 4}
[[ 예 ]] 6.14 모든 자연수 k에 대해 Nk는 유한집합이다.
풀이. 수학적 귀납법으로 증명하자.
먼저 k = 1일 때, N1 ={1}은 한원소 집합이므로 유한집합이다.
k = n일 때 즉, Nn이 유한집합이면, Nn+1도 유한집합이다.
(∵) Nn+1이 무한집합이면
Nn =Nn+1− {n + 1}도 무한집합이다.
이것은 모순이다.
따라서 Nn+1은 유한집합이다.
그러므로 수학적 귀납법에 의해 모든 Nk는 유한집합이다.
정 리 6.15 X : 유한집합
⇐⇒ X = ϕ 이거나
X와 어떤 Nk 사이에 일대일대응이 존재한다.
증명. (⇐) 공집합이 유한집합이고 모든 Nk가 유한집합이므로, 역이 성립한 다.
(⇒ ) 대우명제를 생각하자.
즉 X가 공집합이 아니면서 모든 Nk와 일대일 대응이 존재하지 않으면 X가 무한 집합이 됨을 보이도록 하자.
X ̸= ϕ이므로 x1 ∈ X이라 하자.
그러면 X − {x1} ̸= ϕ이다.
( ∵ 만일 X − {x1} = ϕ이면 X = {x1}이 되고, 따라서 X와 N1사이에 일
대일 대응이 존재하게 되어, 가정에 모순이 되기 때문이다.) X − {x1} ̸= ϕ이므로, x2 ∈ X − {x1}를 택할 수 있다.
그러면 X − {x1, x2} ̸= ϕ이다.
. . .
마찬가지 방법으로 모든 자연수 k에 대해 xk ∈ X − {x1, x2, . . . xk−1}을 택할 수 있다.
Y ={xk | k ∈ N} 놓자.
그러면 Y 는 X의 원소를 가지고 만들어진 집합이므로 Y ⊆ X이다.
또한 Y 는 무한집합이 된다.
(∵) 함수 f : Y → Y − {x1}를
f (xk) = xk+1
로 정의하면 이 함수는 집합 Y 와 그 진부분집합 Y − {x1} 사이
의 일대일 대응이다.
그러므로 정의에 의하여 Y 는 무한집합이다.
그런데 X는 Y 의 포함집합이므로 X는 무한집합이다. [[ 예 ]] 6.16 {a, b, c}는 N3와 일대일대응이 존재하므로 유한집합이다.
{w, x, y, z}는 N4와 일대일대응이 존재하므로 유한집합이다.
{a, b, c, d, {e, f}, {g, h}}는 N6와 일대일대응이 존재하므로 유한집합이다.
{ϕ}는 N1와 일대일대응이 존재하므로 유한집합이다.
{ϕ, 1, {ϕ}, {ϕ, 1}}는 N4와 일대일대응이 존재하므로 유한집합이다.
