第 03 篇、函數 & 鴿籠原理

# 函數

$f \subseteq A \times B$ 滿足:$\forall a \in A \exists !b \in B : afb$
稱$f$ 為$A$ 至$B$ 的函數 function relation ，記作$f: A \rightarrow B$

# 定義

設$f$ 為$A \rightarrow B$ 函數

1. $A$ 稱作定義域 domain
2. $B$ 稱作對應域 codomain
3. $A_1 \subseteq A, f(A_1) = \{ f(a) | a \in A_1 \}$
4. $B_1 \subseteq B, f^{-1}(B_1) = \{ f(a) | a \in B_1 \}$
5. $f(A)$ 稱作值域，即被$A$ 對應到的部分

# 定義

設$f$ 為$A \rightarrow B$ 函數

1. 若$a_1 \neq a_2 \rightarrow f(a_1) \neq f(a_2)$，也就是說，$f(a_1) = f(a_2) \rightarrow a_1 = a_2$
   稱$f$ 為一對一函數 one-to-one 、 injective
2. 若$f(A) = B$，稱$f$ 為映射函數 onto 、 subjective
3. 若$f$ 為 1-1 且 onto ，則稱$f$ 為可逆函數 invertible 、 bijection

# 定理

設$f$ 為$A \rightarrow B$ 函數，且$A_1,A_2 \in A, B_1,B_2 \in B$

1. $A_1 \subseteq A_2 \rightarrow f(A_1) \subseteq f(A_2)$
2. $f(A_1 \cup A_2) = f(A_1) \cup f(A_2)$
3. $f(A_1 \cap A_2) \subseteq f(A_1) \cap f(A_2)$，如果$f$ 是多對一
4. $f(A_1 \cap A_2) = f(A_1) \cap f(A_2)$，如果$f$ 是一對一
5. $B_1 \subseteq B_2 \rightarrow f^{-1}(B_1) \subseteq f^{-1}(B_2)$
6. $f^{-1}(B_1 \cup B_2) = f^{-1}(B_1) \cup f^{-1}(B_2)$
7. $f^{-1}(B_1 \cap B_2) = f^{-1}(B_1) \cap f^{-1}(B_2)$

# 合成

設$f$ 為$A \rightarrow B$ 函數，$g$ 為$B \rightarrow C$ 函數
$g \circ f: A \rightarrow C \Leftrightarrow (g \circ f)(a) = g(f(a))$(先作$f$)

# 定理

設$f$ 為$A \rightarrow B$ 函數，$g$ 為$B \rightarrow C$ 函數

1. f 為 1-1 且 g 為 1-1 $\rightarrow g \circ f$ 為 1-1
2. f 為 onto 且 g 為 onto $\rightarrow g \circ f$ 為 onto
3. f 為 1-1 、 onto 且 g 為 1-1 、 onto $\rightarrow g \circ f$ 為 1-1 、 onto

# 鴿籠原理

# 定理

$m$ 隻鴿子，$n$ 個籠子，在$m > n$ 的情況下，則存在至少一個籠子，含有至少$\left \lceil \frac{m}{n} \right \rceil$ 隻鴿子。

# 例題

待補