函数和选择公理

函数的定义

Definition（函数）对于集合 $A$$A$ 到集合 $B$$B$ 的关系 $f$$f$，若满足下列条件：

• （单值性，保证不会将 $A$$A$ 中的元素对应到多个 $B$$B$ 中的元素）对于任意的 $x\in \mathrm{dom}f$$x\in \operatorname{dom} f$，存在唯一的 $y\in \mathrm{ran}(f)$$y\in \operatorname{ran} (f)$，使得 $xfy$$xfy$ 成立。

• （定义域，保证 $f$$f$ 在 $A$$A$ 每个元素上都有定义）$\mathrm{dom}(f)=A$$\operatorname{dom}(f)=A$.

英文 domain 和 range 的缩写。

则称 $f$$f$ 为从 $A$$A$ 到 $B$$B$ 的函数，或称 $f$$f$ 把 $A$$A$ 映射到 $B$$B$.

Definition（部分函数）如果 $\mathrm{dom}(f)\subset A$$\operatorname{dom}(f)\sub A$，则称为部分函数。

函数的两个条件等价于：

• $(\mathrm{\forall }x)\left(\mathrm{\forall }{y}_1\right)\left(\mathrm{\forall }{y}_2\right)((xf{y}_1\wedge xf{y}_2)\to y_1=y_2)$$(\forall x)\left(\forall y_{1}\right)\left(\forall y_{2}\right)\left(\left(x f y_{1} \wedge x f y_{2}\right) \rightarrow y_{1}=y_{2}\right)$.

• $(\mathrm{\forall }x)(x\in A\to (\mathrm{\exists }y)(y\in B\wedge xfy))$$(\forall x)(x \in A \rightarrow(\exists y)(y \in B \wedge x f y))$.

函数的逆关系不一定是函数。

从关系图和关系矩阵的角度考虑：

• 关系矩阵每行恰好有一个 $1$$1$，其余为 $0$$0$；

• 关系图中每个 $A$$A$ 中的顶点恰好发出一条有向边。

Definition（所有函数的集合） 对于集合 $A$$A$ 和 $B$$B$，从 $A$$A$ 到 $B$$B$ 的所有函数的集合记为 $A_B$$A_B$.

若 $|A|=m,|B|=n$$|A|=m,|B|=n$，则 $A$$A$ 到 $B$$B$ 的函数有 $n^m$$n^m$ 种。

从 $\varnothing$$\varnothing$ 到 $\varnothing$$\varnothing$ 的函数或 $\varnothing$$\varnothing$ 到 $B$$B$ 的函数只有 1 种，即 $\varnothing$$\varnothing$.

从 $A$$A$ 到 $\varnothing$$\varnothing$ 的函数不存在。

Definition（函数的象和完全原象） 设 $f:A\to B$$f:A \rightarrow B$，$A_1\subseteq A$$A_{1} \subseteq A$，定义 $A_1$$A_{1}$ 在 $f$$f$ 下的象 $f\left[A_1\right]$$f\left[A_{1}\right]$ 为

把 $f[A]$$f[A]$ 称为函数的象。

设 $B_1\subseteq B$$B_1\sube B$，定义 $B_1$$B_1$ 在 $f$$f$ 下的完全原象 $f^{-1}[B_1]$$f^{-1}[B_1]$ 为：

$f^{-1}$$f^{-1}$ 表示 $f$$f$ 的逆关系，因为函数的逆关系不一定是函数，所以 $f^{-1}$$f^{-1}$ 一般只表示逆关系，不是逆函数。

$|f[A_1]|\le |A_1|$$|f[A_1]| \le |A_1|$，而 $f^{-1}[B_1]$$f^{-1}[B_1]$ 的大小和 $B_1$$B_1$ 的大小没有一定关系。

特殊的函数

对于函数 $f:A\to B$$f:A\rightarrow B$：

• 若 $\mathrm{ran}(f)=B$$\operatorname{ran}(f)=B$，则称 $f$$f$ 是 满射 的，或称 $f$$f$ 是 $A$$A$ 到 $B$$B$ 上的；

  如果 $f:A\to B$$f:A \rightarrow B$ 是满射的，则对任意的 $y\in B$$y \in B$，存在 $x\in A$$x \in A$，使 $f(x)=y$$f(x)=y$；

• 若对任意的 $x_1,x_2\in A,x_1\ne x_2$$x_{1},x_{2} \in A,x_{1} \neq x_{2}$，都有 $f\left(x_1\right)\ne f\left(x_2\right)$$f\left(x_{1}\right) \neq f\left(x_{2}\right)$，则称 $f$$f$ 是 单射 的，或内射的，或一对一的

  如果 $f:A\to B$$f:A \rightarrow B$ 是单射的，则对任意的 $y\in \mathrm{ran}(f)$$y \in \operatorname{ran}(f)$，存在唯一的 $x\in A$$x \in A$，使 $f(x)=y$$f(x)=y$

• 若 $f$$f$ 是满射的又是单射的，则称 $f$$f$ 是 双射 的。

  特别地，$\varnothing :\varnothing \to B$$\varnothing:\varnothing \rightarrow B$ 是单射的，$\varnothing :\varnothing \to \varnothing$$\varnothing:\varnothing \rightarrow \varnothing$ 是双射的。

  若 $|A|=0$$|A|=0$，则不存在 $x_1,x_2$$x_1,x_2$，因此是单射的；如果 $|B|=0$$|B|=0$，则不存在 $y\in B$$y\in B$，因此是双射的。

Examples：构造双射：

• $\mathbb{R}\to \mathbb{R}$$\R \to \R$.

• $\mathbb{R}\to {\mathbb{R}}_{+}$$\R \to \R_+$. $f(x)=e^x$$f(x)=e^x$.

• $[0,1)\to (\frac{1}{4},\frac{1}{2}]$$[0,1)\to (\frac{1}{4},\frac{1}{2}]$. $f(x)=\frac{1}{2}-\frac{x}{4}$$f(x)=\frac{1}{2} -\frac{x}{4}$.

• $\mathbb{N}\times \mathbb{N}\to \mathbb{N}$$\N\times \N\to \N$. 使用 Cantor table 构造。

• ${\mathbb{N}}_{+}\to \mathbb{N}$$\N_{+}\to \N$，构造 $f(x)=(x-1)/2\mathrm{if}\mathrm{x}\mathrm{is}\mathrm{odd}\mathrm{else}-x/2$$f(x)=(x-1)/2 \mathrm{\ if \ x\ is \ odd\ else\ } -x/2$.

常用的函数

• 设 $f:A\to B$$f:A \rightarrow B$，如果存在一个 $y\in B$$y \in B$，使得对所有的 $x\in A$$x \in A$，有 $f(x)=y$$f(x)=y$，即有 $f[A]=\{y\}$$f[A]=\{y\}$，则称 $f:A\to B$$f:A \rightarrow B$ 为 常函数

• $A$$A$ 上的恒等关系 $I_A:A\to A$$I_{A}:A \rightarrow A$ 称为 恒等函数。对任意的 $x\in A$$x \in A$，有 $I_A(x)=x$$I_{A}(x)=x$

• 对实数集 $\mathbb{R}$$\mathbb{R}$，设 $f:\mathbb{R}\to \mathbb{R}$$f:\mathbb{R} \rightarrow \mathbb{R}$，如果 $(x⩽y)\to (f(x)⩽f(y))$$(x \leqslant y) \rightarrow(f(x) \leqslant f(y))$，则称 $f$$f$ 为 单调递增 的；如果 $(x<y)\to (f(x)<f(y))$$(x<y) \rightarrow(f(x)<f(y))$，则称 $f$$f$ 为 严格单调递增 的，类似可定义单调递减和严格单调递减的函数

• 对集合 $A$$A$，$n\in \mathbb{N}$$n \in \mathbb{N}$，把函数 $f:A^n\to A$$f:A^{n} \rightarrow A$ 称为 $A$$A$ 上的 n 元运算

• 设 $A,B,C$$A,B,C$ 是集合，$B_C$$B_{C}$ 为从 $B$$B$ 到 $C$$C$ 的所有函数的集合，则 $F:A\to B_C$$F:A \rightarrow B_{C}$ 称为一个 泛函（有时 $G:B_C\to A$$G:B_{C} \rightarrow A$ 称为一个泛函）

• 设 $E$$E$ 是全集，对任意的 $A\subseteq E$$A \subseteq E$，$A$$A$ 的 特征函数 ${\chi }_A$$\chi_{A}$ 定义为：

  $${\chi }_A:E\to \{0,1\},{\chi }_A(a)=1\mathrm{if}a\in A\mathrm{else}0$$

• 设 $R$$R$ 是 $A$$A$ 上的等价关系，令 $g:A\to A/R$$g:A \rightarrow A / R$，$g(a)=[a{]}_R$$g(a)=[a]_{R}$，则称 $g$$g$ 为从 $A$$A$ 到商集 $A/R$$A / R$ 的 典型映射 或 自然映射. 这个函数将元素映射到集合。

函数的选择公理

Axiom（选择公理） 对于任意的关系 $R$$R$，存在函数 $f$$f$，使得 $f\subseteq R$$f\sube R$ 且 $\mathrm{dom}f=\mathrm{dom}R$$\operatorname{dom} f =\operatorname{dom} R$.

Examples：例如，对于关系 $R=\{⟨1,a⟩,⟨1,b⟩,⟨2,b⟩\}$$R=\{\langle 1,a \rangle,\langle 1,b \rangle,\langle 2,b \rangle\}$，可以构造：

• $f_1=\{⟨1,a⟩,⟨2,b⟩\}$$f_1=\{\langle 1,a \rangle,\langle 2,b \rangle\}$；

• $f_2=\{⟨1,b⟩,⟨2,b⟩\}$$f_2=\{\langle 1,b \rangle,\langle 2,b \rangle\}$；

都是满足条件的函数。

函数的合成和函数的逆

函数的合成

Definition（函数的合成） 设 $g:A\to B,f:B\to C$$g:A\to B,f:B\to C$，则：

1. $f\circ g$$f\circ g$ 是函数 $f\circ g$$f\circ g$：$A\to C$$A\to C$. 可以理解为 $f$$f$ 作用在 $g$$g$ 的输出之上。

2. 对任意的 $x\in A$$x\in A$，有 $(f\circ g)(x)=f(g(x))$$(f\circ g)(x)=f(g(x))$.

Proof

对于 1. 先证明 $f\circ g$$f\circ g$ 满足 定义域条件，利用 $g$$g$ 的定义域条件和 $f$$f$ 的定义域条件，有：

因此 $f\circ g$$f\circ g$ 也满足定义域条件。再看 单值性条件，即对于任意的 $x\in A$$x\in A$，存在 $z_1,z_2$$z_1,z_2$ 使得 $⟨x,z_1⟩\in f\circ g$$\langle x,z_1 \rangle\in f\circ g$ 且 $⟨x,z_2⟩\in f\circ g$$\langle x,z_2 \rangle\in f\circ g$，则：

因为 $g$$g$ 的单值性条件，有 $y_1=y_2$$y_1=y_2$，因为 $f$$f$ 的单值性条件，有 $z_1=z_2$$z_1=z_2$，因此 $f\circ g$$f\circ g$ 满足单值性条件。

对于 2.，考虑任意的 $x\in A$$x\in A$，因为 $⟨x,g(x)⟩\in g,⟨g(x),f(g(x))⟩\in f$$\langle x,g(x) \rangle\in g,\langle g(x),f(g(x)) \rangle\in f$，所以 $⟨x,f(g(x))⟩\in f\circ g$$\langle x,f(g(x)) \rangle\in f\circ g$，又因为 $f\circ g$$f\circ g$ 是函数，所以可以写作 $(f\circ g)(x)=f(g(x))$$(f\circ g)(x)=f(g(x))$.

Theorem（合成函数维持单射、双射、满射性质） 设 $g:A\to B,f:B\to C$$g:A\to B,f:B\to C$，则：

1. 若 $f,g$$f,g$ 是满射的，则 $f\circ g$$f\circ g$ 是满射的。

2. 若 $f,g$$f,g$ 是单射的，则 $f\circ g$$f \circ g$ 是单射的；

3. 若 $f,g$$f,g$ 是双射的，则 $f\circ g$$f \circ g$ 是双射的；

Proof

1. 对于任意的 $z\in C$$z\in C$，都存在 $y\in B$$y\in B$ 使得 $f(y)=z$$f(y)=z$，对于这个 $y$$y$ 来说，又存在 $x\in A$$x\in A$ 使得 $g(x)=y$$g(x)=y$，因此对于任意的 $z$$z$ 存在 $x$$x$ 使得 $f(g(x))=z$$f(g(x))=z$。因此 $f\circ g$$f\circ g$ 是满射的。

2. 对于任意的 $z\in \mathrm{ran}(f\circ g)$$z\in \operatorname{ran} (f\circ g)$，若存在 $x_1,x_2$$x_1,x_2$ 使得 $(f\circ g)(x_1)=z$$(f\circ g)(x_1)=z$ 且 $(f\circ g)(x_2)=z$$(f\circ g)(x_2)=z$，则存在 $y_1,y_2$$y_1,y_2$ 使得 $x_{1}g{y}_1\wedge y_{1}fz$$x_1 g y_1 \wedge y_1 fz$ 且 $x_{2}g{y}_2\wedge y_{2}fz$$x_2 g y_2 \wedge y_2 f z$，因为 $f$$f$ 是单射的，所以 $y_1=y_2$$y_1=y_2$，因为 $g$$g$ 是单射的，所以 $x_1=x_2$$x_1=x_2$，因此 $f\circ g$$f\circ g$ 是单射的。

形象的证明过程：

3. 由 1.2. 得证。

若 $f$$f$ 是单射的，则 $f:A\to \mathrm{ran}f$$f:A\to \operatorname{ran} f$ 是双射的。

Problem 设 $R$$R$ 是 $A$$A$ 上的等价关系，$g:A\to A/R$$g:A\to A/R$ 是自然映射，什么条件下 $g$$g$ 是双射的？

Solution 1（从单射角度出发）

对于等价类 $[x{]}_R$$[x]_R$，总有 $x$$x$ 使得 $g(x)=[x{]}_R$$g(x)=[x]_R$，则 $g$$g$ 为满射；若 $g$$g$ 为双射，还要要求 $g$$g$ 为单射，即对于任意 $x\ne y$$x\not=y$ 有 $g(x)\ne g(y)$$g(x)\not=g(y)$. 若取 $x,y$$x,y$ 为 $[x{]}_R$$[x]_R$ 中的两个元素，则 $g(x)=g(y)$$g(x)=g(y)$，因此只能 $x=y$$x=y$，则 $[x{]}_R=\{x\}=g(x)$$[x]_R=\{x\}=g(x)$，即 $R=I_A$$R=I_A$.

Solution 2（从双射角度出发）

要求 $|A|=|A/R|$$|A|=|A/R|$，则 $(\mathrm{\forall }x)(g(x))=\{x\}$$(\forall x)(g(x))=\{x\}$.

Theorem（上述定理的逆定理） 设 $g:A\to B,f:B\to C$$g:A\to B,f: B\to C$，则有：

1. 若 $f\circ g$$f\circ g$ 是满射的，则 $f$$f$ 是满射的；

2. 若 $f\circ g$$f\circ g$ 是单射的，则 $g$$g$ 是单射的；

3. 若 $f\circ g$$f\circ g$ 是双射的，则 $f$$f$ 是满射的，$g$$g$ 是双射的。

Proof

1. 对于任意的 $z\in C$$z\in C$，因为 $f\circ g$$f\circ g$ 是满射的，故 $\mathrm{\exists }x\in A$$\exists x\in A$，使得 $x(f\circ g)z$$x(f\circ g) z$，则 $\mathrm{\exists }y\in B$$\exists y\in B$，使得 $xgy\wedge yfz$$xgy \wedge yfz$，则 $\mathrm{\exists }y\in B$$\exists y\in B$，使得 $f(y)=z$$f(y)=z$，$f$$f$ 是满射的。

2. 对于任意的 $y\in \mathrm{ran}(g)$$y\in \operatorname{ran} (g)$，若存在 $x_1,x_2\in A$$x_1,x_2 \in A$，使得 $x_{1}gy\wedge x_{2}gy$$x_1gy \wedge x_2 g y$，即 $g(x_1)=y=g(x_2)$$g(x_1)=y=g(x_2)$. 对这个 $y\in B$$y\in B$，（因为 $\mathrm{ran}(g)\subseteq B$$\operatorname{ran}(g) \sube B$），存在 $z\in \mathrm{ran}(f)$$z\in \operatorname{ran}(f)$ 使得 $zfy$$zfy$，所以 $f(g(x_1))=f(g(x_2))$$f(g(x_1))=f(g(x_2))$. 因为 $f\circ g$$f\circ g$ 是单射的，所以 $x_1=x_2$$x_1=x_2$，所以 $g$$g$ 是单射的。

3. 由 1.2. 得证。

函数的逆

一个关系的逆不一定是函数，一个函数的逆也不一定是函数。

Theorem（双射函数的逆） 若 $f:A\to B$$f:A\to B$ 是双射的，则 $f^{-1}$$f^{-1}$ 是函数 $f^{-1}:B\to A$$f^{-1} :B\to A$.

Proof：

• 利用 $f$$f$ 的满射性质，对于 $\mathrm{\forall }y\in B$$\forall y\in B$，存在 $x\in A$$x\in A$，使得 $xfy$$xfy$，则 $⟨y,x⟩\in f^{-1}$$\langle y,x \rangle\in f^{-1}$，因此 $\mathrm{dom}{f}^{-1}=B$$\operatorname{dom} f^{-1}=B$.（定义域）

• 利用 $f$$f$ 的单射性质，对于 $\mathrm{\forall }y\in B$$\forall y\in B$，如果存在 $x_1,x_2\in A$$x_1,x_2\in A$，使得 $⟨y,x_1⟩\in f^{-1}$$\langle y,x_1 \rangle \in f^{-1}$ 且 $⟨y,x_2⟩\in f^{-1}$$\langle y,x_2 \rangle \in f^{-1}$，则 $⟨x_1,y⟩\in f$$\langle x_1,y \rangle \in f$ 且 $⟨x_2,y⟩\in f$$\langle x_2,y \rangle\in f$，因此 $x_1=x_2$$x_1=x_2$. （单值性）

Definition（反函数） 若 $f:A\to B$$f:A\to B$ 是双射的，则 $f^{-1}$$f^{-1}$ 是函数 $f$$f$ 的反函数。且 $f^{-1}$$f^{-1}$ 是双射的。

Theorem 若 $f:A\to B$$f:A\to B$ 是双射的，则对于任意的 $x\in A$$x\in A$，有 $f^{-1}(f(x))=x$$f^{-1}(f(x))=x$，对于任意的 $y\in B$$y\in B$，有 $f(f^{-1}(x))=x$$f(f^{-1}(x))=x$.

Definition（函数的左逆、右逆）设 $f:A\to B,g:B\to A$$f:A\to B,g:B\to A$，若 $g\circ f=I_A$$g\circ f=I_A$，则称 $g$$g$ 是 $f$$f$ 的左逆；若 $f\circ g=I_B$$f\circ g=I_B$，则称 $g$$g$ 是 $f$$f$ 的右逆。

Theorem 设 $f:A\to B,A\ne \varnothing$$f:A\to B,A\not=\varnothing$，则：

1. $f$$f$ 存在左逆，当且仅当 $f$$f$ 是单射的；

2. $f$$f$ 存在右逆， 当且仅当 $f$$f$ 是满射的；

3. $f$$f$ 存在左逆和右逆，当且仅当 $f$$f$ 是双射的；

4. 若 $f$$f$ 是双射的，则 $f$$f$ 的左逆等于右逆。

对于 1. 先证充分性：设存在 $x_1,x_2$$x_1,x_2$ 使得 $f(x_1)=f(x_2)$$f(x_1)=f(x_2)$，因为 $f$$f$ 存在左逆，假设为 $g$$g$，则：

因此，$x_1=x_2$$x_1=x_2$，$f$$f$ 是单射函数；

再证必要性，因为 $f$$f$ 是单射的，所以 $f:A\to \mathrm{ran}f$$f:A\to \operatorname{ran} f$ 是双射的，则 $f^{-1}:\mathrm{ran}f\to A$$f^{-1}:\operatorname{ran} f \to A$ 是双射的，已知 $A\ne \varnothing$$A\not=\varnothing$，则 $\mathrm{\exists }a\in A$$\exists a\in A$，构造 $g:B\to A$$g:B\to A$ 为：

则对于任一 $x\in A$$x\in A$，有 $g(f(x))=x$$g(f(x))=x$，所以 $g\circ f=I_A$$g\circ f=I_A$.