무한집합의 분류

제 6 장

무한집합의 분류

1

이 장에서 다루는 내용

• 유한집합, 무한집합의 정의와 성질

• 집합의 대등

• 가부번집합, 비가부번집합

• 가산집합, 비가산집합

제 1 절 유한집합과 무한집합

이 장에서는 무한집합의 특성에 대해서 알아본다. 무한집합의 특성을 자세히 알아보기 위하여 데디킨트(Dedekind)가 정의한 무한집합의 정의를 사용하여 이론을 전개하기로 하자.

정 의 6.1 무한집합(infinite set): 적당한 진부분집합과 일대일 대응이

존재하는 집합

유한집합(finite set): 무한 집합이 아닌 집합

참 고 6.2 X가 무한집합이 될 필요충분조건은 X에서 X로 가는 전사가 아닌 단사함수가 존재하는 것이다. 즉,

X가 무한집합

⇐⇒ f : X → X이고 f(X) ̸= X인 단사함수가 존재

[[ 예 ]] 6.3 공집합과 한원소 집합(singleton set)은 유한집합이다.

풀이. 공집합의 진부분집합이 존재하지 않으므로 ϕ은 무한집합일 수 없다.

그러므로 ϕ은 유한집합이다.

임의의 한원소 집합 {a}에 대하여 이 집합의 진부분집합은 공집합 뿐이다.

그런데 {a}와 ϕ 사이에는 일대일 대응이 존재하지 않는다.

따라서 {a}는 유한집합이다.

[[ 예 ]] 6.4 (1) 자연수의 집합 N은 진부분 집합인 짝수의 집합 Ne과 일대일 대응이 되므로 무한집합이다.

(2) 짝수의 집합 Ne도 진부분 집합인 4의 배수의 집합과 일대일 대응이 되므 로 무한집합이다.

정 리 6.5 (1) X : 무한집합, X ⊆ Y =⇒ Y : 무한집합 (2) Y : 유한집합, X ⊆ Y =⇒ X : 유한집합

증명. (1) X가 무한집합이므로 f : X → X이고 f(X) ̸= X인 단사함수가 있다.

지금 함수 g : Y → Y 를

g(y) =







f (y), y ∈ X일 때 y, y ∈ Y − X일 때

로 정의하면 g는 단사함수이다(그림 참조).

(∵) g(y) = g(y^′)

=⇒ g(y) ∈ X 또는 g(y) ∈ Y − X이다.

i) g(y)∈ X일 경우:

=⇒ g(y^′)∈ X

=⇒ f(y) = g(y) = g(y^′) = f (y^′)

=⇒ y = y^′ (∵ f : 단사) ii) g(y) ∈ Y − X일 경우:

=⇒ g(y^′)∈ Y − X

=⇒ y = g(y) = g(y^′) = y^′

=⇒ y = y^′

따라서 i)과 ii)에 의해 g는 단사함수이다.

또한 g(Y ) ̸= Y 이다.

(∵) f : X → X가 전사함수가 아니므로

∃x0 ∈ X, [f(x) ̸= x0,∀x ∈ X]

=⇒ x0 ∈ Y 이고 ∀y ∈ Y, g(y) ̸= x0. 따라서 g(Y ) ̸= Y 이다.

∴ Y : 무한집합

(2) X가 무한집합이라고 가정하자.

위 (1)에 의해 X ⊆ Y 이므로 Y 도 무한집합이다.

이는 가정에 모순이 된다.

따라서 X는 유한집합이다. 

[[ 예 ]] 6.6 N ⊆ Q이므로 유리수의 집합 Q는 무한 집합이다.

N ⊆ R이므로 실수의 집합 R은 무한 집합이다.

정 리 6.7 f : X → Y : 전단사함수 (1) X : 무한집합 =⇒ Y : 무한집합 (2) X : 유한집합 =⇒ Y : 유한집합

증명. X가 무한집합이므로 전사가 아닌 단사함수 g : X → X가 존재한다.

이제 함수 h : Y → Y 를

h(y) = (f◦ g ◦ f⁻¹)(y) 로 정의하자.

Y ^{h -}Y

f⁻¹

?

6f

X _g ^-X

그러면 세 함수 f⁻¹, g, f가 단사이므로 h도 단사함수가 된다.

또한 h : Y → Y 는 전사함수가 아니다.

(∵) g(X) ̸= X

=⇒ f(g(X)) ̸= f(X) (∵ f : 전단사)

=⇒ f(g(f⁻¹(Y ))) ̸= f(f⁻¹(Y )) (∵ f⁻¹(Y ) = X)

=⇒ h(Y ) ̸= 1Y(Y ) = Y 따라서 h(Y ) ̸= Y 이다.

따라서 Y 는 무한집합이다.

(2) 만일 Y 가 무한집합이면 f⁻¹ : Y → X가 전단사함수이므로, X도 무한집합이 된다.

이것은 가정에 모순이 되므로 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가 존재한다.