一、函数

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$）。

  回顾：弱单根性与强单根性

  • $F$ 是弱单根的：$\forall y \in B, \forall x_1, x_2 \in A, x_1Fy \wedge x_2Fy \to x_1 = x_2$。
    • 可以简记为：$\forall y \in B, (\nexists \vee \exists!) x \in A, xFy$。
      • 其中量词 $(\nexists \vee \exists!)$ 表示要么不存在，要么唯一存在。
    • $F$ 是强单根的：$\forall y \in B, \exists! x \in A, xFy$。
      • 也就是弱单值性加上 ${\rm ran} \, F = B$。

• 满射 (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$ 为全函数。

• **【复合函数是单射/满射/双射的充分条件】**单射/满射/双射的复合还是单射/满射/双射。

  证

  • 设 $F:A\to B$，$G: B \to C$，它们的复合为 $G \circ F = \{ (x, z) \, | \, \exists y (xFy \wedge yGz) \}$。
  • 单射：即证明 $\forall z \in C, \forall x_1, x_2 \in A, x_1(G \circ F)y \wedge x_2(G \circ F)y \to x_1 = x_2$。
    • 对于任意 $x_1, x_2 \in A$，根据 $F$ 是单射，$\forall y \in B, \, x_1Fy \wedge x_2Fy \to x_1 = x_2$。
    • 对于任意 $z \in C$ 使得 $x_1(G \circ F)z$ 且 $x_2 (G \circ F)z$，根据复合函数定义，存在 $y_1, y_2 \in B$ 使得 $x_1 F y_1$、$y_1Gz$、$x_2Fy_2$、$y_2Gz$。
      • 根据 $G$ 是单射，根据其中的 $y_1Gz, y_2Gz$ 推理得到 $y_1 = y_2$。
      • 根据 $y_1 = y_2$，根据 $F$ 是单射，$x_1 F y_1, x_2Fy_2$ 得到 $x_1 = x_2$。
  • 满射：即证明 $C = {\rm ran} (G \circ F)$。
    • 因为 ${\rm ran} (G \circ F) \subseteq C$ 一定成立，只需证 $C \subseteq {\rm ran} (G \circ F)$。
      • 对于任意 $z \in C$，根据 $G$ 是满射即 $C = {\rm ran} \, G$，所以 $\exists y \in B$ 使得 $yGz$。又根据 $F$ 是满射即 $B = {\rm ran} \, F$，所以 $\exists x \in A$ 使得 $xFy$。显然 $x (G \circ F)z$，因而说 $z \in {\rm ran} (G \circ F)$。
  • 双射：根据单射和满射可得。