3.3 단사, 전사, 전단사함수

(1)

3.2 함수의 정의

Theorem 6 함수 f : X −→ Y 와 Y ⊆ W 인 집합 W 에 대하여 f : X −→

W 는 함수이다.

Proof. f : X −→ Y 가 함수이므로 f ⊆ X × Y 이고, Y ⊆ W 이므로 f ⊆ X × W 이므로 F0이 만족된다. 함수의 정의 F1, F2은 f : X −→ Y 가 함

수이므로 성립한다.

Theorem 7 두 함수 f : X −→ Y 와 g : X −→ Y 에 대하여, f = g ⇐⇒ f (x) = g(x) for all x ∈ X

Proof. f = g를 가정하자. 그러면 임의의 x ∈ X에 대하여 y = f (x) ⇐⇒ (x, y) ∈ f ⇐⇒ (x, y) ∈ g ⇐⇒ y = g(x) 따라서, f (x) = g(x).

역으로, 모든 x ∈ X에 대하여 f (x) = g(x)라 하자. 그러면 (x, y) ∈ f ⇐⇒ y = f (x) ⇐⇒ y = g(x) ⇐⇒ (x, y) ∈ g

따라서 f = g.

Theorem 8 두 함수 f : A −→ C, g : B −→ D에서 정의역의 교집합 A ∩ B 의 임의의 원소 x에 대하여 f (x) = g(x)일 때 f 와 g의 합 f ∪ g는 다음과 같 이 정의된 함수 h = f ∪ g : A ∪ B −→ C ∪ D와 같다. 여기서

h(x) = f (x) x ∈ A g(x) x ∈ B

Proof. f 와 g가 함수이므로 f ⊆ A × C, g ⊆ B × D 이므로 h = f ∪ g ⊆ (A × C) ∪ (B × D) ⊆ (A ∪ B) × (C ∪ D)

(2)

따라서 F0을 만족한다.

모든 x ∈ A ∪ B 에 대하여 h(x)는 정의 된다. 즉, F1을 만족한다. 이제 F2를 확인하자. x ∈ A ∪ B이면 다음의 세 경우가 있다.

(1) x ∈ A − B (2) x ∈ B − A (3) x ∈ A ∩ B

(1)의 경우 h(x) = f (x)이므로 F2를 만족하고, (2)의 경우 h(x) = g(x)이 므로 F2를 만족한다. (3)의 경우 f (x) = g(x)이므로 F2를 만족한다. 즉, h는

F2를 만족한다.

Exercise 정의역과 공역이 같은 두 함수 f : X −→ Y , g : X −→ Y 에 대 하여, f ⊆ g 이면 f = g임을 증명하여라.

Proof. Theorem 7을 이용하여 증명한다.

임의의 x ∈ X에 대하여 y = f (x)라 하자. 그러면, f ⊆ g이므로 (x, y) ∈ f =⇒ (x, y) ∈ g =⇒ y = g(x)

따라서 모든 x ∈ X에 대하여 f (x) = g(x)이다. 즉, Theorem 7에 의하여

f = g.

3.3 단사, 전사, 전단사함수

Exercises

1. f : A −→ B가 단사함수이고 C ⊆ A 일 때, 제한함수 f |_C : C −→ B 가 단사함수임을보여라.

(3)

풀이.

f |C(x1) = f |C(x2) =⇒ f (x1) = f (x2) (f |C 의 정의)

=⇒ x₁ = x₂ (f 는 injective(단사))

2. 집합 A에 대하여

f = {(x, (x, x)) | x ∈ A}

라 하면, f : A −→ I_A는 전단사함수임을보여라.

풀이. 항등함수의 정의는

I_A= {(x, x) | x ∈ A}

이고 함수 f 는 다음과 같이 정의 된다.

f (x) = (x, x) for all x ∈ A

(1) f 가 단사함수임을 보이자.

f (x₁) = f (x₂) =⇒ f (x₁) = (x₁, x₁) = (x₂, x₂) = f (x₂)

=⇒ x₁ = x₂ (순서쌍의 정의) (2) f 가 전사함수임을 보이자.

임의의 (x, x) ∈ I_A 에 대하여, I_A, x ∈ A의 정의에 의하여 x ∈ A.

f 의 정의에 의하여 f (x) = (x, x). 따라서, 모든 (x, x) ∈ I_A에 대하여,

f (x) = (x, x) 인 x ∈ A가 존재한다.

3. 두 함수 f : A −→ B, g : C −→ D에 대하여, 두 함수의 곱f × g : A × C −→ B × D을 다음과 같이 정의한다.

f × g(x, y) = (f (x), g(y)) for every (x, y) ∈ A × C

(4)

(1) f × g : A × C −→ B × D가 함수임을 증명하여라.

(2) f 와 g가 단사(전사)함수면, f × g도 단사(전사)함수임을 보여라.

풀이. (1) F0. f : A −→ B와 g : C −→ D 가 함수이므로

f ⊆ A × B, g ⊆ C × D =⇒ f × g ⊆ (A × B) × (C × D) = (A × C) × (B × D)

F1. f : A −→ B와 g : C −→ D 가 함수이므로, 임의의 x ∈ A, y ∈ C에 대하여, f (x) ∈ B, g(y) ∈ D가 각각 존재한다. 그러면 (f (x), g(y)) ∈ B × D이고 f × g(x, y) = (f (x), g(y)).

F2. f : A −→ B와 g : C −→ D 가 함수이므로, (x₁, y₁) = (x₂, y₂)이면 (f (x₁), g(y₁)) = (f (x₂), g(y₂)).

따라서 f × g는 함수이다.

4. 자연수 집합 N과 짝수의 집합 사이에 일대일 대응이 존재함을 보여라.

풀이. f : N −→ {n ∈ N | n = 2k for some k ∈ N}을 다음과 같이 정 의하자. 모든 n ∈ N에 대하여, f(n) = 2n. 그러면 f는 전단사함수이

다.

5. 자연수 집합 N과 홀수의 집합 사이에 일대일 대응이 존재함을 보여라.

풀이. f : N −→ {n ∈ N | n = 2k − 1 for some k ∈ N}을 다음과 같이 정의하자. 모든 n ∈ N에 대하여, f(n) = 2n − 1. 그러면 f는 전단사함

수이다.

6. 집합 A와 B는 각각 a, b개의 원소를 지닌 집합일 때, a > b이면, 두 집 합 A, B 사이에 단사함수는 존재하지 않음을 보여라.

풀이. a > b이므로 처음 b개의 원소는 집합 B의 원소와 대응시키면 남아있는 원소는 이미 대응된 원소와 대응 된다. 따라서 단사함수가 될

수 없다.

(5)

7. 위 문제에서 a ≤ b이면, 두 집합 A, B 사이에 단사함수의 갯수는 _(b−a)!^a!

임을 설명하여라.

3.4 집합의 상과 역상

Theorem 9 함수 f : X −→ Y 에 대하여, A, B가 X의 부분집합일 때, A ⊆ B =⇒ f (A) ⊆ f (B)

C, D 가 Y 의 부분집합일 때,

C ⊆ D =⇒ f⁻¹(C) ⊆ f⁻¹(D)

Proof.

y ∈ f (A) =⇒ y = f (a), a ∈ A

=⇒ y = f (a), a ∈ B (가정 A ⊆ B)

=⇒ y ∈ f (B)

x ∈ f⁻¹(C) =⇒ f (x) ∈ C

=⇒ f (x) ∈ D (가정 C ⊆ D)

=⇒ x ∈ f⁻¹(D)

Theorem 10 함수 f : X −→ Y 에 대하여, {Ci}i∈I은 X 의 부분집합족 이고 {D_i}i∈I은 Y 의 부분집합족이라 할 때, 다음의 관계가 성립한다.

(1) f ( ∪

i∈IC_i) = ∪

i∈If (C_i) (2) f ( ∩

i∈IC_i) ⊆ ∩

i∈If (C_i)

(6)

(3) f⁻¹( ∪

i∈ID_i) = ∪

i∈If⁻¹(D_i) (4) f⁻¹( ∩

i∈IDi) = ∩

i∈If⁻¹(Di) Proof. (1)

y ∈ f ( ∪

i∈ICi) ⇐⇒ y = f (x) for some x ∈ ∪

i∈ICi

⇐⇒ y = f (x) for some x ∈ Ci, for some i ∈ I

⇐⇒ y ∈ f (C_i) for some i ∈ I

⇐⇒ y ∈ ∪

i∈If (C_i) 따라서

f ( ∪

i∈IC_i) = ∪

i∈If (C_i) (2) 모든 i ∈ I에 대하여 ∩

i∈ICi ⊆ Ci이므로 정리 9에 의하여 f ( ∩

i∈IC_i) ⊆ f (C_i) for all i ∈ I 따라서

f ( ∩

i∈IC_i) ⊆ ∩

i∈If (C_i) (3)

x ∈ f⁻¹( ∪

i∈IDi) ⇐⇒ f (x) ∈ ∪

i∈IDi

⇐⇒ f (x) ∈ D_i for some i ∈ I

⇐⇒ x ∈ f⁻¹(D_i) for some i ∈ I

⇐⇒ x ∈ ∪

i∈If⁻¹(D_i) 따라서

f⁻¹( ∪

i∈ID_i) = ∪

i∈If⁻¹(D_i)

(4) (3)의 증명에서 ∪을 ∩로 바꾸고, for some 을 for all 로 바꾸면 된다.

(7)

Exercise 함수 f : X −→ Y 가 단사함수이면 f ( ∩

i∈IC_i) = ∩

i∈If (C_i) Solution. 정리 10의 (2)에서 f ( ∩

i∈IC_i) ⊆ ∩

i∈If (C_i)는 증명되었으므로

i∈I∩f (Ci) ⊆ f ( ∩

i∈ICi)을 보이면된다.

y ∈ ∩

i∈If (C_i) =⇒ y ∈ f (C_i) for all i ∈ I

그러면 y = f (x_i), for all x_i ∈ C_i. 가정에서 f : X −→ Y 가 단사함수 이므로 x_i들은 모두같다. 이를 x₀라 하면 x₀ ∈ C_i for all i ∈ I. 따라서

y = f (x₀), x₀ ∈ C_i for all i ∈ I

=⇒y = f (x₀), x₀ ∈ ∩

i∈IC_i

=⇒y ∈ f ( ∩

i∈IC_i) 따라서 ∩

i∈If (Ci) ⊆ f ( ∩

i∈ICi).

Exercise 함수 f : X −→ Y 에 대하여, B와 C가 Y 의 부분집합일 때, f⁻¹(B − C) = f⁻¹(B) − f⁻¹(C)

Solution.

x ∈ f⁻¹(B − C) ⇐⇒ f (x) ∈ B − C

⇐⇒ f (x) ∈ B and f (x) /∈ C

⇐⇒ x ∈ f⁻¹(B) − f⁻¹(C) 그러므로 x ∈ f⁻¹(B − C) ⇐⇒ x ∈ f⁻¹(B) − f⁻¹(C). 따라서

f⁻¹(B − C) = f⁻¹(B) − f⁻¹(C)

(8)

3.5 함수의 합성과 역함수

Theorem 13 함수 f : X → Y 가 전단사함수이면, f⁻¹ : Y → X도 전단 사함수이다.

Proof. 1. f⁻¹ : Y → X는 함수임을 보이자.

f ⊆ X × Y 이므로, 역그래프의 정의에 의하여 f⁻¹ ⊆ Y × X이다. 따라 서 F₀을 만족한다. f : X → Y 가 전단사함수이므로 임의의 y ∈ Y 에 대하여 x ∈ X가 유일하게 존재하여 (x, y) ∈ f 이다. 따라서 (y, x) ∈ f⁻¹. 즉, F₁이 만족된다. F₂가 성립함을 보이기 위하여

(y, x₁) ∈ f⁻¹ and (y, x₂) ∈ f⁻¹ =⇒ (x₁, y) ∈ f and (x₂, y) ∈ f

=⇒ y1 = y2

2. f⁻¹ : Y → X가 단사함수임을 보이자.

f⁻¹(y₁) = x = f⁻¹(y₂) =⇒ y₁ = f (x) = y₂ =⇒ y₁ = y₂

3. f⁻¹ : Y → X가 전사함수임을 보이자.

x를 X의 임의의 원소라하자. 그러면 f (x) = y ∈ Y 이므로 x = f⁻¹(y).

Theorem 14 함수 f : X → Y 가 가역함수이면, f : X → Y 는 전단사함 수이다.

Proof. 1. f : X → Y 는 단사함수이다.

f (x1) = y = f (x2) =⇒ (y, x1) ∈ f and (y, x2) ∈ f

=⇒ (x₁, y) ∈ f⁻¹ and (x₂, y) ∈ f⁻¹

=⇒ x₁ = x₂

(9)

위의 마지막 =⇒은 f⁻¹이 함수이므로 성립한다.

2. f : X → Y 는 전사함수이다.

임의의 y ∈ Y 에 대하여, f 가 역함수 f⁻¹을가지므로 f⁻¹(y) = x임 x ∈ X가 존재한다. 더우기 y = f (x)를 만족하므로 f : X → Y 는 전사함수이다.

Theorem 15 함수 f : X → Y 가 가역함수이면, f⁻¹◦ f = I_X and f ◦ f⁻¹ = I_Y

Proof. f : X → Y 가 역함수 f⁻¹ : Y → X를 가지므로 y = f (x) ⇐⇒ x = f⁻¹(y)

따라서

(f⁻¹◦ f )(x) = f⁻(f (x)) = f⁻¹(y) = x = I_X(x) 이고

(f ◦ f⁻¹)(y) = f (f⁻¹(y)) = f (x) = y = IY(y)

Theorem 16 두 함수 f : X → Y 와 g : Y → X에 대하여 g ◦ f = IX이 고 f ◦ g = I_Y가 성립하면, f : X → Y 는 전단사함수이고, g = f⁻¹이다.

Theorem 17 f : X → Y 가 단사함수이면, g ◦ f = I_X를 만족하는 함수 g : Y → X가 존재한다. 역으로, g ◦ f = I_X를 만족하는 함수 g : Y → X가 존재하면, f : X → Y 가 단사함수이다.

Theorem 18 두 함수 f : X → Y , g : Y → X에 대하여 (1) f 와 g가 단사함수이면, g ◦ f 도 단사함수이다.

(2) f 와 g가 전사함수이면, g ◦ f 도 전사함수이다.

(3) f 와 g가 전단사함수이면, g ◦ f 도 전단사함수이다.

(10)

Proof. (1) (g ◦ f )(x₁) = (g ◦ f )(x₂) =⇒ g(f (x₁)) = g(f (x₂)). g가 단 사함수이므로 f (x₁) = f (x₂)이고 f 가 단사함수이므로 x₁ = x₂이다. 따라서 g ◦ f 는 단사함수이다.

(2) 임의의 x ∈ X에 대하여 g : Y → X가 전사함수이므로, g(y) = x를 만 족하는 y ∈ Y 가 존재한다. 또한, f : X → Y 가 전사함수이므로 y에 대하여 f (x₀) = y를 만족하는 x₀ ∈ X가 존재한다. 따라서

(g ◦ f )(x₀) = g(f (x₀)) = g(y) = x 이므로 g ◦ f 도 전사함수이다.

(3) (1)과 (2) 에 의하여 f 와 g가 전단사함수이면, g ◦ f 도 전단사함수이 다.

Exercise

1. 함수 f : X → Y 에 대하여, I_Y ◦ f = f 이고 f ◦ I_X = f 임을 증명하여라.

Solution. 항등함수의 정의와 6쪽의 Theorem 7에 의하여 (I_Y ◦ f )(x) = I_Y(f (x)) = f (x)

(f ◦ I_X)(x) = f (I_X(x)) = f (x)

2. 두 함수 f : X → Y , g : Y → X에 대하여, g ◦ f 가 단사함수이면 f 가 단사함수임을보여라.

Solution. g : Y → X가 함수이고, g ◦ f 가 단사함수이므로 f (x₁) = f (x₂) =⇒ g(f (x₁)) = g(f (x₂))

=⇒ (g ◦ f )(x₁) = (g ◦ f )(x₂)

=⇒ x₁ = x₂

(11)

3. 두 함수 f : X → Y , g : Y → X에 대하여, g ◦ f 가 전사함수이면 g가 전사함수임을 보여라.

Solution. g ◦ f : X → X가 전사함수이므로, 임의의 x ∈ X에 대하 여 (g ◦ f )(x₀) = x를 만족하는 x₀ ∈ X가 존재한다. y₀ = f (x₀)라 하면 y₀ ∈ Y 이고 g(y₀) = g(f (x₀)) = x를 만족하므로 g가 전사함수이다.

4. 두 함수 f : X → Y , g : Y → X에 대하여, g ◦ f 가 전단사함수이면 f 가 단사함수, g는 전사함수임을 보여라.

Solution. g ◦ f 가 전단사함수이면, g ◦ f 가 단사(전사)함수이므로, 2(3)에 의하여 f (g)는 단사(,전사)함수이다.

5. f 가 단사함수, g는 전사함수 이지만 g ◦ f 가 전단사함수가 아닌 예를 하 나 들어보아라.

Solution. X = {1, 2}, Y = {1, 2, 3}라 하자. f : X → Y 는 f (1) = 1, f (2) = 3으로 정의 하고 g : Y → X를 g(1) = 1, g(2) = 2, g(3) = 1로 정의하면 (g ◦ f )(1) = (g ◦ f )(2) = 1이 되어 g ◦ f 가 전단사함수가 아니 다.