第 3 讲 · 函数

函数不是一条公式，而是满足额外约束的关系。写 $f:X\to Y$ 时，$X$ 是定义域，$Y$ 是陪域；陪域不一定等于实际取到的值域。

函数要同时满足全定义和单值

把 $f$ 看作 $X\times Y$ 的子集，它必须满足：

$$\forall x\in X, \exists!y\in Y, (x,y)\in f.$$

“存在”保证每个输入都有输出，“唯一”保证同一输入不会对应两个不同输出。例如 $y=x^2$ 从 $\mathbb R$ 到 $\mathbb R$ 是函数；关系 $y^2=x$ 不是，因为正数输入通常对应正负两个输出。

单射、满射和双射检查不同问题

• 单射：$f(x_1)=f(x_2)\Rightarrow x_1=x_2$，不同输入不会碰到一起；
• 满射：每个 $y\in Y$ 都能写成某个 $f(x)$，陪域没有遗漏；
• 双射：既单射又满射，每个输出恰好对应一个输入。

有限集合中，存在 $X\to Y$ 的单射要求 $|X|\leq|Y|$，存在满射要求 $|X|\geq|Y|$，存在双射等价于 $|X|=|Y|$。无穷集合则反过来利用双射定义“大小相同”。

复合函数先核对接口

若 $f:X\to Y$、$g:Y\to Z$，则：

$$(g\circ f)(x)=g(f(x)).$$

它源自关系复合，满足结合律，但一般不满足交换律。若 $f,g$ 都是单射、满射或双射，$g\circ f$ 分别仍保持相应性质。

若 $f:X\to Y$ 是双射，才有整个 $Y$ 上的逆函数 $f^{-1}:Y\to X$，且：

$$f^{-1}\circ f=I_X, \qquad f\circ f^{-1}=I_Y.$$

只有单射但不满射时，可以在值域上定义逆；不能不说明陪域就直接写完整逆函数。

函数迭代描述重复应用

对 $f:X\to X$ 定义：

$$f^0=I_X,\qquad f^{n+1}=f\circ f^n.$$

于是 $f^m\circ f^n=f^{m+n}$。这里的上标表示复合次数，不是数值乘方。

特征函数把集合运算变成 0—1 运算

若 $A\subseteq U$，特征函数定义为：

$$\chi_A(x)= \begin{cases} 1,&x\in A,\\ 0,&x\notin A. \end{cases}$$

于是：

$$\chi_{A\cap B}=\chi_A\chi_B,$$ $$\chi_{\overline A}=1-\chi_A,$$ $$\chi_{A\cup B}=\chi_A+\chi_B-\chi_A\chi_B.$$

这说明一个集合也可以看作给全集中每个元素贴上的二元标签，为后面的向量和邻接矩阵表示铺路。