2.2 函数与关系

函数和关系把积集变成有结构的数学对象：函数要求输出唯一，关系记录一般的联系。

函数是特殊的关系

定义

函数

从 $X$ 到 $Y$ 的函数，是 $X \times Y$ 的一个子集，并且要求 $X$ 中每个 $x$ 都只会对应 $Y$ 中唯一一个 $y$。

这是本单元采用的集合论定义。

同一件事可以从几种角度来读：

• $X$ 是 domain，即输入集合。
• $Y$ 是 target，即可能输出的集合。
• $f$ 的图像（graph）是 $\{(x,f(x)):x\in X\}$，即由输入 $x\in X$ 与对应输出 $f(x)$ 组成的有序对集合。
• image 是实际出现过的输出。
• preimage 是会落入某个输出集合的输入。

常见错误

函数不能让一个输入对应多个输出

关系可以让一个输入连到多个输出，但函数不可以。每个输入都必须有且只有一个输出。

如何检验一个候选图像

子集 $\Delta \subset X \times Y$ 是函数 $X\to Y$ 的图像，当且仅当每个 $x\in X$ 都恰好出现在一个有序对 $(x,y)\in\Delta$ 中。漏掉某个输入 违反“存在”，同一输入对应两个不同输出违反“唯一”。例如 $\Delta=\{(n+10,n):n\in\mathbb N\}\subset\mathbb N\times\mathbb Z$ 漏掉了输入 $0$，因为 $n+10=0$ 要求 $n=-10$；所以它不是从 $\mathbb N$ 到 $\mathbb Z$ 的函数图像。把参数改为 $n\in\mathbb Z$ 后，任意 $x\in\mathbb Z$ 都有唯一 $n=x-10$，于是是从 $\mathbb Z$ 到 $\mathbb Q$ 的函数图像。$\{(x^2,x^3):x\in\mathbb Q\}$ 则既漏掉负输入，又有 $(1,1)$ 和 $(1,-1)$ 两个输出，不能成为从 $\mathbb Q$ 到 $\mathbb Q$ 的函数图像。

常见错误

domain 会受语境影响

$1/x$ 不是一个不加限定就完整的函数。它可以是定义在 $R \setminus \{0\}$ 上的函数， 或者定义在 $Q \setminus \{0\}$ 上的函数；但无论如何都不能包含 $0$。

所有函数组成的集合

当函数已经被定义为有序对集合之后，我们也可以建立“以函数为元素”的集合。 若 $A$ 和 $B$ 是集合，记号

$$B^A$$

表示所有从 $A$ 到 $B$ 的函数组成的集合。

这个记号不是偶然的。若 $A$ 有 $n$ 个元素，而 $B$ 有 $m$ 个元素，一个 $A \to B$ 的函数就是给 $A$ 的每个输入各选一个 $B$ 中的输出。因此共有 $m^n$ 个这样的函数。例如 $A = \{a,b,c\}$、$B=\{0,1\}$ 时，$B^A$ 有 $2^3=8$ 个函数。这正是 $|P(A)| = 2^\{|A|\}$ 背后的同一个计数原理。

例题

把 $B^A$ 读成函数集合

令 $A=\{a,b\}$、$B=\{0,1\}$。那么 $B^A$ 恰有四个函数：

$$\begin{array}{c|cc} & a & b \\ \hline f_1 & 0 & 0\\ f_2 & 0 & 1\\ f_3 & 1 & 0\\ f_4 & 1 & 1 \end{array}$$

每一行是一整个函数，而不是某一个函数的一个值。

怎么仔细读一个函数

例题

平方函数会有重复输出

考虑 $f(x) = x^2$。

那么 $f(-2) = 4$ 和 $f(2) = 4$，也就是说不同输入可以有相同输出。这是允许的。

不允许的是同一个输入有两个不同输出。

例如，把 $y^2 = x$ 当成从 $x$ 到 $y$ 的规则时，$x = 4$ 会有 $y = 2$ 和 $y = -2$，所以它不是函数。

函数的 graph 是一个非常特别的积集子集：每一条垂直线在可行输入位置只会碰到一次。

像、原像和合成

对 $f : X \to Y$，image 这个词有三种相关但不同的用法：

• $f(x)$ 是单个输入 $x$ 的像。
• 若 $A \subset X$，则 $f(A) = {f(x) \mid x \in A}$ 是集合的像。
• $f(X)$ 是整个函数的像，也就是实际出现过的输出。

原像定义为

$$f^{-1}(B) = \{x \in X \mid f(x) \in B\}.$$

即使 $f$ 没有逆函数，$f^\{-1\}(B)$ 也仍然有意义。

合成定义为

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

次序很重要：$g \circ f$ 的意思是“先做 $f$，再做 $g$”。

例题：计算函数合成

对 $f(x)=x+1$、$g(x)=x^2$、$h(x)=x-7$，直接代入得到

$$\begin{aligned} f\circ f&:x\mapsto x+2, & f\circ g&:x\mapsto x^2+1, & f\circ h&:x\mapsto x-6,\\ g\circ f&:x\mapsto (x+1)^2, & g\circ g&:x\mapsto x^4, & g\circ h&:x\mapsto (x-7)^2,\\ h\circ f&:x\mapsto x-6, & h\circ g&:x\mapsto x^2-7, & h\circ h&:x\mapsto x-14. \end{aligned}$$

最右边的函数先作用。

像与原像的集合恒等式

设 $f:X\to Y$、$A,B\subset X$、$C,D\subset Y$。像满足

$$f(A\cup B)=f(A)\cup f(B),\qquad f(A\cap B)\subset f(A)\cap f(B)$$

第一式的左到右方向：若 $y\in f(A\cup B)$，则 $y=f(x)$ 且 $x\in A\cup B$，所以 $x\in A$ 或 $x\in B$，从而 $y$ 在右边。 右到左方向：若 $y$ 在 $f(A)$ 或 $f(B)$ 中，它的原像属于 $A\cup B$，所以 $y\in f(A\cup B)$。第二式来自同样的元素追踪， 但等号可能失败。取 $X=\{1,2\}$、$Y=\{0\}$、$f(1)=f(2)=0$、 $A=\{1\}$、$B=\{2\}$，则左边是空集而右边是 $\{0\}$。

原像保留并集与交集，并且所有等号都可逐元素证明：

$$f^{-1}(C\cup D)=f^{-1}(C)\cup f^{-1}(D),\qquad f^{-1}(C\cap D)=f^{-1}(C)\cap f^{-1}(D)$$

例如，$x\in f^{-1}(C\cup D)$ 当且仅当 $f(x)\in C$ 或 $f(x)\in D$， 这又当且仅当 $x\in f^{-1}(C)\cup f^{-1}(D)$；反向阅读就是另一方向。 交集同理，把“或”换成“且”。若补集分别取在目标 $Y$ 和定义域 $X$ 中， 差集与补集也满足

$$f^{-1}(C\setminus D)=f^{-1}(C)\setminus f^{-1}(D),\qquad f^{-1}(Y\setminus C)=X\setminus f^{-1}(C)$$

第一式的成员条件是 $f(x)\in C$ 且 $f(x)\notin D$；第二式明确说明 两个补集的 ambient set 不同。

例题

比较 $f(x)=x^2$ 的像与原像

设 $f : R \to R$ 由 $f(x) = x^2$ 定义，而

$$A = \{-2, -1, 0, 1, 2\}, \qquad B = \{0, 1, 4\}.$$

那么

$$f(A) = \{0, 1, 4\}.$$

而且

$$f^{-1}(B) = \{-2, -1, 0, 1, 2\},$$

每个列出的点都映入 $B$。反过来，若 $x^2\in\{0,1,4\}$，则 $x^2=0$、$x^2=1$ 或 $x^2=4$。分别因式分解得 $x=0$、$x=\pm1$ 或 $x=\pm2$，所以没有其他实数原像。

如果改成 $C = \{4\}$，就有

$$f^{-1}(C) = \{-2, 2\}.$$

单射、满射、双射

定义

三个常用词

• 单射：不同输入不会撞车。
• 满射：目标集合每个值都会被取到。
• 双射：同时单射和满射。

等价说法也很有用：

• $f$ 单射 iff $f(x1) = f(x2)$ 蕴含 $x1 = x2$
• $f$ 满射 iff $f(X) = Y$
• $f$ 双射 iff 每个目标值都刚好被取到一次

例题：直接判断单射与满射

首先，对 $X=\{0,1,3,5\}$、$Y=\{5,7,11\}$，给定值为 $f(0)=7$、$f(1)=5$、$f(3)=11$、$f(5)=5$。值 $5$ 被两个输入取到， 所以不是单射；$5,7,11$ 都出现，所以是满射。

其次，对 $f(x)=x^5+3x+1$（定义域 $\{-2,-1,0,1,2\}$，值域 $\mathbb Z$），五个输出为

$$f(-2)=-37,\quad f(-1)=-3,\quad f(0)=1,\quad f(1)=5,\quad f(2)=39$$

它们互不相同，所以是单射；例如 $0$ 不在像中，所以不是满射。

最后，$f:\mathbb Z\to\mathbb Z$、$f(x)=x^2+x$ 不是单射，因为 $f(0)=f(-1)=0$；它也不是满射，因为 $x(x+1)$ 总是偶数，不能取得奇数。

用箭头区分定义

箭头图可以显示唯一输出、碰撞，以及 target 是否被覆盖。

用同一张箭头图分清 domain、target、image、preimage、单射、满射和合成。

1. domain 和 target

   函数 f:X->Y 是一种关系，其中 X 中每个输入在 target Y 中都有唯一一个输出。

2. graph 作为有序对

   graph 把同一批箭头记成 X x Y 中的有序对，而且每个输入只出现在一个有序对中。

3. image 和 preimage

   image 是向前读到被取到的输出；preimage 是从输出集合反向读回会落入其中的输入。

4. 单射

   单射表示没有碰撞：若两个输入有同一输出，它们其实必须是同一个输入。

5. 满射

   满射表示实际 image 等于整个 target，因此没有 target 元素被漏掉。

6. 合成

   对 g o f，要先做 f，再把得到的输出放入 g。

同一张箭头图可以把主要定义分清楚。函数要求每个输入刚好有一个输出；单射禁止碰撞；满射覆盖 target；合成则把一个输出接到下一个映射。

定理

逆函数存在当且仅当双射

对函数 $f : X \to Y$，逆函数存在，当且仅当 $f$ 是双射。

证明：为什么双射会有逆

如果 $f$ 既单射又满射，那么对每个 $y \in Y$ 都存在唯一一个 $x \in X$ 使 $f(x)=y$。

这个唯一性让我们可以定义一个新函数 $g : Y \to X$，令 $g(y)$ 就是满足 $f(x)=y$ 的唯一 $x$。

按定义，$g(f(x)) = x$ 且 $f(g(y)) = y$，所以 $g$ 就是 $f$ 的逆函数。

证明：逆函数的唯一性与存在性

若 $g,h:Y\to X$ 都是 $f:X\to Y$ 的逆函数，利用合成的结合律可得

$$g=g\circ id_Y=g\circ(f\circ h)=(g\circ f)\circ h=id_X\circ h=h$$

所以逆函数若存在就唯一。更一般地，若 $f:X\to Y$、$g:Y\to Z$、 $k:Z\to W$，则对每个 $x\in X$，

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

因此函数合成满足结合律。下文关于逆函数蕴含关系的证明将说明必要性：有逆函数就必为双射；上面的构造则给出双射的逆函数。

例题

单射和非单射的例子

$n \mapsto n + 1$（定义在 $Z$ 上）既单射又满射，所以是双射。

$x \mapsto x^2$（定义在 $R$ 上）不是单射，因为 $1$ 和 $-1$ 有同一个像。

$x \mapsto e^x$（定义在 $R$ 上）是单射，但不是满射到 $R$，因为它打不到非正数。

常见错误

不要把原像和逆函数混淆

$f^\{-1\}(B)$ 永远有意义，只要 $B$ 是 target 的子集。真正的逆函数 $f^\{-1\}$ 只有在 $f$ 是双射时才存在。

左逆和右逆

• 左逆 $h$ 表示 $h \circ f = id$
• 右逆 $g$ 表示 $f \circ g = id$

一般情况下，这两个条件并不一样。

例题

一个有左逆但没有右逆的映射

设 $X = \{a, b, c\}$，$Y = \{α, β, γ, δ\}$。定义

$$f_1(a)=α,\qquad f_1(b)=β,\qquad f_1(c)=γ.$$

这个映射是单射但不是满射，因为 $δ$ 没有被取到。 所以它可以有左逆，但不可以有右逆。

例如定义 $h : Y \to X$：

$$h(α)=a,\qquad h(β)=b,\qquad h(γ)=c,\qquad h(δ)=a.$$

那么 $h \circ f_1 = id_X$。

缺少输出 $δ$ 排除了 $f_1\circ g=id_Y$，所以没有右逆。

例题

一个有右逆但没有左逆的映射

定义 $f_2 : Y \to X$ 如下：

$$f_2(α)=a,\qquad f_2(β)=a,\qquad f_2(γ)=b,\qquad f_2(δ)=c.$$

这个映射是满射但不是单射，所以可以有右逆但没有左逆。

一个右逆是 $g : X \to Y$，令

$$g(a)=α,\qquad g(b)=γ,\qquad g(c)=δ.$$

那么 $f_2 \circ g = id_X$。

碰撞 $f_2(α)=f_2(β)$ 排除了左逆。

定理

有限自映射：有左逆已足以推出可逆

设 $X$ 是有限集合，且 $g : X \to X$。如果存在 $h : X \to X$ 满足 $h \circ g = id_X$，那么 $g$ 是双射，而且 $h$ 也是 $g$ 的右逆。

证明：有限自映射有左逆时可逆

等式 $h \circ g = id_X$ 首先说明 $g$ 是单射：若 $g(x_1)=g(x_2)$，两边 再作用 $h$，就得到 $x_1=x_2$。

对有限集合而言，从 $X$ 到自身的单射必然也是满射。因此 $g$ 是双射。由于 逆函数唯一，而 $h$ 已经在左边抵消 $g$，所以 $h$ 必须就是 $g$ 的逆函数。 因此也有 $g \circ h = id_X$。

证明：逆映射的蕴含及其逆向构造

设 $f:X\to Y$、$h:Y\to X$。若 $h\circ f=\operatorname{id}_X$，则 $f(x)=f(x')$ 推出 $x=h(f(x))=h(f(x'))=x'$，所以有左逆必为单射。若 $f\circ h=\operatorname{id}_Y$，每个 $y$ 都等于 $f(h(y))$，所以有右逆必为满射。

反过来，设 $f$ 单射且 $X\ne\varnothing$。固定一个 $x_0\in X$；当 $y\in f(X)$ 时令 $h(y)$ 为唯一原像，否则令 $h(y)=x_0$。这给出左逆，不需要选择公理，因为像外只需使用同一个固定值。若 $X=\varnothing$ 而 $Y$ 非空，空集到 $Y$ 的单射没有左逆，因为不存在 $Y\to\varnothing$ 的映射。若两者皆空，空映射就是自己的逆。

对满射，构造右逆要在每个纤维 $f^{-1}(\{y\})$ 中选一个元素。明确构造的选择或有限次选择不需要一般选择公理；断言每个任意满射都有右逆则使用选择公理。这与双射的唯一原像不同，后者无需这样的选择原则。

例题

具有完整左逆的无限包含映射

令 $i:\mathbb N\to\mathbb Z$ 为 $i(n)=n$，其中 $0\in\mathbb N$。定义 $h:\mathbb Z\to\mathbb N$：当 $z\ge0$ 时取 $h(z)=z$，当 $z<0$ 时取 $h(z)=0$。对每个 $n$ 都有 $h(i(n))=n$。但 $i$ 没有右逆，因为负整数（例如 −1）在 $i$ 下没有原像。

关系

定义

关系

$X$ 和 $Y$ 之间的关系，是 $X \times Y$ 的任何子集。

如果 $X = Y$，我们就直接叫它 $X$ 上的关系。

写 $xRy$ 就是说 $(x, y) \in R$。

关系比函数更一般。函数只是带着“每个输入恰好一个输出”这条附加规则的特殊关系。

对于 $R \subset X \times Y$：

• domain 是和至少一个 $y$ 有关系的 $x$
• image / range 是被至少一个 $x$ 命中的 $y$

例题

关系不一定是函数

设 $X$ 是国家集合，$Y$ 是城市集合。

“$y$ 是 $x$ 的首都” 是 $X \times Y$ 上的关系。它是不是函数，要看时代和国家。

$y^2 = x$（定义在 $Z \times Z$ 上）也是关系，但如果把它当成从 $x$ 到 $y$ 的规则， 就不是函数，因为一个输入可能有多个输出。

关系可以处理“有连接，但不要求唯一性”这种情况。顺序和等价类之后都要用到这套语言。

同一个集合上的关系

$X \times X$ 上的关系尤其重要。

定理

四个常用性质

一个 $X$ 上的关系可以有以下性质：

• Reflexive：每个 $x$ 都有 $xRx$
• Symmetric：$xRy$ 蕴含 $yRx$
• Antisymmetric：如果 $xRy$ 且 $yRx$，那就要 $x = y$
• Transitive：如果 $xRy$ 且 $yRz$，那就要 $xRz$

两种特别重要的关系是：

• partial order：reflexive + antisymmetric + transitive
• equivalence relation：reflexive + symmetric + transitive

关系性质与反例

令 $X=\mathcal P(\{1,2,3,4\})$，并以 $x\cap y=\varnothing$ 定义 $xRy$。 它不是自反的，因为非空集合 $\{1\}$ 与自身的交集不为空；它是对称的， 因为交集满足交换律；它不是传递的，取 $x=\{1\}$、$y=\varnothing$、 $z=\{1\}$，则 $xRy$ 且 $yRz$，但不满足 $xRz$；它也不是反对称的， 因为 $\{1\}R\{2\}$ 且 $\{2\}R\{1\}$，而两个集合不相等。

再检验以下整数上的关系：

• $x-y$ 为奇数不是自反的，因为 $x-x=0$；它虽对称，却不传递， 例如 $0R1$、$1R2$，但 $0$ 不与 $2$ 相关。
• $x+y$ 为偶数是等价关系。自反、对称显然；若 $x+y$ 与 $y+z$ 都为偶数， 则 $(x+z)=(x+y)+(y+z)-2y$ 也是偶数。等价类是偶整数类与奇整数类。
• $x+y=0$ 不是自反的（除 $0$ 之外），也不传递：$1R(-1)$、 $(-1)R1$，但 $1$ 不与自身相关。
• $x|y|=|x|y$ 是自反且对称的，因为它等价于“两个整数同号，或至少 一个为零”。但它不传递：$1R0$ 且 $0R(-1)$，而 $1$ 不与 $-1$ 相关。 因此它不是等价关系，也没有等价类可列出。

这些反例说明，判断等价关系必须逐项检验自反、对称、传递三个条件。

symmetric 和 antisymmetric 很容易混淆，但它们意思完全不同：

• symmetric：看到单向箭头就要两边都有
• antisymmetric：如果两边都有，那两个元素必须相等

例题

整除关系是偏序

在正整数 $\mathbb Z_{\gt0}$ 上写 $a \mid b$ 表示 $a$ 整除 $b$。

这个关系是 reflexive，因为每个数都整除自己。 它是 antisymmetric，因为如果 $a \mid b$ 且 $b \mid a$，在正整数里就有 $a = b$。 它也是 transitive，因为整除可以沿链传递。

所以整除是 partial order。

这里必须限定正整数。在全体整数上，$1\mid-1$ 且 $-1\mid1$，但 $1\ne-1$，所以反对称性会失败。

偏序不只是一个名字。它帮助我们整理“包含”“细化”“整除”这些有结构的关系。

例题

子集关系作为一个小型偏序

令 $X=\{a,b\}$，并考虑 $P(X)$，也就是 $X$ 的所有子集组成的集合。 用包含关系排列 $P(X)$。

最底层元素是 $\varnothing$，最顶层元素是 $\{a,b\}$，中间两个元素是 $\{a\}$ 和 $\{b\}$。直接相邻的 covering relations 只有

$$\varnothing \subset \{a\},\quad \varnothing \subset \{b\},\quad \{a\}\subset \{a,b\},\quad \{b\}\subset \{a,b\}.$$

Hasse 图只画这些直接覆盖关系；更长的比较则由传递性自动理解。

例题

一个简单的等价关系

模 $m$ 同余是 $Z$ 上的等价关系：两个整数有相同余数时相关。模 $3$ 时， 整数分成余数为 $0$、$1$、$2$ 的三类，这些类分割整个 $Z$。

证明：模 $m$ 同余

固定 $m\in\mathbb Z$ 且 $m\gt0$。定义 $a\equiv b\pmod m$ 当且仅当 $m\mid(a-b)$。它是 $\mathbb Z$ 上的等价关系。自反性来自 $m\mid0$； 若 $m\mid(a-b)$，则 $m\mid(b-a)=-(a-b)$，所以有对称性；若 $m\mid(a-b)$ 且 $m\mid(b-c)$，则 $m$ 整除两者之和 $a-c$，所以有 传递性。

其等价类为

$$[a]_m=\{b\in\mathbb Z:m\mid(a-b)\}$$

也就是相同余数的整数所组成的 residue class。

等价类和商集

等价关系规定哪些差别不再区分。要把一个等价类当成新的数学对象，必须先证明：类中的不同代表元确定同一个类。下面的划分定理使这一步精确化；整数和有理数的构造会反复使用它。

定义

等价类

设 $R$ 是 $X$ 上的等价关系。对 $x \in X$， $x$ 的等价类定义为

$$[x]_R = \{y \in X \mid yRx\}.$$

定义

商集

如果 $\sim$ 是 $X$ 上的等价关系，那么所有等价类组成的集合记作 $X / \sim$。

定理

等价类会分割集合

如果 $R$ 是 $X$ 上的等价关系，那么等价类会覆盖整个集合，而且任意两个等价类只会相等或者互不相交。

等价类把彼此等价的代表元包装成一个对象，商集再把这些类作为元素来处理。

证明：相交的等价类相等

自反性给出 $xRx$，所以每个 $x\in X$ 都属于 $[x]_R$，等价类覆盖 $X$。

设 $z\in[x]_R\cap[y]_R$，则 $zRx$ 且 $zRy$。若 $u\in[x]_R$，有 $uRx$；由对称性得 $xRz$，再由传递性得 $uRz$ 及 $uRy$。因此 $u\in[y]_R$，证明 $[x]_R\subseteq[y]_R$。

反过来，若 $v\in[y]_R$，有 $vRy$；对称性给出 $yRz$，传递性依次给出 $vRz$ 和 $vRx$，故 $v\in[x]_R$，证明 $[y]_R\subseteq[x]_R$。两个包含关系推出相等。因此不相等的等价类不能相交，各个不同的等价类构成 $X$ 的分割。

基数和运算语言

基数表示大小，但在集合论中，正确的大小比较不一定只是普通计数。两个集合 $X$ 和 $Y$ 等势，意思是它们之间存在一个双射：

$$|X| = |Y| \quad \text{表示存在一个双射 } X \to Y.$$

有限集合中，这与元素个数一致；无限集合中则需要更谨慎地比较。

例题

$N$ 与 $Z$ 之间的第一个双射

$$0, 1, -1, 2, -2, 3, -3, \ldots$$

这对应到一个函数 $f : N \to Z$，例如

$$f(0)=0,\qquad f(2k+1)=k+1,\qquad f(2k+2)=-(k+1).$$

每个整数都恰好出现一次，所以这是一个双射枚举。

例题

从 $N \times N$ 到 $N$ 的一个单射

练习会问：能否把一个自然数有序对编码成一个自然数？一个干净答案是

$$F(m,n)=2^m3^n.$$

这确实定义了一个函数 $F : N \times N \to N$，因为对每个 $(m,n)$， $2^m3^n$ 都是自然数。

要证明 $F$ 是单射，假设

$$F(m,n)=F(m',n').$$

也就是

$$2^m3^n = 2^{m'}3^{n'}.$$

唯一素因数分解说明，一个正整数分解成素数幂的方式只有一种。因此两边的 $2$ 的指数必须相同，$3$ 的指数也必须相同：

$$m=m', \qquad n=n'.$$

所以两个不同有序对不可能被送到同一个自然数。

定义

把运算读成函数

集合 $S$ 上的一个 $n$ 元运算，是一个函数

$$S^n \to S.$$

例如加法是二元运算，因为它取一对输入，并返回同一个集合中的一个输出。

$0$ 元运算初看可能有些奇怪。它是没有输入位置、但有一个 $S$ 中输出的函数， 所以可以理解为在 $S$ 中指定一个特殊元素。

常见错误

常见错误

不要把原像和逆函数混淆

$f^\{-1\}(B)$ 永远有意义，只要 $B$ 是 target 的子集。真正的逆函数 $f^\{-1\}$ 只有在 $f$ 是双射时才存在。

常见错误

对称不等于反对称

$≤$ 是反对称但不是对称。等号既对称又反对称，而正整数 $\mathbb Z_{\gt0}$ 上的整除是反对称但不是对称。

常见错误

关系做不成函数有两种方式

它可以让同一个输入对应多个输出，也可以让某些输入完全没有输出。

小检查

思考检查

$x ≤ y$ 在实数上是关系吗？是函数吗？

先问它是不是 $R \times R$ 的子集，再问每个输入有没有唯一输出。

解答 · 答案

它是关系，因为它是 $R \times R$ 的子集；但它不是函数，因为同一个输入 $x$ 可以对应很多个 $y$。

思考检查

$f^\{-1\}(B)$ 在 $f$ 不是双射时还有意义吗？

分清 preimage 和 inverse function。

解答 · 答案

有。原像永远有意义。

思考检查

如果 $A$ 有三个元素，而 $B$ 有两个元素，$B^A$ 中有多少个函数？

对 $A$ 的每个输入，各自在 $B$ 中选一个输出。

解答 · 答案

共有 $2^3 = 8$ 个函数。

思考检查

若 $g : X \to X$ 有左逆且 $X$ 是有限集合，证明 $g$ 可逆时第一步应证明 $g$ 有什么性质？

使用等式 $h \circ g = id_X$。

解答 · 答案

先证 $g$ 是单射。由于 $X$ 有限，单射推出满射，因此 $g$ 是双射。

思考检查

为什么 $F(m,n)=2^m3^n$ 定义了从 $N \times N$ 到 $N$ 的单射？

留意素数 $2$ 和 $3$ 的指数。

解答 · 答案

如果 $2^m3^n = 2^\{m'\}3^\{n'\}$，唯一素因数分解会迫使 $m=m'$ 且 $n=n'$。 因此相同输出推出相同有序对，所以 $F$ 是单射。

思考检查

如果一个关系是 reflexive、symmetric、transitive，它叫什么？

回想会把集合分成 class 的那种关系。

解答 · 答案

它是等价关系。