一、函数

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

  • 如果已经确认 $F$ 是一个函数，那么还可以等价于：$\forall x_1, x_2 \in A, F(x_1) = F(x_2) \to x_1 = x_2$。这等同于：$\forall x_1, x_2 \in A, x_1 \neq x_2 \to F(x_1) \neq F(x_2)$。这两个就是我们常用的证明单射的方法。

• 满射 (surjection / onto)：函数满足 $B = {\rm ran} \, F$。

  • 如果已经确认 $F$ 是一个函数，那么还可以等价于：$\forall y \in B$，$\exists x \in A$ 使得 $F(x) = y$。

• 双射 / 一一对应 (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|!$。

• **【约束后的单射】**对于单射 $F:A \to B$ 和 $A_0 \subseteq A$，那么可以构造 $G: A_0 \to B$，$G(x) := F(x)$ 是一个单射。

  证明：

  • 良定义性：易得 $A_0$ 中任意元素的像都属于 $B$。
  • 单射性：$\forall x_1, x_2 \in A_0$，$x_1 \neq x_2$，根据 $F$ 的单射性得到 $F(x_1) \neq F(x_2)$，即 $G(x_1) \neq G(x_2)$。

• **【约束后的双射】**对于双射 $F: A \to B$ 和 $A_0 \subseteq A$，那么可以构造 $G: A_0 \to F(A_0)$，$G(x) := F(x)$ 是一个双射。

  证明：

  • 良定义性：根据 $F(A_0)$ 的定义

    $$ F(A_0) = {\rm ran} (F | A_0) = \{ y \mid \exists x \in A_0, \, F(x)=y \} $$

    易得 $\forall x \in A_0$，$G(x) = F(x) \in F(A_0)$。

  • 单射性：同上。

  • 满射性：根据 $F(A_0)$ 的定义，易得 $\forall y \in F(A_0)$，$\exists x \in A_0$ 使得 $F(x) = y$ 即 $G(x) = y$。

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) \}$。