Chapter 5

(1)

Chapter 5 가부번집합

(Denumerable Sets)

(2)

5.1 유한집합과 무한집합

가장 초보적인 정의로써 유한집합은 원소의 수를 자연수로 나타낼 수 있는 집합으로 정의하며 유한집합이 아닌 집합을 무한집합이라고 정의한다. 이러 한 무한, 유한집합의 정의는 좀더 세련되고 명확한 수학적 정의로 발전하였 다. 그 중에서 Dedekind(1831-1916)의 무한집합과 유한집합의 정의를 따 를 것이다.

Definition 5.1.1 주어진 집합 A가 공집합이거나 전단사함수 f : A −→ {1, 2, · · · , n} for some n ∈

N

가 존재하면 A를 유한집합이라고 한다. 유한집합이 아닌 집합을 무한집합이 라고 한다. 만일 A =

∅

이면 A는 0개의 원소를 갖는다고 하고, 전단사함수 f : A −→ {1, 2, · · · , n}가 존재하면 A는 n개의 원소를 갖는다라고 한다.

Definition 5.1.2 공집합이 아닌 집합 X에 대하여, X의 진부분집합 Y 가 존재하여 X와 Y 사이에 일대일 대응이 존재할 때, X를 무한집합이라고 한 다. 무한집합이 아닌 집합을 유한집합이라고 한다.

Remark 주어진 집합 X에 대하여, 단사힘수 f : X −→ X를 정의할 수 있 고 f (X)가 X의 진부분집합이라면 X는 무한집합이다. 예를들면, 자연수의 집합

N

은 무한집합이다. f (n) = 2n 으로 정의 되는 f :

N

^−→

N

^{은 단사함} 수이고 f (

N

⁾ 은 짝수전체집합이다.

Example 정수, 유리수 실수 집합은 무한집합이다.

1

(3)

Theorem 1 (1) X는 무한집합이고 X ⊆ Y 이면 Y 는 무한집합이다.

(2) 임의의 유한집합의 부분집합은 유한집합이다.

Proof. (1) X는 무한집합이고 X ⊆ Y 이라하자. 정의에 따라 단사함 수 f : X → X 가 존재하고, f (X)는 X의 진부분집합이다. 이제 함수 g : Y → Y 를 다음과 같이 정의하자.

g(y) =

n

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⁻¹ : Y → X도 일대일 대응이다. 따라서

h = g ◦ f ◦ g⁻¹ : Y → Y

2

(4)

는 단사함수이고

h(Y ) = (g ◦ f ◦ g⁻¹)(Y ) = (g ◦ f )(g⁻¹(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) =

n

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}

(5)

따라서 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도 무한집합임을 보여라.

2. 집합 A와 B가 각각 무한집합이면 A ∪ A도 무한집합임을 보여라.

3. 집합 A1, A2, · · · A_n이 각각 유한집합이면 A1∪ A2∪ · · · ∪ A_n도 유한집 합임을 보여라.

(6)

5.2 집합의 동치

두 유한집합 X와 Y 에 있어서 일대일 대응 f : X → Y 가 존재하면 그리고 그 때에만 X와 Y 는 같은 수의 원소를 갖는다. X와 Y 가 무한집합일 때, “같은 수의 원소”의 뜻을 쉽게 이해할 수 있도록 다음의 정의부터 내린다.

Definition 5.2.1 두 집합 X와 Y 에 대하여 일대일 대응 f : X → Y 가 존 재할 때, X와 Y 는 동치(equivalent)라고 말하고 X ∼ Y 로 나타낸다.

Remark: 집합족 F 위의 관계 R을 다음과 같이 정의한다.

(A, B) ∈ R ⇐⇒ A ∼ B 그러면 R은 집합족 F 위의 동치관계이다.

Example

1. (0, 1) ∼ (−1, 1) 2. (−1, 1) ∼

R

3. (0, 1) ∼

R

Definition 5.2.2 집합 X에 대하여 X ∼

N

일 때, X를 가부번집 합(denumerable set)이라고 한다. 한편 유한집합 또는 가부번집합 어느 것이나 가산집합(countable set)라 한다.

Example 정수, 유리수 실수 집합은 무한집합이다.

3

(7)

가부번집합은 번호를 붙힐 수 있는 집합, 가산집합은 셀 수 있는 집합 이라고 생각하면 편리하다. 집합 X가 가부번집합이면 일대일 대응 f :

N

^{→ X를 이} 용하여 X의 각 원소에 번호를 붙힐 수 있다:

f (1) = x1, f (2) = x2, f (3) = x3, · · · , f (k) = x_k, · · ·

라고 놓아 집합 X를 {x1, x2, · · · , x_k, · · · }와 같이 나타냄으로써 X의 모든 원 소에 번호를 붙힌다. 또한 자연수를 이용하여 X의 원소에 순서를 결정하여 원소를 셀 수도 있음을 알 수 있다.

Theorem 4 1. 임의의 가부번집합의 부분집합으로서 무한집합인 것은 가 부번집합이다.

2. 가산집합의 임의의 부분집합은 가산집합이다.

Theorem 5 1. A, B가 가부번집합이면, A ∪ B 도 가부번집합이다.

2. n개의 집합 A1, A2, · · · , An이 모두 가부번집합이면, 이들의 합집합 A1 ∪ A2 ∪ · · · ∪ A_n

도 가부번집합이다.

Theorem 6 집합

N

^×

N

^은 ^{가부번집합이다.}

Exercise 다음을 증명하여라.

1. 유리수의 집합

Q

^는 ^{가부번집합이다.}

2. 수직선에서 개구간 (0, 1)은 무한집합으로서 가부번집합이 아니다.

4