1. 函数的概念

• 函数 (function) 分为部分函数和完全函数：

  • 偏（部分）函数的定义：弱单值的（部分函数的）二元关系，记作 $F: A \mapsto B$。
  • 全（完全）函数的定义：强单值的（函数的）二元关系，记作 $F: A \to B$。

  回顾弱单值性与强单值性。

  • $F$ 是弱单值的（部分函数的）：$\forall x \in A, \forall y_1, y_2 \in B, xFy_1 \wedge xFy_2 \to y_1 = y_2$。
    • 等价于：$\forall x \in A, (\nexists \vee \exists!) y \in B, xFy$。
    • $F$ 是强单值的（函数的）：$\forall x \in A, \exists! y \in B, xFy$。
      • 也就是弱单值性加上 ${\rm dom} \, F = A$。

  • 函数的 $xFy$ 也被记作 $F(x)=y$。
  • 下面把全函数简称为函数。
  • 将 $A$ 到 $B$ 的全体函数记为 $B^A = \{ F \, | \, F: A \to B \}$。显然 $|B^A| = |B| ^ {|A|}$。
    • 也可也直接把 $B^A$ 记 $A \to B$，这样所有的 $F: A \to B$ 其实是说 $F \in (A \to B)$。

2. 单射、满射、双射

• 单射 (injection)：映射是弱单根的（$\forall y \in B, (\nexists \vee \exists!) x \in A, xFy$）。
• 满射 (surjection / onto)：映射满足 $B = {\rm ran} \, F$。
• 双射 / 一一对应 (bijection / 1-1 mapping)：即是单射又是满射，即是强单根的。

有多少单射、满射、双射？

• $|A|<|B|$ 时，没有满射和双射，单射的个数是：

  $$ |B|(|B|-1)\cdots (|B| - |A| + 1) = \frac {|B|!}{(|B| - |A|)!} $$

• $|A|>|B|$ 时，没有单射和双射，满射的个数是：

  $$ |A|(|A|-1)\cdots (|A| - |B| + 1) = \frac {|A|!}{(|A| - |B|)!} $$

• $|A|=|B|$ 时单射、满射、双射个数相等，为：$|A|!$。

3. 特殊的函数

• 常数函数：$\exists b \in B, \, \forall x \in A, \, F(x) = b$。
• 恒等函数：$I_A: A \to A, \, \forall x \in A, \, I_A(x) = x$。
• 特征函数：$\chi_A: E \to \{ 0, 1\}, \, \forall x \in E, \, \chi_A(x) = 1 \Leftrightarrow x \in A$。
• 空函数：$\empty$（空关系）。

4. 单调函数

• 给定偏序集（或全序集）$\left< A, \preceq_A \right>, \left< B, \preceq_B \right>$，可定义单调函数：
  • 单调增函数：$\forall x_1, x_2 \in A, \, x_1 \preceq_A x_2 \Rightarrow F(x_1) \preceq_B F(x_2)$。
  • 单调减函数：$\forall x_1, x_2 \in A, \, x_1 \preceq_A x_2 \Rightarrow F(x_1) \succeq_B F(x_2)$。
  • 严格单调函数：把 $\preceq, \succeq$ 换成 $\prec, \succ$。

5. 函数的复合

回顾复合关系：假设 $F \subseteq A \times B$、$G \subseteq B \times C$，它们的复合为 $G \circ F = \{ (x, z) \, | \, \exists y (xFy \wedge yGz) \}$。

• 如果 $F, G$ 都是偏函数（即 $F: A \mapsto B$、$G: B \mapsto C$），可证明：

  1. $G \circ F$ 也为偏函数。
  2. $(G \circ F) (x) = G(F(x))$。
  3. 若 ${\rm ran} \, F \subseteq {\rm dom} \, G$，可得 ${\rm dom} \, G \circ F = {\rm dom} \, F$。那么如果 $F$ 还是全函数（即 $F: A \to B$、$G: B \to C$），$G \circ F$ 也就为全函数。

  1. 的证明

  $\forall x \in A, \forall z_1, z_2 \in C$ 时，如果有 $x (G \circ F) z_1 \wedge x (G \circ F) z_2$；

  根据 $G \circ F$ 复合关系定义，$\exists y_1, x F y_1 \wedge y_1 G z_1$；$\exists y_2, x F y_2 \wedge y_2 G z_2$。

  由于 $F$ 是偏函数即弱单值的，根据定义「$\forall x \in A, \forall y_1, y_2 \in B, xFy_1 \wedge xFy_2 \to y_1 = y_2$」导出 $y_1 = y_2$；由于 $G$ 是偏函数即弱单值的，根据定义「$\forall y \in B, \forall z_1, z_2 \in C, yGz_1 \wedge yGz_2 \to z_1 = z_2$」导出 $z_1 = z_2$。

  因而 $G \circ F$ 仍是弱单值的，因而 $G \circ F$ 也为偏函数。

  2. 的证明

  $xFz$，根据 $G \circ F$ 复合关系定义，$\exists y, x F y \wedge y G z$；因而 $F(x)=y$、$G(y) = z$，因而说 $G(F(x)) = z$。

  3. 的证明

  下面把所有类似 $x \in A, y \in B, z \in C$ 的说明都省略掉了。

  根据定义，${\rm dom} \, F = \{ x \, | \, \exists y (x F y)\}$、${\rm dom} \, G \circ F = \{ x \, | \, \exists z (x (G \circ F) z)\}$。

  于是下面想要证明对于 $\forall x$，有 $\exists y (x F y) \Leftrightarrow \exists z (x (G \circ F) z)$。

  • $\Leftarrow$：根据 $G \circ F$ 复合关系定义，$\exists z (x (G \circ F) z) \Rightarrow \exists z\exists y(xFy \wedge yGz)$ ，可推出 $\exists y (x F y)$ 。
  • $\Rightarrow$：
    • 先推导这个：${\rm ran} \, F \subseteq {\rm dom} \, G$，即 $\{ y \, | \, \exists x (x F y)\} \subseteq \{ y \, | \, \exists z (y G z)\}$，即 $\forall y, \, \exists x (x F y) \Rightarrow \exists z (y G z)$ 。
    • 回到想要证明的 $\forall x$ 上来，蕴含的条件是 $\exists y (x F y)$，可导出 $\exists z (y G z)$ （因为引出的结论对于所有的 $y$ 都有效），因而根据 $G \circ F$ 复合关系定义可导出 $\exists z (x (G \circ F) z)$。

  综上，${\rm dom} \, G \circ F = {\rm dom} \, F$。因而如果 $F$ 还是全函数即 ${\rm dom} \, F = A$，那么 ${\rm dom} \, G \circ F = A$ 即说明 $G \circ F$ 为全函数。

6. 函数的反函数

回顾逆关系：设 $F \sube A\times B$，它的逆关系为 $F^{-1} = \{ (y, x) \, | \, xFy \}$

• 反函数的定义：如果 $F: A \to B$ 为双射，那么 $F^{-1} : B \to A$ 为一个双射（证略），称其为 $F$ 的反函数。