[이산 수학] 함수의 성질

함수의 성질

• 함수의 입력과 출력의 대응 형태에 따라 함수의 성질이 결정된다.
• 함수의 성질을 알면 정의역과 공역의 관계뿐만 아니라 공역과 치역 간의 포함 관계도 알 수 있다.
• 이는 컴퓨터 및 인공지능 시스템에서 자료의 활용을 계획하는 데 좋은 정보가 된다.
• 함수는 정의역과 공역의 대응 관계에 따라서 단사 함수, 전사 함수, 전단사 함수로 구분한다.

 

단사 함수(Injective Function, Injection, One-to-One Function) = 일대일 함수

함수 $f \; : \; X \rightarrow Y$ 가 있을 때, 임의의 두 정의역 원소 $x_{1}, \; x_{2} \; \in \; X$ 에 대하여 $x_{1} \ne x_{2}$ 이면 $f(x_{1}) \ne f(x_{2})$ 인 함수
$$|\text{dom}(f)| ≤ |\text{codom}(f)|, \quad |\text{ran}(f)| ≤ |\text{codom}(f)|, \quad |\text{dom}(f)| = |\text{ran}(f)|$$

• 정의역의 모든 원소가 각각 서로 다른 상을 가질 때, 즉 서로 다른 공역 원소와 대응할 때 그 함수를 단사 함수라고 한다.
• 그러므로 단사 함수의 경우, 공역의 원소 개수가 정의역의 원소 개수나 치역의 원소 개수보다 많거나 같아야 하고(|공역| ≥ |정의역| or |치역|), 정의역과 치역의 원소 개수가 같아야 한다. (|정의역| = |치역|)

단사 함수를 화살표 선도로 표현한 예

• 어떤 함수가 단사 함수임을 판별하려면 정의역의 각 원소가 서로 다른 공역 원소와 대응하는지 확인해야 한다.

 

예

• 집합 $A = \{a, b, c \}$ 와 집합 $B = \{ 1, 2, 3, 4 \}$ 에 대한 함수의 원상과 상의 순서쌍 집합이 다음과 같다고 하자.

$$f_{1} \; : \; A \rightarrow B\text{일 때, } f_{1} = \{(a, 2), (b, 1), (c, 4) \} \\ f_{2} \; : \; A \rightarrow B\text{일 때, } f_{2} = \{(a, 2), (b, 2), (c, 3) \} $$

• 함수 `f_{1}` 의 경우 다음과 같이 정의역 `A` 의 모든 원소가 각각 공역 `B` 의 서로 다른 원소와 대응하므로 단사 함수이다.

$$a, \; b \in A \text{에 대하여, } a \ne b \text{이고 } f_{1}(a) = 2 \ne 1 = f_{1}(b) \\ a, \; c \in A \text{에 대하여, } a \ne c \text{이고 } f_{1}(a) = 2 \ne 4 = f_{1}(c) \\ b, \; c \in A \text{에 대하여, } b \ne c \text{이고 } f_{1}(b) = 1 \ne 4 = f_{1}(c) $$

• 함수 `f_{2}` 의 경우 다음과 같이 정의역 `A` 의 원소 `a, b` 가 각각 공역 `B` 의 같은 원소 `2` 에 대응한다. 따라서 함수 `f_{2}` 는 단사 함수가 아니다.

$$a, \; b \in A \text{에 대하여, } a \ne b \text{이고 } f_{2}(a) = 2 = 2 = f_{2}(b) \\ a, \; c \in A \text{에 대하여, } a \ne c \text{이고 } f_{2}(a) = 2 \ne 3 = f_{2}(c) \\ b, \; c \in A \text{에 대하여, } b \ne c \text{이고 } f_{2}(b) = 2 \ne 3 = f_{2}(c) $$

 

전사 함수(Surjective Function, Surjection, Onto Function)

함수 $f \; : \; X \rightarrow Y$ 가 있을 때, 모든 공역 원소 $y \in Y$ 에 대하여 $f(x) = y$ 인 정의역 원소 $x \in X$ 가 적어도 하나 이상 존재하는 함수
$$|\text{dom}(f)| ≥ |\text{codom}(f)|, \quad |\text{ran}(f)| = |\text{codom}(f)|$$

• 전사 함수는 공역의 모든 원소가 하나 이상의 정의역 원소와 대응하는 함수를 말한다.
• 그러므로 어떤 함수 `f` 가 전사 함수이면, 정의역의 원소 개수가 공역의 원소 개수보다 같거나 많으며(|정의역| ≥ |공역|), 공역이 곧 치역이므로 공역과 치역의 원소 개수가 같다. (|공역| = |치역|)

전사 함수를 화살표 선도로 표현한 예

• 어떤 함수가 전사 함수인지 판별하려면 공역의 모든 원소가 하나 이상의 정의역 원소와 대응하는지 확인해야 한다.

 

예

• 집합 $A = \{a, b, c, d \}$ 와 집합 $B = \{ 1, 2, 3 \}$ 에 대한 함수의 원상과 상의 순서쌍 집합이 다음과 같다고 하자.

$$f_{1} \; : \; A \rightarrow B\text{일 때, } f_{1} = \{(a, 2), (b, 1), (c, 1), (d, 3) \} \\ f_{2} \; : \; A \rightarrow B\text{일 때, } f_{2} = \{(a, 2), (b, 1), (c, 1), (d, 2) \} $$

• 함수 `f_{1}` 의 경우 다음과 같이 공역 `B` 의 모든 원소가 각각 정의역 `A` 의 원소와 대응하므로 전사 함수이다.

$$f_{1}(b) = f_{1}(c) = 1 \text{이므로, } 1 \in B은 \; b, c, \in A \text{와 대응한다.} \\ f_{1}(a) =2 \text{이므로, } 2 \in B은 \; a \in A \text{와 대응한다.} \\ f_{1}(d) = 3 \text{이므로, } 3 \in B은 \; d \in A \text{와 대응한다.} $$

• 함수 `f_{2}` 의 경우 다음과 같이 공역 `B` 의 원소 `3` 이 정의역 `A` 의 원소와 대응하지 않는다. 따라서 함수 `f_{2}` 는 전사 함수가 아니다.

$$f_{2}(b) = f_{2}(c) = 1 \text{이므로, } 1 \in B은 \; b, c \in A \text{와 대응한다.} \\ f_{2}(a) = f_{2}(d) = 2 \text{이므로, } 2 \in B은 \; a, d \in A \text{와 대응한다.} \\ 3 \in B \text{의 경우 함수 } f_{2} \text{로 대응되는 정의역} A \text{의 원소가 없다.} $$

 

전단사 함수(Bijective Function, Bijection, One-to-One Correspondence) = 일대일 대응 함수

단사 함수이면서 전사 함수인 함수
$$|\text{dom}(f)| = |\text{codom}(f)|, \quad |\text{ran}(f)| = |\text{codom}(f)|$$

• 전단사 함수는 정의역의 원소 개수와 공역의 원소 개수가 같으면서, 서로 다른 정의역 원소가 서로 다른 공역 원소와 대응해야 한다.
• 그래서 전단사 함수는 정의역, 공역, 치역의 원소 개수가 모두 같다.

전단사 함수를 화살표 선도로 표현한 예

• 어떤 함수가 전단사 함수인지 판별하려면 함수가 단사 함수이면서 전사 함수인지 확인해야 한다.

 

예

• 집합 $A = \{a, b, c \}$ 와 집합 $B = \{ 1, 2, 3 \}$ 에 대한 함수의 원상과 상의 순서쌍 집합이 다음과 같다고 하자.

$$f_{1} \; : \; A \rightarrow B\text{일 때, } f_{1} = \{(a, 2), (b, 1), (c, 3) \} \\ f_{2} \; : \; A \rightarrow B\text{일 때, } f_{2} = \{(a, 2), (b, 1), (c, 1) \} $$

• 함수 `f_{1}` 의 경우 다음과 같이 서로 다른 정의역 원소가 서로 다른 공역 원소와 대응하므로 단사 함수이다.

$$a, \; b \in A \text{에 대하여, } a \ne b \text{이고 } f_{1}(a) = 2 \ne 1 = f_{1}(b) \\ a, \; c \in A \text{에 대하여, } a \ne c \text{이고 } f_{1}(a) = 2 \ne 3 = f_{1}(c) \\ b, \; c \in A \text{에 대하여, } b \ne c \text{이고 } f_{1}(b) = 1 \ne 3 = f_{1}(c) $$

• 또한 다음과 같이 공역 `B` 의 모든 원소가 정의역 `A` 의 원소와 대응하므로, `f_{1}` 은 전사 함수이다.

$$f_{1}(b) = 1 \text{이므로, } 1 \in B은 \; b \in A \text{와 대응한다.} \\ f_{1}(c) =2 \text{이므로, } 2 \in B은 \; a \in A \text{와 대응한다.} \\ f_{1}(c) = 3 \text{이므로, } 3 \in B은 \; c \in A \text{와 대응한다.} $$

• 따라서 함수 `f_{1}` 은 단사 함수이면서 전사 함수이므로 전단사 함수이다.
• 함수 `f_{2}` 의 경우 다음과 같이 정의역 원소 중 같은 공역 원소와 대응하는 원소가 있어 단사 함수가 아니다.

$$a, \; b \in A \text{에 대하여, } a \ne b \text{이고 } f_{2}(a) = 2 \ne 1 = f_{2}(b) \\ a, \; c \in A \text{에 대하여, } a \ne c \text{이고 } f_{2}(a) = 2 \ne 1 = f_{2}(c) \\ b, \; c \in A \text{에 대하여, } b \ne c \text{이고 } f_{2}(b) = 1 = 1 = f_{2}(c) $$

• 또한 다음과 같이 공역 `B` 의 원소 `3` 이 정의역 `A` 의 원소와 대응하지 않으므로 함수 `f_{2}` 는 전사 함수도 아니다.

$$f_{2}(b) = f_{2}(c) = 1 \text{이므로, } 1 \in B은 \; b, c \in A \text{와 대응한다.} \\ f_{2}(a) = 2 \text{이므로, } 2 \in B은 \; a \in A \text{와 대응한다.} \\ 3 \in B \text{의 경우 함수 } f_{2} \text{로 대응되는 정의역} A \text{의 원소가 없다.} $$

• 전단사 함수인지 판별할 때, 단사 함수와 전사 함수 중 하나라도 만족하지 않으면 전단사 함수가 아니다.
• $f_{2}$ 는 단사 함수도, 전사 함수도 아니므로 당연히 전단사 함수가 아니다.