2.2 函数与关系

有序对 $(x,y)$ 记录从 $X$ 中元素到 $Y$ 中元素的有向联系。把这些联系收集起来，便得到笛卡儿积 $X\times Y$ 的一个子集。有些联系为每个输入指定唯一输出，有些允许多个输出或没有输出；集合语言能精确区分这些情况。

定义 2.2.1

（关系）

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

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

函数是特殊的关系

定义 2.2.2

（函数）

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

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

• $X$ 是定义域（domain），即输入集合。
• $Y$ 是目标集合（codomain），即允许输出所在的集合。
• $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$ 的函数图像。

常见错误

（定义域会受语境影响）

$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|}$ 背后的同一个计数原理。若 $A$ 为空集，则恰有一个空函数，即使 $B$ 也为空集亦如此；这里采用组合计数中的约定 $0^0=1$。

例题 2.2.3

（把 $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}$$

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

怎么仔细读一个函数

例题 2.2.4

（平方函数会有重复输出）

考虑由 $f(x)=x^2$ 定义的函数 $f:\mathbb R\to\mathbb R$。

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

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

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

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

像、原像和合成

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

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

对 $B\subseteq Y$，原像定义为

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

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

设 $f:X\to Y$、$g:Y\to Z$，合成是函数 $g\circ f:X\to Z$，定义为

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

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

例题：计算函数合成

设 $f,g,h:\mathbb R\to\mathbb R$ 分别为 $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)$ 中，就存在 $x\in A$ 或 $x\in B$ 使 $f(x)=y$。这个 $x$ 属于 $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$；第二式明确说明两个补集所依据的全集不同。

例题 2.2.5

（比较 $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\}.$$

单射、满射、双射

定义 2.2.6

（三个常用词）

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

等价说法也很有用：

• $f$ 是单射，当且仅当对任意 $x_1,x_2\in X$，$f(x_1)=f(x_2)$ 都蕴含 $x_1=x_2$。
• $f$ 是满射，当且仅当 $f(X)=Y$。
• $f$ 是双射，当且仅当每个目标值都恰好被一个输入取到。

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

首先，对 $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)$ 总是偶数，不能取得奇数。

用箭头区分定义

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

定理 2.2.7

（逆函数存在当且仅当双射）

对函数 $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)$$

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

例题 2.2.8

（单射和非单射的例子）

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

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

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

常见错误

（不要把原像和逆函数混淆）

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

左逆和右逆

对 $f:X\to Y$，两个逆映射等式的定义域不同：

• 左逆 $h:Y\to X$ 满足 $h \circ f = id_X$。
• 右逆 $g:Y\to X$ 满足 $f \circ g = id_Y$。

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

例题 2.2.9

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

设 $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$，所以没有右逆。

例题 2.2.10

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

定义 $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(β)$ 排除了左逆。

定理 2.2.11

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

设 $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$ 有双侧逆函数 $g^{-1}$。由 $h\circ g=id_X$，

$$h=h\circ id_X=h\circ(g\circ g^{-1})=(h\circ g)\circ g^{-1}=g^{-1}.$$

因此也有 $g\circ h=id_X$。当 $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\})$ 中选一个元素。明确构造的选择或有限次选择不需要一般选择公理；断言每个任意满射都有右逆则使用选择公理。这与双射的唯一原像不同，后者无需这样的选择原则。

例题 2.2.12

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

令 $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$ 下没有原像。

不要求唯一输出的关系

函数要求每个输入恰有一个输出。去掉这个限制，就能用关系比较次序、整除或共同性质，而不必为每个输入挑选一个输出。

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

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

• 定义域是所有至少与一个 $y\in Y$ 相关的 $x\in X$ 所组成的集合。
• 像（或值域）是所有至少与一个 $x\in X$ 相关的 $y\in Y$ 所组成的集合。

例题 2.2.13

（关系不一定是函数）

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

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

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

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

同一个集合上的关系

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

定理 2.2.14

（四个常用性质）

一个 $X$ 上的关系可以有以下性质；各条件须对 $X$ 中所有相应元素成立：

• 自反（reflexive）：对每个 $x$，都有 $xRx$。
• 对称（symmetric）：$xRy$ 蕴含 $yRx$。
• 反对称（antisymmetric）：若 $xRy$ 且 $yRx$，则 $x=y$。
• 传递（transitive）：若 $xRy$ 且 $yRz$，则 $xRz$。

两种特别重要的关系是：

• 偏序（partial order）满足自反、反对称和传递性。
• 等价关系（equivalence relation）满足自反、对称和传递性。

关系性质与反例

令 $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$ 相关。因此它不是等价关系，也没有等价类可列出。

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

对称与反对称描述不同的条件：

• 对称要求每一条关系箭头都有反向箭头。
• 反对称要求互有箭头的两个元素相等。

例题 2.2.15

（整除关系是偏序）

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

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

所以整除是偏序。

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

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

例题 2.2.16

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

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

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

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

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

例题 2.2.17

（一个简单的等价关系）

对正整数 $m$，模 $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)\}$$

也就是相同余数的整数所组成的剩余类。

等价类和商集

模 $3$ 时，整数 $1$、$4$、$-2$ 的余数相同。它们是不同的整数，但同余关系不区分它们相差的 $3$ 的倍数。如果只保留余数信息，就需要一个对象代表这些彼此等价的整数。

用 $1$ 作标签很方便，但改用 $4$ 不应改变所代表的对象。把所有与 $1$ 相关的整数收集成一个集合，便满足这个要求：改用 $4$ 得到的仍是同一个集合。等价类把这种不依赖代表元的性质落实到新对象的构造中。

一般关系未必有此性质：两个元素对应的集合可能相交而不相等。自反性、对称性和传递性排除了这种含糊情况。下面的划分定理说明，等价关系的类为何能成为彼此分开的新对象。

定义 2.2.18

（等价类）

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

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

定义 2.2.19

（商集）

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

定理 2.2.20

（等价类会分割集合）

如果 $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.$$

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

例题 2.2.21

（$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).$$

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

例题 2.2.22

（从 $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'.$$

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

后面的基数笔记 将进一步研究无限集合的大小比较。

用函数组合元素

函数也可以定义运算：输入同一集合中若干元素组成的元组，输出仍在该集合中。写清这个函数类型，便同时明确了输入个数和输出的封闭性。

定义 2.2.23

（把运算读成函数）

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

$$S^n \to S.$$

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

当 $n=0$ 时，$S^0$ 是只包含空元组的单元素集合。因此 $S^0\to S$ 的函数就是在 $S$ 中指定一个元素；若 $S$ 为空集，这样的函数不存在。 幺半群与群 将研究二元运算及其可能满足的定律。

常见错误

常见错误

（对称不等于反对称）

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

常见错误

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

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

小检查

快速检查

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

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

解答 · 答案

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

快速检查

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

分清原像和逆函数。

解答 · 答案

有。原像永远有意义。

快速检查

（如果 $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$ 是单射。

快速检查

（如果一个关系满足自反性、对称性和传递性，它叫什么？）

回想会把集合划分成等价类的关系。

解答 · 答案

它是等价关系。