제 2 절 집합의 대등

제 2 절 집합의 대등

유한집합에서 원소의 개수가 같은 두 집합 사이에는 일대일 대응(전단사함수) 이 존재하고 일대일 대응이 존재하면 두 집합의 원소의 개수가 같다.

무한집합 A와 B 사이에 일대일 대응이 존재하면 이 두 집합의 원소의 개수가 같다고 볼 수 있다.

정 의 6.17 두 집합 X, Y 사이에 일대일 대응이 존재할 때 X와 Y 는대 등(equipotent)하다고 말하고 이것을 X ∼ Y 로 나타낸다.

[[ 예 ]] 6.18 Ne가 0보다 큰 짝수의 집합일 때

f :N → Ne, f (x) = 2x가 전단사함수이므로, 자연수의 집합 N과 짝수의 집 합 Ne는 대등하다. 즉 N ∼ Ne이다.

[[ 예 ]] 6.19 함수 f : N → No, f (x) = 2x− 1이 전단사함수이므로, 자연수 의 집합 N과 홀수의 집합 No는 대등하다. 즉 N ∼ No이다.

[[ 예 ]] 6.20 영이 아닌 3의 배수의 집합 A = {3n | n ∈ N}를 생각할 때, 함 수 f : N → A, f(n) = 3n이 전단사함수이므로, N ∼ A이다.

정 리 6.21 대등관계 “∼ ”는 집합족 위에서 동치관계이다.

증명. (1) 모든 집합 X에 대해 1X : X → X가 전단사함수이므로, X ∼ X이다.

(2) X ∼ Y

=⇒ ∃f : X → Y : 전단사함수

=⇒ ∃f⁻¹ : Y → X : 전단사함수

∴ Y ∼ X

(3) X ∼ Y 이고 Y ∼ Z라 하자.

=⇒ ∃f : X → Y : 전단사함수,

∃g : Y → Z : 전단사함수

=⇒ ∃g ◦ f : X → Z : 전단사함수

=⇒ X ∼ Z

따라서 관계 “∼”은 동치관계이다. 

[[ 예 ]] 6.22 (1) (0, 1)∼ (−1, 1)을 보여라.

(2) (−1, 1) ∼ R임을 보여라.

(3) (0, 1)∼ R임을 보여라.

풀이. (1) 함수 f : (0, 1) → (−1, 1)를 f(x) = 2x − 1로 정의하면 이 함수 는 전단사함수이다.

(∵) i) f(a) = f(b)

=⇒ 2a − 1 = 2b − 1

=⇒ a = b

∴ f : 단사함수 ii) y∈ (−1, 1) 놓자.

그러면 y + 1

2 ∈ (0, 1)이고, f

(y + 1 2

)

= 2· y + 1

2 − 1 = y

∴ f : 전사함수.

i), ii)에 의해서 f는 전단사함수이다.

따라서 (0, 1) ∼ (−1, 1)이다.

(2) 함수 f : (−1, 1) → R를

g(x) = tan (πx

2 )

로 정의하면 g는 전단사함수이다.

따라서 (−1, 1) ∼ R이 된다.

(3) 위에서 정의한 두 함수의 합성함수 g◦ f : (0, 1) → R는 전단사함수이다.

따라서 (0, 1) ∼ R이다.

정 리 6.23 X ∩ Z = ϕ = Y ∩ W f : X ∼ Y , g : Z ∼ W

=⇒ (f ∪ g) : (X ∪ Z) ∼ (Y ∪ W )

증명. h = f ∪ g라 정의하면 분명히 h : (X ∪ Z) → (Y ∪ W )는 함수이다.

(1) h는 단사함수이다.

∵ h(a) = h(b)라 하면 h(a) = h(b) ∈ Y 이거나 h(a) = h(b)∈ W 이다. (∵ Y ∩ W = ϕ) 만일 h(a) = h(b) ∈ Y 이면

f (a) = h(a) = h(b) = f (b)이다.

=⇒ a = b (∵ f : 단사함수) 마찬가지로 h(a) = h(b) ∈ W 이면, g(a) = h(a) = h(b) = g(b)이다.

=⇒ a = b (∵ g : 단사함수) 결국 h는 단사함수이다.

(2) h는 전사함수이다.

(∵) y ∈ Y ∪ W 라 하자.

그러면 y ∈ Y 이거나 y ∈ W 이므로,

이제 y ∈ Y 라 가정하자.

그러면 ∃x = f⁻¹(y)∈ X이고

f (x) = f (f⁻¹(y)) = y이다. (∵ f : 전단사함수 ) 그러므로 x ∈ X ∪ Z이고

h(x) = (f ∪ g)(x) = f(x) = y

마찬가지로 y ∈ W 일 때도 보일 수 있다.

따라서 h = f ∪ g : 전사함수

∴ (1)과 (2)에 의해 h = f ∪ g는 전단사함수이다.  [[ 예 ]] 6.24 {1, 2, 3} ∼ {a, b, c}, {4, 5} ∼ {x, y}이므로

{1, 2, 3, 4, 5} ∼ {a, b, c, x, y}이다.

정 리 6.25 f : X ∼ Y g : Z ∼ W

=⇒ X × Z ∼ Y × W

증명. 함수 h : X × Z → Y × W 를 h(x, z) = (f (x), g(z))로 정의하자.

f와 g가 함수이므로 분명히 h는 함수가 된다.

(1) h는 단사함수이다.

∵ h(x, z) = h(x^′, z^′)

=⇒ (f(x), g(z)) = (f(x^′), g(z^′))

=⇒ f(x) = f(x^′)∧ g(z) = g(z^′)

=⇒ x = x^′∧ z = z^′ (∵ f, g :전단사함수)

=⇒ (x, z) = (x^′, z^′) (2) h는 전사함수이다.

(∵) (y, w) ∈ Y × W

=⇒ y ∈ Y ∧ w ∈ W

=⇒ ∃x ∈ X, f(x) = y이고

∃z ∈ Z, g(z) = w이다. (∵ f, g :전단사함수) 그러므로 ∃(x, z) ∈ X × Z이고

h(x, z) = (f (x), g(z)) = (y, w)이다.

∴ h : 전사함수

 [[ 예 ]] 6.26 N ∼ Ne이고 N ∼ Ne이므로

N × N ∼ Ne× Ne이다.

[[ 예 ]] 6.27 (0, 1)∼ (−1, 1)이고 (0, 1) ∼ (−1, 1)이므로 (0, 1)× (0, 1) ∼ (−1, 1) × (−1, 1)이다.

[[ 예 ]] 6.28 (0, 1)∼ R이고 (0, 1) ∼ R이므로 (0, 1)× (0, 1) ∼ R × R이다.